矩陣乘在通用DSP上的峰值性能模型

摘要：DSP具有能效比高的特點，可以用于通用高性能計算.矩陣乘是許多科學(xué)與計算問題的核心算法，在DSP上取得高性能具有重要的理論和現(xiàn)實意義.面向通用DSP，提出了矩陣乘并行算法，建立了矩陣乘峰值性能模型，根據(jù)性能模型，構(gòu)建了矩陣乘性能達Tflops級DSP體系結(jié)構(gòu)參數(shù)配置，對通用DSP的設(shè)計參數(shù)給出了明確的性能指標(biāo)要求，包括乘加流水線數(shù)量、寄存器數(shù)目、帶寬和延遲.

關(guān)鍵詞：通用DSP；矩陣乘；并行算法；性能評測

中圖分類號：TP332.2 文獻標(biāo)識碼：A

A Peak Performance Model for Matrix Multiplication

on General-Purpose DSP

LIU Jie， CHI Li-hua， XIE Lin-chuan， WANG Yang， GAN Xin-biao， FENG Hua，HU Qing-feng

（Science and Technology on Parallel and Distributed Processing Laboratory， National Univ

of Defense Technology， Changsha， Hunan 410073，China）

Abstract： DSP processor can be used to solve the high performance computation problems， which has the characteristics of high computing performance and low power. Matrix multiplication algorithm is the kernel of many scientific and technology computation， so it is of importance for theorem and practice. Based on general purpose DSP （GPDSP）， a new parallel algorithm for matrix multiplication was proposed. And a peak performance model for matrix multiplication was built. From the peak performance model， an architecture of GPDSP was set up， and the parameter of GPDSP with Tflops was given， which includes the number of pipe-line， the number of SIMD registers， the breadth and latency for the hierarchical memories.

Key words： general purpose DSP； matrix multiplication； parallel algorithm； performance evaluation

DSP是強調(diào)實時處理的低功耗體系結(jié)構(gòu)，對FFT等信號處理專門計算具有很好的支持能力.2011年，基于TI的KeyStone構(gòu)建C66xDSP雙精度性能達到66 Gflops，功耗為10 W，能效比高^[1].目前面向高性能計算的通用DSP成為重要的研究方向.

矩陣乘是許多科學(xué)與工程計算問題的核心算法^[2]，廠商和科研人員為不同的硬件平臺研制了矩陣乘高性能優(yōu)化庫.AMD公司開發(fā)了ACML基本數(shù)學(xué)運算庫，Intel公司開發(fā)了MKL基本數(shù)學(xué)運算庫，均包含了使用匯編語言手工優(yōu)化的高性能BLAS庫[3-4].GotoBLAS[5-6]和ATLAS[7]針對不同的微處理器提供高性能BLAS庫.因為新架構(gòu)硬件平臺不停地推出，新算法和優(yōu)化方法的研制從未停止過，特別是當(dāng)前多核多線的微處理器提供的新的依賴平臺的并行技術(shù)，使得科研人員不斷探索新的最優(yōu)實現(xiàn)方法.

矩陣乘算法（CM，N=AM，K*BK，N）C中的每個結(jié)果元素可以看成是A的一行元素和B的一列元素的內(nèi)積，為提高性能需要采用分塊算法，并行計算時要進行二維的數(shù)據(jù)劃分，對許多科學(xué)與工程計算問題具有借鑒意義.研制一款新型的面向科學(xué)計算的通用DSP，首先要保證矩陣乘能達到峰值性能，Igual等人[8]針對單精度DSP TI公司的C66x設(shè)計了矩陣乘并行算法，可以發(fā)揮峰值性能的70%，能效比達到7.4 Gflops/W，具有明顯的低功耗、高性能特點.

本文面向基于多核和短向量技術(shù)的通用DSP模型，提出了一種新型的矩陣乘并行算法，建立了峰值性能模型，根據(jù)性能模型，對通用DSP的設(shè)計參數(shù)給出了明確的性能指標(biāo)要求，包括乘加流水線數(shù)量、寄存器數(shù)目、帶寬和延遲等，構(gòu)建了矩陣乘性能達到1 Tflops， 2 Tflops和4 Tflops的DSP體系結(jié)構(gòu)框架.

1 通用DSP模型

現(xiàn)代高性能微處理器中大多使用了SIMD技術(shù)，如Intel的MMX和SSE系列，以及AMD的3DNOW！等，使多個運算單元在一條指令的控制下對多個數(shù)據(jù)并行操作，這些SIMD擴展指令基于固定長度的短向量，通常為256位或512位，將多個數(shù)據(jù)打包存放在向量寄存器中進行并行計算，硬件代價低，控制簡單，可以在較低的功耗下獲得較高的性能.

圖1給出了基于超長指令字結(jié)構(gòu)的通用DSP模型，采用SIMD和多核技術(shù)構(gòu)建.每個單核由SPU和VPU構(gòu)成，SPU包括L1I Cache， L1D Cache， SPE， 標(biāo)量寄存器和流控制器，SPE用于一些指令流的控制、對向量單元的配置以及主要的通信任務(wù)；VPU包括AM， 向量寄存器和多個可并發(fā)執(zhí)行的VPE，多個VPE組成的向量SIMD單元主要用于數(shù)值運算.

假設(shè)存儲不受限，通用DSP的峰值性能取決于以下參數(shù)設(shè)置：1）主頻h（單位為GHz）；2）核數(shù)c；3）單核內(nèi)VPE的數(shù)量v；4）單VPE浮點性能f（單位為每周期雙精度浮點數(shù)flop/cycle）.峰值性能有以下計算公式：

Rmax=h×c×v×f.

影響通用DSP性能的帶寬和延遲主要包括：1）Global Memory（下文簡稱GM）到DMA的帶寬和延遲；2）DMA到Array Memory（下文簡稱AM）的帶寬和延遲；3）AM到向量寄存器的帶寬和延遲；4）L1D到標(biāo)量寄存器的帶寬和延遲.

2 矩陣乘并行算法

考慮矩陣乘法運算C=C+A×B，其中C是m×n矩陣、A是m×k矩陣、B是k×n矩陣.矩陣乘要在通用DSP模型上獲得高性能，需要針對通用DSP的結(jié)構(gòu)對矩陣乘進行并行算法的重新設(shè)計，基本原理是采用分塊算法，將原矩陣乘運算轉(zhuǎn)換為圖3給出的分塊矩陣乘運算.

4 通用DSP參數(shù)配置

通用DSP的設(shè)計只要滿足帶寬和延遲的需求，矩陣乘就可以獲得峰值性能，基本原理是將計算過程和數(shù)據(jù)遷移重疊起來，屏蔽數(shù)據(jù)遷移時間.假設(shè)每核向量寄存器的數(shù)目是64個，每拍從AM到向量寄存器可以讀取2個向量，向量長度是16，每個VPE擁有2條乘加流水線，單核每拍可以完成4個向量運算，AM被平均分成兩部分，一部分用來存儲當(dāng)前使用的AIJ數(shù)據(jù)，一部分用于數(shù)據(jù)預(yù)取AIJ.向量寄存器的一半用來存儲矩陣C，矩陣C以流水的方式進入AM，C的子矩陣大小為128×4，即512個雙精度數(shù)據(jù)，留相同大小空間預(yù)取數(shù)據(jù)，C的子矩陣共使用1 024個double數(shù)據(jù)空間.

AM用于存儲矩陣A和矩陣C的當(dāng)前計算數(shù)據(jù)和預(yù)取數(shù)據(jù).AM為1 MB時，共存儲131 072個雙精度數(shù)，可用于存儲矩陣A的元素共130 048個雙精度數(shù)，其中65 024個用于存放當(dāng)前參與計算的子矩陣，故子矩陣A的大小為256×254.AM為2 MB時，共存儲262 144個雙精度數(shù)，可以用于存儲矩陣A的元素共261 120個雙精度數(shù)，其中130 560個用于存放當(dāng)前參與計算的子矩陣，故子矩陣A的大小可以取為256×510.

標(biāo)量L1D Cache的大小取為32 KB，4 096個雙精度數(shù).

公式（5）和（6）中的n為矩陣C的列數(shù)，一般取值較大，對帶寬的影響較小，不妨取為8 192；當(dāng)向量寄存器的數(shù)目為64時，內(nèi)層循環(huán)展開取為8×8×4；每拍取兩個向量；公式（7）實際使用中，需要根據(jù)每拍從AM讀取向量寄存器的數(shù)目決定帶寬要求，比如每拍兩個向量，向量長度為16，則從AM到向量寄存器的帶寬需求為256 Bytes/cycle.

根據(jù)上面給出的矩陣乘峰值性能模型可以得到通用DSP的參數(shù)配置，配置表見表3.

至此我們構(gòu)建了矩陣乘峰值性能Tflops級通用DSP模型，只要通用DSP滿足上述的參數(shù)配置，就可以得到峰值性能達到1Tflops，2 Tflops和4 TFlops的通用DSP.

5 結(jié) 論

DSP具有高性能 、低功耗的特點，非常適用于具有計算密集特點的通用計算，并且越來越受到高性能計算領(lǐng)域的重視.本文嘗試在通用DSP模型上，提出了一種通過DMA完成數(shù)據(jù)遷移的高性能矩陣乘并行算法，基于分塊算法，使用計算與數(shù)據(jù)遷移重疊技術(shù)屏蔽數(shù)據(jù)遷移時間，建立了峰值性能模型，重點對帶寬和延遲進行了分析，基于矩陣乘峰值性能模型構(gòu)建了Tflops級的通用DSP模型，可以給通用DSP的設(shè)計提供指導(dǎo).

下一步需要對具體實現(xiàn)做模擬和仿真，驗證通用DSP模型的實用性和有效性，并可以根據(jù)矩陣乘峰值性能模型、結(jié)構(gòu)具體應(yīng)用問題的計算特點，有針對性地構(gòu)建新的通用DSP.

參考文獻

[1] Texas Instruments Incorporated. TMS320C66x multicore DSPs for high-performance computing [R]. Dallas， Texas： Texas Instruments Incorporated， 2011.

[2] DONGARRA J J， CROZ J D， HAMMARLING S， et al. An extended set of FORTRAN basic linear algebra subprograms [J]. ACM Transactions on Mathematical Software， 1988， 14（1）： 1-17.

[3] DONGARRA J J， CROZ J D， HAMMARLING S， et al. A set of level 3 basic linear algebra subprograms [J]. ACM Transactions on Mathematical Software，1990， 16（1）： 1-17.

[4] KAGSTROM B， LING P， LOAN C V. Gemm-based level3 BLAS： high performance model implementations and performance evaluation benchmark [J]. ACM Transactions on Mathematical Software， 1998， 24（3）： 268-302.

[5] GOTO K， VAN DE GEIJN R.High-performance implementation of the level-3 BLAS [J]. ACM Transactions on Mathematical Software， 2008， 35（1）：1-14.

[6] GOTO K， VAN DE GEIJN R. Anatomy of high-performance matrix multiplication [J]. ACM Transactions on Mathematical Software，2008， 34（3）： 1-25.

[7] WHALEY R C， PETITET A， DONGARRA J J. Automated expirical optimizations of software and the ATLAS project [J]. Parallel Computing， 2001， 27（3）： 3-35.

[8] IGUAL F D， ALI M， FRIEDMANN A， et al. Unleashing the high-performance and low-power of multi-core DSPs for general-purpose HPC[C]//SC'12 Proceedings of the International Conference on High Performance Computing， Networking， Storage and Analysis. Los Alamitos， CA， USA： IEEE Computer Society Press， 2012：26.1-26.19.