周磊濤，陶耀東，劉 生，李 鎖

(1.中國科學(xué)院大學(xué)，北京 100039;2.中國科學(xué)院沈陽計算技術(shù)研究所，遼寧 沈陽 110168;3.沈陽高精數(shù)控技術(shù)有限公司，遼寧 沈陽 110168)

基于FPGA的Systolic乘法技術(shù)研究*

周磊濤1,2，陶耀東2，劉 生1,2，李 鎖3

(1.中國科學(xué)院大學(xué)，北京 100039;2.中國科學(xué)院沈陽計算技術(shù)研究所，遼寧 沈陽 110168;3.沈陽高精數(shù)控技術(shù)有限公司，遼寧 沈陽 110168)

Systolic乘法是一種基于SIMD-MC2模型的矩陣乘算法，無法直接應(yīng)用在單獨的嵌入式系統(tǒng)中，所以提出一種采用FPGA技術(shù)實現(xiàn)Systolic乘法的方法。該方法將FPGA的硬件并行特性與巧妙的并行算法結(jié)合起來，利用FPGA靈活可編程的特點，在FPGA內(nèi)部設(shè)計了一種基于MC2模型的節(jié)點陣列來實現(xiàn)Systolic乘法。實際應(yīng)用中，可以靈活地修改節(jié)點單元的數(shù)量和節(jié)點的功能來滿足不同規(guī)模的運算矩陣需求并充分利用FPGA的資源。仿真結(jié)果驗證了該方法的正確性。實際測試結(jié)果表明：該方法具有較快的速度和較高的實時性。

矩陣乘法；現(xiàn)場可編程門陣列；Systolic乘法；并行計算

1 引言

矩陣乘法在科學(xué)計算、數(shù)字信號處理和圖像處理等領(lǐng)域起著非常重要的作用，其計算性能直接影響到系統(tǒng)的整體性能，所以采用有效的矩陣乘法算法，降低矩陣乘法計算時間，具有非常重要的實際工程意義。通常的矩陣乘運算采用串行計算方法，其計算復(fù)雜度(通常為O(N3))難以滿足計算實時性的要求，所以采用并行計算的方法來求解矩陣乘法是近年來發(fā)展的方向。在并行計算機系統(tǒng)下，為了實現(xiàn)并行計算，需要將數(shù)據(jù)劃分給不同的處理器，并出現(xiàn)了許多性能優(yōu)異的并行矩陣乘算法，比較著名的有DNS算法[1,2]、Cannon算法[2,3]、FOX算法[2,3]、Systolic乘法[3]等，但是這些算法需要多處理器甚至是多計算機才能完成，無法直接應(yīng)用到單獨的系統(tǒng)中，例如嵌入式系統(tǒng)、數(shù)據(jù)處理板卡等。

近年來，現(xiàn)場可編程門陣列FPGA(Field Programmable Gate Array)器件取得了飛速的發(fā)展，其以可編程特性、細(xì)粒度并行能力、豐富的邏輯資源、靈活的算法適應(yīng)性、低硬件代價和高性能低功耗比成為理想的可編程系統(tǒng)平臺。另一方面，由于矩陣乘法運算自身具有良好的并行性，采用FPGA技術(shù)來加速矩陣乘法計算是一種最好的選擇。本文將FPGA技術(shù)與并行矩陣乘算法結(jié)合起來，但在眾多并行矩陣乘算法中，DNS算法是面向立方體的處理器結(jié)構(gòu)，當(dāng)階數(shù)大于2時，此結(jié)構(gòu)難以表示；Cannon算法源于空間對準(zhǔn)的思想，但需要在節(jié)點(Node)單元中預(yù)先置入分配好的數(shù)據(jù)，此過程處理難度大，不容易實現(xiàn)；FOX算法和Cannon算法類似；Systolic乘法源于時間對準(zhǔn)的思想，分配好的數(shù)據(jù)可直接按行列輸入到節(jié)點中，容易實現(xiàn)，所以本文設(shè)計實現(xiàn)了基于FPGA的Systolic乘法。

目前，使用FPGA實現(xiàn)Systolic矩陣乘法已經(jīng)取得一些研究成果，在矩陣向量乘法方面， Karra M Ch 等人[4]在FPGA上實現(xiàn)了基于Systolic結(jié)構(gòu)的矩陣向量乘法，使計算時間復(fù)雜度降為N1+N2+1(N1為被乘矩陣行數(shù)，N2為乘矩陣行數(shù))，但需要在初始化階段預(yù)先為計算節(jié)點賦初值，不容易實現(xiàn)。在矩陣乘法方面， Horita T等人[5]提出了具有容錯機制的二維Systolic結(jié)構(gòu)矩陣乘法，使用了可重配置的開關(guān)網(wǎng)絡(luò)，減少了矩陣乘法的規(guī)模，但不適合小規(guī)模數(shù)據(jù)量的嵌入式系統(tǒng)。Sonawane D N 等人[6]提出了使用四個處理節(jié)點，輪流分發(fā)矩陣行列數(shù)據(jù)的方法，降低了邏輯資源占用，提升了計算性能。但是，當(dāng)矩陣規(guī)模變化時，其計算性能隨之變化，而且需要同時改變控制邏輯，通用性不好，限制了此方法的使用。Vucha M等人[7]利用FPGA實現(xiàn)了一種Systolic陣列結(jié)構(gòu)的矩陣乘法，取得了比較好的計算性能，但擴展性差，不適合靈活變化的嵌入式系統(tǒng)。綜上所述，以上研究都不適合在嵌入式系統(tǒng)中使用。

本文設(shè)計實現(xiàn)了一種具有較高計算性能，且具有良好擴展性的基于FPGA的Systolic算法的矩陣乘法器，其簡單、模塊性好且易重配置的特點特別適合應(yīng)用在嵌入式系統(tǒng)中。該乘法器最大程度使用了FPGA自身的專用乘法硬核，減少對邏輯資源的占用，提高了計算性能。通過對不同情況下矩陣乘法的分析，證實了本矩陣乘法器的計算性能。

2 Systolic陣列

1978年Kung H T博士[8]提出了Systolic陣列，源于時間對準(zhǔn)的思想，以其能充分利用硬件的專用并行結(jié)構(gòu)，巧妙地以空間換時間的硬件實現(xiàn)方法，具有流水線結(jié)構(gòu)和SIMD陣列結(jié)構(gòu)的優(yōu)點，能獲得較高的時間和空間并行性，得到了廣泛的研究和應(yīng)用。

Systolic陣列是一個由一些具有預(yù)定功能的節(jié)點有規(guī)則地互聯(lián)起來的專用并行系統(tǒng)[9]。圖1所示是陣列中的數(shù)據(jù)流動的一個方向，數(shù)據(jù)從存儲器(MEM)中以一定的規(guī)律順序流出后，進(jìn)入陣列中某一個方向的第一個節(jié)點，經(jīng)過節(jié)點處理后，將新的結(jié)果流向同一個方向的下一個節(jié)點，并依此反復(fù)直到從最后一個節(jié)點流出的數(shù)據(jù)返回到存儲器。這樣的工作機制很像從心臟流出的血液經(jīng)過順序處理后又流回心臟中，所以Systolic陣列又譯為“心動陣列”[8,10]。為了更好地利用Systolic陣列的并行性，陣列中可以存在多個方向、不同流動速度的數(shù)據(jù)流，這樣可以得到相當(dāng)高的系統(tǒng)數(shù)據(jù)吞吐量。Systolic陣列采用簡單的通信機制，數(shù)據(jù)在節(jié)點之間以流水線方式傳遞，并且整個陣列按同步方式工作；另外，Systolic陣列具有簡單、規(guī)整、模塊性好的特點，只有少量的節(jié)點與外部有IO操作，這能使系統(tǒng)保持較好的處理速度，同時也可與外部IO帶寬之間的平衡，非常適合FPGA實現(xiàn)。

Figure 1 Principle of Systolic array

3 Systolic乘法思想

Systolic乘法是基于Systolic陣列結(jié)構(gòu)的并行矩陣乘法，通過在時間上延遲矩陣輸入元素的方法來達(dá)到一對下標(biāo)合適的矩陣元素就地相乘的目的[11]。

3.1 并行算法描述

在SIMD-MC2模型上的Systolic乘法算法如下：

輸入矩陣A、B：Am*n、Bn*k。

輸出矩陣C：Cm*n在P(i,j)中存在有乘積矩陣元素Cij。

/*其中P(i,j)為陣列第i行第j列計算節(jié)點，Cij為P(i,j)的計算結(jié)果*/

Begin

Fori=1 tompar-do

Forj=1 tokpar-do

Cij?0

WhileP(i,j) receives two inputsaandbdo

Cij?Cij+a*b

if(i

if(j

end while

end for

end for

End

3.2 數(shù)據(jù)輸入規(guī)則

設(shè)輸入矩陣Am,n和Bn,k，輸出為Cm,k，C=A*B。

A矩陣的行向量按行號輸入到對應(yīng)的陣列行，向量中的每個數(shù)據(jù)按列號從大到小依此進(jìn)入陣列的行。其中第i行輸入的向量中第j個數(shù)據(jù)和第i-1行輸入向量中第j-1個數(shù)據(jù)同時進(jìn)入陣列。B矩陣的列向量按列號輸入到對應(yīng)的陣列列，向量中每個數(shù)據(jù)按行號從大到小依此進(jìn)入陣列的列。其中，第i列輸入的向量中第j個數(shù)據(jù)和第i-1列輸入向量中第j-1個數(shù)據(jù)同時進(jìn)入陣列。當(dāng)行列輸入的數(shù)據(jù)匯合到節(jié)點時，進(jìn)行相乘運算。一個3階Systolic乘法的示例如圖2所示。

Figure 2 An instance of Systolic multiplication

3.3 數(shù)據(jù)在陣列中流動規(guī)則

(1)Aij按照行號從小到大的順序依次穿越第i行節(jié)點單元；Bij按照列號從小到大的順序依次穿越第j列節(jié)點單元；Aij和Bij在同一時鐘控制下，直至A、B所有元素穿越節(jié)點單元陣列的整行和整列。

(2)Aik和Bkj同時到達(dá)P(i,j)時相乘并加入Cij中，Cij=∑Aik*Bkj(k=0,1,…,n-1)。

4 Systolic乘法實現(xiàn)

4.1 節(jié)點單元設(shè)計

節(jié)點是構(gòu)成Systolic乘法的基本單元，可以通過修改節(jié)點中的邏輯功能，實現(xiàn)不同場合下Systolic乘法。其主要由一個乘法器、一個加法器和一個用于存儲計算結(jié)果的寄存器構(gòu)成。 其內(nèi)部結(jié)構(gòu)如圖3所示，圖中Row_in與Col_in為節(jié)點的輸入數(shù)據(jù)，clk為同步時鐘，rstn為異步復(fù)位信號，每次重新計算矩陣乘之前需要復(fù)位清除節(jié)點內(nèi)所有的數(shù)據(jù)。在同步時鐘的控制下，Row_in與Col_in為乘法器的兩個輸入數(shù)據(jù)，數(shù)據(jù)相乘的結(jié)果作為累加器的一個輸入，REG是節(jié)點內(nèi)的存儲單元，用于記憶上一次累加的結(jié)果，并作為累加器的另一個輸入數(shù)據(jù)，累加器將數(shù)據(jù)相乘的結(jié)果和REG中的數(shù)據(jù)相加，并將結(jié)果再寫入REG完成一次乘累加過程。當(dāng)陣列中的節(jié)點再無輸入數(shù)據(jù)時，節(jié)點的REG中的數(shù)據(jù)就是最后計算的結(jié)果。

在節(jié)點輸入數(shù)據(jù)乘累加的同時，將剛接受的數(shù)據(jù)分別輸出到對應(yīng)行列的下一個節(jié)點，即Row_out與Col_out。

Figure 3 Architecture of the nodes

4.2 并行矩陣乘法器設(shè)計

Systolic乘法中節(jié)點以普通的二維網(wǎng)孔互聯(lián)，陣列的節(jié)點規(guī)?？梢愿鶕?jù)相乘矩陣的大小和FPGA芯片的資源情況進(jìn)行調(diào)整，假設(shè)FPGA中有N2個節(jié)點，將節(jié)點排列成如圖4所示的N階陣列形式，陣列中首個行節(jié)點和列節(jié)點作為系統(tǒng)的輸入接口，每個節(jié)點有最終數(shù)據(jù)輸出接口，這樣可以使先計算好的節(jié)點結(jié)果輸出到IO端口，有利于流水線處理[8]。

按照Systolic乘法思想，節(jié)點P(1,1)是第一個數(shù)據(jù)匯合的節(jié)點，依此是節(jié)點P(1,2)，P(2,1)，可知數(shù)據(jù)的流動過程是從左上角開始向右下角方向流動的，又根據(jù)輸入時間延遲的特點可知，節(jié)點P(1,1)是結(jié)束數(shù)據(jù)輸入的第一個節(jié)點，節(jié)點P(N,N)是最后一個結(jié)束計算的節(jié)點。所以，Systolic乘法一次矩陣乘計算總共需要計算的時間是從P(1,1)接受數(shù)據(jù)到P(N,N)結(jié)束計算數(shù)據(jù)，以N階陣列為例，總時間為3*N-1，計算時間復(fù)雜度為O(N)。

Figure 4 Structure of Systolic multiplication array

5 實驗和性能分析

5.1 仿真驗證

用于仿真的兩個4*4的8bit矩陣作為輸入實例，陣列規(guī)模為4階矩陣，用VerilogHDL語言編程，并在QuartusII綜合設(shè)計軟件中進(jìn)行仿真，圖5為仿真結(jié)果。

Figure 5 Simulation results of Systolic multiplication

圖5中ina為被乘矩陣，inb為乘矩陣，其中result值為節(jié)點計算的結(jié)果，圖中選擇了最后一個完成計算的節(jié)點P(3,3)，可以看出經(jīng)過從數(shù)據(jù)的輸入到矩陣完成乘法運算總共使用了11個時鐘周期，與3*N-1的結(jié)果吻合。

5.2 實驗驗證

實驗在Altera DE2開發(fā)板上完成了實際測試。開發(fā)板使用了具有5000LEs的Cyclone II EP2C35F672C6 FPGA芯片。用Quartus II 綜合設(shè)計平臺進(jìn)行編譯，仿真驗證的基礎(chǔ)上，將綜合生成的配置文件下載到FPGA芯片中，為了便于驗證結(jié)果，在設(shè)計中為每行、每列添加了一個數(shù)據(jù)流生成模塊(會占用一定的FPGA邏輯資源)，并使用在Quartus II中集成的Signaltap II在線邏輯分析儀進(jìn)行FPGA片上調(diào)試。實驗使用兩個4*4矩陣8 bit矩陣作為實例，在FPGA中使用了4階Systolic陣列結(jié)構(gòu)。Signaltap II調(diào)試結(jié)果如圖6所示，在復(fù)位信號上升沿捕捉到了各行列輸入的結(jié)果，result值為矩陣運算最后一個節(jié)點輸出結(jié)果，經(jīng)過11個周期，其輸入結(jié)果與實際的矩陣運算結(jié)果完全吻合。

Figure 6 Experimental results of Systolic multiplication

5.3 FPGA內(nèi)部資源使用情況

使用Quaruts II軟件進(jìn)行適配，是將綜合工具產(chǎn)生的網(wǎng)標(biāo)文件，針對當(dāng)前的目標(biāo)器件執(zhí)行包括底層邏輯配置、邏輯分割、邏輯優(yōu)化、邏輯布局布線等邏輯映射操作，產(chǎn)生最終的編程下載文件。表1所示為8 bit不同規(guī)模的矩陣相乘的資源占用情況。

Table 1 Resource usage of FPGA表1 FPGA資源使用情況

由表1中的結(jié)果可知，F(xiàn)PGA內(nèi)部資源的占用情況與Systolic乘法陣列中節(jié)點數(shù)量成正比。由于在設(shè)計中每一個節(jié)點使用了一個FPGA自帶的內(nèi)嵌專用乘法硬核，所以減少了對邏輯單元LE(Logic Elements)的占用，當(dāng)FPGA中內(nèi)置64個節(jié)點時，設(shè)計占用了91%的內(nèi)嵌專用乘法硬核，而只占用了大約6%的LE，這樣既能充分利用FPGA資源，也提升了矩陣乘法的計算性能。

5.4 性能分析

本文通過對2*2陣列、4*4陣列、8*8陣列的Systolic乘法實例進(jìn)行分析，得到如表2所示的結(jié)果。

Table 2 Performance of Systolic multiplication表2 Systolic乘法計算性能

由表2可知，基于FPGA的Systolic乘法的計算時間與矩陣規(guī)模成線性關(guān)系，而且能達(dá)到很高的時鐘頻率。設(shè)計中每個時鐘的最大數(shù)據(jù)吞吐量與矩陣的行列輸入節(jié)點數(shù)量有關(guān)，根據(jù)Systolic乘法中輸入規(guī)則，當(dāng)所有的行列輸入節(jié)點都有輸入數(shù)據(jù)時，能達(dá)到最大的輸入數(shù)據(jù)量，所以本設(shè)計輸入時間與矩陣規(guī)模成線性關(guān)系，可以快速實現(xiàn)數(shù)據(jù)輸入。

5.5 與串行矩陣乘法器比較

通過在Altera DE2開發(fā)板上實際測試Systolic乘法的執(zhí)行時間，并與串行矩陣乘法器執(zhí)行時間的最優(yōu)理論值進(jìn)行比較(完成一次乘法運算與加法運算各為1個時鐘周期)。從表3中可以看出，Systolic乘法的計算時間明顯少于串行矩陣乘法器，達(dá)到了較好的加速效果。

Table 3 Execution time comparison of Systolic multiplication and Serial matrix multiplication表3 Systolic乘法與串行矩陣乘法執(zhí)行時間比較

6 結(jié)束語

本文對應(yīng)用在并行處理計算機系統(tǒng)中的Systolic乘法進(jìn)行介紹和分析，并采用FPGA技術(shù)實現(xiàn)了這一算法。通過在Quartus II綜合開發(fā)軟件上設(shè)計并仿真驗證了該方法的邏輯正確性，并在Altera DE2開發(fā)板上進(jìn)行了實際測試，對該方法的性能與資源占用情況進(jìn)行了分析，并與串行矩陣乘法器在計算時間上進(jìn)行了比較。實驗結(jié)果表明該方法可以達(dá)到非常好的綜合性能，特別適合作為一個模塊應(yīng)用于需要實時性矩陣乘計算的嵌入式系統(tǒng)中，有非常好的加速效果。

[1] Dekel E,Nassimi D,Sahni S. Parallel matrix and graph algorithms[J]. SIAM Journal on Computing,1981,10(4):657-675.

[2] Chen Guo-liang.Parallel computing:Architecture,algorithm,programming[M].3rd Edition. Beijing:Higher Education Press,2009.(in Chinese)

[3] Chen Guo-Liang. Design and analysis of parallel algorithms[M].3rd Edition. Beijing:Higher Education Press,2009. (in Chinese)

[4] Karra M C,Bekakos M P,Milovanovic I Z,et al. FPGA implementation of a unidirectional Systolic array generator for matrix-vector multiplication[C]∥IEEE International Conference on Signal Processing and Communications,2007:1.

[5] Horita T,Takanami I.An FPGA-based fault-tolerant 2D Systolic array for matrix multiplications[M]∥Transactions on Computational Science,2011:108-124.

[6] Sonawane D N,Sutaone M S,Malek I. Systolic architecture for integer point matrix multiplication using FPGA[C]∥Proc of the 4th IEEE Conference on Industrial Electronics and Applications,2009:3822-3825.

[7] Vucha M,Rajawat A. Design and FPGA implementation of Systolic array architecture for matrix multiplication[J]. International Journal of Computer Applications,2011,26(3):18-22.

[8] Kung H T. Why Systolic architectures[J]. IEEE Computer,1982,15(1):37-46.

[9] Zheng Fei,Xie Kang-lin.Systolic array and the algebraic specification of the Global view[J]. Computer Engineering and Science,1992,4(3):25-32.(in chinese)

[10] Guerra C,Melhem R G. Synthesis of Systolic algorithm design[J]. Parallel Computing,1989,12(2):155-207.

[11] Wan C R,Evans D J. Nineteen ways of Systolic matrix multiplication[J]. International Journal of Computer Mathematics,1998,68(1-2):1-2.

附中文參考文獻(xiàn):

[2] 陳國良. 并行計算——結(jié)構(gòu)·算法·編程(·第三版·)[M].北京：高等教育出版社，2009.

[3] 陳國良. 并行算法的設(shè)計與分析(·第三版·)[M].北京：高等教育出版社，2009.

[9] 鄭飛,謝康林. Systolic陣列及其全局視圖的代數(shù)描述[J]. 計算機工程與科學(xué),1992,14(3):25-32.

周磊濤(1990-),男,河南鹿邑人，碩士生，研究方向為嵌入式系統(tǒng)與數(shù)控技術(shù)。E-mail:zhoult@mail.ustc.edu.cn

ZHOU Lei-tao,born in 1990,MS candidate,his research interests include embedded system, and control technology.

Research on Systolic multiplication technology based on FPGA

ZHOU Lei-tao1,2,TAO Yao-dong2,LIU Sheng1,2,LI Suo3

(1.University of Chinese Academy of Sciences,Beijing 100039;2.Shenyang Institute of Computing Technology,Chinese Academy of Sciences,Shenyang 110168;3.Shenyang Golding NC Tech. Co.,Ltd.,Shenyang 110168,China)

Systolic multiplication is an algorithm based on the SIMD-MC2model, but it cannot be applied in the embedded system directly. We propose an implementation of Systolic multiplication by FPGA technology, which combines the hardware parallelism of the FPGA and the parallel algorithm together. To realize Systolic multiplication, we design a node array based on the MC2model inside the FPGA by making use of the flexible and programmable features of the FPGA. In practical applications, the number and function of the nodes can be modified flexibly to meet the needs of different scale matrixes and the FPGA resources are fully utilized. Simulation results verify the proposed method, and the actual test results show that this method has a faster speed and a higher real-time performance.

matrix multiplication;field-programmable gate array;algorithm of Systolic;parallel computing

1007-130X(2015)09-1632-05

2014-03-20;

2014-06-20基金項目：國家科技支撐計劃沈陽特種專用數(shù)控機床產(chǎn)業(yè)集群國產(chǎn)數(shù)控系統(tǒng)創(chuàng)新應(yīng)用示范(2012BAF13B08)

TP303

A

10.3969/j.issn.1007-130X.2015.09.005

通信地址：110168 遼寧省沈陽市東陵區(qū)南屏東路16號

Address:16 Nanping Rd East,Dongling District,Shenyang 110168,Liaoning,P.R.China