CKB-VM: B 扩展指令集与宏指令融合技术

在我们写代码的时候总是会希望代码执行的越快越好, 对于区块链上的智能合约也是.

更快的执行速度意味着更高的 TPS, 当然我这里说的是一个可能性, 因为 TPS 是一个受多因子影响的变量. 同时的话, 这也意味着能承载更多的复杂业务, 因为这代表着我们有能力把一些复杂的密码学算法在虚拟机中实现.

通常有两种方式来实现性能的提升, 即软件上和硬件上. 对于第一种情况来说, 我们有许多在程序员之间口耳相传的代码秘籍, 这些秘籍非常晦涩但却能显著提高性能, 它们可以用两三行代码实现本来需要几十行代码实现的功能, 或者使用某种神秘的算法, 来让代码的性能提升几十上百倍. 我记得在 17 年的时候, 那时候我在做图像相关的工作, 说实话那份工作很好玩, 我需要编写应用于图像的各种算法, 那时候我有几十个 T 的图像数据需要处理, 任何对算法细微优化, 都能几个小时甚至几十个小时的节省处理程序的运行时间.

但是从软件上来节省程序的处理时间的消耗是有极限的, 想要进一步提升就需要从运行软件的载体上着手. CKB 的链上程序运行在 CKB-VM 上, 因此如何让 CKB-VM 本身执行的更快, 也是提升程序运行效率的关键点.

在过去的几个月, 我们主要探索了两个方向: 新的扩展指令集与宏指令融合技术.

B 扩展指令集

B 扩展指令集中的 B 是 Bit Manipulation 的意思, 即"位操作". RISC-V 的 B 扩展指令集可以提高 CKB-VM 处理位操作的能力, 典型的位操作包括前导 0 计数, 循环移位等.

我将向你们展示几个不同版本的前导 0 计数算法版本, 来说明 B 扩展指令集引入的意义. 首先解释一下什么叫做前导 0 计数, 它非常的简单, 它将一个数字作为二进制看待, 并统计数字的开头有多少个零. 例如: 数字 12345678 的前导 0 个数为:

0000000000000000000000000000000000000000101111000110000101001110(12345678)
|<--------------40-------------------->|

我们要编写前导 0 计数的算法. 我认为这很简单, 绝大部分程序员能在一分钟内写出来. 最直观的一种做法是我们写一个循环, 每次将数字左移一位, 然后判断数字的最高位是否为 0 即可.

uint64_t clz(uint64_t n)
{
    int c = 0;
    for (int i = 0; i < 64; i++) {
        if (((n << i) & 0x8000000000000000) == 0) {
            c += 1;
        } else {
            break;
        }
    }
    return c;
}

前导 0 计数在许多加密算法中都是经常被使用的一种功能, 我们不经要思考: 是否有方法可以让它跑的更快呢? 在生活中, 如果我们想更快的完成一件事, "二分法"通常是一个不错的选择. 它的原理是将一个复杂的事情分成两个较为简单的事情, 然后继续对任务做分割, 直到任务不可再分割为止.

uint64_t clz(uint64_t n)
{
    if (n == 0) return 64;
    int c = 0;
    if (n <= 0x00000000FFFFFFFF) { c += 32; n <<= 32; };
    if (n <= 0x0000FFFFFFFFFFFF) { c += 16; n <<= 16; };
    if (n <= 0x00FFFFFFFFFFFFFF) { c += 8; n <<= 8; };
    if (n <= 0x0FFFFFFFFFFFFFFF) { c += 4; n <<= 4; };
    if (n <= 0x3FFFFFFFFFFFFFFF) { c += 2; n <<= 2; };
    if (n <= 0x7FFFFFFFFFFFFFFF) { c += 1; };
    return c;
}

第二个算法的性能远远好于第一个算法. 对于目前的 CKB-VM 来说, 这基本上是我所能想到的最快的代码, 它大概会使用 30 条左右的指令. 当然还有一些方法可以进一步对以上的算法进行提速, 例如使用查表法: 这是很经典的空间换时间的做法.

对此我想要更进一步: 我是说, 既然前导 0 计数的应用如此的广泛, 为什么不能在指令集层面直接提供这个运算呢? RISC-V 有许多指令集, 它们被分为基础指令集和扩展指令集, 其中前导 0 计数就被包含在 B 扩展指令集中. 也就是说, 如果 CKB-VM 实现了 B 扩展, 那么以上的算法就只需要花费一条指令即可完成!

static inline int64_t _rv64_clz(int64_t rs1) {
    int64_t rd;
    __asm__ ("clz %0, %1" : "=r"(rd) : "r"(rs1));
    return rd;
}

完整的 B 扩展指令集提供了 100 多条新的指令, 下面是描述指令集文档的一部分:

img

总的来说, 如果你有位操作的需求的话, 那么使用 B 扩展指令集能带来一个数量级以上的提升.

宏指令融合(Macro-Operation Fusion, MOP)

宏指令融合是在许多现代微架构中都有应用的一种硬件优化技术, 它会在 CPU 解码之前或解码期间, 将一系列相邻的指令合并成单个宏指令, 之后, CPU 会直接对宏指令进行运算.

通常, 有三种方式来提升微架构的性能:

  • 提升频率. 增加 CPU 主频, 从而缩短每个时钟周期在现实中消耗的时长.
  • IPC. 通过利用更多的指令层面上的并行性来提高指令吞吐量.
  • 指令计数. 减少指令计数, 从而减少需要完成的工作总量. 这可以通过优化程序算法, 引入新的编译器优化, 或引入新的指令集扩展来实现. 宏指令融合技术也工作在这个层面.

宏指令融合的思想是将多条相邻的指令组合成一条指令, 融合指令通常在其整个生命周期内保持融合状态. 因此, 融合指令可以用更少的位表示更多的工作.

可以使用一个例子来说明宏指令融合的工作方式. 我们准备做一个除法, 例如 100 / 42, 然后分别获得这个算式的商和余数. 相应的 RISC-V 汇编代码可表示为:

addi t0, t0, 100
addi t1, t1, 42

div a0, t0, t1
rem a1, t0, t1

CKB-VM 会分别执行 div 和 rem 两个指令.

注意到由于我们的 CKB-VM 运行在 x86-64 的机器上, x86-64 在计算除法的时候, 商和余数是一起被计算的.

img

因此, 这里有一个改进空间, 就是当 div 与 rem 指令相邻出现并且它们的两个操作数都相同的时候, 可以使用一条 x86-64 指令替代.

CKB-VM 在解码相邻的 div 和 rem 的时候, 会判断它们是否符合融合条件, 然后使用一条内部指令来表示融合前的两条指令. 这条内部指令只对应了一条 x86 指令, 而不是融合前的两条. 这减少了指令的数量.​