一种面向稀疏矩阵的规整化行块重排及矩阵乘加计算方法与流程
本发明涉及gpu并行计算领域,具体公开了一种面向稀疏矩阵的规整化行块重排及矩阵乘加计算方法。
背景技术:
1、在稀疏矩阵计算中,矩阵中的绝大多数元素通常为0,只有少量元素为非零值。若仍然按照普通二维矩阵的方式存储全部元素,则会存储大量的0,造成存储空间浪费,并增加无效计算。因此,现有技术通常采用专门的稀疏矩阵存储格式,仅存储矩阵中的非零元以及这些非零元在原矩阵中的位置信息。
2、csr格式(compressed sparse row,压缩稀疏行格式)。其基本思想是:按照矩阵的行方向,从上到下、从左到右依次扫描矩阵,只把每一行中的非零元存储下来,同时额外记录这些非零元原来位于哪一列,以及每一行的非零元在存储数组中的起止位置。通常情况下,一个采用csr格式存储的稀疏矩阵可以由三个数组表示,分别是非零元数值数组data、列索引数组col_index和行指针数组row_ptr。其中,data是非零元数值数组,用于按照行方向依次存储原矩阵中的全部非零元素。也就是说,矩阵中为0的元素不会被存入data,只有非零元素才会被依次存入data。col_index是列索引数组,也可称为列号数组,用于记录data中每一个非零元在原矩阵中所在的列号。由于data只保存了非零元的数值,如果没有col_index,就无法知道这些非零元原来位于矩阵的哪一列。因此,data和col_index通常是一一对应的:data[j]表示第j个非零元的数值,col_index[j]表示该非零元在原矩阵中的列号。row_ptr 是行指针数组,也可称为行起止位置数组,用于记录每一行的非零元在data和col_index中的存储范围。对于矩阵的第i行,row_ptr[i]表示该行第一个非零元在data和col_index中的起始下标;row_ptr[i+1]表示该行最后一个非零元之后的下一个下标。因此,第i行的非零元在data和col_index中的存储区间为:从row_ptr[i]到row_ptr[i+1]-1。换言之,row_ptr[i]是第i行的起点,row_ptr[i+1]是第i行终点的后一位。两者相减可以得到第i行的非零元数量,即:第i行非零元数量=row_ptr[i+1]-row_ptr[i]。
3、为了便于理解,下面给出一个简单示例。假设原始矩阵a为3行4列矩阵:
4、;
5、该矩阵共有5个非零元,分别为10、20、30、40和50。按照csr格式,从第0行到第2行依次扫描各行,并在每一行内部从左到右记录非零元,可得到如下三个数组:
6、;
7、;
8、;
9、其中,data[0]=10,表示第0个非零元的数值为10;col_index[0]=0,表示该非零元位于原矩阵的第0列。data[1]=20,col_index[1]=2,表示第1个非零元的数值为20,位于原矩阵的第2列。row_ptr用于说明每一行在data和col_index中的范围。具体而言:对于第0行,row_ptr[0]=0,row_ptr[1]=2,表示第0行的非零元存储在data和col_index的下标0至下标1,即data[0]=10、data[1]=20,对应列号为col_index[0]=0、col_index[1]=2。对于第1行,row_ptr[1]=2,row_ptr[2]=4,表示第1行的非零元存储在data和col_index的下标2至下标3,即data[2]=30、data[3]=40,对应列号为col_index[2]=1、col_index[3]=3。对于第2行,row_ptr[2]=4,row_ptr[3]=5,表示第2行的非零元存储在data和col_index的下标4至下标4,即data[4]=50,对应列号为col_index[4]=0。
10、由上述示例可以看出,csr格式并不是直接保存完整二维矩阵,而是通过data保存非零元的数值,通过col_index保存非零元的列位置,通过row_ptr保存每一行在data和col_index中的起止范围。这样既能够减少对零元素的存储,又能够在进行稀疏矩阵向量乘计算时快速找到每一行需要参与计算的非零元。
11、在不同的软件库或文献中,csr格式中的三个数组可能使用不同名称。例如,row_ptr也可能写作ap,col_index也可能写作ai,data也可能写作av。二者含义相同:ap对应行指针数组,ai对应列索引数组,av对应非零元数值数组。本文后续为了与具体实现方式保持一致,可能使用ap、ai、av表示csr格式中的row_ptr、col_index和data。
12、稀疏矩阵向量乘及其基于不同矩阵数据结构的实现方法:稀疏矩阵向量乘(spmv),是基础计算算子,其基本计算过程为:给定稀疏矩阵a和输入向量x,计算输出向量y,其中y=a×x。由于稀疏矩阵a中大部分元素为零,现有技术通常不会采用普通稠密矩阵格式存储a,而是采用专门的稀疏矩阵存储格式,仅存储矩阵中的非零元数值及其位置信息。常见的稀疏矩阵存储格式包括压缩稀疏行格式、坐标格式、压缩稀疏列格式、ellpack格式、sell-c-σ格式及其变体格式等。
13、以压缩稀疏行格式,即csr格式为例,稀疏矩阵a通常由三个数组表示:非零元数值数组data、列索引数组col_index和行指针数组row_ptr。其中,非零元数值数组data用于按照行方向顺序存储矩阵a中的全部非零元素;列索引数组col_index用于记录每个非零元素在原矩阵a中对应的列号;行指针数组row_ptr用于记录每一行非零元素在非零元数值数组data和列索引数组col_index中的起始位置和结束位置。
14、传统基于csr格式的spmv,对于矩阵a中的第i行,计算设备首先通过row_ptr[i]和row_ptr[i+1]确定第i行非零元素在data和col_index中的存储区间。随后,计算设备遍历该区间内的各个非零元素,依次读取非零元数值data[j]以及对应的列索引col_index[j],并根据col_index[j]从输入向量x中读取对应位置的向量元素x[col_index[j]]。然后,将data[j]与x[col_index[j]]相乘,并对同一行内的多个乘积结果进行累加,最终得到输出向量y中第i个元素y[i]。
15、在gpu等并行处理器上,现有spmv计算通常会根据矩阵行、非零元或行块对计算任务进行划分,并将不同计算任务分配给不同线程、线程组、warp或线程块执行。例如,可以由一个线程处理一行稀疏矩阵,也可以由一个warp处理一行,或者由一个线程块处理若干行。对于采用csr格式的spmv计算,gpu中的线程或warp通常根据row_ptr定位待处理矩阵行的非零元范围,再读取对应的data、col_index和输入向量x,完成乘加累积后写回输出向量y。
16、为了适应不同稀疏矩阵的行长分布特征,现有技术还可以采用ellpack、sell-c-σ等规整化稀疏矩阵格式。例如,ellpack格式通常将各矩阵行补齐到相同长度,并分别存储补齐后的非零元数值和列索引;sell-c-σ格式通常将矩阵行划分为若干行块,在每个行块内部按照该行块中的最大行长进行补齐,并对行进行排序或分组处理。上述格式均属于现有spmv计算中常见的数据组织方式。
17、warp级指令操作:在gpu并行计算架构中,warp是线程调度和执行的基本单元之一。一个warp通常由多个线程组成,例如在cuda架构中,一个warp包含32个线程。同一warp内的多个线程通常以单指令多线程的方式执行,即多个线程在同一时刻执行相同指令,但作用于不同的数据。为了提高小规模矩阵乘法、深度学习、科学计算等场景中的计算吞吐,现代gpu通常提供warp级矩阵乘加指令,例如mma指令或wmma指令。其中,wmma(warp matrixmultiply-accumulate,线程束级矩阵乘累加)。该类指令通常由一个warp内的多个线程协同执行,用于完成固定尺寸矩阵片段之间的乘加运算。其基本计算形式可以表示为:;其中,a和b表示输入矩阵片段,c表示累加器矩阵片段,d表示输出矩阵片段。与普通标量乘加指令不同,warp级矩阵乘加指令不是由单个线程独立完成一次完整矩阵乘法,而是由同一个warp内的多个线程共同持有矩阵片段中的不同元素,并由这些线程协同完成一次矩阵乘加操作。也就是说,warp级矩阵乘加指令的输入和输出通常具有两个重要特点:
18、第一,矩阵片段的形状是固定的。例如,某些指令要求a矩阵片段为m×k,b矩阵片段为k×n,输出或累加矩阵片段为m×n。只有当待计算数据能够被组织成相应的片段形状时,才便于使用该类指令。
19、第二,矩阵片段的数据不是按照普通二维数组的方式连续存放在单个线程中,而是按照硬件规定的线程-寄存器布局,分散存放在同一warp内多个线程的寄存器中。换言之,一个线程通常只持有矩阵片段中的一部分元素,完整的矩阵片段由整个warp共同持有。以fp64 m8n8k4 mma指令为例,该指令可以用于完成固定尺寸的矩阵乘加计算。其中,a矩阵片段的尺寸为8×4,b矩阵片段的尺寸为4×8,c/d累加器或输出矩阵片段的尺寸为8×8。执行该指令时,a、b、c/d中的各个元素会按照预定的线程-寄存器映射关系分布在warp内不同线程的寄存器中。例如,warp内的不同线程分别持有a片段、b片段以及c/d片段中的部分元素,并由整个warp协同完成矩阵乘加。以fp64 m8n8k4 mma指令的一种数据布局为例,t0至t31表示同一warp内的32个线程,a0、b0、c0、c1表示对应线程寄存器中持有的片段数据。warp级矩阵乘加指令通常要求输入数据按照特定的片段形状和线程-寄存器布局组织。基于上述特点可以看出,若希望利用warp级矩阵乘加指令执行稀疏矩阵向量乘计算,则不能简单地将csr格式中的data、col_index和row_ptr直接交给gpu线程逐项乘加。原因在于,传统csr格式主要适合按照矩阵行逐个读取非零元并进行标量累加,而warp级矩阵乘加指令更适合处理形状固定、布局规整的矩阵片段。因此,若要将spmv计算映射到warp级矩阵乘加指令上,需要先将稀疏矩阵中的非零元数据规整为固定尺寸的数据块,并按照目标矩阵乘加指令的片段形状和线程-寄存器布局进行重排。本发明后续提出的规整化行块重排方法,正是为了解决这一数据组织和计算映射问题。
20、对于传统csr格式spmv计算流程,现有技术虽然能够完成稀疏矩阵向量乘计算,并可在gpu上实现一定程度的并行化,但对于具有主导元结构特征的计算流体力学稀疏矩阵,仍存在以下缺点:
21、(1)难以直接利用warp级矩阵乘加指令。现有csr spmv的基本计算过程是对每一行中的多个非零元执行逐项乘法,并将乘积结果累加为一个标量输出。该过程本质上是针对单个矩阵行的点积计算,通常通过线程级标量乘加、warp内归约或线程块级归约实现。
22、然而,现代gpu中通常包含面向小规模矩阵乘法的专用矩阵乘加指令或矩阵计算单元,例如warp级mma/wmma指令。该类指令适合处理具有固定形状的数据片段,例如m×k与k×n的矩阵乘加操作。传统csr spmv中的矩阵行长度不固定,非零元在内存中的组织方式也主要服务于逐行遍历和标量累加,因此难以直接转换为固定形状的矩阵乘加计算。由此导致gpu中的矩阵乘加计算能力无法被充分用于spmv运算。
23、(2)没有充分利用计算流体力学矩阵中的主导元结构特征。在计算流体力学、有限体积法、有限差分法或结构化/半结构化网格离散场景中,稀疏矩阵的非零元分布通常来源于网格单元之间的邻接关系或离散模板。因此,此类矩阵往往具有明显的主导元结构特征,即大多数矩阵行的非零元数量集中在某一固定值或较小范围附近。例如,在三维七点模板相关场景中,大多数矩阵行的非零元数量可能为7或接近7。
24、现有csr、ellpack、sell-c-σ等通用spmv方法通常将稀疏矩阵作为一般稀疏矩阵处理,主要关注压缩存储、行长补齐或线程调度,而没有根据矩阵的主导元数量建立专门的数据规整化方式。也就是说,现有技术没有将“多数行非零元数量接近主导元”这一结构规律转化为适合gpu矩阵乘加指令执行的数据块结构。因此,对于具有主导元结构特征的稀疏矩阵,现有技术未能将占主要比例的矩阵行有效转换为可由warp级矩阵乘加指令处理的定长行块。
25、(3)现有行规整化方法未与矩阵乘加指令的片段形状相匹配。ellpack、sell-c-σ等格式虽然会对矩阵行进行补齐,但其补齐目的通常是使行长一致或使行块内部长度一致,以便改善访存和并行调度。该类补齐方式一般是根据全局最大行长、局部最大行长或分块行长确定补齐宽度,并不一定与gpu矩阵乘加指令的输入片段形状、k维度要求以及线程寄存器布局相匹配。例如,当矩阵中大多数行的非零元数量为7,而目标矩阵乘加指令的k维度为4时,如果不能将规整化宽度设置为大于等于主导元且为k维度整数倍的数值,则补齐后的数据仍难以自然拆分为适合矩阵乘加指令处理的固定片段。由此会导致后续计算仍需额外的数据重排、分支判断或标量乘加过程,无法充分发挥矩阵乘加指令的吞吐优势。
26、综上,现有技术虽然能够通过csr、ellpack、sell-c-σ等格式完成spmv运算,但其计算过程主要仍围绕逐行遍历和标量乘加展开,未能根据计算流体力学稀疏矩阵的主导元结构特征以及gpu矩阵乘加指令的片段形状建立统一的数据规整化和计算映射机制。
27、有鉴于此,本发明提供一种面向稀疏矩阵的规整化行块重排及矩阵乘加计算方法,能够根据主导元数量和矩阵乘加指令的k维度确定规整化宽度,将非零元数量小于或等于该规整化宽度的矩阵行重排为适合warp级矩阵乘加指令执行的数据布局,从而提高此类稀疏矩阵spmv运算对矩阵乘加单元的利用效率。
技术实现思路
1、本发明的目的在于提供一种面向稀疏矩阵的规整化行块重排及矩阵乘加计算方法,解决的问题:如何使非零元数量不定长的稀疏矩阵向量乘计算适配gpu warp级矩阵乘加指令的固定输入片段形状,以提高矩阵乘加硬件单元在spmv计算中的利用率;具体方案如下:
2、一种面向稀疏矩阵的规整化行块重排方法,包括:输入待计算的稀疏矩阵和输入向量;统计所述稀疏矩阵中各矩阵行的非零元数量,得到行非零元数量分布;根据所述行非零元数量分布确定主导元,并根据目标warp级矩阵乘加指令确定矩阵乘加指令参数;所述主导元用于表示多数矩阵行的非零元数量;所述矩阵乘加指令参数包括片段高度和片段宽度;根据所述主导元和所述片段宽度,确定规整化宽度;将非零元数量小于等于所述规整化宽度的矩阵行确定为可规整行,并建立所述可规整行和原始行之间的映射关系;所述原始行是指可规整行在所述稀疏矩阵中的行;根据片段高度,对所述可规整行进行分组,得到规整化行块;所述规整化行块为定长数据块;分别对多组规整化行块进行数据处理,生成规整化后的数值数组和列索引数组;沿列方向分别对多组规整化行块进行划分,得到多个规整化列块。
3、进一步的,所述稀疏矩阵采用csr格式表示,所述csr格式包括行指针数组;所述第i行的非零元数量为:;其中,为第i行的非零元数量;和分别为所述行指针数组中的第i个元素和第i+1个元素。
4、进一步的,所述规整化宽度为大于等于所述主导元且能被所述片段宽度整除的最小整数。
5、进一步的,所述根据片段高度,对所述可规整行进行分组,得到规整化行块,包括:将所述可规整行按照每片段高度行为一组进行分组,每组形成一个所述规整化行块;若最后一组中的可规整行数量不足片段高度行,则补充虚拟行,使该组具有片段高度行;所述虚拟行是指不与所述稀疏矩阵中的任何真实行相对应的行;所述虚拟行的数据按零处理;为每个所述规整化行块中的每一行预留规整化宽度个数据槽位;若所述可规整行的非零元数量小于规整化宽度,则在该可规整行剩余的数据槽位中填充零值,使每个所述规整化行块构成尺寸为片段高度×规整化宽度的定长数据块。
6、进一步的,所述数值数组中各所述数据槽位的存储位置满足:;其中,pos表示当前数据槽位在数值数组中的存储位置;g表示当前规整化行块的编号;m为片段高度;w为规整化宽度;表示该槽位所属的列块编号;k表示片段宽度;r表示当前行在所述规整化行块中的行内编号;q表示当前数据槽位在该行中的序号;q mod k表示当前数据槽位在所属列块中的列内位置。
7、本发明还提供一种面向稀疏矩阵的矩阵乘加计算方法,适用于上述任一项所述的面向稀疏矩阵的规整化行块重排方法得到的规整化列块,包括:获取规整化后的稀疏矩阵的规整化数据;所述规整化数据包括映射关系、数值数组和列索引数组;针对所述规整化行块中的每个规整化列块,根据所述规整化数据和输入向量,构造目标矩阵乘加指令的输入操作数片段;所述输入操作数片段包括a操作数片段和b操作数片段;基于所述输入操作数片段,对每个所述规整化列块执行一次warp级矩阵乘加运算;将各次所述warp级矩阵乘加运算得到的结果按照行方向对应关系进行累加,得到所述规整化行块对应的输出片段;从所述输出片段中提取有效结果;所述有效结果对应于所述规整化行块中的矩阵行与所述输入向量的点积结果;根据所述映射关系,将所述有效结果写回输出向量的对应位置。
8、进一步的,所述构造目标矩阵乘加指令的输入操作数片段,包括:执行所述warp级矩阵乘加运算的warp内的线程按照所述目标矩阵乘加指令的线程-寄存器布局,从所述数值数组中读取所述规整化列块对应的非零元数值和补零值;根据读取到的所述非零元数值和补零值,构造所述a操作数片段;所述warp内的线程根据所述列索引数组中的列索引,从所述输入向量中读取对应位置的向量元素;根据读取到的所述向量元素,按照所述目标矩阵乘加指令的要求,构造所述b操作数片段。
9、进一步的,所述从所述输出片段中提取有效结果,包括:根据所述目标矩阵乘加指令的输出布局,确定所述输出片段中与各矩阵行的点积结果对应的预定位置;从所述预定位置提取所述有效结果;其中,所述输出片段按照硬件规定的线程-寄存器布局,分散存储于执行所述warp级矩阵乘加运算的warp内的多个线程的寄存器中。
10、进一步的,所述规整化行块中的行包括真实矩阵行和虚拟行;所述真实矩阵行是指与所述稀疏矩阵中的原始行相对应的行;所述虚拟行是指所述规整化行块中不与任何所述原始行相对应的行;对于所述虚拟行不执行写回或所述虚拟行的写回结果被忽略。
11、进一步的,还包括:对于所述稀疏矩阵中未被组织为所述规整化行块的非可规整行,通过补充计算方式计算所述非可规整行的稀疏矩阵向量乘结果;将所述非可规整行的稀疏矩阵向量乘结果写回所述输出向量的对应位置;其中,所述规整化行块对应的有效结果与所述非可规整行的稀疏矩阵向量乘结果共同构成所述输出向量。
12、本发明具有如下优点和有益效果:
13、(1)本发明提高了spmv对warp级矩阵乘加指令的利用率。传统csrspmv主要通过逐行遍历、标量乘加和行内累加完成计算,难以直接使用gpu中的mma/wmma指令。本发明将每m行可规整行组成m×n定长行块,并进一步划分为n/k个m×k列块,使每个列块能够作为mma指令的输入片段参与计算,从而将原本的行内点积计算转换为warp 级矩阵乘加计算,提高矩阵乘加单元在spmv运算中的利用率。
14、(2)本发明降低了补零开销并提高了数据块与mma指令的匹配度。现有ellpack、sell-c-σ等格式通常根据全局最大行长或局部最大行长进行补齐,补齐宽度不一定适配mma指令。本发明根据主导元数量和mma指令的k维度确定规整化宽度n,使n同时满足大于或等于主导元、且能够被k整除两个条件。因此,规整后的m×n行块既能够覆盖主要矩阵行,又能够自然划分为m×k列块,减少不必要补零并提升后续mma执行的适配性。
15、(3)本发明提高计算流程的规整性,减少运行时分支判断。传统csr spmv在计算阶段需要根据每一行的实际非零元数量执行不同长度的循环,而本发明在数据准备阶段已经将可规整行补齐为固定宽度n。这样,在kernel执行阶段,一个warp可以按照固定流程处理一个m×n行块,并执行固定次数的mma运算。补零位置的data为0,colindex为合法索引,因此不需要额外分支判断即可保证结果正确,从而提高warp内执行一致性。
16、(4)本发明提高了对计算流体力学主导元稀疏矩阵的适配性。计算流体力学等场景中的稀疏矩阵通常具有明显主导元结构,即多数行的非零元数量集中在某一固定值附近。本发明利用该结构特征,仅对非零元数量小于或等于规整化宽度n的可规整行进行专门重排和mma加速,而对超过n的非可规整行可采用传统spmv或其他补充方法处理。因此,本发明既能针对占主要比例的主导元行提升执行效率,又能保持对完整稀疏矩阵计算结果的兼容性。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com