趙 兵，趙遼英

(杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用研究所，浙江杭州310018)

0 引言

近幾年，現(xiàn)場(chǎng)可編程門陣列正被越來越多的用于各種矩陣運(yùn)算［1］，如定點(diǎn)、浮點(diǎn)數(shù)的運(yùn)算，矩陣乘法［2］，矩陣求逆［3，4］，矩陣特征值分解［5］等。一般的逆矩陣只是對(duì)非奇異矩陣才有意義。實(shí)際問題中遇到的矩陣不一定是方陣，即使是方陣也不一定是非奇異的，廣義逆是奇異方陣和一般矩陣的廣義逆［6］。目前基于可編程門陣列的矩陣求逆設(shè)計(jì)與實(shí)現(xiàn)都只適合非奇異矩陣的求逆，針對(duì)廣義逆的硬件實(shí)現(xiàn)研究未曾報(bào)道。本文提出了基于跡方法求矩陣廣義逆的可編程門陣列實(shí)現(xiàn)方案，對(duì)這一領(lǐng)域的研究具有一定的參考價(jià)值。

1 矩陣的廣義逆求解算法

矩陣的廣義逆求解方法主要有方程求解法、KL分解法、遞推法和跡方法［6］4種，其中跡方法精煉明確，也便于并行計(jì)算設(shè)計(jì)，所以本文選用了此方法來求解矩陣的廣義逆。

1.1 矩陣廣義逆求解的跡方法

設(shè)已知矩陣Am×n的秩為r，矩陣求廣義逆的算法如下:

1.2 基于初等行變換的矩陣求秩

求矩陣偽逆的跡方法需要已知矩陣的秩，矩陣的初等行變換可以確定矩陣的秩［7］。

先給出Hermite標(biāo)準(zhǔn)型的定義［7］。

定義1 設(shè)B∈Cm×nr(r＞0)，且滿足:

(1)B的前行中每一行至少含一個(gè)非零元素，且第一個(gè)非零元素是1，而后m－r行元素為零;

(2)若B中第i行的第一個(gè)非零元素1在第ji列(i=1，2，…，r)，則j1＜j2＜…jr;

(3)B中的j1，j2，…，jr列為單位矩陣Im的前r列。那么就稱B為Hermite標(biāo)準(zhǔn)形。

顯然，任意非零矩陣A∈Cm×nr可通過初等行變換化為Hermite標(biāo)準(zhǔn)形B，且B的前r行線性無關(guān)，其中r就是矩陣的秩。

矩陣的初等行變換有3種:(1)對(duì)調(diào)兩行;(2)以數(shù)k(k≠0)乘某一行的所有元素;(3)把某一行所有元素的k倍加到另一行對(duì)應(yīng)的元素上去。3種初等行變換結(jié)合使用，可以將任意非零矩陣化為Hermite標(biāo)準(zhǔn)型，3種變換中的第1、2兩種變換很容易實(shí)現(xiàn)，但第3種變換比較繁瑣，目的是將矩陣中某元素所在列的其余元素全化為0。針對(duì)第3種變換，文獻(xiàn)8給出了一種矩形對(duì)角線計(jì)算法。通過分析，可以發(fā)現(xiàn)該算法具有很強(qiáng)的并行性，非常適合用可編程門陣列實(shí)現(xiàn)。

2 算法的可編程門陣列實(shí)現(xiàn)

根據(jù)算法描述，將硬件實(shí)現(xiàn)電路劃分為5個(gè)主要模塊:控制模塊、數(shù)據(jù)暫存模塊、矩陣乘法模塊、矩陣求秩模塊、廣義逆求解模塊。硬件系統(tǒng)結(jié)構(gòu)框圖如圖1所示。

圖1 系統(tǒng)硬件結(jié)構(gòu)框圖

2.1 控制模塊和矩陣乘法模塊

控制模塊負(fù)責(zé)協(xié)調(diào)系統(tǒng)各個(gè)功能子模塊的運(yùn)行，控制著數(shù)據(jù)流的流向和各個(gè)模塊的動(dòng)作運(yùn)行的開始和停止。矩陣乘法計(jì)算模塊是由一系列乘累加運(yùn)算組成的，是計(jì)算量比較大的模塊，耗時(shí)也比較多。因此把矩陣乘法模塊單獨(dú)拿出來進(jìn)行設(shè)計(jì)，與矩陣求秩模塊并行來進(jìn)行計(jì)算，提高了設(shè)計(jì)的并行性，從而提高系統(tǒng)的運(yùn)算速度。本文調(diào)用了4個(gè)單精度浮點(diǎn)乘法IP核和4個(gè)單精度浮點(diǎn)加法IP核組成浮點(diǎn)乘累加運(yùn)算單元，進(jìn)而組成4×4浮點(diǎn)矩陣乘法運(yùn)算模塊。

2.2 矩陣求秩模塊

算法中要求已知矩陣的秩r(A)。求秩模塊不僅在最后求解廣義逆模塊用到，而且控制著循環(huán)計(jì)算模塊的循環(huán)計(jì)算次數(shù)。根據(jù)矩形對(duì)角線計(jì)算法［8］設(shè)計(jì)如圖2所示的硬件結(jié)構(gòu)。根據(jù)算法流程對(duì)矩陣求秩模塊進(jìn)行詳細(xì)的模塊劃分。頂層模塊主要包括控制模塊、數(shù)據(jù)輸入、數(shù)據(jù)存儲(chǔ)、接口模塊、選主元模塊、主元化為1(行倍乘運(yùn)算)、行交換和數(shù)據(jù)輸出8個(gè)子功能模塊?？刂颇K(control module)，用來啟動(dòng)和停止數(shù)據(jù)的流動(dòng)，接收狀態(tài)條件以并根據(jù)狀態(tài)條件決定下一步需要做什么。需要將控制模塊設(shè)計(jì)成狀態(tài)機(jī)。整個(gè)模塊的運(yùn)行是在狀態(tài)機(jī)控制下有序進(jìn)行的，把整個(gè)運(yùn)算過程分解為幾個(gè)按一定順序進(jìn)行的子過程來進(jìn)行運(yùn)算實(shí)現(xiàn)，而子過程剛好可以用對(duì)應(yīng)狀態(tài)來表示，子過程進(jìn)行順序計(jì)算的過程剛好對(duì)應(yīng)狀態(tài)轉(zhuǎn)換的過程。因此可以用狀態(tài)機(jī)的思想來實(shí)現(xiàn)整個(gè)運(yùn)算過程。

圖2 矩陣求秩模塊結(jié)構(gòu)

2.3 偽逆計(jì)算模塊

廣義逆求解模塊的核心模塊是循環(huán)計(jì)算模塊。正如前文所述矩陣的秩是一個(gè)關(guān)鍵參數(shù)就體現(xiàn)在這一模塊中，更新矩陣的循環(huán)計(jì)算過程中矩陣的秩r直接控制著循環(huán)計(jì)算的次數(shù)。廣義逆計(jì)算模塊在求出矩陣秩r后開始工作的。核心模塊循環(huán)計(jì)算模塊包括矩陣求跡，矩陣減法，矩陣乘法運(yùn)算。求矩陣跡可以通過對(duì)對(duì)角線元素進(jìn)行累加即可實(shí)現(xiàn)，矩陣乘法可以調(diào)用前邊所用的矩陣乘法模塊，矩陣減法實(shí)現(xiàn)比較簡(jiǎn)單，只需要讀取存儲(chǔ)在存儲(chǔ)器中的矩陣數(shù)據(jù)輸入減法器按順序計(jì)算。

3 實(shí)驗(yàn)仿真結(jié)果分析

軟件程序的編寫和仿真采用Mathworks公司的MATLAB R2010a軟件環(huán)境，輸入非奇異方陣

硬件仿真波形輸出如圖3所示。系統(tǒng)設(shè)計(jì)用Verilog HDL語言來描述，電路的綜合采用Altera公司的Quartus II 9.1軟件完成。結(jié)果數(shù)據(jù)采用單精度浮點(diǎn)十六進(jìn)制數(shù)表示。

圖3 硬件仿真結(jié)果波形圖

從仿真波形可以看出，硬件仿真結(jié)果與軟件仿真結(jié)果完全吻合。求取10次運(yùn)算的平均用時(shí)得出用MATLAB求解示例矩陣廣義逆耗時(shí)約7.5ms;用同樣的矩陣進(jìn)行廣義逆求解運(yùn)算實(shí)驗(yàn)，通過仿真驗(yàn)證可以得出采用現(xiàn)場(chǎng)可編程門陣列的方案僅用時(shí)約15μs，說明對(duì)于4×4的奇異方陣求逆，硬件實(shí)現(xiàn)在保證結(jié)果精確的基礎(chǔ)上運(yùn)算速度提高了近500倍。

4 結(jié)束語

本文通過對(duì)矩陣求廣義逆算法的理論分析，闡述了矩陣求廣義逆的硬件實(shí)現(xiàn)方法，再用Matlab和Quartus II分別進(jìn)行了軟硬件代碼仿真。結(jié)果表明硬件實(shí)現(xiàn)在保證結(jié)果精確的基礎(chǔ)上大大提高了運(yùn)算速度。由于充分利用了硬件的速度優(yōu)勢(shì)，矩陣求廣義逆的可編程門陣列實(shí)現(xiàn)非常適合于要求算法實(shí)時(shí)性高的領(lǐng)域。并且，經(jīng)過適當(dāng)配置，本設(shè)計(jì)可以用來求解其它任意矩陣的廣義逆。因而比采用專用ASIC(專用集成電路)的方法具有更高的靈活性，同時(shí)也節(jié)約了成本。

［1］ 周寧寧，陳燕例，李愛群.基于FPGA技術(shù)的浮點(diǎn)運(yùn)算器的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2005，26(6):1 578－1 581.

［2］ Ioannis Sotiropolos，Ioannis Papaefstathiou.A Fast Parallel Matrix Multiplication Reconfigurable Unit Utilized in Face Recognitions Systems［C］.Prague:IEEE International Conference on Field Programmable Logic and Applications，2009:276－281.

［3］ 王銳，胡永華，馬亮，等.任意維矩陣求逆的FPGA設(shè)計(jì)與實(shí)現(xiàn)［J］.中國集成電路，2007，16(4):51－56.

［4］ 李濤，張忠培.矩陣求逆的FPGA實(shí)現(xiàn)［J］.通信技術(shù)，2010，43(11):147－149.

［5］ 王飛，王建業(yè)，張安堂，等.實(shí)對(duì)稱矩陣特征值分解高速并行算法的FPGA實(shí)現(xiàn)［J］.空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，9(6):67 －74.

［6］ 張賢達(dá).矩陣分析與應(yīng)用［M］.北京:清華大學(xué)出版社，2004∶85－93.

［7］ 房月華，陳萍.矩陣的滿秩分解及其方法［J］.衡水學(xué)院學(xué)報(bào)，2011，13(4):16－18.

［8］ 夏日，張?jiān)Ｉ?對(duì)矩陣初等行變換的算法改進(jìn)［J］.工科數(shù)學(xué)，1994，10(3):121－123.