Page 339 - 《软件学报》2026年第7期

3024 软件学报 2026 年第 37 卷第 7 期

单, 因此本文着重考虑连续操作间的数据依赖关系. 对于位于同一数据流上的操作, 本文使用融合内核技术, 将两
个或多个独立的内核融合为一个内核, 有效降低了核函数启动和全局内存数据交换带来的开销.
面向吞吐量的 CTRU-Prime 总体架构如图 4 所示. 为进一步释放 GPU 在高吞吐量上的优势, 在单个核函数优
化设计的基础上, 本文结合批量模式和单一模式, 引入批处理大小, 使得同时并发多个操作, 这充分利用了多 SM
的多核特点, 进而充分提高吞吐量. 进一步地, 实现过程中存在设备端和主机端的双向数据拷贝, 考虑 GPU 多流技
术能够同步进行不同方向的数值拷贝和数值计算, 本文运用多流技术, 实现不同任务间的异步操作, 进一步提高了
吞吐量. 为充分利用 CPU 端的多线程优势, 本文将多流技术和多线程技术相结合, CPU 端采用多线程模式, 使得
CPU 和 GPU 同时高效工作.

结合批量模式和单一模式

CPU …
线
程
池 数值拷贝 数值计算 数值拷贝

GPU 多流管理
图 4 总计架构

4.2 多项式算子优化
除多项式乘法外, CTRU-Prime 中还包含多项式采样、多项式加法、多项式求逆等多项式算子. 本节对这些多
项式算子的 GPU 优化方法进行说明.
4.2.1 多项式求逆
对于多项式求逆, 主要考虑了两种方法: 方法 1 基于 Bernstein 等人 [31] 提出的多项式求逆方法, 在合理数据划
分的基础上利用多线程完成 GPU 实现; 方法 2 受 OpenSSLNTRU [32] 的启发, 使用蒙哥马利求逆将 n 次多项式求逆
2
转化为 1 次多项式求逆和 n /2+3n/2−2 次多项式乘法. 具体来说, 为计算 Z q [x]/ f(x) 中的 n 个多项式 ( f 1 , f 2 ,..., f n )
∏ n
−1 −1 −1 f mul 进行一次多项式求逆运算得到
的逆, 即 ( f , f ,..., f ), 首先计算 n 个多项式的累乘 f mul = f i , 接着对
1 2 n
∏ ∏ i=1
k−1 n
−1
f mul , 最后只需利用乘法运算计算 f i −1 = f mul · i=1 f i · i=k+1 f i. 本文分别实现了上述两种方式并进行测试. CTRU-
−1
Prime-653 的测试结果表明, 当批处理大小为 100 时, 方法 1 比方法 2 快了 56.01 倍, 这表明蒙哥马利求逆方法并
不适合高并行度平台. 在传统平台上, 蒙哥马利求逆的优势在于转化更为耗时的多项式求逆为多项式乘法, 但在计
算过程中引入了过多串行化的处理流程, 例如多个多项式相乘. 尽管多项式相乘的延迟较多项式求逆更小, 基于高
并行性的特点, 相比串行化的多项式相乘, GPU 更适合并行化的多项式求逆. 此外, 单个多项式求逆无法充分利用
GPU 资源. 因此, 综合上述两个原因, 方法 1 比方法 2 展现出更优性能, 本文采用方法 1 完成多项式求逆操作.
4.2.2 多项式采样与多项式加法
在 CTRU-Prime 中, 使用中心二项分布完成多项式采样. 具体来说, CTRU-Prime-653 使用以整数 3 为参数的
中心二项分布, CTRU-Prime-761 和 CTRU-Prime-1277 使用以整数 2 为参数的中心二项分布. 中心二项分布以随
机值为输入, 以多项式为输出, 多项式系数的生成过程是相互独立的, 因此具备良好的并行特性. 在多项式系数的
数据分块上, 本文综合考虑核函数的理论占用率和多项式系数对输入的依赖关系, 设计了一种基于寄存器的并行
方案. 该方案将计算操作转移到高速寄存器中, 并在多个多项式系数之间共享寄存器值, 充分利用 GPU 资源.
多项式加法天然具备高并行度, 但对于 CTRU-Prime 而言, 直接将其实现为核函数并非最优解. 在 CTRU-
Prime 中, 多项式加法主要包括两个操作: 其一为二倍乘操作 g = f + f ; 其二为加一操作 g = f +1, 其中, f、g 为