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

曹亚松 刘 胜

（国防科技大学计算机学院 长沙 410073）

1 引言

稀疏矩阵向量乘法（Sparse Matrix-Vector Multiplication，SpMV）广泛应用于科学研究和工程实践中（如图像处理、气象分析等），是迭代法求解大型线性方程组的关键算法［1～2］。在求解大型线性方程组的过程中，SpMV往往运行很多次，并且计算访存比较低。因此，提高SpMV 的计算速率将加快大型线性方程组的求解速度。

目前提高系统SpMV 计算性能的方法主要有两方面。

一方面，采用先进工艺和体系结构提高处理器的运算速度［3］，如采用CPU+GPU 的异构并行计算体系［4～6］，采用FPGA 作为加速器辅助计算等［7］。这方面研究较多，也相对成熟。但是，工艺尺寸的更新逐渐变缓，处理器速度的提升也随之放缓。

另一方面，通过减少存储空间消耗来提高访存效率。SpMV 计算中需要不规则访问数据，严重消耗系统资源，降低计算性能。所以，提高存储体访问效率能显著的提高计算性能。通常只存储稀疏矩阵中的非零元素用于计算［8］。目前有多种稀疏矩阵存储格式，如：压缩稀疏行（CSR）、Diagonal（DIA）、ELLPACK（ELL）、HMEC（Hybrid Multiple ELL and CSR）［9］等格式。其中，CSR 是应用最多的通用存储格式，灵活性较高，操作容易［10～11］。

SpMV的计算过程中会引入大量的离散间接寻址操作，使得大量的系统资源消耗在对存储器的访问上［12］。若能在SpMV 的计算过程中，使用特定的硬件结构对矩阵数据进行准确、高效的读取，将显著提升系统对SpMV的计算速度。

高性能共轭梯度（High Performance Conjugate Gradient，HPCG）算法是X-DSP 项目实现的重要算法之一。提高HPCG 算法计算性能关键是加快Sp-MV计算速度［13］。

本文针对SpMV 计算中需要不规则访问大量数据的特点，设计了专用数据通道APip（Application Pipe），支持离散间接寻址操作，能够高效地为SpMV计算提供所需的数据。

2 DMA结构和功能

DMA 结构如图1 所示。原DMA 有通用通道、读专用通道、写专用通道等结构。在此基础上，新增一条APip 专用通道（图中灰色部分），用于为Sp-MV计算提供所需的数据。

图1 DMA结构示意图

通用通道处理DSP核发起的数据传输请求，可以对核内存储体进行读写，也可通过总线对核外存储资源进行读写操作。

新增的APip 通道是面向SpMV 计算的专用数据通道，可以高效地实现不规则访存过程，将数据从核外搬移到核内特定存储体，供计算单元使用。

写专用通道处理从核外存储体返回的读数据，核外未知设备发起的对核内存储资源的写操作。

读专用通道处核外设备对核内存储资源的读操作。

标量处理单元（Scalar Processing Unit，SPU）用于配置DMA传输参数、控制寄存器。

3 APip通道设计

3.1 设计原理

SpMV 计算的方程可以表示为y=Ax，其中A 为稀疏矩阵，x是已知密集向量，y是A与x的向量积［14］。

稀疏矩阵中有大量的零元素，为节省存储空间，提高访存效率，通常只存储用于计算的非零元素。CSR 是比较标准的压缩存储格式，灵活性高，访问方便。本文用CSR格式存储稀疏矩阵。

CSR 存储格式需要三行（数值、列号、行偏移）来表示稀疏矩阵［15～16］。

图2 稀疏矩阵A

图3 CSR存储格式

如图2、图3 所示，分别是稀疏矩阵A 及其CSR格式的示意图。CSR存储格式中：

第一行是数值，保存矩阵A 从首行到尾行所有非零元素的值；

第二行是列号，保存矩阵A 从首行到尾行所有非零元素的列号；

第三行是行偏移，表示矩阵A 每行的首个非零元素在数值行中的索引，最后一个数是矩阵中非零元素的总个数。

CSR存储格式的SpMV计算过程可以用C语言表示如下：

for（int i=0；i ＜Row_ptr_Size-1；i++）｛

for（int j=Row_ptr［i］；j＜Row_ptr［i+1］；j++）

y［i］+=Value［j］*x［Col_inx［j］］；

｝

上述代码中，Row_ptr_Size 表示Row_ptr 中元素的个数，Row_ptr［i+1］- Row_ptr［i］的差值为矩阵A 中第i行的非零元素个数。从计算过程可以看出，对于稀疏矩阵数据的访问是连续的，而对于x向量中的数据的获取需要不规则的访存操作，降低了访存效率。

Gather 访存方式用于不规则读取存储体中的数据，采用基址和索引的方式实现。首先获取待运算的稀疏矩阵元素在CSR 格式中的列号，作为索引，然后对索引扩展并与源数据基址相加，生成实际的源数据地址，再发出读数据请求，从存储体获得特定地址的x向量的数据。

基于上述访存原理，本文在X-DSP 项目原DMA 中设计添加了一条专用通道APip 来满足Sp-MV计算中不规则访存数据的需求。

3.2 设计方案

如图4所示，在DSP核原DMA的基础上增加的一种数据传输模式，称为SuperGather 数据传输模式（SuperGather Data Transmission Mode，SGDTM）。该模式数据传输的行为是：从参数RAM 中获得基址，再从核外存储体取回源地址的索引，然后利用基址和索引生成实际的读地址，之后再发送读写请求将源端数据搬移到目的端。其特点如下：

图4 新增SpMV数据传输模式示意图

1）数据的源地址（Src_Addr）没有规律，不能通过DMA 原有方式产生，而须通过源基址和源地址索引生成；

2）目的地址有规律，可以通过配置DMA 目的起始地址以及偏移而生成；

3）每个Src_Addr 对应一个字宽（64 bits）的数据；

4）源地址索引和源数据均在核外存储，需将它们搬移至核内存储。

从DMA 的角度来看，它需要的操作行为与通用通道相比：

1）增加了“一读”，而且“第一次读”的数据须返回至物理通道；

2）数据的源地址不能直接生成，且需要生成获取源地址索引的请求。

在原有DMA 设计上，需要修改和新增的地方有：

1）DMA 参数和配置寄存器的修改：（1）在传输模式控制字里面增加一位，表示DMA 要进行SuperGather 数据传输模式；（2）在逻辑通道优先级配置寄存器增加一位，指示读出的参数进入APip 物理通道；（3）增加一个配置寄存器，用来指示SGDTM传输的源基址。

2）DMA 启动方面：只有特定逻辑通道才能进行SuperGather 数据传输模式，且APip 通道具有最高优先级。

3）APip 内部存储体设计：源地址和源数据在核外存储，需要搬移到核内。因此，APip 内部需要用来存源地址的存储体。源地址返回存在乱序的问题，为了保证能较高效地正确传输，对存储源地址的存储体控制需做处理，可以采用查找表机制。

4）APip 的控制逻辑设计：主要通过状态机来实现（为方便描述，分为状态机1和状态机2）。

图5 状态机1

状态机1 如图5 所示，它主要用于控制DMA 的启动，读源地址索引请求的发出。APip 通道启动后，根据配置的传输参数，向核外存储体发送读取源地址索引的请求，并等待索引读取完成。

图6 状态机2

状态机2 如图6 所示，用来控制搬移数据请求的发出，计数以及判断传输完成等。由状态机1 获得的源地址索引与源数据基址共同产生实际的源数据地址。APip 通道再向核外存储体发送读源数据的请求并计数，直到所有数据搬移完成。

4 模块级验证

APip 是DMA 的一个专用数据通道，与DMA 内部其他部件密切配合才可以完成SGDTM 数据传输。因此，将DMA 作为待测设计，通过配置APip通道相关的参数，启动SGDTM 数据传输方式。通过分析判断从源端到目的端搬移的数据是否正确，从而判断APip通道功能是否满足预期要求。

APip模块级验证平台如图7所示。

图7 验证平台结构图

验证平台分为五个部分，分别是标量处理单元模型（SPU model）、待测设计（DMA）、核内存储模型（Memory_I）、核外存储模型（Memory_O）、结果比对（Compare&Report）模块。

标量处理单元模型（SPU model）作为激励源，用于配置DMA 参数RAM 以及对DMA 内部控制寄存器的读写访问，启动APip通道等。

待测设计（DMA）与各模块通过接口连接，进行通信，实现数据搬移功能。通过SPU 配置APip通道的相关传输参数以及控制寄存器可以实现SGDTM 传输方式。APip的数据传输方向是从核外到核内。

外围部件模型（Memory_I、Memory_O）模拟存储部件的行为，与DMA 进行通信并存储数据。其中Memory_I 是核内存储模型，Memory_O 是核外存储模型。

数据比较及报告模块（Compare & Report）对DMA 搬移数据等操作的正确性进行判断，并输出判断结果。该模块通过层次化调用（图中虚线表示）获得APip 的传输参数，并根据其中源端参数初始化核外存储模型（Memory_O）中的索引空间。当DMA 搬移数据结束后，该模块根据传输参数，通过层次化调用的方式，判断源端和目的端相关地址的数据是否相同；若不同，则在终端输出错误信息，并暂停仿真。

整个验证平台运行时，各部件进行初始化。SPU_model 产生激励，通过内部总线配置DMA 中某个逻辑通道的传输参数，然后配置相关寄存器设置该逻辑通道进行SuperGather 传输模式，并启动该通道。之后，传输参数会从参数RAM 中被取入到APip 通道中，同时Compare&Report通过层次化调用获得当前的传输参数，并初始化Memory_O 中待访问的源地址索引数据。APip 搬移数据完成后，产生传输完成信号。而后，Compare&Report按照之前获得的传输参数，比较源端和目的端的相应地址的数据是否相同，若不同则在终端输出源端、目的端的地址和数据以及传输参数等信息并暂停仿真。

使用Cadence 公司的NC-Verilog 软件运行验证平台。仿真过程截图如图8、图9 所示。验证结果表明，APip 通道可以准确的按照配置的传输参数进行SGDTM数据传输。

图8 终端打印的仿真过程截图

图9 SG数据传输波形图截图

5 综合结果

在某厂家7nm 工艺条件下，时钟周期设置为0.3 ns。采用Synopsys 公司的Design Compiler 工具综合结果如表1所示。

表1 APip模块综合结果

由DC 综合结果可知，该模块的时序、面积、功耗均满足项目需求。

6 结语

基于X-DSP 项目中的HPCG 算法的SpMV 计算所需的不规则访问数据的需求，本文设计并验证了一种面向稀疏矩阵向量乘法的DMA 专用通道。文中首先介绍目前提高SpMV 计算性能的方法，并提出了在DMA 构建一个专用的数据通道（APip）来实现不规则访问数据的思路；接着详细介绍了APip 专用通道的设计原理和设计方案；最后对设计代码进行了验证和综合分析。验证和综合结果表明预期功能均已实现，并且满足X-DSP 项目对时序、面积以及功耗的要求。