一类国产复杂异构系统上的HPCG并行算法及高效实现研究

HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力,更贴近实际应用,近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义,其不仅可以提升国产超级计算机HPCG的排名,还对很多应用提供了并行算法、优化技术等方面的参考.本文面向某国产复杂异构超级计算机开展研究,首先采用了分块图着色算法对HPCG进行并行,并提出一种适用于结构化网格的图着色算法,该算法并行性能高于传统的JPL、CC等算法,且着色质量高,运用于HPCG后,迭代次数减少了3次,整体性能提升了6%.本文还分析了复杂异构系统各个部件传输的开销,提出一套更适用于HPCG的任务划分方法,并从稀疏矩阵存储格式、稀疏矩阵重排、访存等角度开展了细粒度的优化.另外在多进程计算时,还采用了内外区划分算法将核心函数SpMV、SymGS中的邻居通信操作进行了隐藏.最终整机测试时,性能达到国产超级计算机峰值性能的1.67%,相比单节点,整机弱可扩展性并行效率达到了92%.     

国产异构系统上的HPCG并行算法及高效实现

HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力,更贴近实际应用,近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义,其不仅可以提升国产超级计算机HPCG的排名,还对很多应用提供了并行算法、优化技术等方面的参考.面向某国产复...     

基于CPU-MIC异构众核环境的行星流体动力学数值模拟

数值模拟是行星流体动力学研究的主要工具.本文介绍CPU-MIC异构众核平台的行星流体动力学数值模拟,计算并模拟地球外核的磁流体运动.本文在已有工作的基础上~([1-3]),添加了CPU-MIC异构众核环境的数值模拟支持.首先描述了CPU-MIC异构众核环境的上的数值模拟流程,然后给出了MIC上的分布式并行GMRES(m)众核解法器的实现算法.其次,实现了解法器的计算核心稀疏矩阵向量乘(SpMV)在MIC上的分布式并行算法,该SpMV实现了计算-通信重叠、数据传输-计算重叠.再次,为加速行星流体动力学方程收敛,给出了MIC上以SpMV为基本操作的分布式并行多项式预条件子.最后,提出了一些MIC众核平台的优化措施,如多线程、流存储和数据传输优化等.天河2号数值模拟表明相比CPU版的数值模拟,CPU-MIC异构众核环境下数值模拟在单MIC卡和64块MIC卡分别取得了6.93和6.0倍的加速比.     

基于申威众核处理器的圣维南求解程序的并行与优化

圣维南方程组可用于描述明渠非恒定流的汇流过程,在大规模水文模拟软件中,求该方程组的数值解是制约程序运行时间的最大瓶颈.通过分析串行程序结构及其计算热点,挖掘计算密集型程序中单步模拟循环计算段和指令排列等的可并行性,针对"神威·太湖之光"超级计算机的异构众核架构设计主从核异步并行方案,基于MPI和athread库对求解程...     

面向新一代神威超级计算机平台的大气动力学问题全隐式求解器研究

大气动力学问题的数值模拟在气象预报等领域具有广泛的应用.相关数值模拟依赖超级计算机平台实现高精度高分辨率的气象预报,隐式求解不受稳定性条件限制,相比显式求解更有优势.面向新的超级计算机架构特征研究隐式大气动力学问题中一系列算子操作的并行和优化方法是非常有必要的.本文在规则递推关系的理论框架下对大气动力学问题预条件阶段的稀疏三角回代求解以及ILU矩阵分解操作的特征进行了总结,并结合申威26010Pro处理器的架构特点,对现有结构化稀疏三角线性方程组问题的并行算法进行了推广,设计了一套面向单向规则递推关系的算法框架,解决了预条件阶段各类算子的并行加速问题.本文还面向申威26010Pro处理器对大气动力学问题的模板计算等算子进行了移植和优化.实验结果显示,本文的算法框架对预条件阶段的算子能够实现26-33倍不等的加速效果,对模板计算等算子的优化相比串行计算有10-152倍的加速比.在新的神威超级计算机上最大测试到1700多万核心,浮点性能达到20.5PFlop/s.在大规模测试条件下的强(弱)可扩展性维持在56.81%41.87%以上.     

预处理共轭梯度算法异构并行求解及优化

共轭梯度算法是求解对称正定线性系统的重要方法之一,该算法求解问题通常具有稀疏性.随着问题规模的不断增大,单CPU因其存储及计算能力限制已经不能满足大规模稀疏线性方程组求解的实时需求.基于此,本文提出一种基于CPU+GPU异构平台的MPI+CUDA异构并行求解算法.首先,对共轭梯度算法进行了热点性能分析,说明该算法求解时存在的计算困难及挑战;然后,根据共轭梯度算法特性进行了任务划分,实现异构并行算法设计;最后,针对异构并行算法中存在的通信开销、数据传输开销和存储器访问开销等问题,对异构并行算法进行优化以进一步提升求解效率及性能.实验结果表明,与MPI并行和CUDALib并行相比,MPI+CUDA异构混合并行在串行计算部分较少的Jacobi预处理共轭梯度算法上分别获得336%和33%的性能提升,在串行计算部分较多的ILU预处理共轭梯度算法上也能分别获得25%和7%的性能提升,同时结果还显示MPI+CUDA混合并行随着节点数目的增加具有一定可扩展性.     

面向国产申威26010众核处理器的SpMV实现与优化

世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成,该超级计算机采用了国产申威异构众核处理器,该处理器不同于现有的纯CPU,CPU-MIC,CPU-GPU架构,采用了主-从核架构,单处理器峰值计算能力为3TFlops/s,访存带宽为130GB/s.稀疏矩阵向量乘SpMV（sparse matrix-vector multiplication）是科学与工程计算中的一个非常重要的核心函数,众所周知,其是带宽受限型的,且存在间接访存操作.国产申威处理器给稀疏矩阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种CSR格式SpMV操作的通用异构众核并行算法,该算法从任务划分、LDM空间划分方面进行精细设计,提出了一套动静态buffer的缓存机制以提升向量x的访存命中率,提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响SpMV性能的几个关键因素,并开展了自适应优化,进一步提升了性能.采用Matrix Market矩阵集中具有代表性的16个稀疏矩阵进行了测试,相比主核版最高有10倍左右的加速,平均加速比为6.51.通过采用主核版CSR格式SpMV的访存量进行分析,测试矩阵最高可达该处理器实测带宽的86%,平均可达到47%.     

基于计算与通信重叠的稀疏矩阵-向量乘积及其在AMG中的应用

本文针对代数多重网格(algebraic multigrid,AMG)并行实现中的稀疏矩阵-向量乘,建立了稀疏矩阵新的分布和数据存储模式,提出了一类具有最小通信量以及隐藏通信的新稀疏矩阵-向量乘并行算法,并实现了基于K-循环迭代的求解阶段并行算法.针对现代多核处理器,结合细粒度的并行编程模型,实现了MPI+OpenMP混合编程并行算法.通过同hypre软件包测试比较,在深腾7000集群上求解三维Laplace方程并行规模达到512核心时,并行求解阶段运行时间较hypre(high performance preconditioners)软件包提高了56%,在元集群上提高了39%,验证了算法的有效性.     

一种针对GPU上的油藏数值模拟的高效SpMV

油藏数值模拟和很多其他科学计算问题一样需要求解大型稀疏线性代数方程组.在求解稀疏线性代数方程组的迭代法中,稀疏矩阵向量乘法(SpMV)是影响计算效率的核心函数之一.随着计算机硬件架构异构化,科学计算从单核、多核CPU计算架构逐渐发展到多核CPU+众核加速卡(GPU卡或MIC等)的计算架构.SpMV的实现效率与稀疏矩阵的存储格式及硬件架构关系密切.本文针对油藏模拟中常见的Jacobian矩阵的稀疏模式,利用GPU核心的合并访问和并发计算等特点,结合油藏模拟线性解法器的算法要求,设计了一种BHYB矩阵存储格式及其对应的线程组并行策略.数值实验测得基于该存储格式的SpMV相对串行BCSR格式的SpMV的加速比可达19倍,比cuSPARSE库中效率最高的HYB格式的SpMV快30%到80%.此外,本文所提出的BHYB存储格式对块状矩阵在GPU上的存储以及线程组并行策略对其它GPU并行程序中内核函数的设计和优化能起到一定的借鉴作用.     

基于MRT-LBM方法的大规模可扩展并行计算研究

在大规模三维复杂流动的数值模拟中,针对具有良好数值稳定性的多弛豫时间模型格子Boltzmann方法(MRT-LBM),并结合大涡模拟湍流模型和曲面边界插值格式,分析了在D3Q19离散速度模型下的网格生成、流场信息初始化和迭代计算3部分的可并行性.采用MPI编程模型,从分布式集群的特点和计算量负载均衡的角度出发,分别提出了适合于大规模分布式集群的网格生成、流场信息初始化和迭代计算的并行算法.该并行算法也能有效适用于D3Q15和D3Q27离散速度模型.通过在国产神威蓝光超级计算机上的测试,分别针对求解问题总体计算规模固定和保持每个计算核中计算量一致的2种情况的并行性能分析,验证了该并行算法在十万计算核的量级下仍具有良好的加速比和可扩展性.     

跟踪界面活动网格法并行程序的性能分析

随着超级计算机向着更大规模趋势发展,并行算法与并行机相结合的可扩展性日益得到重视,特别是对实际应用程序的可扩展性研究愈为迫切.新的并行机的发展己成为科学计算本身的一个巨大挑战.目前仍然缺乏能求解“巨大挑战性问题”的数值方法和并行度高、可扩展性好的应用软件.大规模并行计算的一个关键问题是可扩展性问题[1].不可能期望通过将串行代码移植到并行系统上就能获得很大的性能增益.当处理机节点数超过64,16甚至8时,这种做法将使可扩展性降低.我国目前仍局限于中小型计算,原有算法和并行软件是否能求解更大规模问题是个值得关注的问题.     

HPSEPS 在元与神威 • 太湖之光上的移植和性能分析

“神威·太湖之光”高效能计算机系统是世界上首台峰值运算速度超过 10 亿亿次量级的超级计算机,HPSEPS (High Performance Symmetric Eigenproblem Solvers) 是自主开发的大规模对称稠密矩阵特征问题并行求解器,包括标准对称稠密矩阵特征问题的并行计算方法, 对大规模数据问题的计算,表现出较好的性能,本文分别在中科院的“元”超级计算机上和神威·太湖之光超级计算机上进行了移植, 对比了两种超级计算机的系统性能, 并且在“神威·太湖之光”上分别链接适合其异构众核结构的 xMath 数学库和 mkl 数学库, 对求解器在链接两种不同数学库的计算机效果进行了测试与分析。     

自适应谱聚类算法并行实现及优化

谱聚类算法是基于谱图分割理论的聚类方法,其对高维、非凸数据分布问题有很好的聚类效果。但对大规模数据问题的聚类,该方法存在着计算时间和存储空间等方面的瓶颈。本文给出了一个自适应的谱聚类并行算法,通过局部计算和异步循环通信并行方法,最大限度减少了并行谱聚类中数据通信次数,并通过计算与通信重叠策略,进一步降低了并行算法的通信开销。在并行算法实现中,将自主开发的最优预条件共轭梯度法并行求解器 PLOBPCG 用于谱聚类的特征降维。在中科院的“元”超级计算机上,通过对两类大规模数据聚类的测试表明,在 2048 核上的加速比接近线性加速,并行效率达到96%以上。     

基于神威·太湖之光的非结构网格众核优化技术

为解决高性能计算中的非结构网格离散访存问题,以神威·太湖之光国产超级计算机为平台,根据异构众核处理器SW26010的体系结构特点,提出一种基于排序思想的通用众核优化算法,以减少非结构网格计算中的随机访存。基于网格划分原理,在O(n)时间内对生成的稀疏矩阵非零元素进行并行重排序。采用一种内部映射方式对计算向量实现扩展或变换,将细粒度访存转化为无写冲突的粗粒度访存。对多个实际应用算例的通量计算进行众核优化,结果表明,相比主核上的串行算法,该算法能够获得平均10倍以上的加速效果。     

基于MIC集群平台的GMRES算法并行加速

广义极小残量法(GMRES)是最常用的求解非对称大规模稀疏线性方程组的方法之一,其收敛速度快且稳定性良好。Intel Xeon Phi众核协处理器(MIC)具有计算能力强、易编程、易移植等特点。采用MPI+OpenMP+offload混合编程模型将GMRES算法移植到MIC集群平台上。采用进程间集合通信异步隐藏、数据传输优化、向量化以及线程亲和性优化等多种手段,大幅提升了GMRES算法的求解效率。最后将并行算法应用到“局部径向基函数求解高维偏微分方程”问题的求解中。测试表明,CPU节点集群上开启32个进程,并行效率高达71.74%,4块MIC卡的最高加速性能可达单颗CPU的7倍。     

一类大规模稀疏矩阵特征问题求解的并行算法

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.     

基于神威太湖之光架构的LOBPCG并行算法研究

LOBPCG是一种适合大规模稀疏对称问题的特征值数值解法.本文研究了适合神威太湖之光架构的LOBPCG并行算法.首先提出了基于主、从核的混合并行模型;研究了稀疏矩阵-向量积的并行算法,通过核组间通信隐藏、核组内通信隐藏等技术提高程序速度,并提出一种自动调节从核缓冲数据量的算法,可自动逼近最佳的通信隐藏效果;研究了稠密矩阵积在神威太湖之光架构上的并行算法,针对不同"形态"的输入矩阵提出了不同的矩阵分割算法,速度显著优于其它算法库;在计算最高1.25亿阶矩阵、使用936000计算核心的特征值求解测试中表现出良好的扩展性.我们还测试了该应用在凝聚态物理领域的强关联系统中的性能.     

基于谱分割的稀疏矩阵特征值问题并行求解

本文给出了一个基于谱分割并行求解稀疏矩阵特征值的方案,将矩阵的特征值求解区间划分为多个独立的子区间,分别对各个子区间内的特征值进行独立的并行求解.在该方案中,提出了一种通过盖尔圆信息估计矩阵特征值分布的方法,并结合二分法以及插值方法修正特征值的分布,提高估计的准确性,进行谱区间分割.本文还结合谱分割和基于围道积分的近似谱投影算法设计出一个特征值问题多级并行算法,并在"深腾7000"和"元"超级计算机上验证了本文提出谱分割方案的有效性、均衡性以及特征值并行求解的高效性.同通用求解方法相比,基于谱区间分割的并行算法在1024核上性能提高了5倍以上,并行求解的可扩展性显著提升.     

面向国产异构众核系统的Parallel C语言设计与实现

异构众核架构具有超高的性能功耗比,已成为超级计算机体系结构的重要发展方向.但众核系统更为复杂的并行层次和存储层次,给编程和优化带来了极大的挑战,因此研究面向众核系统的并行编程技术,对于降低国产众核系统并行应用的编程难度、提升并行程序的性能都具有重要的意义.提出统一架构的多模式并行编程模型,包括异构融合的加速运算模型和按同构方式编程的自主运算模型,根据编程模型设计了Parallel C语言,能有效描述国产众核系统的异构并行性,与其它众核系统上MPI+X的使用模式相比,编程和系统优化都具有全局视角,在多级局部性描述、单边消息、兼容已有多核应用等方面具有特色;基于Open64构建了Parallel C编译系统,全面支持加速运算模型和自主运算模型,提出并实现了数据布局与自动DMA、编译指导的线程代理和拓扑位置感知的集合通信等优化.Micro Benchmark和实际应用在神威太湖之光计算机系统上的测试数据表明,Parallel C语言和编译系统具有良好的性能和可扩展性,能够有效支撑大型应用.     

共享存储环境下非平衡动力学方程组并行计算

OpenMP是现代多核机群系统采用的主要并行编程模型之一,在单CPU多核上可以获得良好的加速性能,但在整个机群系统上使用时,需要解决可扩展性差的问题.首先设计了求解非平衡动力学方程的并行算法.基于分布共享的多核机群系统,采用显式数据分布OpenMP并行计算方法,将数据进行分布式划分,分配到每个OpenMP线程,通过数据共享实现数据交换.计算结果表明显式OpenMP并行程序在保持可读性的同时,具有良好的可扩展性,在4核Xeon处理器构成的分布共享机群系统上,非平衡动力学方程组的数值并行计算可以扩展到1024个CPU核,具有明显的并行加速计算效果.