一種基于動態可重構陣列的矩陣求逆算法實現方法

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

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

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

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

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

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

1 矩陣求逆核心算子數據流特性分析

1.1 矩陣求逆算法分析

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

1.1.1 LU分解

LU分解數學公式如下：

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

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

1.1.2 三角矩陣求逆

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

相對應的上三角矩陣U的求逆公式如下：

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

1.1.3 三角矩陣乘

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

1.2 矩陣求逆數據流分析

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

圖1 矩陣求逆數據流

這3個運算階段有相同的計算類型單元，將這些單元聚集區稱之為域，則LU分解求逆矩陣的數據流具有以下特征：域內數據計算傳輸具有單向規整性，批量數據并行傳輸；而域間數據流的運算層次結構不一，數據流水的傳播具有發散性或者收斂累和傳輸。

2 可重構平臺介紹及矩陣求逆算子映射

2.1 RASP架構介紹

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

圖2 RASP整體架構

在可重構處理器系統中，包含4個結構完全相同的可重構陣列（Reconfigurable Compute Array，RCA）?？芍貥嬯嚵械幕窘Y構框圖如圖3所示，每個RCA主要包括4個部分：輸入輸出FIFO，配置輸入寄存器，臨時數據寄存器以及計算單元陣列（Processing Element Array，PEA）。

圖3 RCA結構圖

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

圖4 PEA陣列結構圖

2.2 核心子算子映射方案

2.2.1 LU分解映射

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

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

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

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

2.2.2 三角矩陣求逆映射

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

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

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

圖7 三角矩陣求逆映射

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

2.2.3 三角矩陣相乘映射

三角矩陣相乘相對簡單，采用常規的乘法和累加單元即可，如圖8所示。其中，累加陣列的結構與PEA內累加陣列結構相同。

圖8 三角矩陣相乘映射

3 實驗結果及分析對比

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

表1 矩陣求逆性能指標對比

4 結論

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