朱明達,薛濟擎,艾純瑤

(中國石油大學(xué)(北京) 信息科學(xué)與工程學(xué)院,北京 102249)

0 引 言

隨著人工智能技術(shù)的快速發(fā)展,算力向前端及邊緣端遷移的趨勢愈加明顯[1]。由于功耗、體積方面的限制,ARM(Advanced RISC Machine)、FPGA(Field Programmable Gate Array)成為了邊緣端算力實現(xiàn)的重要載體。稀疏矩陣向量乘(Sparse Matrix-Vector Multiplication,SpMV)常用于低延遲和高吞吐量的數(shù)據(jù)分析工作,除了在許多科學(xué)計算應(yīng)用中占據(jù)主導(dǎo)地位,在邊緣數(shù)據(jù)分析處理中也越發(fā)重要。然而,SpMV的性能受到可用存儲帶寬的限制,ARM的串行計算特點只能維持峰值計算性能的一小部分,這使得SpMV在邊緣端有效實現(xiàn)極具挑戰(zhàn)性。

近年來,許多學(xué)者開展了對SpMV運算加速的研究。文獻[2]提出了一種基于高帶寬內(nèi)存的數(shù)據(jù)流SpMV加速器,克服了大矩陣存儲的問題;還提出了兩步流處理方法,但導(dǎo)致了FPGA資源開銷非常高。文獻[3-4]提出的FPGA加速方法通用性相對不足。文獻[5-8]提出的方法基于CPU或GPU來實現(xiàn)[9-11],功耗較高,不利于在邊緣端實現(xiàn)。在實現(xiàn)平臺上,對比CPU及GPU,FPGA可以為不容易并行化的結(jié)構(gòu)提供位級并行計算[12],具有高并行性、強控制能力和可重構(gòu)性,逐漸成為加速計算的重要解決方案,是邊緣端ARM方案的重要補充。

本文基于異構(gòu)Zynq系列FPGA設(shè)計了一種多端口、高吞吐量的SpMV存儲格式與加速系統(tǒng):①設(shè)計了多端口改進的行壓縮存儲格式(Modified Compressed Sparse Row Format,MCSR)存儲稀疏矩陣,提高并行度與計算效率;②研究了在嵌入式異構(gòu)平臺上加速算法的實現(xiàn),在FPGA上完成對算法的加速,使用ARM完成對系統(tǒng)的控制,在ARM+FPGA的架構(gòu)上利用軟硬件協(xié)同方式對加速方法進行了驗證;③ARM+FPGA并行加速后的設(shè)計相比于單ARM方案可以達到10倍的加速效果,計算效率顯著提升,特別是矩陣規(guī)模越大非零值越多加速效果越明顯。

1 加速方法

1.1 稀疏矩陣的存儲格式

為了減少稀疏矩陣的存儲空間,避免零值參與產(chǎn)生無意義的計算,一般采用特定的存儲格式,常用的有三元組存儲格式(Coordinate Format,COO)和行壓縮存儲格式(Compressed Sparse Row Format,CSR)[13-14]。目前稀疏矩陣較常用、效率也較高的存儲格式是CSR格式,但作為一種針對矩陣的通用方法,CSR格式在基于FPGA實現(xiàn)時并不是最高效的。由于CSR格式中row_ptr行偏移數(shù)組存儲的是行起始偏移位置,每行非零元素個數(shù)需要在迭代過程中才能確定,因此外循環(huán)不能使用循環(huán)流水優(yōu)化方法,必須按順序執(zhí)行。這使得SpMV計算效率低下,迭代延遲很高。為了解決這個問題,本文使用MCSR存儲格式,并在此基礎(chǔ)上進行改進。

如圖1(a)所示,MCSR格式中的col_index、value數(shù)組與CSR格式相同,不同之處在于它將CSR格式的row_ptr行偏移數(shù)組更改為row_len行長度數(shù)組,即存儲每行非零元素的個數(shù)。結(jié)合FPGA的特點,為了使用多端口計算進行硬件優(yōu)化,本文先將MCSR格式行、列索引合并起來,形成新的indices索引數(shù)組,再將indices和value數(shù)組按行分成p部分。合并后的單端口MCSR格式如圖1(b)所示,通過連接row_ptr和對應(yīng)數(shù)量的col_index來定義。行、列索引的交錯合并過程不包括任何計算,可在邊緣計算平臺上處理,也可在本地預(yù)處理。在此基礎(chǔ)上,將單端口MCSR格式進一步優(yōu)化為多端口MCSR格式,以便利用多個端口并行存取數(shù)據(jù)來提高算法性能。通過將輸入的稀疏矩陣按行分成p部分,每一部分單獨處理,來實現(xiàn)p倍的運行加速。圖1(c)展示了當(dāng)p為2時indices和value數(shù)組的分塊結(jié)果。具體分塊的p取值將在多端口計算方法中詳細闡述。

圖1 MCSR存儲格式

1.2 硬件優(yōu)化方法

針對SpMV的運算特點,本文將硬件優(yōu)化方法分為兩類:任務(wù)級優(yōu)化和數(shù)據(jù)級優(yōu)化。任務(wù)級優(yōu)化包括多端口計算、數(shù)據(jù)流、循環(huán)流水。在使用優(yōu)化的多端口MCSR存儲格式時,可使用數(shù)據(jù)流實現(xiàn)多端口任務(wù)并行,使用循環(huán)流水實現(xiàn)每個端口內(nèi)的任務(wù)并行。數(shù)據(jù)級優(yōu)化包括數(shù)組分割和流傳輸。數(shù)組分割實現(xiàn)了數(shù)據(jù)讀寫的并行,流傳輸實現(xiàn)了數(shù)據(jù)的緩存。

1.2.1 多端口計算

SpMV計算包含讀、計算和寫3個任務(wù),為了提高讀、寫任務(wù)的數(shù)據(jù)吞吐量,本文利用多個端口并行地將數(shù)據(jù)從存儲器傳輸?shù)紽PGA。如果FPGA包含D個存儲器端口,每個端口具有B位,稀疏矩陣value、indices中的每個元素分別為g、h比特,可將輸入稀疏矩陣的行分成p部分對應(yīng)多端口MCSR的p個端口,每一部分都單獨處理,從而最大限度提高p倍運行速度。p計算公式如式(1)所示:

(1)

每個硬件線程計算輸出向量y的一部分,最后將y合并保存到BRAM中并傳輸?shù)紻DR中。增大p值可有效減小SpMV計算延時,但會增大資源利用率。綜合考慮延時與硬件資源后,本文選擇端口數(shù)p=8進行實驗。

1.2.2 數(shù)據(jù)流

數(shù)據(jù)流優(yōu)化方法實現(xiàn)任務(wù)級流水線,允許函數(shù)或循環(huán)之間的操作并行執(zhí)行,可減少時延,增加RTL并發(fā)度,提高總體吞吐量。不使用數(shù)據(jù)流優(yōu)化時,所有操作默認順序執(zhí)行。例如,程序必須在訪問數(shù)組的函數(shù)或循環(huán)之前完成對數(shù)組的所有讀、寫訪問。這嚴重限制了下一個使用數(shù)組的函數(shù)或循環(huán)的啟動操作。使用數(shù)據(jù)流優(yōu)化后,當(dāng)前函數(shù)或循環(huán)中的操作可在上一個函數(shù)或循環(huán)完成其所有操作之前啟動,如圖2所示。

圖2 數(shù)據(jù)流優(yōu)化方法

如圖3所示,順序函數(shù)之間具有數(shù)據(jù)流,在循環(huán)之間插入Channel通道(Ping-pong RAM、FIFO或Register),以確保數(shù)據(jù)可從一個循環(huán)異步流到下一個循環(huán)。

圖3 數(shù)據(jù)流優(yōu)化方法細節(jié)

在使用優(yōu)化的多端口MCSR存儲格式計算SpMV時,每個端口之間數(shù)據(jù)不存在相互關(guān)聯(lián),因此可使用數(shù)據(jù)流實現(xiàn)多端口任務(wù)并行。其中可并行的任務(wù)如下:多個端口indices和values數(shù)據(jù)的并行讀入、緩存;多個端口indices數(shù)據(jù)中rows和cols的并行緩存;多個端口待計算值(稀疏矩陣中某一元素)與列向量對應(yīng)位的累加求和;多個端口的results數(shù)據(jù)的并行緩存、輸出。具體數(shù)據(jù)緩存類型的選擇將在后文流傳輸方法中闡述。

1.2.3 循環(huán)流水

針對單個循環(huán)的優(yōu)化,一般采用循環(huán)流水,例如在for循環(huán)中對循環(huán)下的代碼做流水化處理。當(dāng)輸入的數(shù)據(jù)不存在依賴性時,可并行化對數(shù)據(jù)進行讀、計算和寫操作,此時可將任務(wù)間隔優(yōu)化到1,相當(dāng)于一個時鐘周期一個運算單元可完成一個操作。循環(huán)流水方法允許以并行方式實現(xiàn)循環(huán)操作,如圖4所示。

圖4 循環(huán)流水優(yōu)化方法

SpMV運算中數(shù)據(jù)是順序流動的,每個端口內(nèi)數(shù)據(jù)不存在相互關(guān)聯(lián),因此可使用循環(huán)流水實現(xiàn)每個端口內(nèi)的任務(wù)并行。其中可并行的任務(wù)如下:每個端口indices和values數(shù)據(jù)的并行讀入、緩存;每個端口indices數(shù)據(jù)中rows和cols的并行緩存;每個端口待計算值(稀疏矩陣中某一元素)與列向量對應(yīng)位乘積的累加求和;每個端口的results數(shù)據(jù)的并行緩存、輸出。

1.2.4 數(shù)組分割

在FPGA中,每個BRAM都有兩個共享數(shù)據(jù)的可配置獨立端口,用于片上數(shù)據(jù)緩存、FIFO緩沖。默認情況下數(shù)組中N個元素連續(xù)存儲在一塊BRAM中,則一個時鐘周期只能提供一個數(shù)據(jù)。為了最優(yōu)化數(shù)據(jù)級流水線間隔,使用數(shù)組分割方法將原始數(shù)組(單一BRAM)拆分為多個更小的數(shù)組(多個BRAM)。這可有效增加內(nèi)存的讀寫端口數(shù)量,改善設(shè)計吞吐量,提高數(shù)據(jù)讀寫并行度。

在每個端口待計算值(稀疏矩陣中的某一非零值)與列向量對應(yīng)位乘積的任務(wù)中,默認情況一個端口中的indices與value數(shù)組分別連續(xù)存儲在兩塊BRAM中。BRAM最大的端口數(shù)量為2,嚴重限制了讀和寫的吞吐量。因此為了改善帶寬,使用數(shù)組分割方法將原一維數(shù)組按獨立元素進行拆分,將內(nèi)存分解為單個寄存器,有效實現(xiàn)了數(shù)據(jù)讀寫的并行。

1.2.5 流傳輸

流傳輸優(yōu)化方法決定了數(shù)據(jù)流通道中的數(shù)據(jù)緩存類型。如圖3所示,在數(shù)據(jù)流的函數(shù)主體或循環(huán)主體獨立通道,將每項任務(wù)的結(jié)果緩存在通道中。根據(jù)不同任務(wù)可選擇不同的數(shù)據(jù)緩存類型,如Ping-Pong RAM或FIFO。通常情況下,Ping-Pong RAM用來存取矢量數(shù)組,FIFO用來存取標(biāo)量。數(shù)據(jù)流所添加的每個通道都包含用于指示Ping-Pong RAM或FIFO已滿或已空的信號。流傳輸優(yōu)化方法如圖5所示。流傳輸方法的優(yōu)勢在于不需要地址管理,不足是讀取完當(dāng)前數(shù)據(jù)之后無法再次對該數(shù)據(jù)進行讀取。但是由于SpMV運算只涉及數(shù)據(jù)的順序讀寫,不受該不足影響,因此可使用流傳輸方法將數(shù)據(jù)流通道中的數(shù)據(jù)緩存類型配置為FIFO,可有效減小資源利用率,提高數(shù)據(jù)存取并行度。

圖5 流傳輸優(yōu)化方法細節(jié)

2 硬件實現(xiàn)

本文采用Xilinx ZCU102開發(fā)平臺,基于Xilinx Zynq UltraScale+ XCZU9EG-2FFVB1156E MPSoC 芯片進行了實現(xiàn)與測試[15]。

基于ZCU102平臺的加速結(jié)構(gòu)如圖6所示。AXI Interconnect為AXI總線實現(xiàn)PS端與PL端互聯(lián),Data Mover為數(shù)據(jù)搬運器,SpMV accelerator為稀疏矩陣乘法加速器。SD卡存入Linux系統(tǒng)硬件啟動文件與數(shù)據(jù),程序初始化時PS端將SD卡數(shù)據(jù)讀入DDR4,PL端SpMV加速模塊通過直接內(nèi)存存取方式(Direct Memory Access,DMA)獲取DDR4中的數(shù)據(jù),PL端實現(xiàn)SpMV并行計算。

圖6 基于ARM+FPGA的SpMV算法加速結(jié)構(gòu)

本文采用Xilinx的SDSoC開發(fā)環(huán)境,將.cpp文件分別轉(zhuǎn)換為BOOT.bin、image.ub、.elf文件和.bit文件。其中,BOOT.bin為啟動文件,包含引導(dǎo)加載程序(FSBL)、引導(dǎo)程序(U-Boot);image.ub包含Linux啟動映像;.elf為應(yīng)用程序的二進制可執(zhí)行文件,可在Linux系統(tǒng)中調(diào)用相關(guān)軟硬件資源,完成數(shù)據(jù)的讀取、輸出和運算;.bit為FPGA比特流文件。圖6給出了基于ARM+FGGA的SpMV算法加速結(jié)構(gòu)。

在硬件設(shè)計中,數(shù)據(jù)傳輸接口的設(shè)計尤為重要。本文中,由于傳輸稀疏矩陣非零值與計算結(jié)果時涉及較大數(shù)據(jù)量,因此選用AXI MM作為Data Mover傳輸數(shù)據(jù),使用SDS data mem attribute指令約束數(shù)據(jù)存儲地址連續(xù)性。相比AXI GP與AXI ACP,AXI HP接口有更高的讀寫帶寬,且AXI MM Data Mover 要求PL端口為主端口,PS端口為從端口,因此選用AXI HP接口,使用SDS data zero_copy指令約束數(shù)據(jù)傳輸量。由于Random接口實現(xiàn)數(shù)據(jù)隨機讀取會占用較多的BRAM等片上資源,且SpMV計算過程中數(shù)據(jù)是順序讀取或?qū)懭氲?因此選用Sequential接口,使用SDS data access pattern指令約束硬件函數(shù)數(shù)據(jù)訪問方式。

根據(jù)本文提出的加速優(yōu)化方法對SpMV進行硬件優(yōu)化,結(jié)合以上加速結(jié)構(gòu),可得到優(yōu)化后的SpMV程序分析結(jié)果,如圖7所示,可以看出程序已經(jīng)實現(xiàn)了多端口indices、values數(shù)據(jù)的并行讀入、緩存,和多端口results數(shù)據(jù)的緩存、輸出。圖中,fmul為程序中的乘積操作,fadd為乘積結(jié)果與緩存results值的累加求和操作,已經(jīng)實現(xiàn)了乘積與累加求和的并行操作。

圖7 SpMV 程序分析

3 結(jié)果分析

3.1 數(shù)據(jù)集介紹

佛羅里達大學(xué)(University of Florida)稀疏矩陣庫包含大量從應(yīng)用程序中收集的稀疏矩陣,被廣泛應(yīng)用于基準(zhǔn)測試。本文從中選擇19個不同類型的稀疏矩陣,行列數(shù)范圍在102～105,非零值數(shù)量在102～106。在計算SpMV時,稀疏矩陣是所選測試矩陣,密集向量是rand()函數(shù)產(chǎn)生的隨機數(shù)。rand()%(b-a+1)+a可以產(chǎn)生[a,b]范圍的一個隨機整數(shù),本文選取a=0,b=1做測試。稀疏矩陣的屬性包含行數(shù)m、列數(shù)n、非零值、稀疏度、2D圖、3D圖,如表1所示。

表1 稀疏矩陣屬性

3.2 性能對比

為了驗證系統(tǒng)性能,本文分別完成了基于PS端(即ARM)和基于PS+PL(即ARM+FPGA)的系統(tǒng)設(shè)計?；赑S的設(shè)計是只使用ARM處理器系統(tǒng)完成全部計算,而基于PS+PL的設(shè)計將SpMV移植到PL端完成,由FPGA實現(xiàn)SpMV計算加速。

在ARM+FPGA系統(tǒng)設(shè)計中,又分別實現(xiàn)了SpMV并行加速前與并行加速后兩種設(shè)計。SpMV并行加速前采用原始的CSR存儲格式,并行加速后采用本文的多端口MCSR格式+數(shù)據(jù)流+循環(huán)流水+數(shù)組分割+流傳輸?shù)挠布?yōu)化方法。這一對比中變量為加速方法,不變量為測試的稀疏矩陣和FPGA實現(xiàn)平臺。通過對比并行加速前后SpMV的硬件資源利用率、處理所需時間等性能指標(biāo),評價SpMV的硬件優(yōu)化效果。

因此,本文一共實現(xiàn)了3種系統(tǒng)設(shè)計方式進行對比,分別是“單ARM”方案、“ARM+FPGA并行加速前”方案、“ARM+FPGA并行加速后”方案。分別對所選的19個稀疏矩陣進行SpMV計算對比,運行時間如圖8所示,“ARM+FPGA并行加速后”相對于“單ARM”的加速比如表2所示?？梢姰?dāng)稀疏矩陣規(guī)模較小非零值較少時“單ARM”的計算效率較高,但是當(dāng)規(guī)模變大非零值少量增加就會導(dǎo)致ARM計算效率下降。而隨著矩陣規(guī)模增大非零值增加,本文提出的“ARM+FPGA并行加速后”方案加速效果顯著提高。

表2 SpMV計算核心橫向?qū)Ρ冉Y(jié)果

圖8 SpMV 計算運行時間

根據(jù)FPGA開發(fā)軟件Vivado生成的資源使用報表可以看出,優(yōu)化前后FPGA的核心資源利用率有所增加,增加的資源消耗在可接受范圍內(nèi),如表3所示。優(yōu)化后實現(xiàn)了并行加速,各硬件資源利用率相比優(yōu)化前略有增加。

表3 并行加速前后FPGA核心資源使用對比

4 結(jié)束語

本文針對FPGA的SpMV計算加速問題提出了一種多端口的MCSR存儲格式,結(jié)合數(shù)據(jù)流、循環(huán)流水、數(shù)組分割、流傳輸?shù)燃铀賰?yōu)化方法實現(xiàn)了SpMV加速求解器設(shè)計。對比研究了“單ARM”“ARM+FPGA并行加速前”“ARM+FPGA并行加速后”3種SpMV的計算耗時與資源使用,實驗結(jié)果表明,本文設(shè)計的加速器在稀疏矩陣規(guī)模增大非零值越多的情況下加速效果越明顯。在本文所實驗的稀疏矩陣中“ARM+FPGA并行加速后”相較于“單ARM”方案最高可以達到10倍的加速效果,而且增加的資源消耗在可接受范圍內(nèi)。因此,本文方法在邊緣端實施SpMV計算方面具有一定的優(yōu)勢。

本文為了保證3種對比方案數(shù)據(jù)的一致性,都使用了浮點數(shù)計算,雖保證了計算準(zhǔn)確率,但增加了FPGA硬件資源消耗。后續(xù)工作計劃采用浮點數(shù)轉(zhuǎn)定點數(shù)的方法,爭取用有限的準(zhǔn)確率損失換取硬件資源利用率的減少。