高性能稀疏矩阵向量乘的程序设计综述

稀疏矩阵向量乘(SpMV)广泛应用于科学计算、图计算、数据分析等领域,是自现代计算机诞生以来经久不衰且挑战依旧的研究热点。本文系统回顾了20世纪70年代以来稀疏矩阵向量乘程序设计的发展脉络和各阶段的代表性工作;分析比较了这一领域4条技术路线,即人工程序设计、自动调优器、稀疏编译器和自动程序设计器,在当今的流行方法;并在此基础上对高性能稀疏矩阵向量乘程序设计的研究趋势做出预测,力图给学习者和研究者带来有益的知识与启示。

NM-SpMM:面向国产异构向量处理器的半结构化稀疏矩阵乘算法

深度神经网络在自然语言处理、计算机视觉等领域取得了优异的成果,由于智能应用处理数据规模的增长和大模型的快速发展,对深度神经网络的推理性能要求越来越高,N∶M半结构化稀疏化技术成为平衡算力需求和应用效果的热点技术之一。国产异构向量处理器FT-M7032为智能模型处理中的数据并行和指令并行开发提供了较大空间。针对N∶M半结构化稀疏模型计算稀疏模式多样性,提出了一种面向FT-M7032的可灵活配置的稀疏矩阵乘算法NM-SpMM。NM-SpMM设计了一种高效的压缩偏移地址稀疏编码格式COA,避免了半结构化参数配置对稀疏数据访存计算的影响。基于COA编码,NM-SpMM对不同维度稀疏矩阵计算进行了细粒度优化。在FT-M7032单核上的实验结果表明,相较于稠密矩阵乘,NM-SpMM能获得1.73~21.00倍的加速,相较于采用CuSPARSE稀疏计算库的NVIDIA V100 GPU,能获得0.04~1.04倍的加速。

基于GPU对角稀疏矩阵向量乘法的动态划分算法

在图形处理器(GPU)上实现对角稀疏矩阵向量乘法(SpMV)可以充分利用GPU的并行计算能力,并加速矩阵向量乘法;然而,相关主流算法存在零元填充数据多、计算效率低的问题。针对上述问题,提出一种对角SpMV算法DIA-Dynamic(DIAgonal-Dynamic)。首先,设计一种全新的动态划分策略,根据矩阵的不同特征进行分块,在保证GPU高计算效率的同时大幅减少零元填充,去除冗余计算量;其次,提出一种对角稀疏矩阵存储格式BDIA(Block DIAgonal)存储分块数据,并调整数据布局,提高GPU上的访存性能;最后,基于GPU的底层进行条件分支优化,以减少分支判断,并使用动态共享内存解决向量的不规则访问问题。DIA-Dynamic与前沿Tile SpMV算法相比,平均加速比达到了1.88;与前沿BRCSD(Diagonal Compressed Storage based on Row-Blocks)-Ⅱ算法相比,平均零元填充减少了43%,平均加速比达到了1.70。实验结果表明,DIA-Dynamic能够有效提高GPU上对角SpMV的计算效率,缩短计算时间,提升程序性能。

基于稀疏矩阵结构的特征选择算法现状研究

在信息时代,数据获取方式简单快捷,使得数据量呈指数型增长。然而这些数据往往是多源高维的,增加了模型的复杂度,容易造成模型过拟合,并且数据中存在的冗余特征会降低模型分类精度。特征选择算法旨在通过去除不相关、冗余或嘈杂的特征,从原始特征中选择一小部分最有效特征,达到降维的效果。目前特征选择算法种类繁多,其中,基于稀疏矩阵结构的特征选择算法由于具有模型简单易懂和易求解的特点而被学者们广泛关注。本文归纳总结了基于稀疏矩阵结构的特征选择算法分类,重点介绍了鲁棒特征选择模型和多视图特征选择模型。首先,介绍了基于稀疏矩阵结构的特征选择算法基本框架;然后,介绍了基于稀疏矩阵结构的一般模型、鲁棒特征选择模型、多视图的特征选择模型,比较了它们在解决目前特征选择算法研究难点中存在的优势和不足;最后,对基于稀疏矩阵结构的特征选择算法进行了总结。文章阐明了理论研究中存在的问题和难点,探讨了基于稀疏矩阵结构的特征选择算法发展思路。

一种不规则稀疏矩阵的SpMV方法

稀疏矩阵-向量乘法SpMV是高性能计算领域的关键算子之一,在新兴的深度学习领域中有着重要应用。现有SpMV算子通常采用行列相等的稀疏矩阵,而对于不规则形状稀疏矩阵(行数与列数不等)的研究仍存在空缺,值得进一步深入探讨。相比于行列相等的稀疏矩阵,不规则形状稀疏矩阵凭借其行数与列数不对等的稀疏特点具有进一步优化的空间。因此,针对这种行数与列数不对等的不规则形状稀疏矩阵建立SpMV性能模型,分析得到其出现性能瓶颈的原因在于缓存和内存之间数据交互的带宽不足。同时做了以下2个方面的优化工作:(1)基于常用稀疏矩阵CSR存储格式,提出新型RCSR存储格式,其针对CSR存储格式中一个制约性能的数组进行了变换和压缩,使得SpMV更加高效;(2)结合国产处理器的SIMD指令扩展设计了基于RCSR格式的SpMV优化算法。在国产飞腾处理器上分别使用规则和不规则稀疏矩阵进行测试,在规则稀疏矩阵的情况下,通过采用RCSR存储格式和SIMD加速指令集,以GFLOPS为性能指标,实现了平均83.35%的性能提升;在不规则稀疏矩阵的情况下,性能提升与行列比相关,在行列不对等加剧时,具有更为明显的优化效果。

基于FPGA和行折叠的稀疏矩阵向量乘优化

稀疏矩阵向量乘(SpMV)是科学与工程计算中的一个关键内核。由于稀疏矩阵中不规则的数据分布和SpMV计算中不规则的访存操作,SpMV在多核CPU和GPU等设备上的性能与这些设备的理论峰值还具有较大差距。现有的CPU和GPU由于在架构上受到限制,导致它们无法很好地利用稀疏矩阵的特殊结构来加速SpMV计算,而现场可编程门阵列(FPGA)可以通过自定义电路实现高效的并行运算,能够更好地处理稀疏矩阵的计算和存储问题。基于FPGA提出了一种SpMV优化方法,该优化方法基于高级综合的流式处理引擎,采用了一种自适应多行折叠的SpMV优化策略。该方法通过行折叠减少了处理引擎中零元的无效存储和计算,从而提升了基于FPGA的SpMV计算性能。实验结果表明,相比于现有的FPGA实现方案,设计的基于行折叠优化的数据流引擎实现了最高1.78倍和平均1.15倍的加速。

基于低秩稀疏矩阵分解与定位窗滤波的混响抑制技术

在强混响背景下,使用传统的预白化处理、时频分析以及子空间分析等方法对动目标检测效果不佳,针对这一问题,本文利用近年来新引入的低秩稀疏矩阵分解理论来提高强混响背景下的动目标检测能力,采用多帧数据联合的鲁棒PCA处理算法,结合混响数据的声学特征将声学检测问题转化为图像分解问题,并通过对比PCA算法处理结果,给出算法的性能比较;与此同时,本文结合目标运动连续性和稀疏杂点随机性的特征差异,提出一种定位窗滤波方法,进一步滤除稀疏杂点,净化主动声呐显示图像,提高主动声呐动目标检测性能。仿真及试验数据处理结果说明,在阵元端信混比-5 dB情况下,算法仍然可以对目标准确定位,滤除稀疏杂点,且在时频域上效果更佳,显著提高了主动声呐动目标检测能力。

稀疏矩阵和改进归一化切割的快速多视图聚类

多视图聚类是一种新颖的聚类算法,它可以有效地探索出数据之间的内在聚类结构。大多数多视图聚类算法在构造相似图时容易受到噪声的影响,而且在聚类过程中还会面临信息损失问题,从而降低聚类结果的准确性。此外,现有多视图聚类算法通常使用交替迭代优化方法获得最优解,多次迭代会导致内存溢出或耗时过长。为了解决上述问题,提出了一种基于稀疏矩阵和改进归一化切割的快速多视图聚类算法(SINFMC)。该算法根据原始数据构造每个视图的相似图,并对相似图进行融合得到共识图矩阵。对共识图矩阵进行l1范数约束获得稀疏矩阵,实现数据降噪和加速计算。使用改进的归一化谱聚类算法对稀疏的共识图进行聚类得到聚类指标矩阵,这样不仅能够直接获得聚类结果,而且消除了聚类过程中的信息损失和偏差。该聚类算法无需交替迭代优化且通过稀疏矩阵表示精简计算过程,大幅降低了算法的时间和空间复杂度。人工和真实数据集上的比较实验结果表明该算法在质量和效率方面优于对比算法。

基于稀疏矩阵填充的级联毫米波雷达高分辨测角方法

级联毫米波雷达将多个射频芯片进行级联,可实现大规模多输入多输出(multiple-input multiple-output,MIMO)天线阵列。然而,现有毫米波雷达的测角方法存在精确度不足、旁瓣过高等问题。对此,提出一种基于稀疏矩阵填充的级联毫米波雷达高分辨测角方法。首先,建立级联毫米波雷达二维稀疏阵列的阵列信号模型。然后,将该阵列的单快拍信号构造为低秩汉克尔(Hankel)矩阵,使用加权非精确增广拉格朗日乘子法进行稀疏矩阵填充,并将填充后的矩阵转化为均匀虚拟阵列的单快拍信号。最后,使用常规波束形成(conventional beamforming,CBF)方法估计目标角度信息并进行配对。仿真和实测实验结果表明,所提方法能够精确地估计目标角度信息,并有效抑制峰值旁瓣电平。

应用于脑机接口系统的动态稀疏矩阵压缩算法

在脑机接口系统中,高通道数神经信号采集是一个核心功能模块,能够为外部计算机设备采集大量人脑中的神经信息;在高通道数神经信号采集中,因其原始数据量巨大,直接传输和处理产生的原始数据会消耗极大的功耗并增加硬件设计上的难度;为解决这个问题,一个有效的方法是在数据传输和处理前依据原始神经信号数据的特点对其进行压缩;神经元动作电位信号具有不应期性即有效信号的时域宽度与信号重复周期之比很小;利用此特点,能够将多通道神经信号的数字标记输出在一定时间范围内定义为一个稀疏矩阵,并对此稀疏矩阵进行特征提取,根据其特征动态地采用优化算法进行数据压缩;所提出的算法在Xilinx平台使用FPGA进行设计与实现,并且将其作为中控硬件在32通道神经信号采集硬件系统上通过实时验证,实验证明提出的动态稀疏矩阵压缩算法可实现83.4%的数据压缩率。

带状稀疏矩阵乘法及高效GPU实现

稀疏-稠密矩阵乘法(SpMM)广泛应用于科学计算和深度学习等领域,提高它的效率具有重要意义。针对具有带状特征的一类稀疏矩阵,提出一种新的存储格式BRCV(Banded Row Column Value)以及基于此格式的SpMM算法和高效图形处理单元(GPU)实现。由于每个稀疏带可以包含多个稀疏块,所提格式可看成块稀疏矩阵格式的推广。相较于常用的CSR(Compressed Sparse Row)格式,BRCV格式通过避免稀疏带中列下标的冗余存储显著降低存储复杂度;同时,基于BRCV格式的SpMM的GPU实现通过同时复用稀疏和稠密矩阵的行更高效地利用GPU的共享内存,提升SpMM算法的计算效率。在两种不同GPU平台上针对随机生成的带状稀疏矩阵的实验结果显示,BRCV的性能不仅优于cuBLAS(CUDA Basic Linear Algebra Subroutines),也优于基于CSR和块稀疏两种不同格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比分别为6.20和4.77。此外,将新的实现应用于图神经网络(GNN)中的SpMM算子的加速。在实际应用数据集上的测试结果表明,BRCV的性能优于cuBLAS和基于CSR格式的cuSPARSE,且在大多数情况下优于基于块稀疏格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比为4.47。以上结果表明BRCV可以有效提升SpMM的效率。

基于监督学习的稀疏矩阵自动任务分配

针对稀疏矩阵与稠密向量乘运算探讨了不同的任务分配策略对性能的影响,观察到任务分配策略的选择会显著地影响稀疏矩阵的运算性能,且不存在一种固定的任务分配策略针对所有的稀疏矩阵都能获得最佳性能。为此,提出了一种基于机器学习的最优任务分配策略选择模型,其训练过程仅使用稀疏矩阵的特征来刻画输入数据集,且能够针对给定的数据集和目标平台自动地训练模型。实验结果表明,相对于默认的块分配方法,使用该模型选择的任务分配方式能够获得平均约35%的性能提升。

基于非局部低秩稀疏矩阵分解的低剂量脑灌注CT统计迭代重建

脑灌注CT成像需要对患者头部进行连续反复扫描,相应的X射线辐射剂量较常规CT显著增加。为减少X射线辐射剂量,提出一种基于非局部低秩稀疏矩阵分解的低剂量脑灌注CT统计迭代重建方法。首先对脑灌注CT序列图像进行分块,然后构建非局部低秩稀疏矩阵分解模型,最后求解相应的目标函数重建出脑灌注CT序列图像。与滤波反投影算法和基于低秩稀疏矩阵分解的惩罚加权最小二乘方法相比,本文方法得到的脑血容参数图像的结构相似性指标分别提高38.07%和5.61%、特征相似性指标分别提高13.17%和2.47%;平均通过时间参数图像的结构相似性指标分别提高59.73%和0.28%、特征相似性指标分别提高20.26%和0.70%。本文方法能在去除低剂量脑灌注CT图像噪声和伪影的同时保持图像的边缘结构信息,并且获得更准确的脑血流动力学参数图像。

基于高预测性的稀疏矩阵向量乘法并行计算优化

稀疏矩阵向量乘法(sparse matrix-vector multiplication,SpMV)是广泛应用于科学计算、工业仿真和智能计算等领域的重要算法,是核心的计算行为之一.在一些应用场景中,需要进行多次的SpMV迭代,以完成精确的数值模拟、线性代数求解和图分析收敛等计算要求.受限于SpMV本身的高度随机性和稀疏性所导致的数据局部性极差、缓存效率极低、计算模式非常不规则等问题,导致其计算负载成为当前高性能处理器的优化难点和研究热点.基于现代高性能超标量乱序处理器的架构特征,深入研究SpMV的各类性能瓶颈,并且提出从提升可预测性和降低程序复杂度的角度进行全面的性能优化.其核心思想是:通过构建串行访问的数据结构,提升数据访问的规律性和局部性,大幅度优化数据预取效率和缓存利用效率;通过构建规则的分支跳转条件,提升程序的分支预测准确率,有效提升程序执行效率;通过灵活运用SIMD指令集,有效提升计算资源利用率.通过对以上特性的优化,该方法可以显著缓解性能瓶颈,大幅度提升处理器资源、缓存资源和访存带宽的利用率,并且获得与主流商用计算库MKL相比平均2.6倍的加速比,相比于现有最先进算法获得平均1.3倍的加速比.

基于半稀疏矩阵的聚乙烯管超声阵列全聚焦成像实验分析

高密度聚乙烯管广泛用于燃气输送等领域,其热熔接头的焊接质量直接影响管道系统的安全。采用全聚焦成像方法对高密度聚乙烯试块的横通孔缺陷进行成像实验,通过对检测信号进行信号预处理,提高全聚焦成像的效果,并提出一种基于半稀疏矩阵采集的超声阵列全聚焦成像方式,将该方式与基于全矩阵、半矩阵和稀疏矩阵采集方式的全聚焦成像结果进行比较。实验结果显示,基于半稀疏矩阵采集的全聚焦成像方法可有效降低计算量,提高实时检测效率,同样能够用于高密度聚乙烯材料中横通孔缺陷的重构且成像信噪比无明显降低。

基于稀疏矩阵的受电弓上框架冲击载荷识别方法

试验搭建受电弓模态测试系统,构建受电弓三维空间结构并给出合适的坐标,采用锤击法对某受电弓进行模态试验,得到受电弓的固有频率、模态振型和阻尼比等相关参数。根据锤击法得到的锤击点与响应点之间的频率响应函数,采用在时域内的L1范数正则化方法构建冲击载荷稀疏反卷积模型,使用截断牛顿内点法对受电弓上框架冲击力进行识别。结果表明:L1范数正则化方法对处理冲击载荷这类的稀疏矩阵问题具有一定的准确性和稳定性。

均匀稀疏矩阵的全聚焦成像算法研究

超声相控阵全聚焦成像算法作为一种后处理成像技术,虽然具有成像精度高、灵活性好的优势,但由于数据量大、计算时间长等问题,该项技术的实际工业应用受到了极大限制。针对该算法的不足,这里提出了基于均匀稀疏矩阵的全聚焦成像算法,通过减少矩阵数据量来提高成像效率。结果表明:相较于传统全聚焦成像算法,基于均匀稀疏矩阵的全聚焦成像算法极大的压缩了数据规模,计算速度同比提高约38%,为全聚焦快速成像提供了一种参考方法。

稀疏矩阵的概念与应用

稀疏矩阵在数据存储、机器学习、图像处理及文本处理方面有广泛的应用。在数据结构等一些课程中,教材会介绍稀疏矩阵,包括压缩存储方法等内容。由于稀疏矩阵的讲解比较少,理论的内容比较多,案例讲解较少,学生不易理解。为了让学生更好地理解稀疏矩阵及其应用,通过垃圾邮件过滤分类的案例,对比采用稠密型矩阵和稀疏矩阵两种形式,验证稀疏矩阵在存储和训练运算方面的优越性。

案例教学模式下的稀疏矩阵的概念与应用

矩阵在数据存储、机器学习、图像处理、自然语言处理中有着广泛的应用。稀疏矩阵是指矩阵中非零元素的个数较少的类型。数据结构这门课程作为高校计算机基础的一门课程,主要介绍的是计算机科学中用于组织和管理数据的方法和技术,其中包括介绍稀疏矩阵的内容。目前,一些教材在数据数组存储介绍上,对稀疏矩阵这个章节内容讲解较少,仅为理论内容,有些具体应用没有叙述清楚,容易使学生理解不深。为此,文章介绍具体案例,讲解稀疏矩阵的存储特点以及在计算效率上的优越性,让学生更好地理解稀疏矩阵,也更好地掌握数据结构这门课的内涵。

面向定制结构的稀疏矩阵分块方法

稀疏矩阵向量乘是科学计算的核心问题,采用定制结构来加速稀疏矩阵向量乘的执行对提升科学计算性能具有重要意义。针对目前面向定制结构的稀疏矩阵分块方法和表示方法的缺点,提出了稀疏矩阵二维均匀分块方法和相应的表示方法嵌套分块CSR。实验结果表明,提出的稀疏矩阵分块方法和表示方法能够有效减少填零个数。