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

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

基于SMP集群的三维网格多粒度混合并行编程模型

为提高大规模三维网格并行算法的执行效率,针对SMP集群分布/共享两级内存层次结构的特点,介绍适用于SMP集群混合编程的不同实现方法.对三维网格模型最短路径问题的并行求解提出了多粒度混合并行编程模型,给出了实现该问题的MPI+OpenMP混合并行算法,并在SMP集群上同粗粒度MPI(Message Passing Interface)并行算法做了性能比较.结果表明,采用该多粒度混合并行编程模型具有更好的加速比和运行效率.     

基于工作站机群并行求解有限元线性方程组

随着计算机高速网络技术的发展,工作站机群正在成为并行计算的主要平台.有限元线性方程组在土木工程结构分析中是最常见的问题.预处理共轭梯度法(PCGM)是求解线性方程组的迭代方法.对预处理共轭梯度法进行并行化并在两个不同的机群上实现,对存储方式进行详细分析,编程中采用了稀疏矩阵向量相乘的优化技术.数值结果表明,设计的并行算法具有良好的加速比和并行效率,说明并行计算能更快地求解大规模问题.     

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

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

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

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

SMP集群系统上矩阵特征问题并行求解器的有效算法

对称矩阵三对角化和三对角对称矩阵的特征值求解是稠密对称矩阵特征问题并行求解器的关键步 .针对SMP集群系统的多级体系结构,基于Householder变换的矩阵三对角化和三对角矩阵特征值问题的分而治之算法,给出了它们的MPI OpenMP混合并行算法 .算法研究集中在SMP集群系统环境下的负载平衡、通信开销和性能评价 .混合并行算法的设计结合了粗粒度线程并行模式和任务共享的动态调用方法,改善了MPI算法中的负载平衡问题、降低了通信开销 .在深腾6800上的实验表明,基于混合并行算法的求解器比纯MPI版本的求解器具有更好的性能和可扩展性 .     

面向磁流体动力学方程组的异构众核全隐求解器研究

磁流体动力学方程组被广泛应用于受控核聚变装置托卡马克、天体物理、磁流体发电等问题的研究中,其往往具有非线性、多尺度、多物理等特征,大规模数值难度较大.目前国际上对不可压缩流体问题的大规模数值求解主要采用全隐或半隐方法,但都是在同构的超级计算机而不是目前主流的异构众核系统上进行计算.论文面向国产神威"太湖之光"超级计算机,开展面向磁流体动力学方程组的异构众核全隐求解器研究.针对Newton-Krylov这类全隐求解器,提出了面向申威26010众核处理器的异构众核并行算法,并对其核心函数开展了众核并行和优化.对核心函数稀疏矩阵向量乘采用Matrix Free的方法来提升性能,对稀疏三角求解采用基于几何信息的异构众核并行算法,针对其访存密集的特点提出了存储格式、数据读取与计算依赖分离、核间寄存器通信等多种优化方法,对非线性残差计算等stencil类计算及10多个向量函数进行了异构众核并行,该异构众核并行算法可被其它应用软件重用.论文采用二维磁场重联问题进行测试,实验结果表明16进程时加速比可达13.6倍,能够支持高分辨率长时间模拟,并准确捕捉磁场重联现象.另外整体并行扩展性已经达到53万核,强可扩展性并行效率达到了33.8%,弱可扩展性并行效率达到了80.7%.     

二元域大型稀疏矩阵向量乘的FPGA设计与实现

作为Wiedemannn算法的核心部分,稀疏矩阵向量乘是求解二元域上大型稀疏线性方程组的主要步骤。提出了一种基于FPGA的二元域大型稀疏矩阵向量乘的环网硬件系统架构,为解决Wiedemannn算法重复计算稀疏矩阵向量乘,提出了新的并行计算结构。实验分析表明,提出的架构提高了Wiedemannn算法中稀疏矩阵向量乘的并行性,同时充分利用了FPGA的片内存储器和吉比特收发器,与目前性能最好的部分可重构计算PR模型相比,实现了2.65倍的加速性能。     

基于MPI的并行计算集群通信及应用

对能有效解大型稀疏矩阵方程的LSQR串行算法进行了并行化分析，并应用可移植消息传递标准MPI的集群通信机制在分布式存储并行系统上设计和实现了LSQR并行算法，该并行算法和程序在地震表层模型层析反演中得到了有效的应用。     

基于图模型的图像分割并行算法研究与实现

为了提高图模型方法的分割速度,本文提出该方法的一种并行实现方案.该方案通过网格划分来实现相似度矩阵的并行计算.同时考虑到相似度矩阵的稀疏性和矩阵向量乘运算的内在并行性,在该方案中本文设计并行Lanczos算法来求解特征值问题.在MPI环境下的实验结果表明,该并行方案是提高图模型分割方法实时性的有效途径.     

基于GPU加速的并行WMD算法

Word Mover's Distance(WMD)是一种度量文本相似度的方法,它将两个文本之间的差异定义为文本的词嵌入向量之间的最小距离.WMD利用词汇表,将文本表示为归一化的词袋向量.文本的单词在语料中所占的比例很小,因此用词袋模型生成的文本向量很稀疏.多个文本可以组成一个高维的稀疏矩阵,这样的稀疏矩阵会生成大量不必要的运算.通过一次性对多个目标文本计算单个源文本的WMD,可以使计算过程高度并行化.针对文本向量的稀疏性,文中提出了一种基于GPU的并行Sinkhorn-WMD算法,采取压缩格式存储目标文本的方式来提高内存利用率,根据稀疏结构减少中间过程的计算.利用预训练词嵌入向量计算单词距离矩阵,对WMD算法进行改进,在两个公开的新闻数据集上进行优化算法的验证.实验结果表明,在NVIDIA TITAN RTX上并行算法与CPU串行相比最高可以达到67.43倍的加速.     

层流扩散燃烧在GPU上的并行计算和数值分析

在实际工程应用中,使用传统的CPU串行计算来开展燃烧数值模拟往往难以满足对模拟速度的要求。利用GPU比CPU更强的计算能力,通过在交错网格上将燃烧物理方程离散化,使用预处理稳定双共轭梯度法(PBiCGSTAB)求解离散化方程,并且探索面向GPU编程的矩阵向量乘并行算法和逆矩阵向量乘并行算法,从而给出一种在GPU上数值求解层流扩散燃烧的可行方法。实验结果表明,GPU并行程序获得了相对串行CPU程序约10倍以上的加速效果,且计算结果与实际情况相符,因而所提方法是可行且高效的。     

改进的求解线性方程组的并行Arnoldi方法

以Galerkin原理为基础,提出了求解循环块三对角线性方程组的并行算法。根据系数矩阵的稀疏性,选取适当的子空间的基,使算法不但不会发生中断,并从理论上证明了当系数矩阵对称正定时,该并行算法收敛。最后,在HP rx2600集群上进行的数值实验结果表明,该算法的并行效率很高,理论和实际计算相一致。     

基于Hadoop的大矩阵乘法处理方法

目前的矩阵乘法算法无法处理大规模和超大规模的矩阵,而随着MapReduce编程框架的提出,并行处理矩阵乘法成为解决大矩阵运算的主要手段。总结了矩阵乘法在MapReduce编程模型上的并行实现方法,并提出了实现高性能大矩阵乘法的策略——折中单个工作节点的计算量和需要网络传输的数据量。实验证明,并行实现算法在大矩阵上明显优于传统的单机算法,而且随着集群中节点数目的增多,并行算法会表现出更好的性能。     

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

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

多核集群系统上的混合编程模型研究

对采用多核处理器作为SMP集群系统的计算节点的系统上的一种混合编程模型-MPI+OpenMP混合编程模型进行了深入的研究.建立了两个矩阵乘的混合并行算法,在多核集群平台上与纯MPI算法分别进行了实验,并进行了性能方面的比较.试验表明,混合编程具有更好的性能.     

广义Hermitian特征问题标准化转换的有效并行块算法

广义Hermitian特征问题并行求解器的性能依赖于所选择的并行算法和矩阵的分布策略等诸多方面.基于块存储和快算法策略,提出了一个新的标准化转化的并行算法,该并行算法将Cholesky分解结合到广义特征问题标准化转换中,降低了已有并行算法的通信开销,并增加了算法的并行性.新算法可显著改善已有并行算法的性能和可扩展性.另外给出了一个有效求解具有多个右端项的三角矩阵方程AX=B的并行块算法.通过自主开发的特征问题并行软件包PSEPS的测试结果表明,并行算法比传统的并行算法快大约1倍,并具有较好的可扩展性.     

MPI+TBB混合并行编程模型在分子动力学中的应用

为了提高分子动力学模拟在对称多处理(SMP)集群上的计算速度,在分子动力学并行方法中引入MPI+TBB的混合并行编程模型。基于该模型,在分子动力学软件LAMMPS中设计并实现混合并行算法,在节点间采用MPI及空间分解技术实施进程级并行,节点内采用TBB及临界区技术实施线程级并行。在SMP集群中的测试表明,该方法在体系较大以及节点数较多时可以明显减少通信时间,使加速比在纯MPI模型上提高45%。结果表明,MPI+TBB混合并行编程模型可促进分子动力学并行模拟且效率明显提升。     

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

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

布尔矩阵乘的分布式异构并行优化

布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法。分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法。布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求。分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法。通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升。