PreNTT:面向zk-SNARK的数论变换计算并行加速方法

简洁非交互式零知识证明(zk-SNARK)由于具备证明验证过程简捷快速的优点,已在加密货币等众多领域得到广泛应用。但其证明生成过程所需计算仍复杂耗时,影响了进一步的应用拓展。针对zk-SNARK证明生成过程中的主要计算瓶颈——数论变换(NTT),提出了一种基于GPU的NTT计算加速方法PreNTT。首先,提出了基于预计算的NTT并行计算方法,利用预计算与旋转因子次幂算法优化,减少NTT并行计算开销,并结合动态预计算,进一步提高NTT计算效率。其次,通过“动态自适应计算核调度”,可以根据NTT输入规模自适应地分配GPU片上资源,提升了大规模NTT任务的计算能效。然后,通过核外整体数据混洗和核内局部数据混洗相结合的方式,避免了访存冲突。最后,使用CUDA多流技术执行数据传输和计算过程,对预计算时间进行了有效隐藏。实验结果表明:基于PreNTT实现的zk-SNARK系统,与目前业界最先进的系统Bellperson相比,NTT模块运行时间获得了全规模最低1.7倍的加速比,最高加速比为9倍。PreNTT能够有效提高NTT算法并行度,降低zk-SNARK运算时间开销。

水利科学计算并行计算平台构建及算法实践

文中采用现代先进的信息技术和计算技术,研究基于高性能并行计算的水利水电大型科学计算平台体系和构建,并采用Sun Fire 6800R和Sun Cluster Tools初步形成了高性能并行计算平台的架构,结合水利水电科学计算的实践,通过数学模型的结构分析、并行改造,探索、推广并行计算技术在水利水电数学模型计算领域的应用,并以此构架基于网络的开发式并行计算共享平台。

基于双向遍历的蒙特卡罗临界计算并行方法

在基于蒙特卡罗粒子输运方法的反应堆模拟中,如裂变堆、聚变裂变混合堆等,达到可接受的统计误差需要大量的计算时间,这已成为蒙特卡罗方法的挑战问题之一,需通过并行计算技术解决。为解决现有方法中通信死锁的问题并保证负载均衡性,设计了基于双向遍历的临界计算并行算法。该方法基于超级蒙特卡罗核计算仿真软件系统SuperMC进行实现,以池式钠冷快堆BN600基准模型进行验证,并与MCNP进行对比。测试结果表明,串行和并行计算结果一致,且SuperMC并行效率高于MCNP。

基于数据对称打包的云计算并行核心失败校验缓解

提出一种具有容错的云计算核心失败校验并行数据打包的前滚校验方法.首先,对云计算的核心失败校验算法进行介绍,同时为避免数据溢出,采用对称打包方式对输入进行并行计算,并利用打包输出所包含的冗余特征,提高连续核心故障的容错性能;其次,利用打包数据进行对应的通用矩阵乘法(generic matrix multiplication,GEMM)操作,建立新的整数矩阵的乘法运算、卷积运算和故障恢复机制,来缓解核心故障问题,并对所提方案的计算复杂度进行理论分析;最后,通过在数据平均吞吐量、数据恢复率以及算法的计算时间三项指标上的对比实验,验证了所提方法的有效性.

基于集群SPMD算法及演化计算并行研究

高性能计算在科学研究领域有着广泛的应用。演化计算因具有计算规模大、种群中个体相关性小等优点,成为并行计算研究的主要对象之一。提出两种并行策略,对顺序GA(Genetic Algorithm)实现并行。首先使用主从模式对多种群协同遗传算法实现并行,在此基础上通过对算法进一步改进,实现了基于对等模式的并行演化计算,从而提高了算法可扩展性。比较了两种并行模式的各自特点,通过SPMD(Single Program Multiple Data)算法实现和基于上海大学“自强2000”高性能计算机上的实例验证,改进算法具有更好的可扩展性,更易于推广到网格环境。

遥感影像区域面积快速计算并行算法研究

为了有效地解决遥感应用中感兴趣区域内有效遥感影像面积统计效率的问题,提出一种基于MPI(Message Passing Interface)的并行计算环境,采用经典数学定理鞋带公式(Shoelace Formula)及计算机图形学中向量积法计算多边形面积。使用三角分割法对多边形进行切割并行,判断多边形之间拓扑关系,获取交集顶点表,使用鞋带公式并行计算交多边形面积。以1.96407的加速比有效提高遥感影像有效面积统计效率,加快网页加载速度,提高用户体验度。

计算并行性的研究和描述

本文对计算并行性的几个级别,给出了Petri nets方式的描述并且研究了它们的并行特点,实现了对典型新一代计算机体系结构和语言的并行流程的描述。

基于Epiphany计算并行矩阵乘法的研究

为了提高矩阵乘法的计算效率,首先通过分析串行实现的矩阵乘法当中的不足之处,找出在单核上计算所存在的问题,提出将操作矩阵进行二维块状划分并行计算的解决方案。基于二维网状结构的多核处理器,先从一般矩阵与特殊矩阵向量间的乘法开始分析,再给出计算一般矩阵乘法的Cannon算法。结合多核并行运算的天然优势,通过对所划分子块的合理调度,来克服核间通信传输速率缓慢的弊端,以实现高效计算矩阵乘法的目的。通过模拟实验与单核上的串行计算对比,证实并行计算的矩阵乘法在耗时上有了显著的提高。

面向国产异构众核架构的CFD非结构网格计算并行优化方法

神威太湖之光在2016-2018年度全球超算top500榜单中排名第一,峰值性能为125.4 PFlops,其计算能力主要归功于国产SW26010众核处理器。由于CFD非结构网格计算存在拓扑关系复杂、离散访存问题严重、存在强相关的线化方程求解等问题,导致CFD非结构网格计算一直是国产众核超级计算机移植与优化的难题。为充分发挥国产异构众核架构的计算效能,首先,提出了一种数据重构模型,提高了数据的局部性和可并行性,使得数据结构更加适应众核架构的特点;然后,针对非结构网格数据存放的无序性导致的离散访存问题,提出了一种基于信息关系预存的离散访存优化方法,将离散访存转化为连续访存;最后,对于存在强相关的线化方程求解问题,引入了从核阵列流水线并行的思想,实现了众核并行。优化后CFD非结构网格计算的整体性能相比原始版本提升了4.19倍,相比通用CPU提升了1.2倍,并扩展到62.4万计算核心的并行规模,能保持64.5%的并行效率。

基于混合有限元法的油浸式变压器稳态流-热耦合场并行计算方法

针对油浸式变压器2维流-热耦合仿真计算效率低的问题,提出了基于混合有限元法的并行计算方法。首先,在Visual Studio 2019中采用C++语言实现无量纲最小二乘有限元法以及迎风有限元法的串行计算方法。然后,基于图形处理器(graphic processing unit,GPU)实现流体场的并行计算,针对单分区分匝模型对比分析了不同GPU卡在不同网格条件下的并行计算效率,分析结果表明数据规模越大,GPU卡流处理器越多并行效果越好。其次,基于Intel MKL(Intel math kernel library)函数库结合共享存储并行编程(open multi-processing,OpenMP)实现了2维温度场的并行计算,并对比分析了不同网格数量对并行效率的影响。最后,在此基础上提出了根据不同仿真条件的混合并行计算方法,并应用到大型油浸式变压器绕组模型的2维温升热点分析中。结果表明,相较于串行程序,混合有限元并行计算方法的加速比达到了69.5,实验测试结果进一步验证了并行计算结果的准确性,研究成果为大型油浸式变压器流-热耦合问题的快速计算奠定了基础。

高性能并行计算的发展历程

并行计算是相对于串行计算而言的,它是将一个计算任务分解成若干相对独立的子任务,然后用若干个处理器对其并行求解。使用并行计算最直接的目的就是提高问题的求解速度以快速完成原问题的解。非数值计算是相对数值计算而言的,它研究的是如何将计算科学中一些不能直接使用数学函数解决的问题并行求解。90年代开始,我带领团队系统地开展了此方面的研究,首先是奠定了所需的理论基础,并逐渐形成了完善的学科体系和应用示范。在此过程中,我们还积极倡导交叉学科研究,及时关注学科前沿技术,并且坚持学术研究要服务于国民经济主战场。在整个研究过程中,我们一方面积极开展国际学术交流,创办国际学术会议和专业期刊;另一方面坚持自力更生,研制自主可控的国产高性能计算机,创建科教平台为普及中国高性能计算机教育服务。

基于并行BICGSTAB的不可压流场计算方法

不可压缩流动广泛存在于日常生活及工程应用之中,随着数值模拟规模不断扩大,CFD算法越来越重视并行计算。该文采用SIMPLE算法对不可压流场进行求解,为求解算法中的大型稀疏矩阵,该文发展一套基于MPI框架的并行BICGSTAB矩阵求解方法。最后采用定常顶盖驱动流算例及非定常圆柱绕流算例验证并行算法的可行性及准确性。

超大规模数据处理中并行计算技术的应用研究

随着人工智能和大数据时代的到来,超大规模数据处理成了一个重要的研究领域。该文主要探讨并行计算技术在超大规模数据处理中的应用,首先详细阐述并行计算和超大规模数据处理的基本理论与概念,特别是并行计算的编程模型与工具,最后通过分析并行计算在搜索引擎、气象预报和金融分析等中的实际案例,阐述并行计算技术在超大规模数据处理中的实际应用。

基于Distance-2算法的并行Jacobian矩阵计算及其在耦合问题中的应用

并行Newton-Krylov方法是求解大规模多物理耦合问题的有效方法,如何高效自动计算Jacobian矩阵是一大难点。利用有限差分方法,可避免推导Jacobian矩阵的表达式,实现矩阵的自动计算。现有工作表明,在串行环境下利用矩阵的稀疏性和图着色算法,Jacobian矩阵的计算效率可提高至少1个量级。但在并行环境下,串行着色算法失效,需采用相应的并行着色算法。本研究将图论领域的Distance-2算法应用于Jacobian矩阵的并行着色。通过求解一个简化多物理耦合问题检验了该并行算法的正确性和计算效率。测试结果表明,该并行算法得到的Jacobian矩阵完全正确;着色数随着并行核数的增加略微有所增加,100个进程下并行效率为56%;基于该算法求解多物理耦合问题,其计算时间和Krylov迭代次数较JFNK减少了约1/2。

异构并行计算下高维混合型数据聚类算法研究

高维数据维度增加,数据空间的体积呈指数增长,容易陷入“维数灾难”,导致聚类算法执行效率低,为此,提出异构并行计算下高维混合型数据聚类算法。构建高维混合型数据相异度矩阵,提取高维混合型数据的统计序列特征值,利用时间窗口进行特征优化。采用K⁃Prototypes聚类算法提取高维混合型数据的统计序列特征,评估数据与类中心的相异性,计算数据与类中心的欧氏距离,实现高维混合型数据聚类。采用异构并行计算技术进行高维混合型数据K⁃Prototypes聚类的并行化处理,合理分配CPU与GPU工作,达到CPU与GPU的工作负载平衡,提高K⁃Prototypes的聚类效率。实验结果表明,此算法对于高维混合型数据的聚类效果好、运行时间短、性能稳定。

三维连续-非连续并行计算方法及其在岩爆过程模拟中的应用

随着深部岩石工程的发展,岩爆变得越发严重。在岩爆的数值模拟方面,连续方法和非连续方法均具有一定的局限性。兼具二者优势的连续-非连续方法更具优势,且正在快速发展。基于CUDA对自主开发的三维拉格朗日元与离散元耦合连续-非连续方法进行了GPU并行加速。为了探索岩爆的机理和过程,模拟了不同静水压力、侧压系数和单元数目(最多达100×10^(4))条件下圆形洞室围岩V形坑的演化规律和单元弹射现象。考察了洞室围岩中裂纹的定量演化规律。研究表明:当静水压力较大时,基于芬纳公式的支护设计偏于不安全。由于V形坑的位置发生改变,V形坑的平均最大深度随着静水压力的增加先缓慢增加后快速增加。关于洞室围岩V形坑的模拟结果能与有关的实验结果、数值结果和现场观测结果吻合。上述研究很好地体现了岩爆并行计算较串行计算和商业软件计算的优势。

高速通信系统中并行CRC计算及电路实现

针对高位宽数据情况下的循环冗余校验码(Cyclic Redundancy Code, CRC)电路计算工作频率较低以及资源占用过多的问题,设计并实现了一种并行CRC计算方法。该方法将CRC计算拆分为数据CRC计算和余数CRC计算两个部分,余数CRC计算由多个余数CRC计算模块级联完成,数据CRC计算模块由固定逻辑表达式实现,对二者计算结果做模二加法即得到CRC计算结果。根据数据长度选择相应的数据CRC计算模块和余数CRC计算模块的组合,以适应高位宽可变数据长度的CRC计算。以100 Gbps远程直接数据存取(Remote Direct Memory Access, RDMA)通信系统中的1 024 bits数据位宽CRC-32的计算为例,在VCU118开发板上实现了该算法的硬件电路。实验结果表明,所提设计仅使用4 760个查找表和2 658个触发器,整个系统带宽最高可达97.85 Gbps,最高工作频率可达326 MHz。与其他相关方法相比,提出的方法具有较高的工作频率且资源占用较少。

新时期“GPU并行计算”课程体系与教学模式设计

为满足新时期人工智能交叉方向人才培养需求,对“GPU并行计算”课程体系与教学模式进行了积极的探索和实践。理论教学方面,夯实并行计算基本理论,强化并行算法设计、GPU并行编程技巧及优化方法。实践教学方面,通过渐进式实验项目的反复迭代,帮助学生建立实践经验和应用信心。新体系通过多样的教学模式使学生紧跟并行计算研究的前沿技术。通过鼓励不断创新和探索的课程评价体系使学生能够自觉、自愿地将并行计算应用于科学研究。

基于图计算的配电网理论线损分层并行计算方法研究

随着配电网规模的不断增大,在理论线损计算等电网分析应用领域,存在计算效率较低的问题。在构建配电网理论线损分析图模型的基础上,提出了一种基于图计算的配电网理论线损分层并行计算方法。该并行图计算方法采用整体同步并行计算模型(bulk synchronous parallel computing model,BSP),能够有效减少大型配电网的潮流计算时间。同时充分考虑配电网多层级的划分,通过分馈线子图并行前推回代潮流计算,能够提高理论线损的分析效率,并且能快速准确地找到网络降损的关键点。最后在IEEE123节点模型上验证了本文提出的模型和算法的有效性。

基于CUDA并行计算的煤矿奥灰突水快速准确预测方法

通过分析目前我国煤矿突水预测研究的现状,提出当前条件下我国煤矿突水预测方法难以实现实时监测突水风险问题。通过将待监测区域进行有限元剖分,根据区域内钻孔水位反演计算监测区域各节点水位,从而进行突水风险预测。结合有限元突水预测方法,将英伟达公司开发的CUDA并行计算技术应用到煤矿突水防治中,详细介绍了CUDA预测突水软件编写思路和模型。编写了CUDA监测突水程序并结合钻孔水位数据对煤矿突水点进行了实际预测,与传统CPU串行计算相比,大大提高了煤矿突水预测计算速度,对实现煤矿突水快速准确预测具有参考意义。