面向稀疏矩陣向量乘的DMA 設(shè)計(jì)與驗(yàn)證?

曹亞松 劉 勝

（國防科技大學(xué)計(jì)算機(jī)學(xué)院 長沙 410073）

1 引言

稀疏矩陣向量乘法（Sparse Matrix-Vector Multiplication，SpMV）廣泛應(yīng)用于科學(xué)研究和工程實(shí)踐中（如圖像處理、氣象分析等），是迭代法求解大型線性方程組的關(guān)鍵算法［1～2］。在求解大型線性方程組的過程中，SpMV往往運(yùn)行很多次，并且計(jì)算訪存比較低。因此，提高SpMV 的計(jì)算速率將加快大型線性方程組的求解速度。

目前提高系統(tǒng)SpMV 計(jì)算性能的方法主要有兩方面。

一方面，采用先進(jìn)工藝和體系結(jié)構(gòu)提高處理器的運(yùn)算速度［3］，如采用CPU+GPU 的異構(gòu)并行計(jì)算體系［4～6］，采用FPGA 作為加速器輔助計(jì)算等［7］。這方面研究較多，也相對成熟。但是，工藝尺寸的更新逐漸變緩，處理器速度的提升也隨之放緩。

另一方面，通過減少存儲空間消耗來提高訪存效率。SpMV 計(jì)算中需要不規(guī)則訪問數(shù)據(jù)，嚴(yán)重消耗系統(tǒng)資源，降低計(jì)算性能。所以，提高存儲體訪問效率能顯著的提高計(jì)算性能。通常只存儲稀疏矩陣中的非零元素用于計(jì)算［8］。目前有多種稀疏矩陣存儲格式，如：壓縮稀疏行（CSR）、Diagonal（DIA）、ELLPACK（ELL）、HMEC（Hybrid Multiple ELL and CSR）［9］等格式。其中，CSR 是應(yīng)用最多的通用存儲格式，靈活性較高，操作容易［10～11］。

SpMV的計(jì)算過程中會引入大量的離散間接尋址操作，使得大量的系統(tǒng)資源消耗在對存儲器的訪問上［12］。若能在SpMV 的計(jì)算過程中，使用特定的硬件結(jié)構(gòu)對矩陣數(shù)據(jù)進(jìn)行準(zhǔn)確、高效的讀取，將顯著提升系統(tǒng)對SpMV的計(jì)算速度。

高性能共軛梯度（High Performance Conjugate Gradient，HPCG）算法是X-DSP 項(xiàng)目實(shí)現(xiàn)的重要算法之一。提高HPCG 算法計(jì)算性能關(guān)鍵是加快Sp-MV計(jì)算速度［13］。

本文針對SpMV 計(jì)算中需要不規(guī)則訪問大量數(shù)據(jù)的特點(diǎn)，設(shè)計(jì)了專用數(shù)據(jù)通道APip（Application Pipe），支持離散間接尋址操作，能夠高效地為SpMV計(jì)算提供所需的數(shù)據(jù)。

2 DMA結(jié)構(gòu)和功能

DMA 結(jié)構(gòu)如圖1 所示。原DMA 有通用通道、讀專用通道、寫專用通道等結(jié)構(gòu)。在此基礎(chǔ)上，新增一條APip 專用通道（圖中灰色部分），用于為Sp-MV計(jì)算提供所需的數(shù)據(jù)。

圖1 DMA結(jié)構(gòu)示意圖

通用通道處理DSP核發(fā)起的數(shù)據(jù)傳輸請求，可以對核內(nèi)存儲體進(jìn)行讀寫，也可通過總線對核外存儲資源進(jìn)行讀寫操作。

新增的APip 通道是面向SpMV 計(jì)算的專用數(shù)據(jù)通道，可以高效地實(shí)現(xiàn)不規(guī)則訪存過程，將數(shù)據(jù)從核外搬移到核內(nèi)特定存儲體，供計(jì)算單元使用。

寫專用通道處理從核外存儲體返回的讀數(shù)據(jù)，核外未知設(shè)備發(fā)起的對核內(nèi)存儲資源的寫操作。

讀專用通道處核外設(shè)備對核內(nèi)存儲資源的讀操作。

標(biāo)量處理單元（Scalar Processing Unit，SPU）用于配置DMA傳輸參數(shù)、控制寄存器。

3 APip通道設(shè)計(jì)

3.1 設(shè)計(jì)原理

SpMV 計(jì)算的方程可以表示為y=Ax，其中A 為稀疏矩陣，x是已知密集向量，y是A與x的向量積［14］。

稀疏矩陣中有大量的零元素，為節(jié)省存儲空間，提高訪存效率，通常只存儲用于計(jì)算的非零元素。CSR 是比較標(biāo)準(zhǔn)的壓縮存儲格式，靈活性高，訪問方便。本文用CSR格式存儲稀疏矩陣。

CSR 存儲格式需要三行（數(shù)值、列號、行偏移）來表示稀疏矩陣［15～16］。

圖2 稀疏矩陣A

圖3 CSR存儲格式

如圖2、圖3 所示，分別是稀疏矩陣A 及其CSR格式的示意圖。CSR存儲格式中：

第一行是數(shù)值，保存矩陣A 從首行到尾行所有非零元素的值；

第二行是列號，保存矩陣A 從首行到尾行所有非零元素的列號；

第三行是行偏移，表示矩陣A 每行的首個(gè)非零元素在數(shù)值行中的索引，最后一個(gè)數(shù)是矩陣中非零元素的總個(gè)數(shù)。

CSR存儲格式的SpMV計(jì)算過程可以用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 中元素的個(gè)數(shù)，Row_ptr［i+1］- Row_ptr［i］的差值為矩陣A 中第i行的非零元素個(gè)數(shù)。從計(jì)算過程可以看出，對于稀疏矩陣數(shù)據(jù)的訪問是連續(xù)的，而對于x向量中的數(shù)據(jù)的獲取需要不規(guī)則的訪存操作，降低了訪存效率。

Gather 訪存方式用于不規(guī)則讀取存儲體中的數(shù)據(jù)，采用基址和索引的方式實(shí)現(xiàn)。首先獲取待運(yùn)算的稀疏矩陣元素在CSR 格式中的列號，作為索引，然后對索引擴(kuò)展并與源數(shù)據(jù)基址相加，生成實(shí)際的源數(shù)據(jù)地址，再發(fā)出讀數(shù)據(jù)請求，從存儲體獲得特定地址的x向量的數(shù)據(jù)。

基于上述訪存原理，本文在X-DSP 項(xiàng)目原DMA 中設(shè)計(jì)添加了一條專用通道APip 來滿足Sp-MV計(jì)算中不規(guī)則訪存數(shù)據(jù)的需求。

3.2 設(shè)計(jì)方案

如圖4所示，在DSP核原DMA的基礎(chǔ)上增加的一種數(shù)據(jù)傳輸模式，稱為SuperGather 數(shù)據(jù)傳輸模式（SuperGather Data Transmission Mode，SGDTM）。該模式數(shù)據(jù)傳輸?shù)男袨槭牵簭膮?shù)RAM 中獲得基址，再從核外存儲體取回源地址的索引，然后利用基址和索引生成實(shí)際的讀地址，之后再發(fā)送讀寫請求將源端數(shù)據(jù)搬移到目的端。其特點(diǎn)如下：

圖4 新增SpMV數(shù)據(jù)傳輸模式示意圖

1）數(shù)據(jù)的源地址（Src_Addr）沒有規(guī)律，不能通過DMA 原有方式產(chǎn)生，而須通過源基址和源地址索引生成；

2）目的地址有規(guī)律，可以通過配置DMA 目的起始地址以及偏移而生成；

3）每個(gè)Src_Addr 對應(yīng)一個(gè)字寬（64 bits）的數(shù)據(jù)；

4）源地址索引和源數(shù)據(jù)均在核外存儲，需將它們搬移至核內(nèi)存儲。

從DMA 的角度來看，它需要的操作行為與通用通道相比：

1）增加了“一讀”，而且“第一次讀”的數(shù)據(jù)須返回至物理通道；

2）數(shù)據(jù)的源地址不能直接生成，且需要生成獲取源地址索引的請求。

在原有DMA 設(shè)計(jì)上，需要修改和新增的地方有：

1）DMA 參數(shù)和配置寄存器的修改：（1）在傳輸模式控制字里面增加一位，表示DMA 要進(jìn)行SuperGather 數(shù)據(jù)傳輸模式；（2）在邏輯通道優(yōu)先級配置寄存器增加一位，指示讀出的參數(shù)進(jìn)入APip 物理通道；（3）增加一個(gè)配置寄存器，用來指示SGDTM傳輸?shù)脑椿贰?/p>

2）DMA 啟動方面：只有特定邏輯通道才能進(jìn)行SuperGather 數(shù)據(jù)傳輸模式，且APip 通道具有最高優(yōu)先級。

3）APip 內(nèi)部存儲體設(shè)計(jì)：源地址和源數(shù)據(jù)在核外存儲，需要搬移到核內(nèi)。因此，APip 內(nèi)部需要用來存源地址的存儲體。源地址返回存在亂序的問題，為了保證能較高效地正確傳輸，對存儲源地址的存儲體控制需做處理，可以采用查找表機(jī)制。

4）APip 的控制邏輯設(shè)計(jì)：主要通過狀態(tài)機(jī)來實(shí)現(xiàn)（為方便描述，分為狀態(tài)機(jī)1和狀態(tài)機(jī)2）。

圖5 狀態(tài)機(jī)1

狀態(tài)機(jī)1 如圖5 所示，它主要用于控制DMA 的啟動，讀源地址索引請求的發(fā)出。APip 通道啟動后，根據(jù)配置的傳輸參數(shù)，向核外存儲體發(fā)送讀取源地址索引的請求，并等待索引讀取完成。

圖6 狀態(tài)機(jī)2

狀態(tài)機(jī)2 如圖6 所示，用來控制搬移數(shù)據(jù)請求的發(fā)出，計(jì)數(shù)以及判斷傳輸完成等。由狀態(tài)機(jī)1 獲得的源地址索引與源數(shù)據(jù)基址共同產(chǎn)生實(shí)際的源數(shù)據(jù)地址。APip 通道再向核外存儲體發(fā)送讀源數(shù)據(jù)的請求并計(jì)數(shù)，直到所有數(shù)據(jù)搬移完成。

4 模塊級驗(yàn)證

APip 是DMA 的一個(gè)專用數(shù)據(jù)通道，與DMA 內(nèi)部其他部件密切配合才可以完成SGDTM 數(shù)據(jù)傳輸。因此，將DMA 作為待測設(shè)計(jì)，通過配置APip通道相關(guān)的參數(shù)，啟動SGDTM 數(shù)據(jù)傳輸方式。通過分析判斷從源端到目的端搬移的數(shù)據(jù)是否正確，從而判斷APip通道功能是否滿足預(yù)期要求。

APip模塊級驗(yàn)證平臺如圖7所示。

圖7 驗(yàn)證平臺結(jié)構(gòu)圖

驗(yàn)證平臺分為五個(gè)部分，分別是標(biāo)量處理單元模型（SPU model）、待測設(shè)計(jì)（DMA）、核內(nèi)存儲模型（Memory_I）、核外存儲模型（Memory_O）、結(jié)果比對（Compare&Report）模塊。

標(biāo)量處理單元模型（SPU model）作為激勵(lì)源，用于配置DMA 參數(shù)RAM 以及對DMA 內(nèi)部控制寄存器的讀寫訪問，啟動APip通道等。

待測設(shè)計(jì)（DMA）與各模塊通過接口連接，進(jìn)行通信，實(shí)現(xiàn)數(shù)據(jù)搬移功能。通過SPU 配置APip通道的相關(guān)傳輸參數(shù)以及控制寄存器可以實(shí)現(xiàn)SGDTM 傳輸方式。APip的數(shù)據(jù)傳輸方向是從核外到核內(nèi)。

外圍部件模型（Memory_I、Memory_O）模擬存儲部件的行為，與DMA 進(jìn)行通信并存儲數(shù)據(jù)。其中Memory_I 是核內(nèi)存儲模型，Memory_O 是核外存儲模型。

數(shù)據(jù)比較及報(bào)告模塊（Compare & Report）對DMA 搬移數(shù)據(jù)等操作的正確性進(jìn)行判斷，并輸出判斷結(jié)果。該模塊通過層次化調(diào)用（圖中虛線表示）獲得APip 的傳輸參數(shù)，并根據(jù)其中源端參數(shù)初始化核外存儲模型（Memory_O）中的索引空間。當(dāng)DMA 搬移數(shù)據(jù)結(jié)束后，該模塊根據(jù)傳輸參數(shù)，通過層次化調(diào)用的方式，判斷源端和目的端相關(guān)地址的數(shù)據(jù)是否相同；若不同，則在終端輸出錯(cuò)誤信息，并暫停仿真。

整個(gè)驗(yàn)證平臺運(yùn)行時(shí)，各部件進(jìn)行初始化。SPU_model 產(chǎn)生激勵(lì)，通過內(nèi)部總線配置DMA 中某個(gè)邏輯通道的傳輸參數(shù)，然后配置相關(guān)寄存器設(shè)置該邏輯通道進(jìn)行SuperGather 傳輸模式，并啟動該通道。之后，傳輸參數(shù)會從參數(shù)RAM 中被取入到APip 通道中，同時(shí)Compare&Report通過層次化調(diào)用獲得當(dāng)前的傳輸參數(shù)，并初始化Memory_O 中待訪問的源地址索引數(shù)據(jù)。APip 搬移數(shù)據(jù)完成后，產(chǎn)生傳輸完成信號。而后，Compare&Report按照之前獲得的傳輸參數(shù)，比較源端和目的端的相應(yīng)地址的數(shù)據(jù)是否相同，若不同則在終端輸出源端、目的端的地址和數(shù)據(jù)以及傳輸參數(shù)等信息并暫停仿真。

使用Cadence 公司的NC-Verilog 軟件運(yùn)行驗(yàn)證平臺。仿真過程截圖如圖8、圖9 所示。驗(yàn)證結(jié)果表明，APip 通道可以準(zhǔn)確的按照配置的傳輸參數(shù)進(jìn)行SGDTM數(shù)據(jù)傳輸。

圖8 終端打印的仿真過程截圖

圖9 SG數(shù)據(jù)傳輸波形圖截圖

5 綜合結(jié)果

在某廠家7nm 工藝條件下，時(shí)鐘周期設(shè)置為0.3 ns。采用Synopsys 公司的Design Compiler 工具綜合結(jié)果如表1所示。

表1 APip模塊綜合結(jié)果

由DC 綜合結(jié)果可知，該模塊的時(shí)序、面積、功耗均滿足項(xiàng)目需求。

6 結(jié)語

基于X-DSP 項(xiàng)目中的HPCG 算法的SpMV 計(jì)算所需的不規(guī)則訪問數(shù)據(jù)的需求，本文設(shè)計(jì)并驗(yàn)證了一種面向稀疏矩陣向量乘法的DMA 專用通道。文中首先介紹目前提高SpMV 計(jì)算性能的方法，并提出了在DMA 構(gòu)建一個(gè)專用的數(shù)據(jù)通道（APip）來實(shí)現(xiàn)不規(guī)則訪問數(shù)據(jù)的思路；接著詳細(xì)介紹了APip 專用通道的設(shè)計(jì)原理和設(shè)計(jì)方案；最后對設(shè)計(jì)代碼進(jìn)行了驗(yàn)證和綜合分析。驗(yàn)證和綜合結(jié)果表明預(yù)期功能均已實(shí)現(xiàn)，并且滿足X-DSP 項(xiàng)目對時(shí)序、面積以及功耗的要求。