EIP-616: EVM 的 SIMD 操作
| Authors | Greg Colvin <greg@colvin.org> |
|---|---|
| Created | 2017-04-25 |
摘要
此提案旨在为以太坊虚拟机提供单指令多数据类型和操作，充分利用 256 位宽的 EVM 堆栈项，并为向量和标量操作提供显著的性能提升。
动机
几乎所有现代 CPU 都包含 SIMD 硬件，该硬件对宽数据寄存器进行操作，将单个指令并行应用于多个数据通道，其中通道将寄存器划分为大小相等的标量元素的向量。这种模型非常适合 EVM 的宽堆栈项，可以为可以表示为标量向量并行运算的操作提供显著的性能提升。例如，一个简短的文献搜索发现 SIMD 的加速比为：
- SHA-512 最高可达 7 倍
- 椭圆曲线标量乘法 达 4 倍
- BLAKE2b 达 3 倍到 4 倍
- OpenSSL 最高可达 3 倍
- 椭圆曲线模乘 达 2 倍到 3 倍
- SHA-256 达 1.7 倍到 1.9 倍
- RSA 加密 达 1.3 倍
规范
编码
我们建议使用简单的编码将 SIMD 操作表示为扩展的两个字节代码。第一个字节是操作码，第二个字节是 SIMD 类型：标量类型、通道宽度和元素数量。
| N 位 | 字段 |
|---|---|
| 8 | 操作码 |
| 1 | 标量类型：0 = 无符号整数，1 = IEEE 浮点数 |
| 1 | 保留：0 |
| 2 | 通道宽度：字节数的以 2 为底的对数，作为 MSB 最先的整数 |
| 1 | 保留：0 |
| 3 | 元素计数：通道数的以 2 为底的对数，作为 MSB 最先的整数 |
因此，我们可以指定 SIMD 类型，其具有从 8 位到 64 位的无符号整数通道，向量分别从 32 到 2 个通道。但是，浮点通道仅支持 32 位和 64 位 IEEE 浮点数。类型 _0x7F_ 表示普通的 256 位 EVM 整数。
请注意，当元素计数为 1 时，运算在一个标量上进行，因此本规范还提供了对本机大小的单个标量进行本机运算。
请注意，不建议在初始版本中包含浮点运算，但我们认为为可能的未来扩展保留代码空间非常重要。
语义
我们定义了以下 EVM 的算术、逻辑和比较操作的扩展版本。与正常版本一样，它们从堆栈中使用其参数并将结果放置在堆栈上，只是它们的参数是向量而不是标量。
| lo\hi | B | C |
|---|---|---|
| 0 | XLT | |
| 1 | XADD | XGT |
| 2 | XMUL | XSLT |
| 3 | XSUB | XSGT |
| 4 | XDIV | XEQ |
| 5 | XSDIV | XISZERO |
| 6 | XMOD | XAND |
| 7 | XSMOD | XOR |
| 8 | XXOR | |
| 9 | XNOT | |
| A | XINDEX | |
| B | XSHL | |
| C | XSHR | |
| D | XSAR | |
| E | XCAST | XROL |
| F | XSHUFFLE | XROR |
除了 XSHUFFLE、XCAST 和 XINDEX 之外，无符号整数值的所有扩展操作都具有与代码 01 到 1F 对应的操作相同的语义，只是模数因标量类型而异，并且这些操作成对应用于源操作数的元素以计算目标元素。源操作数必须具有相同的元素类型和元素数量。 例如
PUSH uint8[1, 2, 3]
PUSH uint8[4, 5, 6]
XADD
在堆栈上留下
uint8[5, 7, 9]
XSHUFFLE 在堆栈上获取两个向量：一个用于置换的向量和一个置换掩码。例如
PUSH uint64[4, 5, 6, 0]
PUSH uint8[2, 0, 1, 3]
SHUFFLE
在堆栈上留下
uint64[6, 4, 5 , 0]
掩码必须具有整数类型，并且与源向量具有相同数量的元素。
XCAST 操作码的第二个字节应用于堆栈上的项，以创建指定类型的新向量。元素按照通常的 C 约定进行转换，缺少的元素设置为零，多余的元素被丢弃。如果堆栈项不是向量，则通过首先获取其最低有效位，然后将其复制到每个元素的对应位（首先是最低有效元素）来将其转换为向量。同样，多余的数据会被截断，缺少的数据会用 0 填充。向量通过反向处理转换为 256 位 EVM 整数，浮点 NAN 的元素被标准化为所有位都为 1。
请注意，MLOAD 和 MSTORE 仅对 256 位 EVM 整数有效。对于 SIMD 向量，在加载后和存储之前需要 XCAST，以在向量和 256 位整数之间进行转换。
XINDEX 具有与 BYTE 相同的语义，只是向量的各个元素被索引。
浮点值遵循 IEEE 754 语义。由于未针对移位和旋转定义这些语义，因此在此将这些操作定义为无效。
XSHUFFLE 和 XCAST 以外的扩展操作仅对相同 SIMD 类型的向量有效。这可以在合约创建时进行验证，否则可以在运行时进行检查。
子程序
如果 EIP-187 被接受，则需要一种类型安全的语法来声明采用向量参数的子程序。
BEGINSUBX n_args, arg_types... n_results, result_types...标记子程序的单个条目。在进入子程序时，从堆栈中取出n_args项，并在从子程序返回时，将n_results项放置在堆栈上。n_args和n_results各自以一个立即字节给出。arg_types和result_types以与 SIMD 操作码的第二个字节相同的编码给出，并且必须与堆栈上的值匹配。子程序的字节码在下一个BEGINSUB、BEGINSUBX或BEGINDATA指令或字节码结束时结束。
原理
目前，SIMD 硬件（例如 Intel SSE2 和 ARM Neon）的最低公分母是 16 字节的寄存器，支持 1、2、4 和 8 字节的整数通道，以及 4 和 8 字节的浮点通道。更新的 SIMD 硬件（例如 Intel AVX）支持 32 字节的寄存器，EVM 堆栈项也是 32 字节宽。以上限制源自这些数字，确保 EVM 代码在可用硬件的范围内 - 并且保留位为增长提供了空间。
对于大多数现代语言（包括 Rust、Python、Go、Java 和 C++），编译器可以很好地生成用于可并行循环的 SIMD 代码，并且/或者有内在函数或库可用于显式访问 SIMD 硬件。因此，可移植的软件实现可能会很好地利用大多数平台上的硬件，并且可以根据需要使用内在函数或库。因此，我们可以期望这些操作花费的时间大致相同（或者对于 128 位硬件上的 256 位向量，最多花费两倍的时间），而与元素大小或元素数量无关。
Gas
除了充分利用硬件外，这些操作的另一个动机是为较小的标量操作分配较低的 gas 成本。
在具有 64 位寄存器的机器上，来自 Knuth 的 计算机程序设计艺术 的标准算法需要 32 位数字，使用寄存器的上半部分进行溢出，因此对于 256 位值，需要 N=8 位数字，对于 64 位值，需要 N=2 位数字。这些算法的周期计数为：
| 运算 | 周期 | N = 2 | N = 4 | N = 8 |
|---|---|---|---|---|
| 加法 | 10 N + 6 | 26 | 46 | 86 |
| 减法 | 12 N + 3 | 27 | 51 | 99 |
| 乘法 | 28 N**2 + 11 N + 3 | 137 | 495 | 1883 |
| 除法 | 15 N**2 + 119 N + 111 | 409 | 827 | 2023 |
其余运算的复杂度与加法和减法大致相同，或更低。假设 JUMPDEST 是一个空操作，并且分配了 1 的 gas 价格，则可以将其视为解释器的开销。所有算术运算都被分配了相同的 gas 价格 5，剩余运行时为 4。解释器循环本身大约需要 6 到 8 个 C 指令，因此 ADD 和 SUB 的定价合理，但 MUL 比 ADD 或 SUB 慢大约 5 到 21 倍，而 DIV 慢大约 15 到 23 倍，因此它们显然定价错误。
相比之下，在大多数 Intel 和 ARM SIMD 单元上，指令大约需要以下周期计数，与寄存器宽度无关。
| 运算 | Intel 周期 | ARM 周期 | gas |
|---|---|---|---|
| 加法 | .5 | 1 | 1 |
| 减法 | .5 | 1 | 1 |
| 乘法 | 2 | 1 | 1 |
| 除法 | 10 | 12 | 2 |
由于除法运算以外的所有运算都比解释器开销花费的周期更少，因此它们被分配了最小成本 1。除法花费的时间稍多，因此分配了成本 2。
Citation
Please cite this document as:
Greg Colvin <greg@colvin.org>, "EIP-616: EVM 的 SIMD 操作 [DRAFT]," Ethereum Improvement Proposals, no. 616, April 2017. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-616.