一種基于動(dòng)態(tài)可重構(gòu)陣列的矩陣求逆算法實(shí)現(xiàn)方法

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

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

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

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

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

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

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

1.1 矩陣求逆算法分析

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

1.1.1 LU分解

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

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

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

1.1.2 三角矩陣求逆

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

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

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

1.1.3 三角矩陣乘

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

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

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

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

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

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

2.1 RASP架構(gòu)介紹

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

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

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

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

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

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

2.2 核心子算子映射方案

2.2.1 LU分解映射

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

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

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

圖5 行列式分塊順次計(jì)算矩陣LU分解

2.2.2 三角矩陣求逆映射

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

圖6 迭代計(jì)算三角矩陣逆矩陣元素

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

圖7 三角矩陣求逆映射

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

2.2.3 三角矩陣相乘映射

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

圖8 三角矩陣相乘映射

3 實(shí)驗(yàn)結(jié)果及分析對(duì)比

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

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

4 結(jié)論

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