基于FPGA的Systolic乘法技術研究*

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

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

基于FPGA的Systolic乘法技術研究*

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

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

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

矩陣乘法；現場可編程門陣列；Systolic乘法；并行計算

1 引言

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

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

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

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

2 Systolic陣列

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

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

Figure 1 Principle of Systolic array

3 Systolic乘法思想

Systolic乘法是基于Systolic陣列結構的并行矩陣乘法，通過在時間上延遲矩陣輸入元素的方法來達到一對下標合適的矩陣元素就地相乘的目的[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)的計算結果*/

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 數據輸入規(guī)則

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

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

Figure 2 An instance of Systolic multiplication

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

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

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

4 Systolic乘法實現

4.1 節(jié)點單元設計

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

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

Figure 3 Architecture of the nodes

4.2 并行矩陣乘法器設計

Systolic乘法中節(jié)點以普通的二維網孔互聯，陣列的節(jié)點規(guī)?？梢愿鶕喑司仃嚨拇笮『虵PGA芯片的資源情況進行調整，假設FPGA中有N2個節(jié)點，將節(jié)點排列成如圖4所示的N階陣列形式，陣列中首個行節(jié)點和列節(jié)點作為系統(tǒng)的輸入接口，每個節(jié)點有最終數據輸出接口，這樣可以使先計算好的節(jié)點結果輸出到IO端口，有利于流水線處理[8]。

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

Figure 4 Structure of Systolic multiplication array

5 實驗和性能分析

5.1 仿真驗證

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

Figure 5 Simulation results of Systolic multiplication

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

5.2 實驗驗證

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

Figure 6 Experimental results of Systolic multiplication

5.3 FPGA內部資源使用情況

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

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

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

5.4 性能分析

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

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

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

5.5 與串行矩陣乘法器比較

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

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

6 結束語

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

附中文參考文獻:

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

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

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

周磊濤(1990-),男,河南鹿邑人，碩士生，研究方向為嵌入式系統(tǒng)與數控技術。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基金項目：國家科技支撐計劃沈陽特種專用數控機床產業(yè)集群國產數控系統(tǒng)創(chuà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