基于異構(gòu)多核可重構(gòu)系統(tǒng)的矩陣求逆設(shè)計(jì)與實(shí)現(xiàn)?

錢慶松

（昆明船舶設(shè)備研究試驗(yàn)中心 昆明 650051）

基于異構(gòu)多核可重構(gòu)系統(tǒng)的矩陣求逆設(shè)計(jì)與實(shí)現(xiàn)?

錢慶松

（昆明船舶設(shè)備研究試驗(yàn)中心 昆明 650051）

矩陣求逆是一種常見的計(jì)算密集型信號處理算法，廣泛應(yīng)用于聲納探測、雷達(dá)等高實(shí)時(shí)性要求的數(shù)字信號處理領(lǐng)域。隨著多核芯片技術(shù)的成熟，其強(qiáng)大運(yùn)算能力提供了一種全新的矩陣求解途徑。論文在基于NoC的異構(gòu)多核可重構(gòu)系統(tǒng)上，映射了一種高斯消去法與上下三角矩陣分解（LU分解）法相結(jié)合的矩陣求逆方法。通過權(quán)衡系統(tǒng)并行度，核內(nèi)存儲(chǔ)空間和系統(tǒng)處理速度等多方面因素，進(jìn)行并行算法分解、組合和任務(wù)分配，實(shí)現(xiàn)了64維以下任意維的復(fù)數(shù)矩陣求逆。

矩陣求逆；LU分解；異構(gòu)多核；算法映射

1 引言

現(xiàn)代探測聲納發(fā)展呈現(xiàn)運(yùn)算量大、實(shí)時(shí)性強(qiáng)及小型化的趨勢［1］，因而對聲納的信號處理平臺提出了越來越高的要求，高性能處理器在聲納信號處理中發(fā)揮的作用日趨重要，對其運(yùn)算能力和數(shù)據(jù)吞吐能力的要求也越來越高［2］?；诳芍貥?gòu)技術(shù)的片上多核處理器是一種將可重構(gòu)技術(shù)與片上多核系統(tǒng)（Multi Processor System-on-Chip，MPSoC）相結(jié)合的硬件方案，利用集成片內(nèi)的可重構(gòu)硬件的可編程特性，可以針對不同的應(yīng)用特征，定制片上數(shù)據(jù)路徑。通過提高算法與硬件結(jié)構(gòu)間的適配性，充分利用其并行計(jì)算處理能力，在確保數(shù)據(jù)吞吐率及處理速度情況下，具有更高的使用靈活性，有效地滿足數(shù)據(jù)密集型和計(jì)算密集型任務(wù)的要求［3～5］。

在數(shù)字信號處理領(lǐng)域，矩陣求逆運(yùn)算是一項(xiàng)非常重要的基本操作，廣泛應(yīng)用于通訊、導(dǎo)航、水下探測和雷達(dá)等領(lǐng)域。矩陣求逆的方法很多，比如初等變換法、伴隨矩陣法、分塊矩陣法等［6］。目前多使用定制專用硬件加速模塊方法實(shí)現(xiàn)其快速求解，矩陣求逆計(jì)算的強(qiáng)數(shù)據(jù)相關(guān)性的特點(diǎn)給算法在多核系統(tǒng)中的實(shí)現(xiàn)帶來了很大挑戰(zhàn)，這在處理大維數(shù)矩陣時(shí)表現(xiàn)的更加顯著［7～9］。本文在一種基于NoC的異構(gòu)多核可重構(gòu)系統(tǒng)，結(jié)合已有的三角矩陣求逆硬件實(shí)現(xiàn)方法、高斯消去法和矩陣的LU分解算法，探索了一種易在多核系統(tǒng)上以較高并行度執(zhí)行的復(fù)數(shù)矩陣求逆方法。充分的利用異構(gòu)多核系統(tǒng)的并行性，提高計(jì)算效率，保證計(jì)算結(jié)果具有較高精度。

2 算法分析

矩陣的一種比較常用的分解方法是矩陣的LU三角分解，將一個(gè)n階矩陣A分解為一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積［7］。對上下三角矩陣求逆是非常方便的，可以利用這一特性減少求任意n階矩陣A的逆矩陣的運(yùn)算量和復(fù)雜度。具體的流程為：首先對矩陣進(jìn)行LU分解，然后對L和U矩陣求逆得到L-1和U-1，最后通過矩陣乘積求得原始矩陣A的逆A-1=U-1L-1。

2.1 矩陣的LU分解［6］

高斯消去法可行的充要條件是方程（3）的系數(shù)矩陣A的所有順序主子式Di≠0,i=1,2,…,n，本文硬件求逆方法所適用的矩陣也需滿足這一條件。其中，高斯消去法包括消元和回代兩個(gè)過程，本文只利用了消元過程，故回代過程就不做贅述。

2.3 矩陣求逆

將待解矩陣A右接一單位矩陣E，得到(A,E)。利用矩陣的初等行變換對(A,E)進(jìn)行高斯消元過程得到(U,B)，易知B=L-1。同樣，將U右接一單位矩陣(U,E)，進(jìn)行初等變換得到(E,U-1)，最終得到原始矩陣A的逆矩陣A-1=U-1L-1，完成整個(gè)矩陣求逆的過程。

3 異構(gòu)多核可重構(gòu)系統(tǒng)

ReMPSOC是一款可編程異構(gòu)多核SoC處理系統(tǒng)，結(jié)構(gòu)簡單，具有極大的數(shù)據(jù)吞吐量級計(jì)算核集成度，主要面向高密度計(jì)算應(yīng)用。本系統(tǒng)不僅適用于某些特殊類型運(yùn)算，并具有一定的通用性［10］。

系統(tǒng)結(jié)構(gòu)圖［11］如圖1所示，系統(tǒng)中包含通信網(wǎng)絡(luò)、主控單元（MC）、計(jì)算單元（Cluster，C）、接口單元及存儲(chǔ)模塊（MEM），不同的功能單元（以下稱為簇）連接在不同的mesh網(wǎng)絡(luò)的路由節(jié)點(diǎn)上，完成控制、運(yùn)算、接口通訊、訪存等任務(wù)。每個(gè)簇分別有一個(gè)狀態(tài)上傳接口、一個(gè)配置下達(dá)接口、PCC數(shù)據(jù)接口；簇間通過狀態(tài)網(wǎng)絡(luò)、系統(tǒng)主控制器及配置網(wǎng)絡(luò)傳遞控制信息；通過PCC網(wǎng)絡(luò)傳輸運(yùn)算數(shù)據(jù)。運(yùn)算簇實(shí)現(xiàn)數(shù)據(jù)運(yùn)算，并提供符合IEEE 754標(biāo)準(zhǔn)的32位單精度浮點(diǎn)運(yùn)算能力。運(yùn)算簇包括兩種：可重構(gòu)計(jì)算單元（RCU）運(yùn)算簇、協(xié)處理器（COP）運(yùn)算簇。

圖1 多核系統(tǒng)芯片結(jié)構(gòu)示意圖

1）RCU運(yùn)算簇［10］

RCU運(yùn)算簇提供符合IEEE 754標(biāo)準(zhǔn)的32位浮點(diǎn)運(yùn)算能力，主要完成規(guī)則的浮點(diǎn)復(fù)數(shù)∕實(shí)數(shù)運(yùn)算，包括復(fù)數(shù)乘、復(fù)實(shí)乘、矩陣乘、乘法、加減法等運(yùn)算。RCU運(yùn)算簇具有可重構(gòu)特性，采用2PE結(jié)構(gòu)，支持存儲(chǔ)運(yùn)算和流運(yùn)算兩種運(yùn)算模式。

2）COP運(yùn)算簇

COP運(yùn)算簇提供符合IEEE 754標(biāo)準(zhǔn)的32位浮點(diǎn)運(yùn)算能力，主要完成非規(guī)則的浮點(diǎn)復(fù)數(shù)∕實(shí)數(shù)運(yùn)算，包括：乘法、加減法、除法、開方、正余弦等運(yùn)算。COP運(yùn)算簇基于SIMD架構(gòu)，采用Microblaze作為運(yùn)算的控制單元，并采用符合Microblaze的DFSL接口協(xié)議的硬件浮點(diǎn)運(yùn)算協(xié)處理器作為加速單元，能夠同時(shí)完成2路32位寬的浮點(diǎn)運(yùn)算。

4 算法映射

本文映射的是基于高斯消元法和LU分解法的64維復(fù)數(shù)矩陣的求逆，分5個(gè)任務(wù)完成整個(gè)求逆過程，各個(gè)任務(wù)的源數(shù)據(jù)、結(jié)果數(shù)據(jù)和及功能可從圖2看出，其中Λ為一對角矩陣，U'為一下三角矩陣。通過修改配置信息和軟件代碼中的循環(huán)次數(shù)可實(shí)現(xiàn)64維以下任意維復(fù)數(shù)矩陣的求逆。

圖2 矩陣求逆流程圖

4.1 求解U-1和L過程的映射

為了方便起見，以式（3）中的 A=A(0)為例，task1為計(jì)算下三角矩陣L并根據(jù)消元過程中得到的系數(shù)矩陣，并根據(jù)系數(shù)矩陣對單位矩陣進(jìn)行列變換得到U-1。計(jì)算下三角矩陣和進(jìn)行列變換時(shí)，都是基于高斯消元方法，具體的計(jì)算過程是通過不斷地循環(huán)完成的，每一次循環(huán)完成對A矩陣中一列元素的消元。該過程屬于計(jì)算密集型運(yùn)算，前后數(shù)據(jù)相關(guān)性大，計(jì)算不規(guī)則，因此采用具有較強(qiáng)的本地運(yùn)算能力和靈活的地址控制機(jī)制COP完成主要操作。task1的任務(wù)映射圖如圖3所示。以64維矩陣為例進(jìn)行說明，整個(gè)消元過程是通過63次大的循環(huán)完成的，以第一次循環(huán)為例：COP0首先向MEM存儲(chǔ)單元請求原始矩陣A，計(jì)算消元系數(shù)

將系數(shù)向量通過數(shù)據(jù)網(wǎng)絡(luò)傳遞給COP1、COP2同時(shí)寫回MEM存儲(chǔ)單元；COP1和COP0分別用于根據(jù)系數(shù)矩陣求下三角矩陣L和對單位陣進(jìn)行列變換求U-1，避免對系數(shù)矩陣的重復(fù)讀取而降低運(yùn)算效率。COP1、COP2進(jìn)行復(fù)數(shù)乘，將對應(yīng)的系數(shù)乘以第一列；RCU0、RCU1執(zhí)行復(fù)數(shù)加即消元過程，當(dāng)RCU0和RCU1復(fù)數(shù)加任務(wù)完成時(shí)也就說明第一列的消元已經(jīng)全部完成，這時(shí)COP0會(huì)向MEM存儲(chǔ)單元請求新生成的矩陣執(zhí)行第二次循環(huán)。圖4用偽碼表示了整個(gè)消元過程。

圖3 高斯消元過程偽碼

圖4 task1任務(wù)映射圖

4.2 求解LT過程的映射

task2對task1得到的L矩陣進(jìn)行轉(zhuǎn)置操作。為了充分的利用系統(tǒng)中的運(yùn)算簇以提高算法的執(zhí)行效率，本文采用分塊轉(zhuǎn)置的方法，其公式如下。

在轉(zhuǎn)置過程中將原矩陣分為四塊，對其中的每一塊進(jìn)行轉(zhuǎn)置操作。在轉(zhuǎn)置任務(wù)時(shí)，使用具有靈活地址跳變規(guī)律的COP進(jìn)行轉(zhuǎn)置運(yùn)算，task2中使用4個(gè)COP并行執(zhí)行轉(zhuǎn)置操作，每個(gè)COP對其中的矩陣中的一塊進(jìn)行轉(zhuǎn)置，然后將計(jì)算完成的結(jié)果寫回DDR存儲(chǔ)單元，以作為后續(xù)操作的源數(shù)據(jù)。task2的任務(wù)映射圖如圖5所示。

圖5 task2任務(wù)映射圖

4.3 U-1L-1的映射

根據(jù)任務(wù)分解圖可以得知，task3與task1的操作基本相同，僅是源數(shù)據(jù)和結(jié)果數(shù)據(jù)不同，因此task3與task1的任務(wù)映射圖相同。task3根據(jù)task2轉(zhuǎn)置得到的LT，使用相同的計(jì)算方式得到一對角矩陣Λ和一下三角矩陣L'。task4將L'的每一列除以矩陣Λ相應(yīng)行中對角線上的元素，得到(LT)-1在RCU和COP中，只有COP支持復(fù)數(shù)除法操作，為了提高運(yùn)算效率，依然使用4個(gè)COP進(jìn)行相除計(jì)算，任務(wù)映射圖與圖4基本相同。

task5將LU分解得到的兩個(gè)結(jié)果相乘，進(jìn)行U-1L-1計(jì)算，完成整個(gè)求逆操作。在task4中得到的結(jié)果為(LT)-1，在計(jì)算過程中，不再對(LT)-1進(jìn)行轉(zhuǎn)置操作，而是直接按其逆矩陣的形式取出與L-1執(zhí)行矩陣乘操作。矩陣乘任務(wù)為比較規(guī)整的任務(wù)，為了充分的使用系統(tǒng)中的運(yùn)算簇，此任務(wù)使用8個(gè)RCU執(zhí)行并行計(jì)算，RCU根據(jù)其地址控制機(jī)制對輸入的數(shù)據(jù)進(jìn)行乘累加，最后將A-1寫回MEM存儲(chǔ)單元。

5 實(shí)驗(yàn)和結(jié)果分析

本次實(shí)驗(yàn)是在Xilinx公司Virtex7系列的XC7V2000T FPGA芯片上實(shí)現(xiàn)的，工作頻率為100MHz。實(shí)驗(yàn)結(jié)果通過網(wǎng)口簇上傳至主機(jī)，并與MATLAB軟件計(jì)算結(jié)果進(jìn)行了對比，絕對誤差為10-4，整個(gè)計(jì)算過程共需要907222個(gè)時(shí)鐘周期，其中包括了數(shù)據(jù)傳輸時(shí)間。以下是各個(gè)任務(wù)所消耗周期數(shù)：

圖6 task5任務(wù)映射圖

表1 矩陣求逆中各任務(wù)的計(jì)算時(shí)間

為了方便對實(shí)驗(yàn)結(jié)果進(jìn)行的分析，直觀的表示計(jì)算效率，以不同任務(wù)的并行度DP表示系統(tǒng)的計(jì)算效率，并行度定義如公式6所示［12］。

在公式中，Calculation Cycles表示任務(wù)計(jì)算過程中所需的計(jì)算周期，Execution Cycles表示完成整個(gè)任務(wù)所消耗的周期數(shù)。各任務(wù)的計(jì)算并行度如表2所示。

表2 矩陣求逆中各任務(wù)的并行度

在本文的映射方案中，對于64維以下的矩陣求逆只需改變task1中的循環(huán)次數(shù)及部分?jǐn)?shù)據(jù)信息即可，具有較好的靈活性。計(jì)算過程中任務(wù)計(jì)算的并行度不僅與參與運(yùn)算的運(yùn)算簇有關(guān)，還與計(jì)算任務(wù)的類型有關(guān)，從表2可以看出，task1由于計(jì)算過程中前后數(shù)據(jù)相關(guān)性大，且整個(gè)計(jì)算過程需要不斷的循環(huán)完成，任務(wù)并行度相對較低。在task5中，計(jì)算過程中沒有數(shù)據(jù)相關(guān)性且充分的利用系統(tǒng)中的運(yùn)算簇，任務(wù)并行度達(dá)到最高，也反應(yīng)出系統(tǒng)對于規(guī)則運(yùn)算的良好適應(yīng)性及計(jì)算效率。

6 結(jié)語

在數(shù)字信號處理領(lǐng)域，研究在大維數(shù)矩陣求逆中減少運(yùn)算時(shí)間，提高運(yùn)算效率具有重要意義。本文通過對矩陣求逆算法的理論分析，提供了一種基于異構(gòu)多核可重構(gòu)系統(tǒng)的硬件復(fù)數(shù)矩陣求逆解決方案，并在FPGA開發(fā)板上驗(yàn)證了其正確性。

通過實(shí)驗(yàn)結(jié)果分析可得，系統(tǒng)性能仍有較大的提升空間，為了得到更高的處理速度和任務(wù)并行度，可以增強(qiáng)和改善多核系統(tǒng)中各個(gè)運(yùn)算簇的功能，減少求逆過程中不必要的運(yùn)算。進(jìn)一步研究矩陣求逆的算法，加強(qiáng)矩陣求逆算法的并行度，提高加速效果等，對于研究多核芯片技術(shù)具有重要意義。

［1］任宇飛，袁俊舫，李崢，等.多核DSP在無人平臺探測聲納中的應(yīng)用研究［J］.應(yīng)用聲學(xué)，2014，33（6）：496-504.

［2］張曉燚.基于多核DSP的陣列信號處理系統(tǒng)設(shè)計(jì)［D］.北京：中國科學(xué)院大學(xué)，2015.

［3］Chen F Y，Zhang D S，Wang Z Y.Research of the Heterogeneous Multi-Core Processor Architecture Design［J］.Computer Engineeringamp;Science，2011，33（12）：27-36.

［4］ Ju R.A Hardware∕Software Method for Heterogeneous Cores Cooperating on Stream Architecture［J］.Chinese Journal of Computers，2008，31（11）：2038-2046.

［5］杜高明.MPSoC-NoC多核體系結(jié)構(gòu)及原型芯片實(shí)現(xiàn)技術(shù)研究［D］.合肥：合肥工業(yè)大學(xué)，2007.

［6］蘇育才.萎翠波，張躍輝.矩陣?yán)碚摚跰］.北京：科學(xué)出版社，2006：166-172.

［7］郭春煊，毛志剛，謝憬，等.矩陣求逆運(yùn)算的VLSI實(shí)現(xiàn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（5）：219-223.

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

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

［10］Wang Xing，Zhang Duoli，Song Yukun，et al.Design and Implementation of a reduced floating-point reconfigurable computing unit［C］∕International Conference on Computer，Network Security and Comunication Engineering，2014.

［11］SONG Y，JIAO R，ZHANG D，et al.Performance analysis for matrix-multiplication based on an heterogeneous multi-core SoC［C］∕ASIC，2015 IEEE 11th International Conference on.IEEE，2015：1-4.

［12］張多利，沈休壘，宋宇鯤，等.基于異構(gòu)多核可編程系統(tǒng)的大點(diǎn)FFT卷積設(shè)計(jì)與實(shí)現(xiàn)［J］.電子技術(shù)應(yīng)用，2017，43（3）：16-20.

Design and Implementation of Matrix Inversion on Heterogeneous Multicore Reconfigurable System

QIAN Qingsong
（Kunming Shipborne Equipment Research and Test Center，Kunming 650051）

Matrix inversion is a common computationally intensive signal processing algorithm，widely used in sonar detection，radar and other high real-time requirements of digital signal processing.With the maturity of multi-core chip technology，its powerful computing power provides a new matrix solution.In this paper，a matrix inversion method combining Gaussian elimination method with upper and lower triangular matrix decomposition（LU decomposition）is mapped on a heterogeneous multicore reconfigurable system based on NoC.The parallel algorithm is decomposed by combining the parallelism of the system，the memory space and the processing speed of the kernel.The parallel algorithm is decomposed by the parallel algorithm，and the complex matrix inverse of any dimension of 64 dimensions is realized.

matrix inversion，LU decomposition，heterogeneous multicore，algorithm mapping

TP301

10.3969∕j.issn.1672-9730.2017.10.009

Class Number TP301

2017年4月10日，

2017年5月28日

錢慶松，男，碩士，助理工程師，研究方向：水下信號處理。