曹亞松 劉 勝

（國防科技大學計算機學院 長沙 410073）

1 引言

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

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

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

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

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

高性能共軛梯度（High Performance Conjugate Gradient，HPCG）算法是X-DSP 項目實現的重要算法之一。提高HPCG 算法計算性能關鍵是加快Sp-MV計算速度［13］。

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

2 DMA結構和功能

DMA 結構如圖1 所示。原DMA 有通用通道、讀專用通道、寫專用通道等結構。在此基礎上，新增一條APip 專用通道（圖中灰色部分），用于為Sp-MV計算提供所需的數據。

圖1 DMA結構示意圖

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

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

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

讀專用通道處核外設備對核內存儲資源的讀操作。

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

3 APip通道設計

3.1 設計原理

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

稀疏矩陣中有大量的零元素，為節(jié)省存儲空間，提高訪存效率，通常只存儲用于計算的非零元素。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ù)的，而對于x向量中的數據的獲取需要不規(guī)則的訪存操作，降低了訪存效率。

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

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

3.2 設計方案

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

圖4 新增SpMV數據傳輸模式示意圖

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

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

3）每個Src_Addr 對應一個字寬（64 bits）的數據；

4）源地址索引和源數據均在核外存儲，需將它們搬移至核內存儲。

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

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

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

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

1）DMA 參數和配置寄存器的修改：（1）在傳輸模式控制字里面增加一位，表示DMA 要進行SuperGather 數據傳輸模式；（2）在邏輯通道優(yōu)先級配置寄存器增加一位，指示讀出的參數進入APip 物理通道；（3）增加一個配置寄存器，用來指示SGDTM傳輸的源基址。

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

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

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

圖5 狀態(tài)機1

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

圖6 狀態(tài)機2

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

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