(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211206857.X (22)申请日 2022.09.30 (71)申请人 北京天数微芯 半导体科技有限公司 地址 100083 北京市海淀区学院路3 5号世 宁大厦14层 (72)发明人 肖利民　沈润楠　肖希源　王良　 郭为　 (74)专利代理 机构 南京钟山专利代理有限公司 32252 专利代理师 张力 (51)Int.Cl. G06F 9/50(2006.01) (54)发明名称 一种面向zk-SNARK运 算的GPU并行加速方法 (57)摘要 本发明公开了一种面向zk ‑SNARK运算的GP U 并行加速方法， CP U执行输入输出任务， 将待处理 数据读入内存， CPU执行Prescan过程， 根据给定 进制划分指数， 并将对应指数的底数分离； CPU 为 GPU分配内存空间和桶数组， 将底数放入桶中； GPU根据桶数据执行Bucket Mul计算， 为每个桶完 成桶内数据乘积计算； GPU使用完成桶内乘积计 算的值， 执行WindowReduce操作， 进行桶间组内 乘积的计算； GPU将每一位的值整合起来， 执行 FinalReduce过程， 使对应位的指数完成自乘， 并 将自乘后的数值相乘得到最终的结果。 本发明在 GPU上实行， 可更好地支撑大规模数据计算处理 的需求。 权利要求书2页 说明书7页 附图2页 CN 115543616 A 2022.12.30 CN 115543616 A 1.一种面向zk ‑SNARK运算的GPU并行加速方法， 其特 征在于， 包括： 步骤(1)： CPU执行输入输出任务， 将待处理数据读入内存， CPU执行Prescan过程， 根据 给定进制划分指数， 并将对应指数的底数分离； 其中， 输入输出任务指 计算椭圆 曲线有限域 上的多重点加任务 并给出结果M， P1…PN为底数， a1…aN分別为各项对应之 指数； 待处 理数据即输入 步骤(2)： CPU为GPU分配内存空间和桶数组， 将底数放入桶中； 步骤(3)： GPU根据桶数据执 行BucketMul计算， 为每 个桶完成桶内数据乘积计算； 步骤(4)： GPU使用完成桶内乘积计算 的值， 执行WindowReduce操作， 进行桶间组内， 也 即指数某一 位的全部底数乘积的计算； 步骤(5)： GPU根据步骤(4)的计算结果， 将每一位的值整合起来， 执行FinalReduce过 程， 使对应位的指数完成自乘， 并将自乘后的数值相乘得到最终的结果。 2.根据权利要求1所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(1)具体过程 为： 步骤(1.1)， CPU执行输入输出任务， 将待处理数据读入内存， CPU执行Prescan任务， 计 算出每个桶Tim内的元素索引， 并为GPU设计分配区域存放； 步骤(1.2)， 采用一次性分配的方式， 使用标记数组记录每个桶对应的索引缓存区的起 始位置与终止位置， 从而划分出每 个桶的索引缓存区。 3.根据权利要求2所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(1.1)中， 根据 的计算内容， 分析得出， Tim中i相同， 即属于同一Ri 的桶， 并起来是全体输入P1,P2,…,PN； Ri的个数即指数的2C进制位数 因此共需分配 个 索引的空 间， 上述运算中， 假设P1…PN为底数， Multiexp运算有N项， 每个指数为二进制的B位 数， 每C位划为 一组。 4.根据权利 要求2或3所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所述步骤(1.2)中， 根据指数的数值确定确定每个输入出现于桶的位置， 对 k＝0～ N， 通过右移并取与， 得出输入的指数ak在2C进制下第i位 的值bki， 则索引k应放入桶 的 索引缓存区。 5.根据权利要求4所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(2)具体过程 为： 步骤(2.1)， CP U分配 个索引的索引缓存区idxbuf并分配 个索引的起始与终止位 置记录标记数组sear r； 步骤(2.2)， 扫描输入统计每个桶的元素个数， 根据元素个数信息， 填写searr数组， 再 扫描一次输入， 结合sear r记录的桶 的起始位置， 将索引k实际放入idxbuf的对应位置 。 6.根据权利要求4所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 步 骤(3)所述Buc ketMul计 算使用GPU的多线程能力完成， 每个桶对应 一个线程， 则 桶Tij应当对 应第i*2C+j个线程， 该线程从属于对应桶的idxbuf区域读取索引， 根据索引从输入取得数权　利　要　求　书 1/2 页 2 CN 115543616 A 2据， 与结果相乘并返回。 7.根据权利要求4所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(4)具体过程 为： 步骤(4.1)， WindowReduce 需要计算 将Ri的计算任务分配给第i个线 程完成， 共需 个线程； 在完成向各线程分配任务后， 利用累乘的思想进 行各项数据的乘积， 计算式为： 步骤(4.2)， 实现Ri的结果计算： 将Run ningSum过程和乘到总和上Ri并进行迭代。 8.根据权利要求2所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(4.2)首先将变量RunningSu m与Ri初始化为单位元， 其次从 遍历到Ti1， 每轮将 Tij乘到RunningSum上， 并将Run ningSum乘到Ri上， 遍历完成即得到最终所需的Ri。 9.根据权利要求8所述的一种面向zk ‑SNARK运算的GPU并行加速方法， 其特征在于， 所 述步骤(5)具体过程 为： 步骤(5.1)， FinalRedu ce使用单线程计 算 利用累乘思想进行乘积运 算， 计算式为： 步骤(5.2)， 将M初始化为单位元， 从RW遍历到R0， 再将每轮Ri乘到M上， 并将M自乘C次， 遍 历完成即得到最终的M 。权　利　要　求　书 2/2 页 3 CN 115543616 A 3