TEB:GPU上矩阵分解重构的高效SpMV存储格式

稀疏矩阵向量乘法(SpMV)是科学与工程领域中一个至关重要的计算过程,CSR(compressed sparse row)格式是最常用的稀疏矩阵存储格式之一,在图形处理器(GPU)平台上实现并行SpMV的过程中,其只存储稀疏矩阵的非零元,避免零元素填充所带来的计算冗余,节约存储空间,但存在着负载不均衡的问题,浪费了计算资源。针对上述问题,对近年来效果良好的存储格式进行了研究,提出了一种逐行分解重组存储格式——TEB(threshold-exchangeorder block)格式。该格式采用启发式阈值选择算法确定合适分割阈值,并结合基于重排序的行归并算法,对稀疏矩阵进行重构分解,使得块与块之间非零元个数尽可能得相近,其次结合CUDA(computer unified device architecture)线程技术,提出了基于TEB存储格式的子块间并行SpMV算法,能够合理分配计算资源,解决负载不均衡问题,从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性,在NVIDIA Tesla V100平台上进行实验,结果表明TEB相较于PBC(partition-block-CSR)、AMF-CSR(adaptive multi-row folding of CSR)、CSR-Scalar(compressed sparse row-scalar)和CSR5(compressed sparse row 5)存储格式,在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍;在浮点计算性能方面,平均可提高3.36、5.95、2.29和2.13倍。

毫米波通信系统中可重构智能表面辅助多用户信道估计方案

为了解决可重构智能表面(Reconfigurable Intelligent Surface,RIS)辅助的多用户毫米波通信系统中级联信道的信道估计问题,提出了一种新的基于压缩感知(Compressive Sensing,CS)的两阶段级联信道估计方案,该方案在传统的压缩感知信道估计上引入级联信道双时间尺度性质和行列稀疏邻近结构,同时利用信道特性和双结构正交匹配追踪算法(Double-Structured Orthogonal Matching Pursuit,DS-OMP)在节约导频开销的同时也提高了信道估计的精度和性能。通过仿真分析各变量对所提方案归一化均方误差(Normalized Mean Square Error,NMSE)的影响,相较于传统基于压缩感知的信道估计算法,所提方案具有较好性能,同时有较小的导频开销。

扩展有限元刚度矩阵的CSR存储实现

扩展有限元方法(XFEM)是处理裂纹、孔洞、夹杂等不连续问题中应用最为广泛的数值方法之一。XFEM基于单位分解方法,在标准有限元方法的位移近似函数中引入附加函数项来反映位移场的间断特性和奇异特性。附加函数项的引入,导致XFEM单元刚度矩阵大小不定,标准有限元方法的总体刚度矩阵的组集方法不能直接使用于扩展有限元方法中。本文提出一种基于‘广义相邻节点对’的非零元素存储方案,该方案通过使用“广义相邻节点对”和总体刚度矩阵中非零元素的位置一一对应的关系,配合大型稀疏矩阵的CSR存储格式(Compressed Sparse Row format:行压缩存储格式),直接从单元刚度矩阵组集形成压缩存储的总体刚度矩阵。该方案较好的解决了扩展有限元总体刚度矩阵的压缩存储和组集问题,详细阐述该方案的实现过程,将此方案成功实现于Fortran语言自主开发的扩展有限元程序中,并对程序的准确性进行了验证。

历史图上基于CSR结构的PageRank算法

近年来,学者们对静态图的研究越来越全面、深入,已经形成了完善的理论体系。但是,对于生活中的一些应用问题,如社交网络中不断变化的关系等,使用静态图表示此类动态变化的关系似乎显得有些乏力。而历史图可以表示动态的变化。PageRank算法是用于衡量网页重要程度的算法,而网络中不断有网站新建或删除,这样的网络用历史图来表示更为合适,因此考虑在历史图上利用CSR(Compressed Sparse Row)结构实现PageRank,使得程序能够给出几个目标时间上各网站的评分,进而能够提供网站评分的变化情况,给出网站影响力趋势的预测。在Wekipedia提供的网页互相连接的Hyperlink networks数据集上,将所提方法与在链表上实现PageRank算法做比较,结果显示其性能大大优于使用链表的结构,并且随着数据规模和目标时间规模的增大,其优势将会越来越明显。

基于GPU的稀疏矩阵向量乘优化

针对稀疏矩阵运算难以发挥图形处理器的强大运算能力的现状,基于图形处理器的统一计算架构,在线程映射、数据复用等方面研究了一系列并行计算优化方法,从而完成了一种行压缩存储表示下的稀疏矩阵向量乘并行算法。这些优化方法包括:(1)利用Warp内线程天然同步特性,Half-warp完成结果向量一个元素的计算;(2)取整读取数据,实现合并访问;(3)输入向量放入纹理存储器,数据复用;(4)申请分页锁定内存,加速数据传输;(5)使用共享存储器,加速数据存取。实验分析表明,提出的各种手段起到了优化的作用。与已有的CUDPP和SpMV library中的CSR-vector算法相比,本算法获得了更高的存储器带宽和浮点运算吞吐量;整体性能比CPU串行执行版本快了3倍以上。

稀疏存储的显式有限元三角网格地震波数值模拟及其PML吸收边界条件

有限元法是复杂介质地震模拟的有力工具,它能比较客观地反映地震波的传播,比较细致地再现地震图像.但是,为了获得较精确的结果,有限元法模拟地震波的传播需要的网格点数多,具有计算量大和消耗内存多的缺点.针对上述缺点,本文对刚度矩阵采用压缩存储行（CSR）格式,以减少计算量并节省内存;采用集中质量矩阵得到对角的质量矩阵以提高有限元法（显式有限元）的计算效率;时间离散采用保能量的Newmark算法以提高有限元法的计算精度;采用变分形式（弱形式）的PML吸收边界条件对人工截断边界进行处理.通过与高精度的数值方法——谱元法的数值试验的对比表明,上述方法的引入可使有限元法在计算精度和计算效率方面均可取得比较显著的改进.为了获得相当的计算精度,相比于7阶谱元法,显式有限元法需要更精细的网格.然而,显式有限元法的计算速度比前者快近2倍,而内存需求仅为谱元法的1/4～1/6.

基于GPU的稀疏线性系统的预条件共轭梯度法

研究了基于GPU的稀疏线性方程组的预条件共轭梯度法加速求解问题,并基于统一计算设备架构(CUDA)平台编制了程序,在NVIDIAGT430 GPU平台上进行了程序性能测试和分析。稀疏矩阵采用压缩稀疏行(CSR)格式压缩存储,针对预条件共轭梯度法的算法特性,研究了基于GPU的稀疏矩阵与向量相乘的性能优化、数据从CPU端传到GPU端的加速传输措施。将编制的稀疏矩阵与向量相乘的kernel函数和CUSPARSE函数库中的cusparseDcsrmv函数性能进行了对比,最优得到了2.1倍的加速效果。对于整个预条件共轭梯度法,通过自编kernel函数来实现的算法较之采用CUBLAS库和CUSPARSE库实现的算法稍具优势,与CPU端的预条件共轭梯度法相比,最优可以得到7.4倍的加速效果。

基于局部加密等级网格的2.5D直流电法有限元模拟

合理截取半圆形计算区域,采取局部加密的?-等级网格,结合对称行索引存贮格式(CSR)及并行稀疏直接求解器PARDISO,提出一种高效、高精度的2.5D直流电阻率法有限元正演方案,并编制相应的Fortran程序,对具有解析解的3个典型地电模型进行计算与分析。研究结果表明:圆形截断边界不仅便于在径向方向上采取?-等级网格剖分,而且能大大简化有限元模拟中单元刚度矩阵的计算;结构化的等级网格避开了通常非结构化网格有限元计算时繁琐的网格剖分及总体刚度阵的集成过程,且能在不增大问题规模的前提下,显著提高2.5D直流电法正演源点附近的模拟精度;Intel MKL的PARDISO求解器能在普通PC机上5 s内求解电法正演有限元离散得到的100万阶稀疏线性方程组,可广泛用于各种地球物理正演问题。

对角线稀疏矩阵的SpMV自适应性能优化

稀疏矩阵向量乘(SpMV)是科学计算中常用的内核之一,其运行速率跟非零元分布相关.针对对角线稀疏矩阵,提出了压缩行片段对角(compressed row segment diagonal,CRSD)存储格式.它利用"对角线格式"有效描述矩阵的对角线分布,区别于以往通用的计算方法,CRSD通过对给定应用的对角线稀疏矩阵采样再进行特定的优化.并且在软件安装阶段,通过自适应的方法选取适合具体运行平台的最优SpMV实现.在CPU端进行多线程并行化实现时,自适应调优过程中收集的信息还被用于线程间任务划分,以实现负载平衡.同时完成CRSD存储格式在GPU端的实现,并根据GPU端计算与访存的特点进行优化.实验结果表明:在Intel和AMD的多核平台使用相同线程数的情况下,与DIA相比,使用CRSD的加速比可以达到2.37X(平均1.7X);与CSR相比,可以达到4.6X(平均2.1X).

大范围点质量模型快速构建方法研究

针对大范围点质量模型构建中遇到的大型线性方程解算的难题,提出基于窗口控制的残差点质量模型构建方法。将点质量模型由原来的稠密线性方程转化为稀疏线性方程,并在普通计算机上完成112 896阶稀疏线性方程的求解。以空中扰动引力计算为例,与传统的点质量模型和位系数模型的计算结果进行比较。结果表明,该方法能够在保证计算精度的同时有效扩大解算范围,提高解算效率。

基于哈夫曼编码的稀疏矩阵的存储与计算

在科学计算中,稀疏矩阵与向量乘积SMVP是一个十分重要的计算内核,它的效率主要是由稀疏矩阵的存储模式及相应的SMVP算法所决定。为了在稀疏矩阵的存储模式方面获得较好的性能,在哈夫曼压缩编码的基础上,对现有的分块压缩行存储BCRS方法进行了改进,在一定程度上减少了冗余零元素的存储,并且给出了与新的BCRS方法相对应的SMVP算法。理论分析和数据实验表明,基于哈夫曼压缩编码的BCRS方法在数据复杂度方面优于原始的两种BCRS方法。

面向稀疏矩阵向量乘的DMA设计与验证

稀疏矩阵向量乘法(SpMV)是迭代法求解大型线性方程组的核心算法,被广泛应用在科研和工程中。高性能共轭梯度算法(HPCG)是评价高性能计算系统性能的测试程序之一,需要多次调用SpMV进行迭代计算。但是,SpMV计算过程中包含大量不规则访存操作,降低了系统计算性能。基于X-DSP项目,在DMA中设计一条面向SpMV的专用数据通道实现不规则访存的功能,提高HPCG算法运算速度。设计代码的验证与综合结果表明预期的功能实现正确,且满足项目对时序、面积和功耗的要求。

基于便笺式存储器的向量化SpMV算法的性能评估与分析

便笺式存储器是一种结构简单、访问延迟固定且软件可直接控制的片上高速存储,在现代处理器设计中得到了广泛应用。稀疏矩阵向量乘SpMV是高性能计算、人工智能等应用领域重要的内核计算函数之一。在传统多级Cache处理器中,SpMV算法计算过程中对稠密输入向量的不规则访问操作会导致大量Cache访问请求失效,从而影响SpMV算法执行效率。为了评估便笺式存储器对SpMV向量算法的性能影响,使用ARM SVE指令对基于CSR格式的SpMV算法向量化,并将算法中的热点数据即稠密输入向量存储在便笺式存储器中,在集成了便笺式存储器的ARM架构处理器中对SpMV向量算法进行了性能分析。在gem5模拟器中针对来自真实应用程序的2562个稀疏矩阵进行了实验。实验结果表明,集成了便笺式存储器的处理器与传统多级Cache处理器相比,针对向量化SpMV算法能够实现的最大加速比为7.45,平均加速比为1.11。

三角网格谱元法地震波场数值模拟

谱元法结合了有限元法的灵活性和谱方法的指数收敛性,高效且高精度,是近年来发展的一种重要的地震波场数值模拟方法.经典的谱元法采用四边形(六面体)网格,利用一维Gauss-Legendre-Lobatto(GLL)积分的张量积得到对角的质量矩阵,以大大提高计算效率,但是四边形(六面体)网格不能够灵活地刻画复杂的几何模型的弯曲界面.为此,在谱元法中引入三角形(四面体)网格到二维(三维)是十分必要的.不同于经典的谱元法,在非结构化网格中不能使用GLL积分的张量积,使得非结构化网格的谱元法的实现存在着诸多的困难.目前,比较流行的三角网格谱元法,通过使用KoornwinderDubiner(KD)正交多项式,并正交化这些KD多项式构建基函数,同时利用重合的插值节点和积分节点以获取对角的质量矩阵;它所使用的积分点为优化的点集——Fekete点,且这些积分点能与四边形网格完全耦合.相比于四边形,三角网格谱元法能显著提高复杂模型的描述能力,对起伏地表模型有很大优势.本文引入高效的最佳匹配层(PML)吸收边界条件,并通过数值试验将三角网格谱元法与经典的谱元法进行对比研究.相比于经典的谱元法,三角网格谱元法显著缺点为较低的计算精度.对于7阶谱元,为了能够精确地模拟面波,三角网格谱元法需要在每个最短的面波波长内至少有11个采样点,然而经典的谱元法仅需4个采样点,并且前者所需的内存量约为后者的5.5倍.

工程计算中大型稀疏矩阵存储方法研究

在工程实际中,许多问题都可以归结为数值法求解偏微分方程（组）的问题.偏微分方程数值解法主要包括有限差分法、有限元法和有限体积法,其中大多数方法都是通过离散的方式将方程转化为线性方程组,通过求解线性系统得到原方程的数值解.在这个过程中,线性方程组的系数矩阵通常很大并且很稀疏,会占用大量存储空间并使方程组难以求解.针对这个问题,本文研究大型稀疏矩阵的压缩存储方法,只存储非零元素,降低存储空间消耗,避免零元素参与计算,提升计算效率.具体来说,在稀疏矩阵生成过程中,使用十字链表法存储,可以在常数时间内完成非零元素的插入操作;在方程组求解过程中,使用按行（列）压缩存储方法,既节约存储空间,又可以提高求解器的求解效率.在实验部分,本文分别使用有限差分法求解Laplace方程和有限元法计算圆环截面应力分布问题,对其中大型稀疏线性方程组的系数矩阵,采用十字链表法和按行（列）压缩存储法存储,使用直接法和迭代法求解线性方程组.实验结果显示,对于结构化和非结构化的稀疏矩阵,压缩存储方法不仅能够大幅度减少内存空间的占用,而且能够显著提升求解器的效率.