李榮春,周 鑫,喬 鵬,王慶林
(1. 國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院, 湖南 長(zhǎng)沙 410073; 2. 國(guó)防科技大學(xué) 并行與分布計(jì)算全國(guó)重點(diǎn)實(shí)驗(yàn)室, 湖南 長(zhǎng)沙 410073)
低密度奇偶校驗(yàn)(low density parity check, LDPC)碼[1]是一類前向糾錯(cuò)(forward error correction, FEC)碼。LDPC碼由于接近最佳性能,已經(jīng)被WiFi、DVB-S2和WiMAX等通信系統(tǒng)所采用。LDPC碼也被納入5G標(biāo)準(zhǔn),成為第五代新無(wú)線電的信道編碼方案。目前,高吞吐率的LDPC譯碼器取得了一定的進(jìn)展[2-5],但基于5G無(wú)線電的LDPC譯碼器工作目前并不多。首先,按照第三代合作伙伴計(jì)劃(3rd generation partnership project, 3GPP)交付的標(biāo)準(zhǔn)描述,5G無(wú)線系統(tǒng)的速度將達(dá)到20 Gbit/s[6]。編碼和譯碼的吞吐率必須足夠高,才能滿足高速數(shù)據(jù)傳輸?shù)男枨?。因?LDPC譯碼器需要提高譯碼吞吐率。在應(yīng)用5G無(wú)線電時(shí),需要更高吞吐率的LDPC譯碼器來(lái)實(shí)現(xiàn)高速信號(hào)傳輸。其次,5G新型無(wú)線電(new radio, NR)標(biāo)準(zhǔn)要求支持更廣泛的碼率和碼長(zhǎng),利用一些新的結(jié)構(gòu)特點(diǎn),如碼型設(shè)計(jì)和譯碼技術(shù)來(lái)實(shí)現(xiàn)更好的性能。
基于專用硬件平臺(tái)(如ASIC和FPGA)的譯碼吞吐率可以非常高[7-11]。傳統(tǒng)FPGA方案可以采用脈動(dòng)陣列等方式來(lái)實(shí)現(xiàn)流水并行,提高譯碼吞吐率,降低譯碼延遲。同時(shí)其功耗較低,被廣泛用于各種無(wú)線通信系統(tǒng)中。目前,圖形處理單元(graphic processing unit, GPU)由于其強(qiáng)大的并行計(jì)算能力和靈活的編程形式,被廣泛應(yīng)用于各種科學(xué)計(jì)算、智能計(jì)算中?;贕PU的無(wú)線通信譯碼器也不斷涌現(xiàn),其吞吐率較高,甚至在某些情況下可以超越FGPA[12]。GPU譯碼器的優(yōu)勢(shì)之一是良好的靈活性,利用基于GPU的譯碼器,可以通過(guò)軟件實(shí)現(xiàn)多標(biāo)準(zhǔn)、多模式的通信系統(tǒng)?;贕PU的譯碼器可以輕松實(shí)現(xiàn)對(duì)LDPC譯碼的不同碼率和碼長(zhǎng)的支持,從而可以快速實(shí)現(xiàn)軟件定義無(wú)線電平臺(tái)。此外,開發(fā)時(shí)間短也使得基于GPU的譯碼器非常有吸引力。
WiFi和WiMAX系統(tǒng)采用準(zhǔn)循環(huán)LDPC(quasi cyclic-LDPC, QC-LDPC)碼,它是編碼和譯碼復(fù)雜度較低的結(jié)構(gòu)化LDPC碼。5G無(wú)線電標(biāo)準(zhǔn)設(shè)計(jì)了新的QC-LDPC碼。目前已有的基于GPU的QC-LDPC譯碼器都是特定碼長(zhǎng)的實(shí)現(xiàn),如IEEE802.16e(2 304,1 152)的LDPC碼[13],IEEE802.11n (1 944,972)的LDPC碼[13]。但是其缺少支持5G無(wú)線電所需更長(zhǎng)碼長(zhǎng)和更高碼率的高吞吐率QC-LDPC譯碼器。
本文提出了一種基于GPU的5G新型無(wú)線電高通量QC-LDPC譯碼器。為了提高譯碼吞吐率,利用GPU實(shí)現(xiàn)了并行MSA算法。在消息更新過(guò)程中的最小值和符號(hào)計(jì)算在GPU上實(shí)現(xiàn)了并行計(jì)算。此外,實(shí)現(xiàn)了對(duì)數(shù)似然比(log-likelihood ratio, LLR)和中間值的量化,以合理的性能損失來(lái)節(jié)省片上和片下帶寬。同時(shí),還利用數(shù)據(jù)打包方法來(lái)降低GPU和中央處理器(central processing unit, CPU)之間數(shù)據(jù)傳輸?shù)拈_銷。在Nvidia RTX 2080Ti上測(cè)量了不同碼長(zhǎng)和碼率的吞吐率。最終實(shí)驗(yàn)顯示,基于GPU的譯碼器取得了較高的吞吐率和峰值性能利用率。最后,提出了一種評(píng)估方法來(lái)計(jì)算GPU上并行譯碼的最優(yōu)線程設(shè)置。
LDPC碼由M×N奇偶校驗(yàn)矩陣(parity check matrix, PCM)H構(gòu)造,其中M代表校驗(yàn)節(jié)點(diǎn)(check node, CN)的數(shù)量,N代表變量節(jié)點(diǎn)(variable node, VN)的數(shù)量。將K表示為信息位的長(zhǎng)度,K=N-M。PCM中的每一行代表一個(gè)奇偶校驗(yàn)方程,如式(1)所示。
c1?c2?…?ck=0
(1)
式中,?表示模2加,c1,c2,…,ck是行中的非零位。CN和VN之間的關(guān)系也可以用Tanner圖[14]來(lái)描述。Tanner圖中CNi和VNj之間的邊對(duì)應(yīng)于PCM中的非零條目,這意味著H(ij)=1,其中,i=1,2,…,M;j=1,2,…,N。
QC-LDPC碼的PCM可以根據(jù)基礎(chǔ)矩陣Hb來(lái)構(gòu)造,Hb是一個(gè)mb×nb矩陣,由Z×Z右移標(biāo)識(shí)和零矩陣組成。3GPP為NR定義了兩個(gè)速率兼容的基礎(chǔ)矩陣,即BG1和BG2。BG1的目標(biāo)是編碼長(zhǎng)度較大(500≤K≤8 448)、碼率較高(1/3≤r≤8/9);BG2的目標(biāo)是編碼長(zhǎng)度較小(40≤K≤2 560)、碼率較低(1/5≤r≤2/3)。Z是右移大小,代表右移單位矩陣的大小。3GPP對(duì)基本圖使用8組右移尺度,值為Z=2j×a,其中a∈{2,3,5,7,9,11,13,15},j∈{0,1,2,3,4,5,6,7}。表1顯示了不同a和j變化情況下Z的大小變化及數(shù)值集合,Z最大為384。
表1 5G新型無(wú)線電協(xié)議中的右移系數(shù)
假設(shè)偏移值
s=Hb(ib,jb)∈{-1}∪{0,1,…,Z-1}
(2)
式中,1≤ib≤mb, 1≤jb≤nb。
PCM通過(guò)使用該映射對(duì)Hb進(jìn)行擴(kuò)充和單位矩陣的右移來(lái)得到。
(3)
其中:Is是一個(gè)Z×Z單位矩陣,經(jīng)過(guò)了s次的循環(huán)右移;0是Z×Z零矩陣。H的大小為(mb×Z)×(nb×Z)。對(duì)于BG1,mb=46,nb=68,信息列數(shù)量kb=nb-mb=22。在5G新型無(wú)線電中,mb和nb可以調(diào)整以適應(yīng)碼率。以下步驟描述了碼率r和待編碼的碼長(zhǎng)W條件下QC-LDPC的PCM構(gòu)造過(guò)程。
步驟1:求滿足以下條件的縮短長(zhǎng)度Ns。
(4)
式中,kb為每行的非零條目,nb為校驗(yàn)矩陣寬度,Ns為縮短長(zhǎng)度,d為最大碼率偏差。按照上述構(gòu)造方法,目標(biāo)碼率可能無(wú)法完全滿足要求,因此允許最終碼率與目標(biāo)碼率有微小的偏差。
步驟2:通過(guò)消除最右邊的Ns列[15]來(lái)縮短基圖,縮短后基圖的大小為(mb-Ns)×(nb-Ns)。
步驟3:通過(guò)選擇表1中的最小Z值來(lái)確定Z,使kb×Z≥K。
步驟4:根據(jù)修改后的基圖,由右移的單位矩陣和零矩陣構(gòu)成PCM,如式(3)所述。
5G新型無(wú)線電LDPC碼的基圖如圖1所示。在5G新型無(wú)線電QC-LDPC碼中,為了獲得所需的信息塊長(zhǎng)度和高碼率,對(duì)基圖進(jìn)行了縮短,剔除的列是擴(kuò)展奇偶校驗(yàn)部分。
圖1 5G新型無(wú)線電LDPC碼的基圖Fig.1 Base graph of LDPC code for 5G new radio
給定H,LDPC編碼的目標(biāo)是求解奇偶性方程
HcT=0
(5)
式中,c是編碼后的碼字,由信息位和奇偶校驗(yàn)位組成。QC-LDPC的編碼方法包括高斯消除法、Richardson等[16]提出的RU方法以及Nguyen等[17]提出的為5G無(wú)線電設(shè)計(jì)的高效編碼方法。一旦PCM被確定,生成矩陣G可以從H中得到。
c=uG
(6)
式中,u是要編碼的信息位數(shù)組。在5G無(wú)線電中,編碼的LDPC碼字在傳輸前會(huì)被打孔。前2×Z位總是被打孔,而不是傳輸[18]。
步驟1:初始化APP比和CTV消息。
(7)
Rij=0,1≤i≤M1≤j≤N
(8)
(9)
其次,更新Rij
(10)
(11)
步驟3:在計(jì)算了所有層的CN和所有1≤l≤mb和1≤j≤N的VN后,信息位由最后一層的結(jié)果決定,其中,l=mb,
(12)
最終得到譯碼結(jié)果v。
在本節(jié)中,描述了幾種用于5G新型無(wú)線電的高吞吐率譯碼技術(shù)。重點(diǎn)介紹使用BG1構(gòu)建的QC-LDPC碼的并行譯碼過(guò)程。譯碼算法MSA是一種分層譯碼算法,可以在GPU上進(jìn)行并行高效譯碼。為了實(shí)現(xiàn)高吞吐率譯碼,有必要進(jìn)一步優(yōu)化譯碼過(guò)程。此外,高碼率和大碼長(zhǎng)對(duì)GPU的內(nèi)存帶寬提出了挑戰(zhàn)。一般來(lái)說(shuō),內(nèi)存訪問(wèn)的開銷會(huì)影響譯碼速度。在5G新型無(wú)線電中,PCM的大小顯著增加,對(duì)GPU的內(nèi)存資源需求也相應(yīng)增加。在譯碼時(shí),合理分配GPU上的資源至關(guān)重要。
H是一個(gè)稀疏矩陣。一般來(lái)說(shuō),利用壓縮結(jié)構(gòu),而不是將整個(gè)PCM傳輸?shù)紾PU。定位H中非零項(xiàng)的常用方法是在譯碼前生成一個(gè)查找表,可以在每一行中存儲(chǔ)非零條目的位置。然而,H中每一行的非零條目數(shù)量并不完全相同。如果大多數(shù)行中的非零條目很少,那么執(zhí)行相同次數(shù)的迭代會(huì)造成時(shí)間浪費(fèi)。因此,不僅要記錄每行非零位的位置,還要記錄非零項(xiàng)的數(shù)量。
將Pik表示為H中第i行中第k個(gè)非零條目的指數(shù)。因?yàn)樵贖中每行最多有kb個(gè)非零條目,那么1≤k≤kb。設(shè)Ci為第i行的非零條目數(shù),則CN和VN之間的聯(lián)系可由Pik和Ci決定。壓縮H的結(jié)構(gòu)可以節(jié)省內(nèi)存空間和訪問(wèn)時(shí)間。而且,壓縮在GPU上很容易實(shí)現(xiàn)。
除了壓縮H外,CTV消息R也可以被壓縮。如上所述,VN和CN之間的連接在譯碼前是已知的。如果VNj和CNi之間存在連接的話,則只需要在第i行中保存VN的消息值。R的大小可以從(mb×Z)×(nb×Z)壓縮到(mb×Z)×kb。注意到R的壓縮也是GPU上內(nèi)存凝聚的一種優(yōu)化方法。CTV消息是譯碼過(guò)程的中間結(jié)果。將R壓縮到連續(xù)空間有助于減少GPU上線程束內(nèi)的塊沖突。
本文采用的LDPC譯碼算法是MSA算法,MSA算法適合在GPU上進(jìn)行并行譯碼。PCM是使用右移單位矩陣構(gòu)建的,對(duì)于H中的每個(gè)Z×Z塊,所有非零條目都來(lái)自不同的列。當(dāng)計(jì)算CTV和VTC消息從i×Z到(i+1)×Z層時(shí),不存在依賴性,其中i=0,1,…,mb-1。所以可以通過(guò)固定的線程分配來(lái)實(shí)現(xiàn)譯碼計(jì)算。本文為MSA的分層譯碼分配Z線程。對(duì)于5G新型無(wú)線電來(lái)說(shuō),最大的Z為384,不超過(guò)GPU上每個(gè)塊的最大線程數(shù)。
(13)
(14)
那么,可以通過(guò)式(15)得到VNj的最小值。
(15)
(16)
然后通過(guò)式(17)得到S。
(17)
因?yàn)橹挥胸?fù)值才會(huì)影響Sglobal的符號(hào),所以只在Lik<0時(shí)更新Sglobal。同時(shí),如果Lik≥0,S=Sglobal?;诖?乘法中的式(10)被式(16)~(17)所取代。這種替換減少了GPU上的計(jì)算量。
算法1 并行層譯碼算法
如上所述,每塊有Z線程并行譯碼。但在GPU上,每塊最大線程數(shù)為1 024或2 048。雖然不建議超過(guò)Z的線程數(shù),但最大Z是384,遠(yuǎn)遠(yuǎn)沒(méi)有超過(guò)每塊線程的最大限制。因此,有可能在同一塊內(nèi)分配更多的線程來(lái)譯碼多個(gè)碼字。因此,我們實(shí)現(xiàn)了多塊譯碼,提高GPU的并行度。讓Np作為同一塊中被譯碼的碼字?jǐn)?shù)量。那么每個(gè)塊的線程數(shù)為Np×Z。因此,用Nc表示輸入碼字的數(shù)量,為譯碼內(nèi)核分配Nc/Np塊。有Nc/Np塊一起被譯碼,每個(gè)塊由Np×Z個(gè)線程進(jìn)行譯碼。
為了充分利用GPU上的內(nèi)存資源,經(jīng)常訪問(wèn)的值被存儲(chǔ)在共享內(nèi)存中。在本文實(shí)現(xiàn)中,f、s和L被存儲(chǔ)到共享內(nèi)存中。它們的大小分別是1×Z、1×Z和Z×nb。不建議將R放入共享內(nèi)存中。因?yàn)镽的大小是(mb×Z)×kb,BG1中kb=22,最大mb=46。R尺寸過(guò)大,以至于把它放在共享內(nèi)存中可能會(huì)限制譯碼時(shí)常駐塊的數(shù)量,所以本文將R存儲(chǔ)在全局內(nèi)存中。
L的大小只有nb×Z。本文只關(guān)心最后的結(jié)果,中間的結(jié)果會(huì)在后幾層的迭代中被覆蓋。由于譯碼時(shí)經(jīng)常訪問(wèn)L,所以必須要將L放到離計(jì)算單元較近的存儲(chǔ)層次中。在5G新型無(wú)線電中最大的nb=68,Zmax=384。L的大小小于GPU共享存儲(chǔ)的容量。因此將L的值存儲(chǔ)到共享內(nèi)存中,便于GPU的CUDA核心快速訪問(wèn)到L。
以往工作很多都提出了量化方案來(lái)提高LDPC的譯碼吞吐率[20]。在本文實(shí)現(xiàn)中,為了更有效地利用帶寬,同時(shí)減少對(duì)性能的損失,提出了一種兩級(jí)量化方案。
一般來(lái)說(shuō),GPU支持的內(nèi)置類型的最小長(zhǎng)度為8位。小于8位的量化方案不適合基于GPU的高吞吐率譯碼。因?yàn)檩^小的長(zhǎng)度可能會(huì)引入許多類型轉(zhuǎn)換,這些類型轉(zhuǎn)換是為了適應(yīng)CUDA中原生算術(shù)指令支持的最小長(zhǎng)度而執(zhí)行的。與加法和乘法等其他算術(shù)運(yùn)算相比,類型轉(zhuǎn)換在GPU上的吞吐率較低。此外,像AND、XOR以及移位等位元運(yùn)算吞吐率也很低。
L和R的兩級(jí)量化可以節(jié)省片上帶寬。為了實(shí)現(xiàn)高吞吐率譯碼,片上帶寬也是需要考慮的重要因素。
兩級(jí)量化也節(jié)省了共享內(nèi)存和寄存器的空間。駐留塊受共享內(nèi)存占用率的限制。節(jié)省共享內(nèi)存和寄存器有助于實(shí)現(xiàn)更多的并行性。與8位方案相比,兩級(jí)方案的性能損失可以忽略。
數(shù)據(jù)打包可以減少CPU和GPU之間數(shù)據(jù)傳輸造成的譯碼延遲。譯碼器的輸出是二進(jìn)制比特位。雖然在GPU上實(shí)現(xiàn)比特運(yùn)算效率不高,但不難發(fā)現(xiàn),我們可以對(duì)譯碼結(jié)果進(jìn)行打包來(lái)節(jié)省帶寬。在本文實(shí)現(xiàn)中,每8個(gè)譯碼位在硬性決定后打包成一個(gè)8位char值。然后將打包后的數(shù)據(jù)傳輸給CPU。
圖2顯示了譯碼器在GPU上的內(nèi)存層次結(jié)構(gòu)和數(shù)據(jù)打包策略。在譯碼前,輸入數(shù)據(jù)被量化為4位值,中間值為8位值。L,f和s存儲(chǔ)在共享內(nèi)存中;R存儲(chǔ)在全局存儲(chǔ)器中。8個(gè)譯碼后的信息位被打包成一個(gè)char類型的值。然后將打包后的數(shù)據(jù)傳送給CPU。
圖2 內(nèi)存層次和數(shù)據(jù)打包Fig.2 Memory hierarchy and data package
本文在基于圖靈架構(gòu)的Nvidia RTX 2080Ti上實(shí)現(xiàn)了QC-LDPC譯碼器,該譯碼器擁有4 352個(gè)CUDA核心、68個(gè)多處理器和11 GB的GDDR6內(nèi)存,CPU為Inteli7-8700K,CUDA版本為10.2。
在生成編碼值時(shí),采用了正交相移鍵控調(diào)制方式,并用加法白高斯噪聲作為信道噪聲。MSA的尺度因子為0.75,信噪比為3 dB,d=0.15。在測(cè)量譯碼吞吐率時(shí),不采用提前終止法,所以上述參數(shù)設(shè)置為常用值。
表2 不同碼率的基圖
采用不同優(yōu)化方法的譯碼器的吞吐率結(jié)果如表3所示。采用兩級(jí)量化的量化方式,吞吐率提升了2.1倍。采用多碼塊譯碼方法,吞吐率進(jìn)一步提升了18.6%。此外,數(shù)據(jù)打包方案也有很好的效果,與不進(jìn)行數(shù)據(jù)打包的方法相比,吞吐率獲得了16.9%的提高。
表3 不同優(yōu)化方法下吞吐率性能對(duì)比
本文同時(shí)測(cè)量了表2中不同碼率的譯碼吞吐率。對(duì)于高碼率,H會(huì)被縮短。如表2所示,mb和nb的大小隨著碼率的增加而減小。如此,迭代次數(shù)在水平和垂直方向上都相應(yīng)減少,這就造成并行譯碼器的譯碼時(shí)間減少,而吞吐率顯著增加。圖3描述了不同碼率下的譯碼吞吐率。多碼率譯碼的吞吐率比普通譯碼的吞吐率平均提高了40%以上。
圖3 不同碼率下的譯碼吞吐率Fig.3 Decoding throughput under different code ratio
為了最有效地利用GPU上的資源,線程的分配是根據(jù)碼率來(lái)調(diào)整的。眾所周知,每個(gè)線程塊和每個(gè)多處理器的寄存器和共享內(nèi)存的數(shù)量是有限的。此外,為了避免過(guò)載,還要考慮每個(gè)流多處理器(streaming multiprocessor, SM)的最大常駐塊和線程數(shù)。本文將Np、Nr、Nm、Nt表示為每個(gè)塊的碼字?jǐn)?shù)、寄存器數(shù)、共享內(nèi)存數(shù)和線程數(shù),并用RSM、MSM、TSM、BSM表示每個(gè)SM的最大寄存器、共享內(nèi)存、常駐線程和常駐塊,NSM為GPU上SM的數(shù)量,Nb為每個(gè)SM上的常駐塊。
那么就可以得到相應(yīng)的線程分配如下
(18)
同時(shí)被譯碼的碼塊數(shù)量可以用以下方法來(lái)評(píng)估
Nc≤NbNpNSM
(19)
表4 GPU上資源的占用情況
表5描述了RTX 2080Ti上實(shí)現(xiàn)的線程參數(shù)配置情況下的吞吐率情況。為了實(shí)現(xiàn)更高的吞吐率,本文選擇了一個(gè)合適的Np參數(shù)來(lái)實(shí)現(xiàn)。
表5 最佳線程分配和吞吐率
圖4顯示了每個(gè)SM中的最大常駐塊與GPU上的碼率的變化關(guān)系。M、R、T、B分別代表共享內(nèi)存、寄存器、常駐線程和每個(gè)SM的常駐塊。在低碼率情況下,Z很小,限制了每個(gè)SM的最大常駐塊。在高碼率情況下,Z較大,Np和Nc受到每個(gè)塊的最大線程量和最大共享內(nèi)存量的限制。最終的常駐塊是M、R、T、B四個(gè)數(shù)值的最小值。
圖4 每個(gè)SM中的最大常駐塊與r的變化關(guān)系Fig.4 Changing relationship between the maximum resident block in each SM and r
目前,基于GPU的5G新型無(wú)線電的QC-LDPC譯碼器很少。在5G新型無(wú)線電中,信息列的數(shù)量kb較多,達(dá)到22個(gè),而 WiMAX中最大的非零條目是7個(gè)。表6為本文LDPC譯碼器和其他LDPC譯碼器的比較。其中,迭代次數(shù)為10次,譯碼算法為MSA的分層譯碼,表中的吞吐率用Mbit/s表示。雖然我們?cè)谧g碼時(shí)需要處理更多的迭代,但本文提出的譯碼器在高碼率下實(shí)現(xiàn)了Gbit/s的吞吐率,超過(guò)其他相關(guān)工作。另外本文利用吞吐率/峰值性能的比值來(lái)衡量同樣的峰值性能情況下實(shí)現(xiàn)的吞吐率,以此來(lái)比較不同的工作對(duì)GPU峰值性能的利用率。從最終結(jié)果可以看出,本文算法峰值性能利用率也是最高的,證明了本文GPU并行算法及優(yōu)化方法的優(yōu)越性。
表6 不同GPU的譯碼器性能比較
本文提出了一種基于GPU的5G新型無(wú)線電的LDPC譯碼器。同時(shí)提出了基于GPU的并行MSA算法。在實(shí)現(xiàn)細(xì)節(jié)上,本文利用多塊譯碼方法實(shí)現(xiàn)了碼塊內(nèi)的并行譯碼,提出了兩級(jí)量化方案,以進(jìn)一步節(jié)省GPU的片上和片下帶寬。通過(guò)評(píng)估目標(biāo)GPU的最佳線程分配,最終實(shí)現(xiàn)了基于GPU的高吞吐率5G新型無(wú)線電LDPC譯碼器。在(2 080,1 760),r=5/6的配置下,本文提出的譯碼器吞吐率最高可達(dá)到1.38 Gbit/s。