基于X-DSP 的GEMM 算法實(shí)現(xiàn)?

王華龍 陳小文

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

1 引言

隨著超大規(guī)模集成電路技術(shù)的發(fā)展，處理器的體系結(jié)構(gòu)也由于追求高性能，低功耗發(fā)生了重大變化。在高性能計(jì)算應(yīng)用中，由于能耗的因素，促進(jìn)了多核、向量處理、可編程可配置、可重構(gòu)等體系結(jié)構(gòu)的發(fā)展［1］。數(shù)字信號處理器（DSP）一直是嵌入式系統(tǒng)的核心組成部分，主要優(yōu)勢在于高功耗效率，價格低廉及易編程。但是多核環(huán)境下并行訪問存儲器的性能依然是多核系統(tǒng)設(shè)計(jì)和應(yīng)用開發(fā)的難點(diǎn)之一。

為了發(fā)揮不同體系結(jié)構(gòu)處理器的性能，通常需要提供高效的標(biāo)準(zhǔn)函數(shù)庫。BLAS算法庫是大規(guī)?？茖W(xué)計(jì)算最常用的核心數(shù)學(xué)算法庫之一，而BALS庫中最常用的核心算法是矩陣乘法（General Matrix-Matrix Multiplication，GEMM），其在高性能計(jì)算中扮演著重要角色，是一種同時具有計(jì)算密集和訪存密集的運(yùn)算［5］，對處理器的運(yùn)算能力、訪存帶寬及延遲的要求非常高，甚至占用高性能標(biāo)準(zhǔn)測試程序HPL 主要運(yùn)算量的90%以上。吳少剛［7］等在基于Intel 微處理器的PC 作為節(jié)點(diǎn)機(jī)的類Beowulf 機(jī)群系統(tǒng)上使用分支優(yōu)化、訪存優(yōu)化、譯碼優(yōu)化以及執(zhí)行優(yōu)化技術(shù)，將矩陣乘運(yùn)算單機(jī)性能較原始BLAS 提升5 倍。Sohl 等［9］面向一種異構(gòu)并行DSP體系結(jié)構(gòu)研究了大規(guī)模矩陣乘法，研究表明針對處理器的并行結(jié)構(gòu)和存儲系統(tǒng)優(yōu)化設(shè)計(jì)的矩陣乘法映射能夠有效地隱藏?cái)?shù)據(jù)訪問開銷。Gunnel［11］在基于Cache 的多級存儲的體系結(jié)構(gòu)下，提出了分層計(jì)算的方法實(shí)現(xiàn)BLAS 中的矩陣乘算法，這種方法降低了存儲層次間搬運(yùn)數(shù)據(jù)的平均開銷。Goto［12］等發(fā)現(xiàn)，二級Cache 到寄存器的帶寬足以滿足核心循環(huán)運(yùn)算速度的要求，對于經(jīng)典矩陣乘法C=AB+C，他提出把矩陣A 的分塊存放在二級Cache 中，B矩陣的分塊存放在一級Cache 中，這樣就增大了A矩陣分塊的大小，同時也就提升了B 矩陣的運(yùn)算訪存比。

本文主要在X-DSP 平臺實(shí)現(xiàn)GEMM 算法設(shè)計(jì)。X-DSP是一款高性能多核DSP，每個內(nèi)核均擁有一級程序Cache（L1P）和一級數(shù)據(jù)Cache（L1D）各32KB，二級統(tǒng)一存儲器512KB 的L2，并能夠配成Cache（默認(rèn)）、SRAM，或是兩者的組合。SM（Shared Memory）負(fù)責(zé)處理系統(tǒng)中所有master對SM和DDR3 的訪問請求。首先針對X-DSP 的硬件資源和體系結(jié)構(gòu)，選擇最終的分塊方式以及數(shù)據(jù)搬移方案，實(shí)現(xiàn)單核GEMM 的設(shè)計(jì)；然后再對存儲空間進(jìn)行合理劃分，采用分塊的方式對數(shù)據(jù)進(jìn)行并行分解，使塊與塊之間的計(jì)算相互獨(dú)立，結(jié)合X-DSP 多核通信及同步機(jī)制將并行的分塊算法映射至多個核中，完成多核GEMM 設(shè)計(jì)；最后通過對單核與多核GEMM的性能測試，實(shí)現(xiàn)高性能GEMM的設(shè)計(jì)。

2 單核GEMM的設(shè)計(jì)與實(shí)現(xiàn)

GOTO-BLAS是目前使用最廣泛且性能最佳的BLAS 實(shí)現(xiàn)之一。從早期版本開始，它已經(jīng)成功移植到許多可擴(kuò)展的架構(gòu)中［13］。其核心就是分塊，將GEMM 分解為不同的層，每個層映射到存儲結(jié)構(gòu)中不同層次。同時分塊計(jì)算也會隱藏?cái)?shù)據(jù)搬移的時間，從而接近最佳性能。

2.1 GEMM分塊方案

一般情況下，矩陣乘法可以分為小矩陣乘法和矩陣向量乘法［14］（矩陣向量乘法一般性能比較差），而小矩陣乘法又可以分為GEPP、GEMP 和GEPM，可再進(jìn)一步分解為GEBP、GEPB 和GEPDOT，如圖1 所示。Watts D J［15］等比較了這些分塊方法以及不分塊方法的性能，發(fā)現(xiàn)分塊的方法性能遠(yuǎn)高于不分塊的方法，進(jìn)一步證明了分塊方法的有效。

圖1 GEMM分塊實(shí)現(xiàn)方案

本文主要研究基于GEMM-GEPP-GEBP 進(jìn)行分塊計(jì)算，單核計(jì)算C=A×B 時，首先外層循環(huán)沿著A 矩陣的列方向進(jìn)行分塊，采用GEPP 分塊方式計(jì)算GEMM，最后內(nèi)層循環(huán)沿著A 矩陣的行方向進(jìn)行分塊，采用GEBP 分塊方式計(jì)算GEPP。單核運(yùn)算中基于SM 的分塊方案如圖2，灰色分塊便是GEBP的運(yùn)算部分，虛線箭頭表示GEBP 逐漸完成GEPP的分塊，真正解決的是單核的分塊運(yùn)算和存儲層次間的映射，數(shù)據(jù)的放置、移動及計(jì)算和數(shù)據(jù)移動的重疊。

圖2 基于GEBP的GEPP

2.2 映射到X-DSP核心架構(gòu)

矩陣A 的分塊如圖3，選擇合適大小分塊放入L2 ，基于Goto-BLAS 諸多文獻(xiàn)的研究結(jié)果［16～17］和X-DSP 的實(shí)際情況考慮，用L2 Cache 的一半（256KB）存放該分塊。矩陣B 被分成小塊，選擇合適大小放入L1 中，通常選擇一半L1（16KB）作為緩存，實(shí)際中，L1 Cache 還要用來緩存其它的數(shù)據(jù)（如程序中的其它變量、循環(huán)的開銷）。已經(jīng)保存在L2中的分塊被進(jìn)一步細(xì)分為Mkernel*KSM的較小子塊。矩陣B 的子塊也被分為KSM*Nkernel。通過駐留在L2中的A 子塊與L1 中的B 子塊相乘得到Mkernel*Nkernel的小塊矩陣C。通常情況下，為了減少L1 Cache 的沖突，B 矩陣分塊KSM*Nkernel容量應(yīng)該小于L1 Cache容量的一半。Mkernel與Nkernel的選擇取決于內(nèi)核中可用的寄存器數(shù)量。Goto BLAS 針對以往處理器研究的大量文獻(xiàn)［18～21］的實(shí)驗(yàn)結(jié)果都表明Mkernel*Nkernel分塊大致為方陣時效果更好，不過在實(shí)際的優(yōu)化設(shè)計(jì)中，對分塊參數(shù)Mkernel與Nkernel選擇還會有其他的影響因素。內(nèi)核的內(nèi)部循環(huán)使用內(nèi)部向量指令進(jìn)行優(yōu)化，以充分利用X-DSP的內(nèi)核架構(gòu)。

2.3 數(shù)據(jù)搬移方案

數(shù)據(jù)搬移要求盡可能地將數(shù)據(jù)移動與計(jì)算重疊，從而需要充分利用X-DSP 的DMA 功能。如圖3，說明了GEPP 即A 矩陣的一列乘以B 矩陣的一行，A、B矩陣最初駐留在DDR存儲器中并以列順序存儲。我們在X-DSP 的存儲器中創(chuàng)建暫存緩沖區(qū)，用來存儲A和B矩陣的子塊。

SM 有三個數(shù)據(jù)buffer 用于接收由DMA 從DDR 中搬移的數(shù)據(jù)，一個buffer 接收A 矩陣子塊m_SM * k_SM，另外兩個buffer 接收B 矩陣子塊k_SM*n，雙buffer 的設(shè)計(jì)可以將GEBP 數(shù)據(jù)搬移和計(jì)算重疊。

L2 中也有兩個buffer 分別用于接收C 矩陣子塊和A矩陣子塊。

L1中緩存區(qū)主要存放B矩陣子塊。

圖3 基于GEPP-GEBP數(shù)據(jù)搬移

最終目的是將駐留在L2 存儲器中的B 矩陣子塊與位于L1 中的A 矩陣的子塊相乘。首先，DMA搬運(yùn)A 矩陣和B 矩陣子塊到SM 中相應(yīng)位置，傳輸完成后，A矩陣子塊最終存儲在L1緩沖區(qū)中，SM 中緩沖區(qū)變空準(zhǔn)備接收下一個A 矩陣子塊；B 矩陣子塊最終存儲在L2 緩沖區(qū)。此時，啟動DMA 搬移下一次乘法所需的A 矩陣子塊與B 矩陣子塊到SM。這次搬移與A 矩陣與B 矩陣的GEBP 同時發(fā)生。在封裝B Panel 子矩陣的同時，需要更新的Cj的子矩陣由DMA 搬移至相應(yīng)的L2 buffer 中，待所有的數(shù)據(jù)準(zhǔn)備好后，核心循環(huán)的運(yùn)算開始運(yùn)行（圖3 第四欄）。

3 多核GEMM的設(shè)計(jì)與實(shí)現(xiàn)

在多核的環(huán)境下，追求高性能的GEMM依然非常重要。分析多核的存儲體系結(jié)構(gòu)如何進(jìn)行數(shù)據(jù)的并行分解，以便可以更好地使用多核進(jìn)行并行的相互獨(dú)立的運(yùn)算處理，從而達(dá)到最佳的性能。根據(jù)文獻(xiàn)［22～23］對多核DSP 的并行編程研究，同時考慮X-DSP 存儲體系結(jié)構(gòu)，以便可以更好地使用多核進(jìn)行并行的相互獨(dú)立的運(yùn)算處理，并且要使得多核間的負(fù)載均衡，最終實(shí)現(xiàn)kernel設(shè)計(jì)。

3.1 多核并行性分析

多核并行性的重要性在于可以讓不同的核獨(dú)立的運(yùn)算每個分塊矩陣，而且每一個獨(dú)立運(yùn)算都可以按照單核的計(jì)算方式進(jìn)行，這樣就可以大大提高執(zhí)行速度。

X-DSP 的多核體系結(jié)構(gòu)采用共享SM 和DDR的存儲結(jié)構(gòu)，分塊矩陣乘法的不同子塊間的計(jì)算不需要考慮數(shù)據(jù)交換，因此可以適合數(shù)據(jù)并行?？紤]一個經(jīng)典的矩陣乘法C=A*B+C，假設(shè)共有P 個核，標(biāo)號分別為P0，P1……PP-1。本文將A 矩陣按行進(jìn)行劃分為P塊，這些塊依次記為A0，A1……AP-1，矩陣C 同時按行進(jìn)行相應(yīng)的劃分，每塊子矩陣Ci和Ai含有連續(xù)的mi=m/P 行，Ci=AiB+Ci便可以由相應(yīng)的核進(jìn)行獨(dú)立的計(jì)算。然后再將共享矩陣B 也按照列進(jìn)行相應(yīng)的劃分為P 塊，依次記為B0，B1……BP-1，C矩陣對應(yīng)的按照列劃分為P 塊，每塊子矩陣Cj和Bj含有連續(xù)的nj=n/p 列，Cj=ABj+Ci便可以由相應(yīng)的核進(jìn)行獨(dú)立的計(jì)算。

3.2 多核GEMM的設(shè)計(jì)與實(shí)現(xiàn)

從圖4 中可以看出多核并行運(yùn)算時矩陣B 是每個核都需要訪問的，根據(jù)X-DSP 的體系結(jié)構(gòu)，矩陣B 的數(shù)據(jù)可在SM 中共享，則矩陣乘法計(jì)算只需要搬移A，C 矩陣即可。但是由于SM 大小的限制，矩陣B 必須分塊進(jìn)入SM，其最大子塊在SM 中直至所有的核不再訪問為止。為防止不同的核運(yùn)行速度不同而把SM 中的數(shù)據(jù)沖掉，再訪問B 矩陣的下一個分塊之前需要做一次同步，同步之后所有的核將全速運(yùn)行，而且同步之后各個核將互不影響彼此的運(yùn)行。

圖4 多核GEMM設(shè)計(jì)

本次所研究的X-DSP 共有10 組DMA 通道可以同時傳輸數(shù)據(jù)，因此其不同核可以使用不同的DMA 資源，數(shù)據(jù)的搬移與計(jì)算在不同核中可以滿足重疊條件的。SM 中Buffer 中數(shù)據(jù)到位后，每個核只需要包裝搬移自己所需要處理的數(shù)據(jù)且更新的是不同的C 矩陣子塊，計(jì)算完成后由DMA 將結(jié)果搬回到DDR 中即可。為了避免多個核之間重復(fù)的數(shù)據(jù)搬移，設(shè)計(jì)中對SM 做了存儲段的數(shù)據(jù)分配：設(shè)計(jì)兩個buffer 接收KSM*Ncore的B Panel，此外再設(shè)計(jì)8 個buffer 接收每個核所需的KSM*SM。L2 和L1是每個核私有的，無需作特殊的處理。

4 性能測試與分析

4.1 單核性能

圖5 中顯示了基于GEBP 的GEPP 在X-DSP中單核上的性能曲線，從曲線中可以看出本次設(shè)計(jì)所達(dá)到的單精度浮點(diǎn)數(shù)的最高性能為8.49GFLOPS，性能損失的主要原因大部分與體系結(jié)構(gòu)相關(guān)，取決于X-DSP 中的緩存機(jī)制。通過性能測試及時間的統(tǒng)計(jì)，分析其原因主要在于：

1）搬移新的A 矩陣子塊時，每次調(diào)用kernel 時cache未命中；

2）循環(huán)開銷受限于于L1 和L2 的大?。?/p>

3）跨不同層和數(shù)據(jù)打包，移動的開銷。

4.2 多核性能

圖6 顯 示 了 基 于GEPP-GEBP 的GEMM 在X-DSP的8個核上運(yùn)行實(shí)現(xiàn)的性能曲線。8核上并行的BLAS 實(shí)現(xiàn)，單精度GEMM 的峰值性能為52.8GFLOPS。分析影響性能的主要因素在于核間的同步造成了并行時的串行等待。此外，多核并行對于共享存儲器進(jìn)行劃分時，其實(shí)限制了運(yùn)算分塊的大小，雖然是多核同時計(jì)算數(shù)據(jù)，但是分塊的大小會影響核心循環(huán)的性能，從而可能會影響最終的性能。

圖6 X-DSP多核GEMM性能

5 結(jié)語

本文主要針對X-DSP 的體系結(jié)構(gòu)特點(diǎn)研究GEMM 的運(yùn)算性能。主要設(shè)計(jì)實(shí)現(xiàn)基于GEBP 的GEPP 在X-DSP 單核上的性能，對X-DSP 的存儲空間進(jìn)行了合理劃分，得到單核的單精度浮點(diǎn)數(shù)的最佳性能達(dá)8.49GFLOPS。對于GEBP 的GEPP 在X-DSP多核上的性能，采用分塊的方式對數(shù)據(jù)進(jìn)行并行分解，使塊與塊之間的計(jì)算相互獨(dú)立，結(jié)合X-DSP 多核通信及同步機(jī)制將并行的分塊算法映射至多個核中，同時對X-DSP 的硬件傳輸機(jī)制和共享存儲進(jìn)行了優(yōu)化設(shè)計(jì)。經(jīng)過測試，X-DSP的多核最佳性能達(dá)52.8GFLOPS。