王 雷

(南京理工大學(xué)電子工程與光電技術(shù)學(xué)院 江蘇 南京 210000)

大規(guī)模MIMO中基于低復(fù)雜度雅克比預(yù)編碼算法及實(shí)現(xiàn)

王 雷

(南京理工大學(xué)電子工程與光電技術(shù)學(xué)院 江蘇 南京 210000)

迫零線性預(yù)編碼可以獲得接近最優(yōu)的系統(tǒng)容量，不同于傳統(tǒng)MIMO系統(tǒng)，大規(guī)模MIMO將會(huì)配置成百根天線，隨著天線數(shù)量增加，使得迫零線性預(yù)編碼矩陣求逆計(jì)算復(fù)雜，不利于在應(yīng)用中實(shí)現(xiàn)。為了減小線性預(yù)編碼計(jì)算復(fù)雜度，提出基于低復(fù)雜度的雅克比迭代算法，該算法通過線性迭代，避免了矩陣求逆運(yùn)算，減少了計(jì)算量。為了更進(jìn)一步的減少計(jì)算時(shí)間，提出基于統(tǒng)一計(jì)算架構(gòu)的異構(gòu)多核并行算法，該方法利用GPU具有多核多線程結(jié)構(gòu)特點(diǎn)，實(shí)現(xiàn)了異構(gòu)多核并行計(jì)算。仿真結(jié)果表明，基于低復(fù)雜度雅克比預(yù)編碼算法可以達(dá)到迫零預(yù)編碼算法性能，同時(shí)與傳統(tǒng)的線性預(yù)編碼相比，該算法的計(jì)算量更少、時(shí)間更短。

預(yù)編碼 雅克比 統(tǒng)一計(jì)算架構(gòu) 迫零 異構(gòu)多核

0 引 言

和傳統(tǒng)的MIMO系統(tǒng)不一樣，大規(guī)模MIMO系統(tǒng)在基站端配置了大量的天線單元(幾百根)同時(shí)對(duì)小區(qū)中的多個(gè)用戶同時(shí)傳輸數(shù)據(jù)。理論證明大規(guī)模MIMO系統(tǒng)比傳統(tǒng)的小規(guī)模MIMO系統(tǒng)提高了幾個(gè)數(shù)量級(jí)的系統(tǒng)容量和能效，該技術(shù)有望用在未來5G無線通信系統(tǒng)當(dāng)中[1]。

然而，在實(shí)際的大規(guī)模MIMO系統(tǒng)中，面臨著許多挑戰(zhàn)。例如，在下行鏈路多用戶系統(tǒng)中，為了消除其他用戶對(duì)某個(gè)用戶的干擾，該用戶必須做均衡處理[2]。然而，在用戶端做復(fù)雜的均衡處理，會(huì)使得用戶設(shè)備能耗高。目前，pad、手機(jī)如何節(jié)約能效一直是一個(gè)難點(diǎn)，在實(shí)際當(dāng)中，在用戶端做復(fù)雜的均衡計(jì)算，往往是不切實(shí)際的。因此，有必要對(duì)發(fā)射端做預(yù)編碼(盡管會(huì)增加基站負(fù)荷)，將會(huì)大大減少用戶端均衡復(fù)雜度。最優(yōu)的預(yù)編碼是非線性臟紙預(yù)編碼DPC(dirty paper precoding)[3]。然而在大規(guī)模MIMO中，由于維度很大，臟紙預(yù)編碼算法難以實(shí)現(xiàn)。線性預(yù)編碼中，有向量轉(zhuǎn)置預(yù)編碼、格約簡(jiǎn)輔助預(yù)編碼和迫零預(yù)編碼[4-5]，該三種線性預(yù)編碼在低維度時(shí)，計(jì)算量少，然而隨著天線數(shù)量增加，其復(fù)雜度將大大增加。因此，如何減少計(jì)算復(fù)雜度同時(shí)獲得接近最優(yōu)的系統(tǒng)容量，是一個(gè)迫在眉睫的問題。

與傳統(tǒng)的中心處理單元CPU不同，圖形處理單元GPU提供了大量的并行架構(gòu)，GPU中大多數(shù)晶體管是用來處理算術(shù)邏輯單元ALU(Arithmetic Logic Unit)，而不是像CPU那樣大多用來緩存和數(shù)據(jù)流控制[6-9]。理論測(cè)試表明，顯卡Geforce GT620可以到達(dá)到每秒約120億次浮點(diǎn)計(jì)算。在無線通信系統(tǒng)中，基于GPU加速是一個(gè)研究熱點(diǎn)，尤其在加速仿真和軟件無線電SDR(software defined radio)。

本文提出了基于低復(fù)雜雅克比算法。該算法通過迭代的方法，避免了矩陣求逆計(jì)算，分析表明本文提出的算法比傳統(tǒng)求逆迫零預(yù)編碼算法減少一個(gè)數(shù)量級(jí)的計(jì)算量，同時(shí)獲得了和迫零預(yù)編碼算法一樣的性能。為了更進(jìn)一步地減少計(jì)算時(shí)間，提出了基于統(tǒng)一計(jì)算架構(gòu)的異構(gòu)多核并行算法，該方法利用GPU具有多核多線程結(jié)構(gòu)特點(diǎn)，實(shí)現(xiàn)了異構(gòu)多核并行計(jì)算。仿真結(jié)果表明，基于低復(fù)雜度雅克比預(yù)編碼算法可以達(dá)到迫零預(yù)編碼算法一樣的性能，同時(shí)與傳統(tǒng)的線性預(yù)編碼相比，該算法的計(jì)算量更少，時(shí)間更短。

1 系統(tǒng)模型

我們考慮單基站，多用戶大規(guī)模MIMO系統(tǒng)，如圖1所示，基站端配置天線個(gè)數(shù)為N，用戶數(shù)為K，每個(gè)用戶配有一根天線，其中N≥K。在下行鏈路系統(tǒng)中，基站同時(shí)對(duì)K個(gè)用戶傳輸數(shù)據(jù)，可以表示為：

(1)

其中，ρ表示的是信噪比SNR,H∈CK×N表示平坦衰落瑞利信道矩陣，該矩陣中的每個(gè)元素服從CN(0,1)，n=[n1,n2,…,nK]T表示加性高斯白噪聲，服從CN(0,1)，用戶端接收信號(hào)為y=[y1,y2,…,yK]T。x是預(yù)編碼之后的發(fā)射數(shù)據(jù)。

x=Ps

(2)

其中P是預(yù)編碼矩陣，s=[s1,s2,…,sK]T是傳輸給K個(gè)用戶的信息，且x滿足：

E{‖x‖2}=K

(3)

當(dāng)發(fā)射端天線數(shù)N增大時(shí)，信道矩陣H中的列向量趨近于正交，因此利用簡(jiǎn)單的線性預(yù)編碼技術(shù)可以獲得接近最優(yōu)的容量。

圖1 多用戶MIMO系統(tǒng)

2 低復(fù)雜度雅克比預(yù)編碼實(shí)現(xiàn)

本小節(jié)，首先簡(jiǎn)要介紹一下經(jīng)典迫零ZF(zero forcing)算法，其次提出了基于雅克比迭代算法，然后介紹了基于CUDA的并行架構(gòu)，最后對(duì)提出的算法進(jìn)行了復(fù)雜度分析。

2.1 迫零預(yù)編碼原理

在基站端做迫零預(yù)編碼，可以消除用戶之間的干擾，經(jīng)典的迫零預(yù)編碼矩陣PZF可以表示成如下形式：

PZF=βH+=HH(HHH)-1=HHG-1

(4)

其中HH表示信道矩陣H的厄米特共軛轉(zhuǎn)置，H+表示矩陣H的偽逆矩陣，G=HHH，β表示每個(gè)用戶的平均發(fā)射功率，我們可設(shè)β為：

(5)

根據(jù)式(1)、式(2)、式(4)和式(5)，可以得到等效信道：

Heq=βHHHG-1

(6)

由式(4)可知道PZF需要矩陣求逆，其計(jì)算復(fù)雜度為O(K3)，當(dāng)用戶數(shù)增多時(shí)，其將會(huì)大大增加基站的負(fù)荷。

假設(shè)基站可以完全獲得信道狀態(tài)信息，對(duì)于任何用戶k，其信干噪比SINR可表示為：

(7)

利用式(4)可得其信干噪比為：

(8)

經(jīng)典迫零矩陣使得其他用戶對(duì)某個(gè)用戶的干擾完全消除。在利用基于雅克比迭代求解時(shí)，如果迭代次數(shù)不夠，會(huì)使得式(7)中分母的第一項(xiàng)不為0，會(huì)降低信干噪比，使得誤碼率增加。通過仿真表明，當(dāng)?shù)螖?shù)為3以上時(shí)，性能就已經(jīng)很接近迫零算法。

最后根據(jù)式(7)，可得到總的系統(tǒng)頻譜效率為：

(9)

2.2 基于雅克比迭代預(yù)編碼算法

雅克比迭代算法(Jacobi)是用來求解如下形式的線性方程組：

Ay=b

(10)

其中矩陣A是大小為N×N的矩陣，b是已知的大小為N×1向量，y是所求的列向量。不同于傳統(tǒng)的直接求解y=A-1b，雅克比算法通過如下迭代求解y：

yk+1=-D-1(L+U)yk+D-1b

(11)

其中A=D+L+U,矩陣D為矩陣A的對(duì)角矩陣，矩陣L為矩陣A的嚴(yán)格下三角矩陣，矩陣U為矩陣A的嚴(yán)格上三角矩陣，yk+1表示向量y的第k+1次迭代。

由式(2)和式(4)，向量x可表示為：

x=Ps=βHHG-1s

(12)

引理1矩陣G可逆且是正定矩陣

由于G=HHH，GH=HHH,因此G=GH，說明矩陣G厄米特共軛轉(zhuǎn)置。對(duì)于任意非零列向量α：

αHGα=(αHH)(αHH)H≥0

(13)

在瑞利信道矩陣H下，信道H中列向量趨于正交，因此矩陣H是列滿秩的，因此αHGα>0，說明矩陣G可逆且是正定矩陣。

2.3 異構(gòu)多核并行架構(gòu)

異構(gòu)多核架構(gòu)通常包含主機(jī)端(CPU)和設(shè)備端(GPU)。主機(jī)端通常處理和控制級(jí)聯(lián)算法，而設(shè)備端含有大量的核，通常用來做并行計(jì)算。如圖2所示。

圖2 異構(gòu)多核架構(gòu)

統(tǒng)一計(jì)算架構(gòu)CUDA(Compute Unified Device Architecture)是用來對(duì)GPU作并行計(jì)算的運(yùn)算平臺(tái)。我們可以把設(shè)備端的數(shù)據(jù)傳輸?shù)街鳈C(jī)端，也可以把主機(jī)端的數(shù)據(jù)傳輸給設(shè)備端，因此設(shè)備端和主機(jī)端之間的數(shù)據(jù)可以相互傳輸。首先把所處理的數(shù)據(jù)存在主機(jī)端，主機(jī)端把該數(shù)據(jù)傳輸?shù)皆O(shè)備端中去，設(shè)備端對(duì)這些數(shù)據(jù)進(jìn)行處理計(jì)算，計(jì)算后的值再傳輸?shù)街鳈C(jī)端中去，CUDA-GPU通常包含四種寄存器：全局寄存器、共享存儲(chǔ)器、常量存儲(chǔ)器和紋理存儲(chǔ)器。由于共享內(nèi)存嵌入在線程塊中，可以提供最快的讀寫操作，每個(gè)線程塊中的線程通過合作同步高效率的執(zhí)行。

2.4 復(fù)雜度分析

(14)

3 仿真分析

為了分析基于雅克比預(yù)編碼算法性能，我們把該算法與經(jīng)典迫零算法進(jìn)行了比較。調(diào)制方式為64QAM，N×K=256×16，仿真結(jié)果如圖3所示。

圖3 迫零算法與基于雅克比算法性能分析對(duì)比

如圖3所示，基于雅克比算法迭代次數(shù)為i=2時(shí)，在信噪比小于15 dB時(shí)，誤比特率與迫零算法接近相同，當(dāng)信噪比大于15 dB時(shí)，其誤比特率要高于迫零算法，這是由于迭代次數(shù)過少，迭代出的值有較大的誤差。然而，當(dāng)?shù)螖?shù)大于等于3時(shí)，其誤比特與迫零算法趨于一致，這說明當(dāng)?shù)螖?shù)大于等于3時(shí)，就可以得到精確的值，說明了該算法收斂速度快，所需的計(jì)算量少。

考慮到基于雅克比預(yù)編碼算法的并行性能，CPU是i3-3220四核內(nèi)存，GPU是英偉達(dá)Geforce GT620，共包含32個(gè)CUDA核，如圖4所示。

圖4 基于CPU串行與GPU并行計(jì)算時(shí)間比較

從圖4可以看出，相同矩陣維數(shù)，基于CPU計(jì)算時(shí)間比GPU并行計(jì)算時(shí)間要長(zhǎng)，為了定量知道并行程序的執(zhí)行速度相對(duì)于串行程序的執(zhí)行速度加快了多少，我們定義其加速比，表示的是同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間比率。如圖5所示給出了雅克比算法次數(shù)為2、3和4時(shí)的加速比，仿真結(jié)果表明，隨著矩陣維數(shù)增大，其加速比越大，說明時(shí)間縮短的比例越大。

圖5 基于GPU并行計(jì)算加速比

4 結(jié) 語

本文針對(duì)無線通信系統(tǒng)預(yù)編碼計(jì)算量大的缺點(diǎn)，提出了基于低復(fù)雜雅克比算法。該算法通過迭代，避免了矩陣求逆計(jì)算，與傳統(tǒng)的迫零算法相比，計(jì)算量減少了一個(gè)數(shù)量級(jí)，仿真結(jié)果表明該算法收斂速度快。當(dāng)?shù)螖?shù)大于等于3時(shí)，就可以得到精確的值，所需的計(jì)算量少。然后，我們提出了快速雅克比預(yù)編碼算法并行實(shí)現(xiàn)。仿真結(jié)果表明并行計(jì)算可以大大減少計(jì)算時(shí)間，當(dāng)矩陣維數(shù)越大，其獲得的加速比越大，說明了相對(duì)于串行計(jì)算時(shí)間而言，并行計(jì)算所需要的時(shí)間更短。

[1] Rusek F,Persson D,Lau B K,et al.Scaling Up MIMO:Opportunities and Challenges with Very Large Arrays[J].IEEE Signal Processing Magazine,2012,30(1):40-60.

[2] Gao X,Dai L,Zhang J,et al.Capacity-approaching linear precoding with low-complexity for large-scale MIMO systems[C]//2015 IEEE International Conference on Communications (ICC),2015:1577-1582.

[3] Costa M.Writing on dirty paper[J].IEEE Transactions on Information Theory,1983,29(3):439-441.

[4] Gao X,Dai L,Hu Y,et al.Matrix inversion-less signal detection using SOR method for uplink large-scale MIMO systems[C]//Global Communications Conference.IEEE,2015:3291-3295.

[5] Prabhu H,Rodrigues J,Edfors O,et al.Approximative matrix inverse computations for very-large MIMO and applications to linear pre-coding systems[C]//Wireless Communications and NETWORKING Conference.IEEE,2013:2710-2715.

[6] 陳國良.并行計(jì)算[M].高等教育出版社,2011.

[7] 盧風(fēng)順,宋君強(qiáng),銀?？?等.CPU/GPU協(xié)同并行計(jì)算研究綜述[J].計(jì)算機(jī)科學(xué),2011,38(3):5-9.

[8] Yu D,He S,Huang Y,et al.A fast parallel matrix inversion algorithm based on heterogeneous multicore architectures[C]//IEEE Global Conference on Signal and Information Processing,2015:903-907.

[9] Mahfoudhi R,Mahjoub Z,Nasri W.Parallel Communication-Avoiding Algorithm for Triangular Matrix Inversion on Homogeneous and Heterogeneous Platforms[J].International Journal of Parallel Programming,2015,43(4):631-655.

LOWCOMPLEXITYJACOBIBASEDPRECODINGFORLARGE-SCALEMIMO

Wang Lei

(SchoolofElectronicandOpticalEngineering,NanjingUniversityofScienceandTechnology,Nanjing210000,Jiangsu,China)

Linear precoding techniques, such as zero forcing, can achieve the near optimal capacity. In contrast to traditional multiple input multiple output (MIMO), large scale MIMO installed hundreds of antennas, with the increasing numbers of antennas, zero forcing precoding involve the matrix inversion of large size with high computational complexity, which may cause difficulty for the realization of the application. To reduce the computational complexity of linear precoding, we propose a low complexity iterative algorithm based on the degree of Jacobi. This method realized through the linear iteration meanwhile avoided the matrix inversion. To further reduce the computation time, we propose a heterogeneous multicore parallel algorithm based on CUDA (compute unified device architecture), which leverage the Graphics Processing Unit (GPU) characteristic of multicores and multithreads to realize heterogeneous multicore architecture parallel computation. Experimental result demonstrates this proposed algorithm not only can achieve the same performance of zero forcing precoding, but also has less computation time and shorter time than traditional linear precoding.

Precoding Jacobi CUDA Zero forcing Heterogeneous multicore

TP391

A

10.3969/j.issn.1000-386x.2017.10.052

2017-01-03。王雷，副研究員，主研領(lǐng)域：通信與信息系統(tǒng)，信號(hào)信息處理。