一种基于GPU的并行算法功耗评估方法

随着软件和硬件的不断发展,图形处理器(GPUs)已经广泛用于通用计算领域,并作为加速器来协助CPU加速程序的运行。为了追求高性能,GPU往往包含成百上千个核心运算单元,高密度的计算资源使其在性能远高于CPU的同时功耗也高于CPU,因此功耗问题已经成为制约GPU发展的重要问题之一。分析了并行程序在GPU上运行时消耗的功耗,提出了并行算法在GPU上运行的功耗评估方法,接着通过并行前缀求和算法对该方法进行了详细的论述与分析。在实验部分通过稀疏矩阵向量乘算法的实际应用对该方法的正确性以及敏感性进行了证明与分析。结果表明,对于给定的程序,在满足性能要求的前提下,最优线程块数、存储访问方式以及任务分配顺序是影响系统功耗的关键因素。

间断Galerkin有限元隐式算法GPU并行化研究

为了提高间断伽辽金(discontinuous Galerkin,DG)有限元方法的计算效率,围绕求解Euler方程,构建了基于图形处理器(graphics processing unit,GPU)并行加速的隐式DG算法。算法结合Roe格式进行空间离散,采用人工黏性法处理激波等间断问题,时间推进选用下上对称高斯-赛德尔(lower-upper symmetric Gauss-Seidel,LU-SGS)隐式格式。为了克服传统隐式格式固有的数据关联依赖问题,借助于本文提出的面向任意网格的单元着色分组技术,先给出了LUSGS隐式格式的并行化改造,使得隐式时间推进能按颜色组别依次并行,由于同一颜色组内算法已不存在数据关联,可以据此实现并行化。在此基础上,再结合DG算法局部紧致等特点,基于统一计算设备架构(compute unified device architecture,CUDA)编程模型,设计了依据单元的核函数,并构建了对应的线程与数据结构,给出了DG有限元隐式GPU并行算法。最后,发展的算法通过了多个二维和三维典型流动算例考核与性能测试,展示出隐式算法GPU加速的效果,且获得的计算结果能与现有的文献或实验数据接近。

基于GPU并行算法的景观斑块周长模拟测量仿真

针对景观斑块周长模拟测量过程中收敛速度较慢的问题,提出基于GPU并行算法的景观斑块周长模拟测量方法。通过航拍技术采集景观斑块航拍图像,利用纠偏处理过程与高斯滤波处理过程对景观斑块航拍图像进行预处理。将景观斑块航拍图像输入GPU内,通过计算机GPU片段程序构建景观斑块航拍图像的高斯差分金字塔模型,并行运算过程提取景观斑块航拍图像特征点,确定景观斑块航拍图像中景观斑块的边界线。以边界线为基础,计算景观斑块周长。仿真测试结果显示,上述方法特征点提取过程中横轴与纵轴误差完全收敛时间分别为2.12s和1.80s,周长测量绝对误差与相对误差分别控制在0.60m和1.00%以下。

双通道交替最小化算法的GPU并行加速

大气湍流和系统噪声的存在使得天文或空间目标成像模糊。而双通道交替最小化算法是复原湍流和噪声降质图像的有效方法之一。但该算法比较复杂,需要反复迭代运算,处理耗时较长。为了提高算法运行速率,结合算法结构特征,将图形处理器(GPU)加速技术应用于双通道交替最小化算法,重点优化交替最小化迭代过程。实验结果表明:在不同湍流且信噪比(SNR)20 dB的条件下,与直接采用中央处理器(CPU)的算法相比,GPU并行加速用于双通道交替最小化算法,能够实现图像复原的“U-step”运算速率提升80%以上,点扩散函数求解的“H-step”运算速率提升60%以上,且恢复后的图像效果接近衍射极限。并行加速技术与已有的算法相结合的方式能够有效提高运行速率,为湍流和噪声降质图像的复原提供一定的参考。

基于GPU加速的全源对最短路径并行算法

针对最短路径算法处理大规模数据集低效的问题,提出了基于图形处理器(Graphics Processing Unit,GPU)加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据,然后减少了非规则行造成的工作项分支,最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明,与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理(Open Multi-Processing, OpenMP)并行算法和基于统一计算设备架构(Compute Unified Device Architecture, CUDA)并行算法相比,最短路径并行算法在开放式计算语言(Open Computing Language, OpenCL)架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比,验证了提出的并行优化方法的有效性和性能可移植性.

面向多尺度拓扑优化的渐进均匀化GPU并行算法研究

针对多尺度结构拓扑设计计算效率低等问题,提出了一种基于水平集渐进均匀化的多尺度拓扑优化并行算法。基于通用图形处理器(graphics processing unit,GPU),通过水平集初始化、大型稀疏刚度矩阵方程求解以及本构矩阵并行计算,可大幅提升渐进均匀化算法的效率。实验结果表明,当三维晶胞单元网格细化至分辨率为10万时,多尺度结构拓扑优化GPU并行算法较CPU串行算法快数十倍。

基于GPU加速的分布式水文模型并行计算性能

针对具有物理机制的分布式水文模型对大流域、长序列模拟计算时间长、模拟速度慢的问题,引入基于GPU的并行计算技术,实现分布式水文模型WEP-L(water and energy transfer processes in large river basins)产流过程的并行化。选择鄱阳湖流域为实验区,采用计算能力为8.6的NVIDIA RTX A4000对算法性能进行测试。研究表明:提出的基于GPU的分布式水文模型并行算法具有良好的加速效果,当线程总数越接近划分的子流域个数(计算任务量)时,并行性能越好,在实验流域WEP-L模型子流域单元为8712个时,加速比最大达到2.5左右;随着计算任务量的增加,加速比逐渐增大,当实验流域WEP-L模型子流域单元增加到24897个时,加速比能达到3.5,表明GPU并行算法在大尺度流域分布式水文模型计算中具有良好的发展潜力。

DRM:基于迭代归并策略的GPU并行SpMV存储格式

稀疏矩阵向量乘(SpMV)在线性系统的求解问题中具有重要意义,是科学计算和工程实践中的核心问题之一,其性能高度依赖于稀疏矩阵的非零分布。稀疏对角矩阵是一类特殊的稀疏矩阵,其非零元素按照对角线的形式密集排列。针对稀疏对角矩阵,在GPU平台上提出的多种存储格式虽然使SpMV性能有所提升,但仍存在零填充和负载不平衡的问题。针对上述问题,提出了一种DRM存储格式,利用基于固定阈值的矩阵划分策略和基于迭代归并的矩阵重构策略,实现了少量零填充和块间负载平衡。实验结果表明,在NVIDIA■ Tesla■ V100平台上,相比于DIA、HDC、HDIA和DIA-Adaptive格式,在时间性能方面,该存储格式分别取得了20.76,1.94,1.13和2.26倍加速;在浮点计算性能方面,分别提高了1.54,5.28,1.13和1.94倍。

增材制造中GPU并行扫描线填充算法

增材制造模型朝着大型化和精细化的趋势发展,对模型数据处理效率的要求越来越高。路径填充作为模型数据处理的一项重要环节,其效率直接影响模型的整体处理效率。本文重点研究基于GPU的并行化扫描线填充算法,采用轮廓预处理算法实现GPU并行求交运算的负载平衡,提出基于哈希值的三维坐标快速排序算法,构造轮廓组序号+坐标哈希值压缩结构,实现扫描线GPU并行化填充求交计算。经实验验证,本算法可大大减少扫描线填充算法耗时,对大型或精细模型的处理效果更为明显。

基于最小剩余时间算法与SR-IOV技术的GPU资源优化调度方案

为了优化GPU资源利用率,文章提出了一种新型的GPU资源调度方案。该方案结合了最小剩余时间算法与SR-IOV(SingleRootI/OVirtualization)技术,可优化多用户、多任务环境下的GPU资源利用率和系统性能。传统的GPU调度方法往往面临资源利用不足、任务等待时间长和系统吞吐量受限等问题。为了应对这些挑战,该方案通过动态分析任务的剩余执行时间,利用SR-IOV技术实现了GPU资源的细粒度隔离与共享,可为更高效的资源分配和任务调度提供支持。实验结果表明,相较于传统的无调度、容器调度和常见机器学习调度方案,该方案在均值准确率、GPU利用率、系统吞吐量和任务执行时间等方面均具有一定的优势,可为多用户多任务场景下的GPU资源管理提供有益的参考。

研究生课程“并行算法”教学内容优化设计研究

研究生课程“并行算法”是在大规模科学与工程计算需求越来越大的情况下开设的,旨在让学生学会如何实现并行计算的方法,熟练掌握并行计算的实现过程。基于课程教学经验和实践,论述了侧重并行计算思维训练和理论实践相结合的教学理念,以及基于该理念与模块化方式,从基本概念、基本技术、具体算法到编程实践等层面对教学内容的优化设计,以提升学生的学习效果与综合素质。

基于GPU并行算法的水动力数学模型建立及其效率分析

应用非结构化网格建立水动力模型目前已经得到了广泛的应用.针对在网格数过多,且无集群机情况下难以快速获得计算结果这一问题,基于GPU的高性能计算技术,在CUDA开发平台下设计并行算法,建立非结构化网格的二维水动力模型.与利用GTX460显卡和集群机的计算效率对比表明,在保持计算精度的前提下,速度提升了一个量级,且随着网格数的持续递增,可以保持较高的加速比增幅,比较适合应用于大范围海域的水动力模型的数值计算.

一种求解机组组合问题的内点半定规划GPU并行算法

针对内点法求解机组组合问题的半定规划（SDP）模型时大规模线性方程组计算时间太长的问题，提出一种基于图形处理器（GPU）的Krylov子空间并行算法。该算法采用预条件处理的拟最小残差法（QMR法），并以矩阵分块技术为基础。在CSR存储格式下使用GPU实现Incomplete Cholesky并行预处理矩阵的计算。通过对不同规模线性方程组的计算分析表明，与传统的Ch01eskv直接法相比，QMR并行算法具有速度和存储优势．可获得良好的并行加速比。10-100机6个系统的仿真结果也表明，该SDP并行内点法在减少计算时间的同时可求得近似最优解。

基于GPU的多通道倍频程并行算法研究

倍频程分析是一种噪声与振动信号处理中的常用分析方法,在声与振动测量软件或仪器中广泛使用,但是由于这种算法的计算量很大,特别是多通道信号的倍频程分析,占用测量软件或仪器的大量计算资源,成为提高分析速度的瓶颈因素。为了解决这个问题,本文引入了一种在GPU实现的多通道信号倍频程分析的并行算法,利用GPU的并行计算模型,采用多通道FIR并行滤波的方法,将倍频程滤波转换成信号矩阵相乘的结构进行迭代计算,从而实现多通道倍频程分析的并行处理。在256个通道的实例测试中,这种算法带来了最高120倍的速度提升。

一种基于Dual-GPU的三次卷积插值并行算法研究

针对传统三次卷积插值算法实现遥感图像放大在运算规模、计算速度等方面的不足,结合GPU的高性能计算优势,提出一种基于Dual-GPU(Graphic Processing Unit)的三次卷积插值并行算法(CCPA),即应用GPU的高性能计算技术将传统的三次卷积插值算法进行并行化处理,将图像的像素点个数平均分配给每个线程块,每个线程针对一个像素,线程在GPU中同时执行,以提高其插值效率。实验结果表明,该算法在保持放大后图像质量的同时,速度得到提升,随着图像分辨率的增大,该算法的优势更明显,在分辨率10240*10240的情况下,用GPU处理的速度比CPU提升了97.7%,用双GPU处理的速度是单GPU的2倍,并且在对放大遥感图像的质量和实时性均要求较高如地震、洪水等灾害的情况下,该算法具有实用价值。

一种基于GPU集群的深度优先并行算法设计与实现

深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低。为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排。提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡。为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作。实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销。在一个GPU集群中,它可以对含有数十亿节点的图有效地执行分布式DFS。

基于GPU加速求解MINLP问题的SQP并行算法

针对确定性算法求解大型复杂混合整数非线性规划的时间不可接受问题,通过对序贯二次规划算法(SQP)和图形处理器(GPU)的架构特点分析,提出了基于GPU加速策略的并行化SQP算法。算法的主要思想是通过枚举法确定二元变量的取值,在保证取值完整的基础上,使用CPU+GPU的并行策略,同时运用大量线程进行非线性规划子问题的求解。算例的数值实验结果表明:本文所提出的算法较之传统串行计算具有较好的加速效果,特别适合求解二元变量较多,约束条件相对少的MINLP问题。

基于GPU的机电暂态仿真细粒度并行算法

提出一种基于图形处理器(GPU)并采用隐形梯度法的机电暂态仿真细粒度并行算法。该算法将整个系统分为发电机节点系统和非发电机节点系统,对发电机节点系统求解时,先将在网络中直接相连的发电机节点合并成一个子系统,然后在GPU中给每个子系统分配相应线程块进行并行求解,其中采用了LU并行分解来求解线性方程组。求解完成后,利用从发电机节点系统传递来的LU分解信息,再对非发电机节点系统使用GPU进行求解。通过对不同规模的算例进行分析表明:所提出的GPU并行算法的计算结果与CPU串行算法和BPA软件的计算结果大致相同,且随着系统规模的增加,GPU并行算法的加速效果更为明显。

面向指数积分方法的电磁暂态仿真GPU并行算法

为满足对大规模可再生能源接入的电力系统进行快速电磁暂态仿真的需求,提出了一种面向指数积分方法的电力系统电磁暂态仿真图形处理器(GPU)并行算法。首先,分析了矩阵指数积分算法求解过程所具有的高度数据并行性,进而将该特性与GPU计算资源相结合;利用GPU处理指数积分方法求解时所需的大规模矩阵运算,而将较为复杂的系统状态判别与更新保留在CPU中完成,有效提升了仿真计算速度。最后,分别针对17台和100台风机的风电场算例进行了测试,验证了所提并行算法的正确性和有效性,同时也说明了算法的加速效果会随着系统规模的增加而愈发明显。

基于GPU的二部图联合聚类并行算法研究

提出一种基于GPU的二部图联合聚类并行算法,它能够在单指令多线程模型下完成高性能并行计算。针对空间联合聚类算法中存在大量的空间聚类计算和约束判断计算(文中为求和计算),并行算法分别采用共享存储器和全局存储器加速技术,来提高算法执行的效率。该文以表示同一地区多时相、多比例尺的两个空间要素集的聚类为例,表明二部图并行算法比CPU串行算法最高可以获得858倍的加速比。GPU的实时处理能力和计算能力可以为海量的空间数据聚类提供新的思路和参考。