GSVM：一種支持Gather/Scatter的向量存儲器

陳海燕，劉 勝，吳健虢

(國防科技大學 計算機學院， 湖南 長沙 410073)

為充分開發(fā)微處理器的數據并行性、以較低的硬件代價和功耗實現密集型數據處理，獲得較高的峰值運算性能，單指令多數據流(Single Instruction Multiple Data,SIMD)技術成為微處理器體系結構發(fā)展的一個重要擴展。對于地址連續(xù)或等距跨步等規(guī)則應用的數據訪存模式，一般的SIMD結構處理器往往都能提供充足的訪存帶寬，得到較理想的峰值運算性能；但在處理不規(guī)則應用時，其訪存帶寬性能急劇下降，主要原因是不規(guī)則應用的訪存模式復雜、無規(guī)律，數據的空間局部性差，目前的SIMD架構微處理器不能很好支持。如何高效支持不規(guī)則應用訪存以提高通用性能成為SIMD微處理器設計中面臨的一個重要問題。

科學計算和工程應用中存在大量的不規(guī)則數據訪存，例如稀疏矩陣計算、圖像邊緣檢測和語音識別等[1-2]。有學者總結出十余類基本的并行計算模式，其中一半以上都是不規(guī)則的[3]，即這些并行計算模式中存在大量的不規(guī)則數據訪存，數據訪存模式隨機無規(guī)律，時間和空間局部性差等[4]。隨著SIMD技術的不斷發(fā)展，片上集成的按SIMD方式操作的運算單元越來越多，需要越來越寬的SIMD訪存帶寬支持，而不規(guī)則訪存潛在的訪問沖突降低了處理器的實際數據帶寬，增加了訪存延時，降低了數據訪存效率[5-6]。支持單指令多線程(Single Instruction Multiple Threads, SIMT)的向量訪存僅支持SIMD結構中每個運算單元訪問各自對應的數據地址空間，不能共享整個數據存儲器，限制了其應用范圍。通過支持SIMT方式的直接存儲器訪問(Direct Memory Access，DMA)控制器加載[7]，能將外部存儲器中不規(guī)則訪存數據通過DMA方式重新組織并加載到向量存儲器的連續(xù)地址空間中，但是這種方式需要程序員進行顯式的訪存數據組織，DMA設計需配置大量的數據緩沖器，可編程性差且DMA的硬件代價較大。

Gather/Scatter指令起源于早期的向量處理機，如Cray-2[8-9]、Fujitsu的 VP-100/200[10]和NEC的SX[11]，隨著半導體工藝的發(fā)展開始被集成到了片上。近年來，Intel也為短向量SIMD結構增加了Gather和Scatter指令操作：AVX2設計了Gather指令，Knights Corner設計了有限的Gather/Scatter指令[12]，AVX-512擁有完整的Gather/Scatter指令[13]。表1為Gather/Scatter的表示[14]，其中Scatter指的是將向量寄存器Rin中的n個數據寫入一組訪存地址Rout[L[i]]，即由整數向量L索引的n個不同的訪存地址。Gather指的是讀取n個訪存地址的數據，這些數據的地址由整數向量L定義，并將其輸出到向量寄存器Rout中。

表1 Gather/Scatter的表示

1 GSVM總體結構設計

1.1 寬SIMD 架構DSP總體結構

V-DSP是一款自主研制的面向圖像處理及稀疏矩陣運算等數據密集型應用的寬SIMD架構32位數字信號處理器(Digital Signal Processor，DSP)，主頻為1 GHz。為開發(fā)指令級和數據級并行性，V-DSP采用超長指令字和SIMD技術，支持標、向量并行處理，每拍最多可派發(fā)、執(zhí)行11條標、向量指令。其總體結構如圖1所示，主要包括取指單元、一級程序Cache(first Level Program Cache，L1P)、指令派發(fā)單元、標量處理部件(Scalar Processing Unit，SPU)、標量存儲器(Scalar Memory，SM)、向量處理部件(Vector Processing Unit，VPU)、Gather/Scatter向量存儲器(Gather/Scatter Vector Memory，GSVM)以及DMA等。其中，SPU完成指令流控制和標量數據處理，SM為其提供標量數據訪存；VPU實現向量數據運算，其內部集成了16個按SIMD方式操作的向量運算單元(Vector Processing Element, VPE)，每個VPE每拍能進行3次32位浮點乘加運算；GSVM是程序員可見的片上大容量向量存儲器，為16個VPE提供兩條并行向量訪存指令操作支持，并通過DMA實現GSVM與DSP核外的數據傳輸。

圖1 V-DSP總體結構示意Fig.1 Architecture of V-DSP

1.2 GSVM訪存指令設計

GSVM支持半字(16 bit)、單字(32 bit)和雙字(64 bit)粒度的常規(guī)向量訪存和Gather/Scatter訪存指令操作，可同時支持2條向量訪存指令和DMA讀、DMA寫4請求并行訪問，與VPU的最大數據帶寬為2×128 B/Cycle，與DMA的數據傳輸帶寬為32 B/Cycle。

常規(guī)向量訪存操作只能對地址連續(xù)或等地址跨步的規(guī)則數據進行訪問，只需提供一個訪存起始地址即可得到各個VPE的訪存地址，因而其訪存指令只需指定一組基址寄存器和地址偏移寄存器就可實現線性尋址。而Gather/Scatter訪存要支持不規(guī)則數據向量隨機訪存，即各個VPE的訪存地址是隨機、無規(guī)律的，因此GSVM設計了多組專用的向量地址寄存器文件，每組向量地址寄存器文件包括一個向量基址寄存器(Vector base Address Register，VAR)和一個向量地址偏移寄存器(Vector address Offset Register，VOR)，單個VAR和VOR又分別由16個基址寄存器和16個地址偏移寄存器組成。Gather/Scatter訪存指令譯碼后，GSVM會讀取某組向量地址寄存器文件中16個基址寄存器和16個地址偏移寄存器，由地址計算單元根據向量地址寄存器的內容并行計算出16組訪存地址，實現Gather/Scatter的向量訪存。

GSVM訪存指令分為常規(guī)的向量Load/Store訪存指令和Gather/Scatter訪存指令兩種類型，指令編碼設計統(tǒng)一采用V-DSP的32位指令編碼格式。

1.3 GSVM總體結構

GSVM的整體結構如圖2所示，由向量訪存指令譯碼、向量地址計算單元(Vector Address Generating Unit，VAGU)、向量存儲體、向量存儲控制器(Vector Memory Controller，VMC)、數據對齊與同步等功能模塊構成，以實現向量訪存流水線操作。其中，向量存儲體采用多體地址交叉組織結構，為VPE、DMA提供并行訪存帶寬；向量訪存指令譯碼模塊對派發(fā)的向量訪存指令進行譯碼，獲得向量訪存指令類型、尋址模式、訪存粒度、地址寄存器文件、目標向量寄存器等訪存信息；VAGU根據尋址模式和地址寄存器文件計算16個VPE的訪存地址并進行請求分流處理；VMC實現向量訪存和DMA讀/寫訪存沖突仲裁和緩存，如果存在訪存沖突，根據仲裁規(guī)則確定各VPE訪問向量存儲器的順序。若訪存指令為向量Store或Scatter，則將向量數據按仲裁順序寫入對應的向量存儲體地址中；若訪存指令為向量Load或Gather，則數據從向量存儲體讀出后還需經過數據對齊與同步后再返回給VPU的向量寄存器。若為DMA讀訪問，則通過向量轉換緩沖接口(Vector Transformation Buffer interface，VTB)返回給DMA。

圖2 GSVM的總體結構示意Fig.2 Overall structure of GSVM

1.4 向量存儲體結構

向量存儲體容量為512 KB，為所有VPE所共享。為了滿足16個VPE和DMA的并行向量訪存需求，向量存儲體由16個存儲塊(圖2中Bank 0～Bank 15)按雙字低位地址交叉組織，每個Bank容量為32 KB。為減少片上存儲器面積，同時提高并行訪存帶寬能力，單個Bank采用多個單端口靜態(tài)隨機存儲器(Static Random Access Memory，SRAM)組成。

由于Gather/Scatter訪存是無規(guī)律的，即任何一個VPE都可能訪問任意地址，極端情況下同拍最多可能會有16個請求訪問同一Bank。設計Bank多體結構時，需要對并行訪存帶寬能力和硬件代價進行折中考慮。

假設每個VPE的訪存地址為全隨機均勻分布，即16個VPE隨機訪問任一Bank的概率都是相同的。根據搭建的Gather/Scatter訪存分布模型和訪存沖突模型對訪存行為進行理論和量化分析[15]，得到結果：16個VPE隨機訪問16個Bank，在所有可能的訪存情況排列組合中，訪問同一Bank的請求數小于或等于4的情況已經覆蓋了96%以上的訪存情況。因此，向量存儲體的每個Bank采用4個單端口SRAM(SRAM 0～SRAM 3)按高、低位地址交叉方式組織，構成上下存儲空間，每個SRAM容量為8 KB，最多可完成4個并行訪存請求。該存儲體組織方式既支持常規(guī)向量訪存方式下的4請求并行訪問，減少了訪存指令與DMA訪問的沖突；又符合Gather/Scatter訪存模式下多個VPE訪問同一Bank時發(fā)生訪存沖突概率的情況，提高了向量訪存帶寬效率。

2 GSVM訪存流水線設計

2.1 向量地址計算單元

圖3 VAGU結構示意Fig.3 Structure of VAGU

在Gather/Scatter訪存模式下，VPU中的每個VPE的訪存地址都是無規(guī)律的，因此需要提供和VPE個數相同的向量訪存地址VAddr(Addr 0～Addr 15)。如圖3所示， VAGU首先實現向量訪存地址計算，即根據指令譯碼的相關請求信號，讀取某組VAR和VOR中16個基址寄存器(AR 0～AR 15)和16個地址偏移寄存器(OR 0～OR 15)的數據，再根據指令訪存粒度和尋址方式計算各VPE的訪存地址，若指令需要更新基址，則使用計算出的訪存地址更新基址寄存器。

由于Gather/Scatter訪存是不規(guī)則的，各個VPE的訪存地址隨機分布，VAGU在計算各VPE的訪存地址后，需要將每個VPE訪存請求相關的控制信號、數據及地址信息組合成對應的訪存請求數據包，通過訪存地址譯碼出各個VPE訪問的Bank編號，然后將各VPE訪存請求的數據包按其訪問的不同Bank進行并行分流處理，訪問同一Bank的請求包按VPE編號從小到大的優(yōu)先級順序進入該Bank的請求打包分流緩沖器。如圖4所示，VPE 0、VPE 1和VPE 5 這3個訪存請求都訪問Bank 0的數據，VAGU分別將與這3個訪存請求相關的控制信號和數據信息打包并分流到Bank 0中處理。極端情況下，16個VPE可能訪問同一Bank，因此每個Bank對應的VPE請求打包分流緩沖器深度為16。

2.2 訪存仲裁與沖突緩沖器陣列

各個Bank的訪存請求打包分流后進入訪存沖突仲裁與緩存流水站，如果有多個訪存請求訪問同一Bank的相同SRAM，則存在訪存沖突。由于每個Bank由4個單端口SRAM體組成，最多可支持4個不沖突的并行訪存請求進行讀、寫操作，為了減小沖突判斷邏輯開銷且不降低訪問性能，每次最多對4個同一Bank的訪存請求進行沖突判斷，多余的請求則緩存至該流水線的站間寄存器中，當前面的請求處理完畢后再取出剩余的訪存請求進行處理。當發(fā)生訪存沖突時，該Bank的仲裁部件對訪存請求進行仲裁，確定VPE訪存請求的訪問順序。仲裁的優(yōu)先級按照VPE編號由小到大的順序遞減；每拍訪問同一Bank中的相同SRAM的請求只有1個仲裁成功，其余仲裁失敗的VPE請求則按優(yōu)先級順序存入對應的沖突緩沖器；訪問不同SRAM的請求則可以并行執(zhí)行。

為了解決訪存沖突問題，GSVM為16個Bank設計了一個沖突緩沖器陣列來緩存各Bank仲裁失敗的訪存請求，如圖5所示，該沖突緩沖器陣列由與SIMD寬度匹配的(即16個)、深度為3的緩沖器(buffer 0～buffer 15)組成。Bank和沖突緩沖器一一對應，當拍訪問同一Bank仲裁失敗的請求按仲裁順序都被緩存進對應的buffer中，仲裁成功的訪存請求則直接訪問該Bank，下一拍再從該buffer中順序取出一個訪存請求繼續(xù)訪存操作。當同拍所有請求都處理完畢后才允許發(fā)送下一拍的請求。訪存請求不存在沖突時，每拍最多可并行處理4個訪問同一Bank的訪存請求；存在沖突時，除了仲裁成功進入后面訪存流水線的訪存請求外，最多需要緩存3個仲裁失敗的訪存請求。因此，buffer深度設計為3即可滿足需求。緩沖器陣列的設計降低了沖突仲裁和訪存控制器的復雜度，以較低的硬件開銷實現了多請求隨機訪存。

會計主體假設作為會計學中主要假設因素，同時也是政府會計制度及有待處理的關鍵問題，要想促進政府預算會計和財務會計的融合，就要從會計主體入手，促進二者協(xié)調。結合新政府會計制度得知，政府會計主體一般以各級政府部門、各級單位為主，充分展現出了政府會計主體和本級政府財政部門之間的關系。在把組織當作會計主體時，需要綜合思考各個應用預算資金單位及公共部門設定特點，促進政府預算會計和財務會計融合。此外，在進行會計主體選擇時，也可以把“基金”當作會計主體，也可以將“政府整體”作為會計主體。根據新政府會計制度要求，合理選擇。

圖4 VPE訪存請求分流Fig.4 VPE access memory requests split

圖5 沖突判斷與緩沖器陣列結構Fig.5 Structure of conflict judgement and buffer array

2.3 數據對齊與同步

由于V-DSP采用SIMD結構，指令流水線采用鎖步執(zhí)行方式，故Gather/Scatter訪存存在訪存沖突時，不僅將造成其他指令流水線停頓，該拍訪存指令操作也將延遲1拍或多拍完成，直到訪存流水線按仲裁順序完成當拍所有存在沖突的訪存請求。對Gather指令而言，訪存數據讀出后還要進行數據整理對齊與同步，才能獲得該讀指令所需的全部向量數據。如圖6所示，數據對齊與同步單元需要將當前讀出的16個數據(D 0～D 15)按照訪存粒度截取有效部分，根據輸出數據對應的VPE請求編號，將有效數據重新排列對齊，并完成同步后寫回到對應的VPE中。

存在訪存沖突時，同一條Gather指令不同時鐘周期從向量存儲器讀出的數據需要進行節(jié)拍同步，優(yōu)先讀出的數據被緩存在該讀出流水線的站間向量寄存器里，等待后面的讀數據，每讀出一個有效數據就將相應的標志位Mask置為1。當向量寄存器對應的所有Mask位都置為1時，則表示該指令16個訪存數據都全部讀出，可以將向量寄存器的數據寫回給VPU，同時準備處理下一條指令。

3 面積與性能評估

3.1 邏輯綜合結果分析

使用邏輯綜合工具，時鐘周期約束設置為0.54 ns，基于某廠家40 nm工藝庫，在相同的綜合環(huán)境和約束下分別對支持Gather/Scatter和不支持Gather/Scatter的向量存儲器進行邏輯綜合[16]。綜合結果表明，支持Gather/Scatter后，向量存儲器面積增加了22%。主要原因是：增加了向量地址寄存器文件，VAGU由原來的1套地址計算邏輯增加為16套，并增加了16套VPE請求打包分流邏輯；每個Bank分別又增加了1套仲裁和3深度的沖突緩沖器以及大量的站間向量寄存器。

3.2 性能評估與分析

3.2.1 實驗環(huán)境

稀疏矩陣向量乘(Sparse Matrix-Vector multiplication, SpMV)廣泛應用于線性代數求解和科學計算領域，是科學計算中重要的計算核心[17-18]。由于SpMV計算中訪存數據是不規(guī)則跨步的，常規(guī)的向量存儲器訪存帶寬瓶頸導致SpMV的運算性能一般都比較低。

本文基于V-DSP的RTL級全芯片驗證環(huán)境，通過SpMV部分測試集對GSVM的訪存效率和性能進行評估，比較Gather/Scatter訪存和常規(guī)向量Load/Store訪存在SpMV運算中的效率。測試時采用V-DSP指令集編寫系統(tǒng)級匯編激勵，通過模擬工具NC-Verilog進行仿真。

圖6 數據重整理對齊與同步結構Fig.6 Structure of data alignment and synchronization

實驗采用的稀疏矩陣測試集來自佛羅里達大學稀疏矩陣集合(SuiteSparse Matrix Collection)[19]，該測試集廣泛用于線性代數領域中對稀疏矩陣算法進行開發(fā)和性能評估，涵蓋了結構工程、計算流體力學，電路模擬等領域，本實驗選取其中一部分作為測試集。測試前，首先使用MATLAB對測試集的矩陣數據進行壓縮處理，然后分別使用Gather/Scatter和常規(guī)向量Load/Store兩種不同的向量訪存指令對不同的稀疏矩陣測試進行評估，對運行結果進行分析。

為發(fā)揮SIMD寬向量處理單元的優(yōu)勢，采用基于狀態(tài)壓縮表(State transition Compress Table, SCT)格式的稀疏矩陣壓縮算法，去除稀疏矩陣中多余的0元素以降低存儲開銷，并將壓縮后的矩陣跨步合并為新的矩陣[20]。通過MATLAB對稀疏矩陣測試集的數據進行壓縮，具體算法如下。

設VPU的SIMD寬度為L，每次取矩陣的L行進行壓縮，去除矩陣每行多余的0元素。為了避免條件操作帶來的性能開銷，壓縮后的矩陣長度(即矩陣的列數)與其中具有最多非0元素的矩陣行壓縮后的長度一致，若某行非0元素較少，壓縮后則需要在該行末尾補0，使得該行長度與對應的數據壓縮矩陣長度相同。采用列索引矩陣記錄壓縮后矩陣中的非0元素在原矩陣中的列索引，行計數矩陣記錄該矩陣的L行壓縮后的長度。對于較大規(guī)模的稀疏矩陣，按SIMD寬度對矩陣按行分塊進行壓縮并補0，然后將壓縮后得到的數據矩陣塊、列索引矩陣塊分別進行拼接，得到矩陣行數與SIMD寬度相同的壓縮矩陣，并記錄拼接的每個壓縮數據矩陣塊的長度。

如圖7所示的一個8×8的稀疏矩陣，假設VPU的SIMD寬度L=4，則該矩陣可按SIMD寬度分為上下兩個子塊，每個子塊壓縮后的數據矩陣長度與其中具有最多非0元素的矩陣行壓縮后的長度相同，即圖7中兩個數據矩陣子塊對應的壓縮后矩陣長度分別為原矩陣的第3行和第7行壓縮后的元素個數，長度不夠的行需在末尾補0；列索引矩陣記錄壓縮后數據矩陣中的非0元素在原矩陣中的列索引，在列索引矩陣中，數據矩陣補的0元素對應的列索引用x表示。通過列索引訪問向量數據為不規(guī)則訪存，為了避免壓縮后數據矩陣補0帶來的訪存沖突，數據矩陣中補0的位置，即在列索引矩陣中索引值x的位置需填補與其他非0元素列索引值不同的值，從而減少訪存沖突的發(fā)生。圖8所示為壓縮后的矩陣塊拼接得到的數據矩陣、列索引矩陣和行計數矩陣。行計數矩陣記錄壓縮后的各個矩陣塊的長度，1～4行壓縮后矩陣塊的長度為3，5～8行壓縮后矩陣塊的長度為2。壓縮后的矩陣分別由一維數組存儲，通過DMA傳輸將壓縮后的矩陣搬運至向量存儲器。實驗中GSVM的SIMD寬度為16，每個VPE分別對壓縮矩陣的一行進行乘加運算，各行之間的乘加運算是并行的，行計數值用來做判斷條件，判斷該行數據的運算是否結束。

數據矩陣 列索引矩陣

圖7 稀疏矩陣按行壓縮示意

Fig.7 Sparse matrix compressed by rows

數據矩陣 列索引矩陣 行計數矩陣

1～4行 5～8行

圖8 稀疏矩陣行拼接示意
Fig.8 Sparse matrix splicing by rows

3.2.3 實驗結果分析

稀疏矩陣的非0元素分布是無規(guī)律的，矩陣的列索引也是無規(guī)律的，通過壓縮矩陣元素的列索引訪問數據屬于不規(guī)則訪存。Gather/Scatter訪存指令根據矩陣列索引讀取離散的向量數據，只需要一條Gather指令即可獲取VPU所需數據，其向量訪存帶寬利用率高，因此程序執(zhí)行時間較短。常規(guī)的向量訪存指令不支持不規(guī)則數據訪存，只能串行訪問存儲的數據，因此需要通過標量訪存指令根據元素列索引讀取數據，然后通過標向量轉換寄存器將標量指令讀取的數據轉換為向量數據提供給VPU使用，因而常規(guī)向量訪存指令在訪問不規(guī)則數據時需要更多的時間。

圖9所示為基于V-DSP的RTL級全芯片運行環(huán)境，使用Gather/Scatter訪存指令運行部分稀疏矩陣測試程序相比常規(guī)向量Load/Store訪存指令運行獲得的加速比，可見這些測試程序的性能都至少提高了1倍以上。當無訪存沖突發(fā)生時，GSVM訪存效率最高，如測試集Meszaros/gams30a和Oberwolfach/t2dal_e，此時均獲得了超過8的性能加速比[16]。實驗結果表明，Gather/Scatter訪存能顯著提升SpMV的運算效率，數據訪存沖突越少則使用Gather/Scatter訪存獲得的性能越高。

圖9 Gather/Scatter訪存加速比Fig.9 Access memory speedup of Gather/Scatter

4 結論

針對一般的寬SIMD架構DSP面向不規(guī)則數據訪存應用的性能瓶頸，設計了支持Gather/Scatter的向量存儲器GSVM整體架構，通過多存儲體組織的方式來提供并行訪存帶寬、減少訪存沖突，通過沖突緩沖器陣列來緩存仲裁失敗的訪問請求，有效解決不規(guī)則訪存沖突的問題，實現了不規(guī)則向量訪存全流水設計，提高了訪存效率。通過實驗對有無Gather/Scatter訪存指令情況下稀疏矩陣乘的部分測試集進行性能測試，結果表明GSVM對不規(guī)則數據訪存具有顯著的加速作用，能有效提高SIMD架構DSP的性能。