朱明達(dá),薛濟(jì)擎,艾純瑤

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

0 引 言

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

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

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

1 加速方法

1.1 稀疏矩陣的存儲(chǔ)格式

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

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

圖1 MCSR存儲(chǔ)格式

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

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

1.2.1 多端口計(jì)算

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

(1)

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

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

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

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

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

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

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

1.2.3 循環(huán)流水

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

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

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

1.2.4 數(shù)組分割

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

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

1.2.5 流傳輸

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

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

2 硬件實(shí)現(xiàn)

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

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

圖6 基于A(yíng)RM+FPGA的SpMV算法加速結(jié)構(gòu)

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

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

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

圖7 SpMV 程序分析

3 結(jié)果分析

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

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

表1 稀疏矩陣屬性

3.2 性能對(duì)比

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

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

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

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

圖8 SpMV 計(jì)算運(yùn)行時(shí)間

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

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

4 結(jié)束語(yǔ)

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

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