陳海燕，劉 勝，吳健虢

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

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

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

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

表1 Gather/Scatter的表示

1 GSVM總體結(jié)構(gòu)設(shè)計(jì)

1.1 寬SIMD 架構(gòu)DSP總體結(jié)構(gòu)

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

圖1 V-DSP總體結(jié)構(gòu)示意Fig.1 Architecture of V-DSP

1.2 GSVM訪存指令設(shè)計(jì)

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

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

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

1.3 GSVM總體結(jié)構(gòu)

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

圖2 GSVM的總體結(jié)構(gòu)示意Fig.2 Overall structure of GSVM

1.4 向量存儲體結(jié)構(gòu)

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

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

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

2 GSVM訪存流水線設(shè)計(jì)

2.1 向量地址計(jì)算單元

圖3 VAGU結(jié)構(gòu)示意Fig.3 Structure of VAGU

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

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

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

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

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

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

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

圖5 沖突判斷與緩沖器陣列結(jié)構(gòu)Fig.5 Structure of conflict judgement and buffer array

2.3 數(shù)據(jù)對齊與同步

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

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

3 面積與性能評估

3.1 邏輯綜合結(jié)果分析

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

3.2 性能評估與分析

3.2.1 實(shí)驗(yàn)環(huán)境

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

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

圖6 數(shù)據(jù)重整理對齊與同步結(jié)構(gòu)Fig.6 Structure of data alignment and synchronization

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

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

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

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

數(shù)據(jù)矩陣 列索引矩陣

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

Fig.7 Sparse matrix compressed by rows

數(shù)據(jù)矩陣 列索引矩陣 行計(jì)數(shù)矩陣

1～4行 5～8行

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

3.2.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

4 結(jié)論

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