王華龍 陳小文

（國防科技大學計算機學院 長沙 410073）

1 引言

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

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

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

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

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

2.1 GEMM分塊方案

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

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

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

圖2 基于GEBP的GEPP

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

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

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

數(shù)據(jù)搬移要求盡可能地將數(shù)據(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è)計可以將GEBP 數(shù)據(jù)搬移和計算重疊。

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

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

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

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

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

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

3.1 多核并行性分析

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

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

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

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

圖4 多核GEMM設(shè)計

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

4 性能測試與分析

4.1 單核性能

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

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

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

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

4.2 多核性能

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

圖6 X-DSP多核GEMM性能

5 結(jié)語

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