(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211138724.3 (22)申请日 2022.09.19 (71)申请人 浙江大学 地址 310058 浙江省杭州市西湖区余杭塘 路866号 (72)发明人 陈文智　陆涛　魏成坤　余瑞璟　 张紫徽　 (74)专利代理 机构 杭州天勤知识产权代理有限 公司 33224 专利代理师 曹兆霞 (51)Int.Cl. G06F 17/16(2006.01) G06F 7/544(2006.01) (54)发明名称 基于GPU加速的大规模椭圆 曲线多标量乘法 的并行计算方法 (57)摘要 本发明公开了一种基于GPU加速的大规模椭 圆曲线多标量乘法的并行计算方法， 包括以下步 骤： 大规模椭圆曲线多 标量乘法的原始运算任务 的切分得到多个子运算任务； 并行存储子运算任 务的曲线点； 一系列并行稀疏矩阵操作； 稀疏矩 阵中曲线点元素进行加权求和； 规约子运算任务 结果获取最终大规模椭圆 曲线多标量乘法结果。 该计算方法将原始大规模椭圆曲线多标量乘法 任务切分成子任务， 并且将计算过程中多种复杂 操作简化 成并行稀疏矩阵运算， 为大规模椭圆 曲 线多标量乘法提供加速。 该计算方法的时间复杂 度相比于现有方法更少， 在理论上可以达到接近 GPU提供的线程个数的并行加速 。 权利要求书2页 说明书5页 附图2页 CN 115481364 A 2022.12.16 CN 115481364 A 1.一种基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 包括 以下步骤： (1)将原始运算任务切分： 将大规模椭圆曲线多标量乘法的原始运算任务依据标量切 分多个子运 算任务； (2)并行存储子运算任务的曲线点： 将多个子运算任务的所有曲线点根据曲线点对应 的子标量并行存 储至一个稀疏矩阵中； (3)并行稀疏矩阵操作： 对存储有曲线点的稀疏矩阵进行矩阵转置、 矩阵向量乘法操 作， 以获得曲线点向量； (4)并行计算子运算任务结果： 对曲线点向量中的曲线点进行加权相加， 获得子运算任 务结果； (5)计算原 始运算任务结果： 将所有子运 算任务结果归约得到原 始任务结果。 2.根据权利要求1所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 步骤(1)中， 原始运算任务为： 其中， n表示运算的规模， ki表 示第i个标量， Pi表示第i个曲线点， kiPi表示标量 ki与曲线点Pi的数乘， Q表示 运算的结果； 对应λ位的标量ki切分为λ/s个s位的子标量mi j， 多个子标量mi j满足公式 这样， 将原始计算任务 切分为 λ/s个子运 算任务 其 中， Gj是子运算任务的运 算结果， j表示子运 算任务的索引。 3.根据权利要求1所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 步骤(2)中， 创建一个尺寸为t ×2s–1的稀疏矩阵， 其中， t表示GPU能够提供的 GPU线程总数， s表示子标量的位数； 每个GPU线程平均分配n/t个曲线点任务， 根据曲线点对应子标量mij的值， 将曲线点放 置在稀疏矩阵每一行的mij列位置处， 实现子运 算任务的所有曲线点在稀疏矩阵中的存 储。 4.根据权利要求3所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 还包括： 根据曲线点对应子标量mij的值， 将曲线点在原始曲线点向量中的索引 放置在稀疏矩阵每一行的mij列位置处， 实现子运算任务的所有曲线点在稀疏矩阵中的存 储， 其中， 原 始运算任务中曲线点组成原 始曲线点向量。 5.根据权利要求1所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 步骤(3)中， 首 先， 对存储有曲线点的稀疏矩阵进行并行矩阵转置操作； 然后， 将经过矩阵转置操作后的稀疏矩阵与由单位标量组成的长度为n的向量， 并行进 行一次向量与稀疏矩阵的乘法， 该乘法的结果为长度为2s–1的曲线点向量， 记为 其中 均为曲线点。 6.根据权利要求5所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 在 进行矩阵向量乘法操作时， 通过动态调度不同数量的GPU线程来处理不同的 矩阵行以克服各个线程间的负载不平衡， 包括： 首先对稀疏矩阵的行根据行长进行排序， 并根据行长将所有行分成不同的组； 然后根权　利　要　求　书 1/2 页 2 CN 115481364 A 2据每个组中非零矩阵条目的比例为组调 度不同数量的线程， 使得每个线程工作的非零条目 数为相似的， 其中， 行长为每行中非零矩阵条目的个数。 7.根据权利要求1所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其特征在于， 步骤(4)中， 首先， 将每个GPU线程平均分配(2s‑1)/t个曲线点的计算任务， 对 分配到的第i个曲线点Bi求其对下标的加权值， 也 就是iBi； 然后， 将所有加权值归约， 计算子运 算任务结果 8.根据权利要求1所述的基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法， 其 特 征 在 于 ， 步 骤 ( 5 ) 中 ，将 所 有 子 运 算 任 务 结 果 归 约 到 原 始 任 务 结 果 其中， Gj为第j个子运 算任务结果。权　利　要　求　书 2/2 页 3 CN 115481364 A 3