用于導(dǎo)航解算的矩陣運(yùn)算硬件加速器設(shè)計(jì)

馬鄴晨，李醒飛

(天津大學(xué)精密測(cè)試技術(shù)及儀器國(guó)家重點(diǎn)實(shí)驗(yàn)室，天津 300072)

1 概述

作為慣導(dǎo)系統(tǒng)核心環(huán)節(jié)，導(dǎo)航解算的實(shí)時(shí)性決定著慣導(dǎo)系統(tǒng)能否及時(shí)跟蹤運(yùn)載體的運(yùn)動(dòng)［1］。導(dǎo)航解算從計(jì)算顆粒劃分，主要包括向量加法、三維向量叉乘、四元數(shù)乘法、矩陣-矢量積和矩陣乘法5種運(yùn)算，其中，矩陣乘積計(jì)算量大，耗時(shí)也最多［2］。從解算流程劃分，載體坐標(biāo)系旋轉(zhuǎn)更新模塊，姿態(tài)、速度、位置更新模塊中均包含一次或多次矩陣乘法，初始對(duì)準(zhǔn)中采用的濾波器算法也包含大量的矩陣乘法運(yùn)算［3］。因此，提高浮點(diǎn)矩陣乘法運(yùn)算速度對(duì)慣導(dǎo)系統(tǒng)實(shí)時(shí)性的提高具有重要意義。

之前的浮點(diǎn)矩陣乘積運(yùn)算一般都采用PC或DSP實(shí)現(xiàn)，但這種串行處理器在應(yīng)對(duì)高階數(shù)、高復(fù)雜度的算法時(shí)，更新速率并不高。伴隨超大規(guī)模集成電路技術(shù)的發(fā)展，國(guó)內(nèi)外很多學(xué)者開(kāi)始研究使用具有并行處理能力的FPGA來(lái)計(jì)算浮點(diǎn)矩陣乘積［4］。文獻(xiàn)［5］提出了一種各計(jì)算單元之間不存在任何通訊的并行矩陣乘法器結(jié)構(gòu)，但其所需要的存儲(chǔ)空間隨矩陣維數(shù)的增加而顯著增加，且效率較低。文獻(xiàn)［6］在Xilinx FPGA上設(shè)計(jì)了用于雙精度浮點(diǎn)矩陣乘法的處理單元(Process Element，PE)陣列結(jié)構(gòu)，峰值計(jì)算性能可達(dá)到3 GFLOPS，但其并未采取任何運(yùn)算優(yōu)化措施，且計(jì)算性能隨矩陣維數(shù)增加而下降。文獻(xiàn)［7］基于Nios II系統(tǒng)，應(yīng)用浮點(diǎn)運(yùn)算宏功能模塊設(shè)計(jì)了矩陣硬件加速器，但并未探究其加速機(jī)理;另外雖然該方法總體消耗的周期數(shù)較串行方法有所下降，但部分環(huán)節(jié)效率依舊較低。

針對(duì)上述問(wèn)題，本文分析了FPGA浮點(diǎn)矩陣乘積運(yùn)算加速原理，包括經(jīng)典脈動(dòng)陣列結(jié)構(gòu)并行提速以及近兩年新提出的用于增強(qiáng)矩陣處理并行度的數(shù)據(jù)空間、迭代空間處理方法。基于上述原理，編寫(xiě)出高性能浮點(diǎn)矩陣乘積模塊，用于提高計(jì)算速度;在數(shù)據(jù)交換方面，摒棄傳統(tǒng)傳輸模式，利用DMA大批量高速傳輸速度優(yōu)勢(shì)進(jìn)行數(shù)據(jù)交換，從而設(shè)計(jì)出性能良好的浮點(diǎn)矩陣乘積加速器。最后利用嵌入式邏輯分析儀SignalTap II對(duì)運(yùn)算過(guò)程進(jìn)行性能實(shí)測(cè)。

2 FPGA浮點(diǎn)矩陣乘積加速原理

2.1 計(jì)算單元陣列結(jié)構(gòu)

矩陣乘法作為操作次數(shù)大于輸入輸出象元的運(yùn)算，屬于計(jì)算受限類(lèi)型。常采用具有并行-流水線特點(diǎn)的脈動(dòng)(systolic)陣列［8］實(shí)現(xiàn)并行計(jì)算。該陣列由功能相同或相近的PE組成，運(yùn)算中數(shù)據(jù)受同一個(gè)時(shí)鐘控制，在各PE間沿著預(yù)設(shè)的方向流動(dòng)，在數(shù)據(jù)流流入、流出陣列的過(guò)程中完成運(yùn)算。以 Cm×n=Am×p×Bp×n為例，m 個(gè) PE 串聯(lián)而成的一維 systolic線陣運(yùn)算過(guò)程如下:B陣中的數(shù)據(jù)按照行序串行流過(guò)陣列中每一個(gè)PE單元，同時(shí)A陣形成m條數(shù)據(jù)流分別輸入相應(yīng)的單元，在每n個(gè)周期內(nèi)保持恒定，以列序p循環(huán)。2個(gè)數(shù)據(jù)在PE中相遇進(jìn)行相應(yīng)運(yùn)算，并把形成的部分結(jié)果存放在加法循環(huán)回路中，這樣當(dāng)B陣傳輸結(jié)束時(shí)，各PE元分別輸出結(jié)果矩陣各行計(jì)算結(jié)果。

與微處理器串行實(shí)現(xiàn)方法2×m×p×n，即ο(n3)的計(jì)算復(fù)雜性相比，采用一維systolic線性陣列結(jié)構(gòu)，計(jì)算的復(fù)雜性降低至2×p×n，即ο(n2/m)。矩陣運(yùn)算時(shí)空映射而得出的二維脈動(dòng)陣列能將矩陣計(jì)算的復(fù)雜性降至ο(n2/mp)。

2.2 分塊映射策略

應(yīng)對(duì)不同規(guī)模的矩陣，尤其針對(duì)較大矩陣，簡(jiǎn)單依賴(lài)增大陣列規(guī)模，以資源換速度的計(jì)算方法會(huì)受到片上資源約束，因而需將大規(guī)模問(wèn)題映射到較小或(固定)規(guī)模的陣列上?，F(xiàn)今常用的映射方法是循環(huán)分塊［9］，即以局部并行、全局串行的方式完成調(diào)度。其核心思想是:將計(jì)算過(guò)程分為2層循環(huán)，內(nèi)層并行完成矩陣運(yùn)算，外層通過(guò)有限狀態(tài)機(jī)完成過(guò)程控制、外部存儲(chǔ)器與計(jì)算陣列之間的數(shù)據(jù)傳輸。

針對(duì)循環(huán)中大批量的數(shù)據(jù)訪問(wèn)，對(duì)數(shù)據(jù)空間分割及迭代空間合并是增加訪問(wèn)并行度的有效手段［10］。其思路是:通過(guò)建模獲取循環(huán)控制流下訪存密集數(shù)組的訪問(wèn)形式及相關(guān)性，若迭代空間中矩陣數(shù)目大于1，且未遇到新矩陣，則依照迭代空間維度順序由內(nèi)向外將所有數(shù)據(jù)空間內(nèi)矩陣分為(N×所需寬度)個(gè)矩陣。為不失分塊后矩陣間相關(guān)性，再合并迭代空間，合并過(guò)程減少了循環(huán)次數(shù)，因而狀態(tài)機(jī)跳轉(zhuǎn)次數(shù)也降低，循環(huán)迭代過(guò)程所占的延時(shí)降低。以A×B，分塊數(shù)4為例，處理前后的數(shù)據(jù)訪問(wèn)為:

其中，array分別為矩陣A，B的行、列向量;a1～ a4，b1～b4分別為矩陣A，B分塊后的子矩陣。

數(shù)據(jù)空間和迭代空間經(jīng)優(yōu)化后，設(shè)處理器空間的PE單元數(shù)為Sp，矩陣A和B存儲(chǔ)模塊深度為St1，St2。此時(shí)加載矩陣A，B，加載并存儲(chǔ)結(jié)果矩陣C帶來(lái)的數(shù)據(jù)傳輸量分別為:

可見(jiàn)St1的大小對(duì)數(shù)據(jù)傳輸量沒(méi)有影響，故不考慮其他因素時(shí)可將St1設(shè)為1，即讓A矩陣的存儲(chǔ)模塊退化為寄存器，給St2留更多余量，可增大其值以進(jìn)一步減少數(shù)據(jù)傳輸耗時(shí)，提高運(yùn)算速度。

3 浮點(diǎn)矩陣乘積加速器設(shè)計(jì)

基于多處理器核FPGA/SOPC的導(dǎo)航解算以解算模塊流水線化、模塊內(nèi)各粒度計(jì)算單元同時(shí)進(jìn)行的方式［7］完成解算任務(wù)。處理器調(diào)度各運(yùn)算單元完成操作數(shù)的讀取、運(yùn)算、結(jié)果存儲(chǔ)。

對(duì)于完成浮點(diǎn)矩陣乘積的運(yùn)算單元，其任務(wù)可分為矩陣計(jì)算和對(duì)緩沖區(qū)數(shù)據(jù)訪問(wèn)兩部分。上述兩方面著手提升運(yùn)算速度，據(jù)此設(shè)計(jì)的加速器總體結(jié)構(gòu)如圖1所示。作為導(dǎo)航解算中的協(xié)處理器，加速器采用硬件方法完成復(fù)雜耗時(shí)的矩陣乘積運(yùn)算，同時(shí)還可以通過(guò)Avalon-MM總線與導(dǎo)航系統(tǒng)中其他模塊通信。

各模塊設(shè)計(jì)說(shuō)明如下:

(1)浮點(diǎn)矩陣乘積模塊:基于浮點(diǎn)矩陣乘積加速原理制成的浮點(diǎn)矩陣乘積單元由矩陣A，B存儲(chǔ)模塊、寄存器、高速緩存器、高性能點(diǎn)乘、求和計(jì)算單元5個(gè)部分組成。其結(jié)構(gòu)如圖2所示。

圖1 浮點(diǎn)矩陣乘積加速器總體結(jié)構(gòu)

圖2 浮點(diǎn)矩陣乘法單元結(jié)構(gòu)

應(yīng)用中，依據(jù)數(shù)據(jù)空間分割及迭代空間合并理論選擇矩陣分塊參數(shù)vectorsize，block的最優(yōu)值。矩陣乘法宏功能模塊據(jù)此參數(shù)生成相應(yīng)規(guī)模的DSP block二維陣列完成點(diǎn)乘計(jì)算。陣列中DSP block完成18×18乘積和運(yùn)算并兼具高頻流水線、反饋累加與級(jí)聯(lián)功能，使得內(nèi)層迭代僅耗(vectorsize/(2×block))個(gè)時(shí)鐘周期，再經(jīng)(A矩陣的列數(shù)/vectorsize)次迭代運(yùn)算，高性能求和計(jì)算單元將中間量對(duì)應(yīng)相加，得到結(jié)果矩陣C。另外優(yōu)化為部分寄存器的A矩陣存儲(chǔ)模塊由M144K充當(dāng)，相比B矩陣帶寬較窄，使用中需要在A當(dāng)?shù)丶拇嫫髦写娣哦鄠€(gè)數(shù)據(jù)以拓展帶寬，使數(shù)據(jù)加載用時(shí)不超過(guò)處理耗時(shí)，達(dá)到較高的占空比。

加速器中設(shè)定矩陣分塊參數(shù)，例化生成的硬件描述語(yǔ)言文件，再根據(jù)時(shí)序圖將運(yùn)算過(guò)程劃分為數(shù)據(jù)加載、運(yùn)算開(kāi)啟、運(yùn)算處理、結(jié)果輸出4個(gè)狀態(tài)，編寫(xiě)狀態(tài)機(jī)控制乘積單元運(yùn)算，完成浮點(diǎn)矩陣乘積運(yùn)算。

(2)DMA［11］:FPGA/SOPC 平臺(tái)上傳統(tǒng)的Avalon-MM(Avalon Memory Mapped Interface)總線數(shù)據(jù)傳輸方式基于地址映射方式，控制信號(hào)繁多，尤其在大批量數(shù)據(jù)傳輸時(shí)，CPU中斷載荷負(fù)擔(dān)重，導(dǎo)致傳輸速率較低。但同樣采用Avalon-MM總線的DMA以單向點(diǎn)對(duì)點(diǎn)方式傳輸，用精簡(jiǎn)的控制方式及高速流模式進(jìn)行數(shù)據(jù)傳輸，不會(huì)影響CPU的其他工作。大批量數(shù)據(jù)傳輸時(shí)具有非常高的傳輸效率。

SOPC中DMA數(shù)據(jù)傳輸依賴(lài)于硬件系統(tǒng)搭建和DMA控制器控制。加速器硬件系統(tǒng)需配置處理器、PLL、DMA、外部存儲(chǔ)控制器等組件，設(shè)置DMA長(zhǎng)度寄存器位寬、構(gòu)建方式、基址和中斷級(jí)，連接讀寫(xiě)主端口與源、目的地址所在的組件?？刂品绞讲捎脼镹ios II系統(tǒng)提供設(shè)備驅(qū)動(dòng)程序的HAL庫(kù)中功能語(yǔ)句，而非寄存器方式。

(3)組件接口:浮點(diǎn)矩陣乘積模塊只有添加MM總線讀寫(xiě)從機(jī)并進(jìn)行封裝后才能被Nios II系統(tǒng)調(diào)用，另外DMA傳輸單個(gè)浮點(diǎn)數(shù)用時(shí)不恒定，而矩陣乘積運(yùn)算的數(shù)據(jù)加載要求字加載速度恒定在一個(gè)時(shí)鐘周期，這樣就出現(xiàn)數(shù)據(jù)傳送速率不匹配。故在編寫(xiě)MM讀寫(xiě)從機(jī)程序的基礎(chǔ)上采用FIFO實(shí)現(xiàn)數(shù)據(jù)傳輸與加載間的同步。使用存儲(chǔ)器處理跨域傳輸，避免了握手信號(hào)和邏輯同步處理機(jī)制在同步設(shè)計(jì)中大量的時(shí)鐘周期消耗，保證了通信雙方較高的數(shù)據(jù)吞吐率。設(shè)計(jì)中編寫(xiě) FIFO讀寫(xiě)時(shí)序，使得FIFO能在DMA數(shù)據(jù)線上數(shù)據(jù)正確時(shí)將其讀入，當(dāng)FIFO中暫存的數(shù)據(jù)量達(dá)到指定數(shù)目后，再依照加載時(shí)序讀出，實(shí)現(xiàn)數(shù)據(jù)傳輸與加載間的同步。

浮點(diǎn)矩陣乘積加速器硬件系統(tǒng)設(shè)計(jì)完成后，進(jìn)行軟件部分設(shè)計(jì)。軟件部分任務(wù)是控制DMA實(shí)現(xiàn)RAM與自定義外設(shè)之間的流模式數(shù)據(jù)傳輸。為保證計(jì)算結(jié)果的及時(shí)輸出，注冊(cè)PIO中斷標(biāo)志量，使其在浮點(diǎn)矩陣乘積模塊計(jì)算結(jié)果有效時(shí)置1，并在中斷服務(wù)子程序中完成DMA2到RAM2之間的數(shù)據(jù)輸送。系統(tǒng)主程序流程如圖3所示。

圖3 系統(tǒng)主程序流程

4 實(shí)驗(yàn)分析

4.1 浮點(diǎn)矩陣乘積模塊功能測(cè)試

本文以非方陣乘積 A10×8×B8×12為例，對(duì)浮點(diǎn)矩陣乘積模塊進(jìn)行功能仿真測(cè)試。選取A，B矩陣vectorsize=8，blocksize=2，testbench 腳本中時(shí)鐘信號(hào)200 MHz，在Modelsim_altera平臺(tái)上進(jìn)行仿真。仿真測(cè)試結(jié)果如圖4所示。

圖4中整個(gè)運(yùn)算過(guò)程消耗了1885 ns，即377個(gè)時(shí)鐘周期。浮點(diǎn)操作數(shù)表達(dá)式為:

其中，F(xiàn)Hz表示系統(tǒng)運(yùn)行頻率;tload，tprocess，tnaive分別表示數(shù)據(jù)加載、處理、簡(jiǎn)單算法時(shí)間。依據(jù)上述公式及仿真結(jié)果得出:時(shí)鐘信號(hào)200 MHz時(shí)浮點(diǎn)矩陣乘積模塊的浮點(diǎn)操作數(shù)達(dá)到了2.09 GFLOPS。由于浮點(diǎn)矩陣乘積單元的峰值頻率可以達(dá)到412 MHz［12］，因此峰值計(jì)算性能可達(dá)到4.30 GFLOPS。

使用浮點(diǎn)矩陣乘積模塊與在PC上使用Matlab計(jì)算矩陣乘積的部分結(jié)果對(duì)比如表1所示。從運(yùn)算結(jié)果可以看出，浮點(diǎn)矩陣乘積模塊可以正確完成乘積計(jì)算。只是乘積模塊直接計(jì)算單精度浮點(diǎn)數(shù)，而Matlab中間過(guò)程以雙精度形式進(jìn)行，結(jié)果轉(zhuǎn)換為單精度形式輸出，從而導(dǎo)致了結(jié)果的微小差異。

圖4 Modelsim仿真測(cè)試結(jié)果

表1 部分運(yùn)算結(jié)果對(duì)照

4.2 浮點(diǎn)矩陣乘積加速器性能實(shí)測(cè)

將浮點(diǎn)矩陣乘積加速器的.sof文件下載至Altera DE3開(kāi)發(fā)板，在Nios EDA平臺(tái)上以硬件方式運(yùn)行軟件程序，使用嵌入式邏輯分析儀SignalTap II對(duì)浮點(diǎn)矩陣乘積加速器的計(jì)算性能進(jìn)行測(cè)試，選取CPU的時(shí)鐘信號(hào)作為采集時(shí)鐘，實(shí)時(shí)采集得到的信號(hào)如圖5所示。由實(shí)測(cè)圖可以看出，浮點(diǎn)矩陣乘積加速器計(jì)算時(shí)序與功能測(cè)試吻合。從數(shù)據(jù)讀取、矩陣運(yùn)算到結(jié)果輸出一共消耗了842個(gè)時(shí)鐘周期。在200 MHz時(shí)鐘實(shí)驗(yàn)條件下，耗時(shí)4.21 μs。各種浮點(diǎn)矩陣乘積方法的性能分析如表2所示，本文方法較其他文獻(xiàn)中硬、軟件實(shí)現(xiàn)方法速度分別提升71.3%，78%。

圖5 SignalTap II實(shí)測(cè)圖

表2 浮點(diǎn)矩陣乘積方法的性能分析

5 結(jié)束語(yǔ)

為提高導(dǎo)航解算中矩陣乘積運(yùn)算速度，本文從硬件實(shí)現(xiàn)角度設(shè)計(jì)了應(yīng)用于Nios II系統(tǒng)的矩陣運(yùn)算加速器。首先分析了FPGA用于浮點(diǎn)矩陣運(yùn)算的加速原理，據(jù)此編寫(xiě)性能優(yōu)越的矩陣乘積模塊并使用Modelsim進(jìn)行功能仿真驗(yàn)證。之后設(shè)計(jì)DMA傳輸通道及外設(shè)，并將整體封裝成自定義組件作為Nios II系統(tǒng)的協(xié)處理器。為驗(yàn)證其實(shí)際特性，將所有程序下載至Altera DE3開(kāi)發(fā)板進(jìn)行實(shí)測(cè)，利用SignalTap II拾取的信號(hào)與其他實(shí)現(xiàn)方法對(duì)比表明，本文設(shè)計(jì)的矩陣運(yùn)算硬件加法器具有明顯的速度優(yōu)勢(shì)，有利于提高導(dǎo)航解算的實(shí)時(shí)性。

［1］秦永元.慣性導(dǎo)航［M］.北京:科學(xué)出版社，2006.

［2］林燦龍，馬龍華，吳鐵軍，等.高動(dòng)態(tài)條件下的捷連慣導(dǎo)并行算法研究［J］.彈箭與制導(dǎo)學(xué)報(bào)，2012，32(2):1-5.

［3］李宗濤.高動(dòng)態(tài)捷連慣導(dǎo)系統(tǒng)的并行實(shí)現(xiàn)分析［D］.杭州:浙江大學(xué)，2011.

［4］Underwood K.FPGAsvs.CPUs:Trendsin Peak Floating-point Performance［C］//Proc.of International Symposium on Field Programmable Gate Arrays.Monterey，USA:ACM Press，2004:171-180.

［5］Campbell S J，Khatri S P.Resource and Delay Efficient Matrix Multiplication Using NewerFPGA Devices［C］//Proc.of the 16th ACM Great Lakes Symposium onVLSI.Philadelphia，USA:ACM Press，2006:308-311.

［6］田 翔，周 凡，程耀武，等.基于FPGA的實(shí)時(shí)雙精度浮點(diǎn)矩陣乘法器設(shè)計(jì)［J］.浙江大學(xué)學(xué)報(bào):工學(xué)版，2008，42(9):1611-1615.

［7］許 芳，席 毅，陳 虹，等.基于 FPGA/Nios-II的矩陣運(yùn)算硬件加速器設(shè)計(jì)［J］.電子測(cè)量與儀器學(xué)報(bào)，2011，25(4):377-382.

［8］Dutta H，HannigF，Ruckdeschel H，et al.Efficient Control Generation for Mapping Nested Loop Programs onto Processor Arrays［J］.Journal of Systems Architecture，2007，53(5):300-309.

［9］Wolfe M J，Shanklin C，Ortega L.High Performance Compilers for Parallel Computing［M］.Boston，USA:Addison-Wesley Longman Publishing Co.，Inc.，1995.

［10］Asher Y，Rotem N.Automatic Memory Partitioning:Increasing Memory Parallelism via Data Structure Partitioning［C］//Proc.of International Conference on Hardware/Software Codesign and System Synthesis.Scottsdale，USA:IEEE Press，2010:155-161.

［11］Altera Corporation.ALTERA Embedded Peripherals IP User Guide［EB/OL］.(2011-06-10).http://www.altera.com.cn/literature/ug/ug_embedded_ip.pdf.

［12］Altera Corporation.ALTERA Floating-point Megafunctions User Guide ［EB/OL］.(2011-06-10).http://www.altera.com.cn/literature/ug/ug_altfp_mfug.pdf.

［13］雷 晶，金心宇，王 銳.矩陣相乘的并行計(jì)算及其DSP 實(shí)現(xiàn)［J］.傳感技術(shù)學(xué)報(bào)，2006，19(3):737-740.