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

王華龍 陳小文

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

1 引言

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

為了發(fā)揮不同體系結(jié)構(gòu)處理器的性能，通常需要提供高效的標(biāo)準(zhǔn)函數(shù)庫(kù)。BLAS算法庫(kù)是大規(guī)模科學(xué)計(jì)算最常用的核心數(shù)學(xué)算法庫(kù)之一，而B(niǎo)ALS庫(kù)中最常用的核心算法是矩陣乘法（General Matrix-Matrix Multiplication，GEMM），其在高性能計(jì)算中扮演著重要角色，是一種同時(shí)具有計(jì)算密集和訪存密集的運(yùn)算［5］，對(duì)處理器的運(yùn)算能力、訪存帶寬及延遲的要求非常高，甚至占用高性能標(biāo)準(zhǔn)測(cè)試程序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ī)模矩陣乘法，研究表明針對(duì)處理器的并行結(jié)構(gòu)和存儲(chǔ)系統(tǒng)優(yōu)化設(shè)計(jì)的矩陣乘法映射能夠有效地隱藏?cái)?shù)據(jù)訪問(wèn)開(kāi)銷。Gunnel［11］在基于Cache 的多級(jí)存儲(chǔ)的體系結(jié)構(gòu)下，提出了分層計(jì)算的方法實(shí)現(xiàn)BLAS 中的矩陣乘算法，這種方法降低了存儲(chǔ)層次間搬運(yùn)數(shù)據(jù)的平均開(kāi)銷。Goto［12］等發(fā)現(xiàn)，二級(jí)Cache 到寄存器的帶寬足以滿足核心循環(huán)運(yùn)算速度的要求，對(duì)于經(jīng)典矩陣乘法C=AB+C，他提出把矩陣A 的分塊存放在二級(jí)Cache 中，B矩陣的分塊存放在一級(jí)Cache 中，這樣就增大了A矩陣分塊的大小，同時(shí)也就提升了B 矩陣的運(yùn)算訪存比。

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

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

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

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 時(shí)，首先外層循環(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)算和存儲(chǔ)層次間的映射，數(shù)據(jù)的放置、移動(dòng)及計(jì)算和數(shù)據(jù)移動(dòng)的重疊。

圖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 還要用來(lái)緩存其它的數(shù)據(jù)（如程序中的其它變量、循環(huán)的開(kāi)銷）。已經(jīng)保存在L2中的分塊被進(jìn)一步細(xì)分為Mkernel*KSM的較小子塊。矩陣B 的子塊也被分為KSM*Nkernel。通過(guò)駐留在L2中的A 子塊與L1 中的B 子塊相乘得到Mkernel*Nkernel的小塊矩陣C。通常情況下，為了減少L1 Cache 的沖突，B 矩陣分塊KSM*Nkernel容量應(yīng)該小于L1 Cache容量的一半。Mkernel與Nkernel的選擇取決于內(nèi)核中可用的寄存器數(shù)量。Goto BLAS 針對(duì)以往處理器研究的大量文獻(xiàn)［18～21］的實(shí)驗(yàn)結(jié)果都表明Mkernel*Nkernel分塊大致為方陣時(shí)效果更好，不過(guò)在實(shí)際的優(yōu)化設(shè)計(jì)中，對(duì)分塊參數(shù)Mkernel與Nkernel選擇還會(huì)有其他的影響因素。內(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ù)移動(dòng)與計(jì)算重疊，從而需要充分利用X-DSP 的DMA 功能。如圖3，說(shuō)明了GEPP 即A 矩陣的一列乘以B 矩陣的一行，A、B矩陣最初駐留在DDR存儲(chǔ)器中并以列順序存儲(chǔ)。我們?cè)赬-DSP 的存儲(chǔ)器中創(chuàng)建暫存緩沖區(qū)，用來(lái)存儲(chǔ)A和B矩陣的子塊。

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

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

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

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

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

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

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

3.1 多核并行性分析

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

X-DSP 的多核體系結(jié)構(gòu)采用共享SM 和DDR的存儲(chǔ)結(jié)構(gòu)，分塊矩陣乘法的不同子塊間的計(jì)算不需要考慮數(shù)據(jù)交換，因此可以適合數(shù)據(jù)并行。考慮一個(gè)經(jīng)典的矩陣乘法C=A*B+C，假設(shè)共有P 個(gè)核，標(biāo)號(hào)分別為P0，P1……PP-1。本文將A 矩陣按行進(jìn)行劃分為P塊，這些塊依次記為A0，A1……AP-1，矩陣C 同時(shí)按行進(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矩陣對(duì)應(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)算時(shí)矩陣B 是每個(gè)核都需要訪問(wèn)的，根據(jù)X-DSP 的體系結(jié)構(gòu)，矩陣B 的數(shù)據(jù)可在SM 中共享，則矩陣乘法計(jì)算只需要搬移A，C 矩陣即可。但是由于SM 大小的限制，矩陣B 必須分塊進(jìn)入SM，其最大子塊在SM 中直至所有的核不再訪問(wèn)為止。為防止不同的核運(yùn)行速度不同而把SM 中的數(shù)據(jù)沖掉，再訪問(wèn)B 矩陣的下一個(gè)分塊之前需要做一次同步，同步之后所有的核將全速運(yùn)行，而且同步之后各個(gè)核將互不影響彼此的運(yùn)行。

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

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

4 性能測(cè)試與分析

4.1 單核性能

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

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

2）循環(huán)開(kāi)銷受限于于L1 和L2 的大小；

3）跨不同層和數(shù)據(jù)打包，移動(dòng)的開(kāi)銷。

4.2 多核性能

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

圖6 X-DSP多核GEMM性能

5 結(jié)語(yǔ)

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