楊苗苗，郭 鋒，李向東，張永亮

（陸軍工程大學(xué)軍械士官學(xué)校，湖北 武漢 430070）

MIMO（multiple-input multiple-output）技術(shù)[1]作為當(dāng)前無線通信領(lǐng)域的關(guān)鍵技術(shù)之一[2]，可以在提高通信系統(tǒng)的傳輸速率、提升通信系統(tǒng)的傳輸質(zhì)量的同時，不增加額外的帶寬消耗。在未來的通信發(fā)展中占據(jù)越來越重要的地位[3]。

MIMO接收機(jī)的一個關(guān)鍵特性是它依賴矩陣運算，包括矩陣乘法、矩陣加法和矩陣求逆[4]等。例如，在MIMO接收機(jī)的檢測模塊，迫零（Zero Forcing，ZF）檢測算法[5]、最小均方誤差（Minimum Mean square Error，MMSE）檢測算法[6]、基于MMSE的并行干擾消除（parallel Interference Cancellation，PIC）檢測算法[7]等的核心算法之一都是矩陣求逆運算。傳統(tǒng)的矩陣求逆算法是在按順序執(zhí)行的微處理器上實現(xiàn)，他們的效率，特別是實時應(yīng)用程序的效率無法滿足當(dāng)前的性能需求。為了提高性能，文獻(xiàn)[8]研究了高階矩陣求逆的超大規(guī)模集成電路（Very Large Scale Integrated circuit，VLSI）陣列架構(gòu)，雖然ASIC架構(gòu)可以顯著提高性能，但是，顯而易見的，ASIC主要是剛性結(jié)構(gòu)，靈活性差。為此，一種高靈活性、高性能的粗粒度動態(tài)可重構(gòu)體系結(jié)構(gòu)[9]被提出。

目前最常用于處理矩陣求逆運算的算法有基于QR的矩陣求逆、伴隨矩陣求逆以及基于LU的矩陣求逆等。其中，伴隨矩陣求逆的運算過程因包含伴隨矩陣和矩陣模求解而顯得復(fù)雜又繁重，應(yīng)用中一般不采用；QR分解求逆和LU分解求逆運算的基本思想相似，都是通過高斯消元將矩陣變換為上下2個三角矩陣，通過對子矩陣求逆最終獲得原矩陣的逆。但是QR分解運算在硬件上要求定制[6-10]，且其并行計算能力相比LU分解法更弱。綜合硬件架構(gòu)和算法特性考慮，本文針對LU矩陣求逆運算提出了一種基于動態(tài)可重構(gòu)陣列的高效、可擴(kuò)展的實現(xiàn)方法。通過對算法子數(shù)據(jù)流特性的分析，針對每個子算法的特性設(shè)計各自的映射方案，并將其映射到可重構(gòu)架構(gòu)中。該映射結(jié)構(gòu)提高核心算子可重構(gòu)計算陣列流水效率，增加互連拓展的靈活性，減少硬件開銷，增加資源利用率。

本文剩余部分的結(jié)構(gòu)如下：第一節(jié)主要介紹矩陣求逆算法的原理，分析歸納其數(shù)據(jù)流特征；第二節(jié)介紹了可重構(gòu)平臺及其具體陣列結(jié)構(gòu)，通過對數(shù)據(jù)流的分析，將矩陣求逆的運算過程映射到該可重構(gòu)陣列中；第三節(jié)將本文的矩陣求逆實現(xiàn)方案與現(xiàn)有方案在性能、靈活性等方面進(jìn)行了對比與分析；第四節(jié)對整個工作加以總結(jié)。

1 矩陣求逆核心算子數(shù)據(jù)流特性分析

1.1 矩陣求逆算法分析

LU分解求逆運算分為3個步驟，首先對矩陣Ann進(jìn)行高斯消元，經(jīng)過一系列變換，將其表示為上三角矩陣U和下三角矩陣L的乘積。然后對A進(jìn)行求逆運算，其過程包含三角矩陣求逆以及三角矩陣乘。下面對這3個步驟進(jìn)行一一分析。

1.1.1 LU分解

LU分解數(shù)學(xué)公式如下：

首先，對a11同一列下方數(shù)據(jù)進(jìn)行消元，再以a22為列主元，對已消元的矩陣進(jìn)行第二列消元，以此類推，將本次消元得的矩陣作為下次消元的主矩陣進(jìn)行消元，重復(fù)操作直至運算完成。

對于消元過程中的除法運算來講，其運算周期較長，消元基行與消元系數(shù)相乘的運算過程中存在數(shù)據(jù)等待現(xiàn)象，因此需要將消元系數(shù)復(fù)制多份，及時地傳輸至其需要的多個計算單元中。而LU分解過程中同列消元元素之間的運算并沒有直接的數(shù)據(jù)關(guān)系，因此可以并列執(zhí)行。

1.1.2 三角矩陣求逆

設(shè)下三角矩陣L的逆矩陣為R，那么矩陣L求逆的公式如下：

相對應(yīng)的上三角矩陣U的求逆公式如下：

從公式（2）、（3）可以看出，同列元素之間數(shù)據(jù)關(guān)系緊密，比如在求rji時，必須知道其上列的所有元素，也就是執(zhí)行循環(huán)時必須從上至下，但同行元素可并列執(zhí)行。

1.1.3 三角矩陣乘

由公式（4）知，A的逆矩陣是由U和L的逆矩陣相乘得來，U的逆矩陣逐行與L的逆矩陣相乘，則得出A的逆矩陣的每一行元素，如此循環(huán)迭代出所有元素。從理論層面來講，若不考慮硬件資源的占用，矩陣U的一行元素可同時與矩陣L的所有列元素并行執(zhí)行乘法運算，大大提高了數(shù)據(jù)流水線以及并行運算度。

1.2 矩陣求逆數(shù)據(jù)流分析

如圖1所示，在矩陣求逆數(shù)據(jù)流運算的3個步驟中，涉及3種運算類別。在矩陣LU分解和三角矩陣求逆階段計算均由除運算、乘運算、加運算構(gòu)成；三角矩陣乘階段則由乘和加運算構(gòu)成。

圖1 矩陣求逆數(shù)據(jù)流

這3個運算階段有相同的計算類型單元，將這些單元聚集區(qū)稱之為域，則LU分解求逆矩陣的數(shù)據(jù)流具有以下特征：域內(nèi)數(shù)據(jù)計算傳輸具有單向規(guī)整性，批量數(shù)據(jù)并行傳輸；而域間數(shù)據(jù)流的運算層次結(jié)構(gòu)不一，數(shù)據(jù)流水的傳播具有發(fā)散性或者收斂累和傳輸。

2 可重構(gòu)平臺介紹及矩陣求逆算子映射

2.1 RASP架構(gòu)介紹

本文將矩陣求逆算法映射到可重構(gòu)處理器系統(tǒng)架構(gòu)RASP之中。RASP的整體架構(gòu)如圖2所示，RASP可重構(gòu)系統(tǒng)由3部分組成：一是為可重構(gòu)陣列提供運算的數(shù)據(jù)存儲部分，包括常數(shù)和共享存儲器；二是可重構(gòu)陣列，作為RASP架構(gòu)的核心部分，主要完成陣列計算，通過可重構(gòu)單元間的互連，形成高效流水線運算模式，將送入陣列數(shù)據(jù)處理完成后送回存儲單元；三是配置部分，根據(jù)使用場景向數(shù)據(jù)存儲部分和可重構(gòu)陣列提供配置信息。

圖2 RASP整體架構(gòu)

在可重構(gòu)處理器系統(tǒng)中，包含4個結(jié)構(gòu)完全相同的可重構(gòu)陣列（Reconfigurable Compute Array，RCA）?？芍貥?gòu)陣列的基本結(jié)構(gòu)框圖如圖3所示，每個RCA主要包括4個部分：輸入輸出FIFO，配置輸入寄存器，臨時數(shù)據(jù)寄存器以及計算單元陣列（Processing Element Array，PEA）。

圖3 RCA結(jié)構(gòu)圖

PEA陣列的具體運算結(jié)構(gòu)如圖4所示，其中除法陣列在首行，包含8個除法子陣列，可以并列執(zhí)行運算；通用計算陣列是6*8規(guī)模的二維陣列，可應(yīng)用于諸多場景計算如LU分解和三角矩陣求逆；累加陣列為2*8規(guī)模的二維陣列，是通用陣列的協(xié)處理陣列，主要作用是完成大量數(shù)據(jù)的累加運算。累加陣列與通用陣列協(xié)同完成運算，并行度高，且不占用過高的硬件資源。本文的矩陣求逆算子主要是映射在PEA陣列結(jié)構(gòu)中。

圖4 PEA陣列結(jié)構(gòu)圖

2.2 核心子算子映射方案

2.2.1 LU分解映射

一般情況下，隨著矩陣階數(shù)的增大，運算中所需硬件資源也逐步增大。而RCA中的硬件資源是有限的，因此當(dāng)處理階數(shù)高于陣列PEA數(shù)量的矩陣時，必須對計算任務(wù)進(jìn)行切割處理，以適應(yīng)陣列的大規(guī)模運算需求。

本文采用行列式分塊順次映射的方法，以96階矩陣為例，將計算劃分為3個模塊，首先，將3個96*32的子矩陣一一映射到3個RCA上，此時每行數(shù)據(jù)一次性即可完成映射。再切割96*32的矩陣成4個24*32的子矩陣，映射到4個RCA上單獨完成計算，且同一列的4個子矩陣可實現(xiàn)并行計算，那么切割后的矩陣如公式（5）所示：

將按行切割的4組數(shù)據(jù)一一映射到RCA0到RCA3進(jìn)行計算，例如第一行[A11A12A13]3塊數(shù)據(jù)在RCA0內(nèi)經(jīng)行消元計算，第二行[A21A22A23]3塊數(shù)據(jù)在RCA1內(nèi)經(jīng)行消元計算，以此類推。在行列式分塊順次計算矩陣LU分解計算過程中，遵循逐列消元、逐行計算的原則進(jìn)行。單個陣列的映射圖如圖5所示。

圖5 行列式分塊順次計算矩陣LU分解

2.2.2 三角矩陣求逆映射

由三角矩陣求逆迭代運算分析可知，其緊密的數(shù)據(jù)關(guān)系要求運算必須逐行進(jìn)行。三角矩陣求逆運算過程如圖6所示，為了維持最高的并行計算度，從主對角線元素開始，依次向內(nèi)逐行求解次對角線元素。對于第n行對角線而言，待求元素共97-n個，每個元素上方共有n-1個元素，因此對于求解第n行每個元素而言需要n-1組乘、n-2次加以及1次乘系數(shù)。

圖6 迭代計算三角矩陣逆矩陣元素

數(shù)據(jù)映射如圖7所示，將通用計算陣列分為上下2個區(qū)域，這2個區(qū)域包含相同的運算單元。1個基本計算單元包含2個乘法運算和1個乘積累加運算。這樣相同的上下運算區(qū)域?qū)?shù)據(jù)流分成了兩級流水，流水運算過程有2個特點，一是運算過程中先進(jìn)行乘法運算，不存在中間值傳輸阻滯問題；二是采用單個PE循環(huán)計算同一個元素，因此即使上下區(qū)域內(nèi)每一個PE接收數(shù)據(jù)不同步，也不影響最終的結(jié)果。

圖7 三角矩陣求逆映射

最后，當(dāng)累加陣列完成運算后，將和傳輸至乘單元中進(jìn)行乘系數(shù)操作，前后數(shù)據(jù)運算等待時間僅為（A+T）cycle。該映射方法并行度高，同時采用的流水快速，可以更高效地解決三角矩陣求逆。

2.2.3 三角矩陣相乘映射

三角矩陣相乘相對簡單，采用常規(guī)的乘法和累加單元即可，如圖8所示。其中，累加陣列的結(jié)構(gòu)與PEA內(nèi)累加陣列結(jié)構(gòu)相同。

圖8 三角矩陣相乘映射

3 實驗結(jié)果及分析對比

本文基于RASP可重構(gòu)架構(gòu)的實現(xiàn)方法可適用于任意階矩陣，具有高度的靈活性。對于高階矩陣，當(dāng)矩陣階數(shù)為48時，操作域的利用率為50%，而在96階矩陣消元中，利用率可達(dá)100%。所以，本文的方法在高階矩陣應(yīng)用時效果最好。本文將基于RASP可重構(gòu)架構(gòu)實現(xiàn)矩陣求逆方法的實驗結(jié)果與其他不同的矩陣求逆方法包括DSP、FPGA等比較，實驗結(jié)果表明，相比DSP，本文提出的矩陣求逆在3-9階矩陣時，性能是DSP的幾十倍，計算性能遠(yuǎn)高于DSP，同時本方法還可用于高階矩陣。與FPGA相比，雖然低階矩陣性能略低，但是對于高階的36階矩陣，性能提高了1.19倍，接近ASIC性能，相比于ASIC架構(gòu)實現(xiàn)，本方法又同時兼顧了高性能和高靈活性的要求。矩陣求逆性能指標(biāo)對比見表1。

表1 矩陣求逆性能指標(biāo)對比

4 結(jié)論

矩陣求逆是通信領(lǐng)域的核心算法之一，本文提出了一種基于動態(tài)可重構(gòu)陣列的矩陣求逆算法實現(xiàn)方法，選取硬件并行度高的LU分解矩陣求逆算法，通過對該算法的數(shù)據(jù)流分析，詳細(xì)設(shè)計了該算法在RASP架構(gòu)上的映射方法，并進(jìn)行性能分析。結(jié)果顯示，本文的設(shè)計方案適用于任意階矩陣，靈活性高。性能在低階時優(yōu)于DSP，且在高階矩陣方面有較大優(yōu)勢，高階性能相比FPGA提高了1.19倍，接近了ASIC的性能，并比ASIC靈活。因此本文提出的基于可重構(gòu)陣列的矩陣求逆算法實現(xiàn)方法可同時兼顧性能和靈活性。