[论文] 利用 SIMD 加速大数算术

Source: arXiv - 2604.21566v1

概述

本文介绍了 DigitsOnTurbo (DoT)，这是一种在现代 CPU 上利用 SIMD（单指令多数据）单元进行大整数运算的新方法。DoT 通过重新设计算法，而不是仅仅对现有算法进行“向量化”，在支撑科学模拟和密码协议的核心运算上实现了显著的加速。

关键贡献

• 算法重新设计： 重新构建加法、减法和乘法，使其暴露出独立、数据并行的工作，能够自然映射到 SIMD 通道。
• 性能提升： 与之前的 SIMD 尝试相比，SIMD 加法/减法提升高达 1.85×，乘法提升 2.3×。
• 库集成： 当集成到主流大整数库时，DoT 可实现加法/减法最高 4× 的加速，乘法 2× 的加速，进而为科学工作负载带来约 19 % 的端到端吞吐量提升。
• 密码学影响： 在真实的密码学原语（如 RSA、ECC）上展示 7.9 % 的延迟降低和 5.9 % 的吞吐量提升。
• 开源原型： 提供参考实现，供其他开发者采用并在通用 CPU 上进行基准测试。

方法论

1. 数据布局转换 – 数字存储为固定大小的“位块”数组，这些位块与 SIMD 寄存器宽度对齐（例如 128 位或 256 位向量）。
2. 消除依赖 – 传统的大整数算法顺序传播进位或借位。DoT 用 并行前缀（扫描）操作取代这些操作，在少量 SIMD 步骤中计算整个向量的进位。
3. 向量友好乘法 – 使用 竖式 方法，但将部分积批量放入 SIMD 通道，然后进行并行归约合并，避免串行进位链。
4. 实现细节 – 为核心内核手写 intrinsics（AVX2/AVX‑512），并提供标量回退路径。作者还构建了一个轻量抽象层，使相同代码能够针对不同 SIMD 宽度编译。
5. 基准测试套件 – 在 Intel Xeon Cascade Lake（AVX‑512）和 AMD Zen 4（AVX2）上进行评估，使用微基准（单操作延迟/吞吐）和宏基准（矩阵乘法、FFT、RSA 密钥生成）。

结果与发现

* 在将库的默认大整数后端替换为支持 DoT 的内核后测得的增益。

关键要点

• 并行前缀技术消除了经典的进位传播瓶颈，使 SIMD 通道得到充分利用。
• 即使在较小的向量宽度（AVX2）下，DoT 仍然优于早期的 SIMD 尝试，证明该方法与架构无关。
• 实际应用中可见 个位数 的加速，累积后形成可衡量的端到端提升。

实际影响

• 密码学库（OpenSSL、libsodium、BoringSSL）可以采用 DoT 内核来降低 RSA/ECDSA 操作的延迟，这对 TLS 握手和区块链验证至关重要。
• 科学计算框架（NumPy、SciPy、Julia）依赖任意精度算术进行高精度模拟（例如轨道力学、量子化学），可以在不使用 GPU 的情况下实现更高吞吐量。
• 性能关键服务（证书颁发机构、安全消息服务器）可以降低每笔交易的 CPU 成本，可能会降低云费用。
• 这种设计模式——重新思考算法以实现数据并行，而不是强行适配——可复用于其他依赖性强的领域，如大整数除法、模指数运算或多项式算术。

开发者可以通过获取开源 DoT 原型、在构建系统中替换大整数后端，并使用自己的工作负载进行基准测试，开始实验。

限制与未来工作

• Carry‑scan 开销 随着 SIMD 通道数量的增加而增长；在非常宽的向量（例如未来的 AVX‑1024）上，扫描可能会成为新的瓶颈。
• 当前实现侧重于 无符号 整数；有符号算术和混合基数表示需要额外的处理。
• 乘法仍然采用学校算法；将更高级的算法（Karatsuba、Toom‑Cook）与 SIMD 友好的扫描相结合是一个待研究的方向。
• 尚未探索 GPU 或加速器扩展；将 DoT 的原理扩展到异构平台可能会释放更多性能提升。

总体而言，DigitsOnTurbo 证明了经过深思熟虑的算法重构能够释放 SIMD 在大整数工作负载中的潜在能力，为构建高性能、对安全敏感的软件的开发者提供了立竿见影的收益。

作者

• Subhrajit Das
• Abhishek Bichhawat
• Yuvraj Patel

论文信息

• arXiv ID: 2604.21566v1
• 分类: cs.DC
• 出版日期: 2026年4月23日
• PDF: Download PDF