葛 帥 劉榮科 侯 毅

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191)

LDPC(Low-DensityParity-Check)碼由Gallager于1962最早提出［1］，但限于當時的計算機仿真水平，它的出現(xiàn)并沒有得到足夠的重視.直到20世紀末，Mackay，Neal等人發(fā)現(xiàn)其為具有逼近香農(nóng)限性能的優(yōu)秀糾錯編碼，具有很強的糾錯和檢錯能力.準循環(huán)低密度奇偶校驗碼(QCLCPC，Quasi-Cyclic LDPC)以其碼字設(shè)計的低復(fù)雜度，正逐漸取代Turbo碼成為信道編碼的研究熱點.經(jīng)典的LDPC碼的譯碼方式是基于Tanner圖的雙相消息傳遞(TPMP，Two Phase Message Passing)譯碼算法.TPMP譯碼算法具有性能優(yōu)異且易于使用并行計算實現(xiàn)等優(yōu)點.現(xiàn)今采用的LDPC碼譯碼方式大多由TPMP譯碼算法演化而來.由于現(xiàn)今采用的LDPC碼多為準循環(huán)碼，其校驗陣可按行劃分為最大列重不大于1的若干行塊，譯碼時可以將LDPC碼看作若干單校驗分量碼的級聯(lián)碼，利用Turbo原理進行分量碼之間的迭代消息傳遞過程，稱為Turbo消息傳遞(TDMP，Turbo Decoding Message Passing)譯碼算法［2-3］，也稱分層譯碼算法.

在實際應(yīng)用中，為獲得高吞吐量和實時處理能力，LDPC碼的譯碼實現(xiàn)通常采用硬件平臺，如FPGA(Field Pregrammable Gate Arrays).但通常硬件平臺靈活性和可擴展性較差［4-6］，只能勝任某些固定碼率和碼長的LDPC碼的譯碼工作.由于LDPC碼的應(yīng)用場合不斷擴大，對譯碼靈活性、擴展性的要求越來越高，使得傳統(tǒng)硬件平臺實現(xiàn)的LDPC碼的譯碼架構(gòu)難以應(yīng)付多碼長、變碼率譯碼的缺點日益突出.

如今，采用多核并行處理是提升處理器性能的重要方式［7］.圖形處理單元(GPU，Graphic Processing Unit)通常包含成并行結(jié)構(gòu)的海量運算單元.由于市場的需要對GPU所提出的要求越來越高，GPU已經(jīng)發(fā)展成為了并行度高、多線程、計算快速、儲存器帶寬大的高性能通用計算設(shè)備［8-9］.然而傳統(tǒng)的GPU編程大多需依靠如Direct3D或OpenGL的標準圖形接口，這使GPU編程受限于圖形應(yīng)用程序編程接口，使用這些圖像渲染語言要求編程者擁有相應(yīng)的計算機圖形學(xué)知識.Nvidia公司發(fā)布的統(tǒng)一計算設(shè)備架構(gòu)(CUDA，Compute Unified Device Architecture)，通過對標準C語言的一定拓展與改造，使得用戶可以通過類C語言代碼來實現(xiàn)GPU線程的調(diào)度，為GPU在通用計算領(lǐng)域的應(yīng)用提供了良好的開發(fā)環(huán)境.

由于GPU執(zhí)行高并行計算任務(wù)體現(xiàn)出的巨大優(yōu)勢，尤其是其相對于傳統(tǒng)硬件平臺的靈活性與可擴展性優(yōu)勢，其在LDPC碼譯碼領(lǐng)域具有很高的應(yīng)用前景，得到了廣泛的研究.文獻［10］中利用OpenGL提供的標準圖型接口，在Caravela平臺上對5種碼字進行譯碼，相對于CPU譯碼吞吐量獲得3.5倍加速.文獻［11］中利用異步數(shù)據(jù)傳輸技術(shù)在NVIDIA Tesla C1060平臺上相比CPU平臺未優(yōu)化結(jié)果獲得了271倍的譯碼速度提升.文獻［12］中通過分析LDPC碼譯碼的數(shù)據(jù)結(jié)構(gòu)，提出針對GPU平臺的聯(lián)合內(nèi)存訪問的優(yōu)化方式，在NVIDIA 8800GTX平臺和8位精度條件下，獲得了40 MB/s的吞吐量.文獻［13］提出通過充分利用顯存帶寬并引入提前停止準則的方式提高LDPC碼TPMP譯碼的吞吐量.文獻［14］采用一種校驗陣壓縮存儲的方式，將校驗陣存儲在常量內(nèi)存中，對規(guī)則和非規(guī)則QC-LDPC碼，相比傳統(tǒng)存儲方法分別獲得了2倍和1.5倍的加速.

本文提出一種基于Nvidia公司Fermi GPU架構(gòu)的LDPC存儲器優(yōu)化分層譯碼算法實現(xiàn)結(jié)構(gòu)，幀間與幀內(nèi)并行相結(jié)合的并行結(jié)構(gòu)，減少節(jié)點信息更新的運算分支，對全局存儲器采用高效的聯(lián)合內(nèi)存訪問以及使用常數(shù)存儲器.測試結(jié)果表明，在同等硬件條件下，本文提出的基于GPU的兩級并行和合并訪存的譯碼優(yōu)化方案可以顯著提升LDPC譯碼速度.

1 分層譯碼算法

分層算法(TDMP)是一種按照因子圖上的校驗節(jié)點順序進行消息更新傳遞的串行譯碼機制，對目前廣泛應(yīng)用的QC-LDPC碼，將校驗矩陣依據(jù)列重不超過1的原則分為若干行塊，每一行塊為一層，層內(nèi)校驗節(jié)點的更新可并行完成，層間的消息傳遞為串行方式.每層可以定義一個新的校驗矩陣Ct，各層校驗矩陣的總和構(gòu)成了原校驗矩陣，即:

在迭代過程中逐層進行更新，以最后一層的輸出作為當前次迭代的譯碼輸出，進行硬判決以及提前停止校驗.

基于Log-BP的TDMP的算法描述如下:

第一步:初始化信息:

第二步:各層依次進行迭代更新:

在每一層中，對于校驗節(jié)點c和變量節(jié)點v，層間的置信度傳遞如下計算:

第三步:譯碼判決.待一次迭代結(jié)束后將獲得的信息進行比特硬判決:

若譯碼結(jié)果滿足校驗方程或達到最大迭代次數(shù)則終止譯碼迭代.其中，對于第k次迭代中的第t層，校驗節(jié)點 c傳遞給變量節(jié)點 v的信息由Rk，t，cv表示，變量節(jié)點 v傳遞給校驗節(jié)點 c的信息由 Lk，t，cv表示，第 t層傳遞給下一層的變量節(jié)點的信息由 Lk，t，v表示，Li表示從信道接收得到的對數(shù)似然比軟信息，log-BP算法中的函數(shù)φ(x)定義為

相較于傳統(tǒng)的TPMP譯碼算法，分層譯碼算法對比特節(jié)點的信息利用更加及時，對每一層進行并行譯碼后，立即將更新的置信信息傳遞到下一層進行置信度更新，減少了譯碼的迭代次數(shù).根據(jù)文獻［3］，相對于TPMP算法，分層譯碼算法能夠?qū)⑹諗康螖?shù)降低約50%.

部分并行的分層譯碼算法利于并行資源受限的GPU平臺進行譯碼結(jié)構(gòu)實現(xiàn)，尤其是碼長上千的中長碼.本文提出的分層譯碼結(jié)構(gòu)利用幀間與幀內(nèi)并行相結(jié)合，充分發(fā)掘了GPU運算潛力.

2 結(jié)構(gòu)優(yōu)化設(shè)計

2.1 校驗陣壓縮與constant memory

constant memory是GPU的片上只讀存儲器，其訪問延遲相比片外顯存中的global memory低兩個數(shù)量級.在Fermi架構(gòu)中，constant memory存儲空間為64 KB，多用于存儲CUDA程序中需讀取頻繁的只讀參數(shù).對于計算能力為2.x的GPU，當屬于同一個half-warp的線程訪問constant memory中的同一數(shù)據(jù)時，則發(fā)生數(shù)據(jù)廣播，只需一個訪存周期即可獲取數(shù)據(jù).

傳統(tǒng)的校驗陣存儲方式是將校驗陣中每一行的非零元素所對應(yīng)的列號依次存儲至片下global memory存儲器中.譯碼過程中對校驗陣的頻繁讀取會導(dǎo)致譯碼延遲.本文提出的LDPC碼分層譯碼結(jié)構(gòu)采用constant memory存儲校驗矩陣，如圖1.短碼的校驗矩陣可以直接寫入存儲器，但對中長碼，其校驗矩陣規(guī)模遠超過constant memory大小，必須對校驗陣進行壓縮存儲.

對于大部分QC-LCPC碼，其校驗矩陣可分割為多個子方陣，每個子方陣為零陣或經(jīng)循環(huán)右移后的單位陣.對非零子陣，其所在列號、層號、層內(nèi)序號及右移次數(shù)即可表征其全部性質(zhì)，層內(nèi)序號U指本子陣在本層內(nèi)為第U個非零子陣.存儲校驗陣時，僅需記錄非零子陣的位置信息與其單位陣右移位數(shù)即可.如圖1所示，將第L層層內(nèi)序號為U非零子陣的列號及其循環(huán)右移的位數(shù)分別存至兩個位寬為32 byte的constant memory區(qū)塊中的第L行第U列內(nèi).故存儲校驗陣非零子陣列號及右移次數(shù)所需空間分別為G×32 byte.其中G為校驗陣總層數(shù).以碼長40960校驗位24576，子方陣階數(shù)2048的QC-LDPC碼為例，校驗陣層數(shù)為G=24576/2048=12，存儲空間共需32×12×2=768 byte.

圖1 校驗陣壓縮方式

2.2 global memory的聯(lián)合訪問

global memory位于GPU片外的顯存中，在聯(lián)合讀取的條件下，global memory可提供很高的訪問帶寬，否則會產(chǎn)生分區(qū)訪問沖突，造成較高的訪存延遲.聯(lián)合訪問是指對于計算性能為2.x的Fermi架構(gòu)GPU，當同一warp中的32個線程按照一定字長依次訪問對齊后的數(shù)據(jù)段時，僅需一次傳輸就可處理warp內(nèi)線程的訪存要求.

對QC-LDPC碼的分層譯碼結(jié)構(gòu)，式(2)、式(3)中的 Rk，t，cv和 Lk，t，v的對數(shù)似然比數(shù)值存儲于global memory中.對于一個校驗陣大小為P×Q，子陣為D階方陣最大行重為B的QC-LDPC碼，對校驗節(jié)點 c傳遞給變量節(jié)點 v的信息 Rk，t，cv，傳統(tǒng)的訪存方式的存儲地址為

其中，pc為當前線程更新的 Rk，t，cv對應(yīng)列號;U 為當前線程更新的 Rk，t，cv所在子陣的層內(nèi)序號，這種訪存方式的訪存位置依據(jù)于線程處理的Rk，t，cv對應(yīng)于校驗陣的位置，易于理解，但訪存不能滿足聯(lián)合的訪問要求.

本文提出的訪存模式如圖2所示，Rk，t，cv的存儲位置不依據(jù)校驗陣的位置，而依據(jù)于線程所在線程網(wǎng)格的位置.通過對 Rk，t，cv重新排列，將編號為 T 的線程所讀取的 Rk，t，cv存放于:

T代表當前線程編號;M代表該線程所處線程塊編號.通過重排不同線程訪存地址隨線程號增加，使得每個線程塊內(nèi)的線程依次訪問global memory內(nèi)連續(xù)存儲空間，滿足聯(lián)合存儲要求.

對于譯碼過程中層間傳遞信息 Lk，t，v，傳統(tǒng)訪存方法為按塊對齊，當某warp訪問至對齊邊緣時，若不能滿足同一warp內(nèi)的32個線程同時處于對齊邊緣內(nèi)，則會產(chǎn)生分區(qū)沖突，導(dǎo)致多次訪存.如圖3a中，當某warp訪問至子塊邊緣時，若第K號線程與第K+1號線程屬于同一warp，則會發(fā)生分區(qū)訪問沖突.

圖2 Rk，t，cv 聯(lián)合存儲信息更新模式

圖3 更新至子塊邊緣時訪存狀況

對此，本文所提譯碼結(jié)構(gòu)采用圖4所示訪存模式:圖中W為warp的包含的線程總數(shù)，對于Fermi架構(gòu)的GPU，W取為32.圖中LK，D代表第K個子塊中的第D個層間傳遞信息，在按塊大小對齊的原信息塊基礎(chǔ)上前后分別添加長度為W-1的數(shù)據(jù)作為對齊頭和補齊尾，將第K個子塊的前W-1個數(shù)據(jù)拷貝至第K個子塊的補齊尾，將第K個子塊的后W-1個數(shù)據(jù)拷貝至第K個子塊的對齊頭，并保持數(shù)據(jù)同步.當某warp訪問至對齊邊緣時，如圖3b，若第K號線程與第K+1號線程屬于同一warp，則將線程號大于K的線程得出的層間傳遞信息數(shù)據(jù)寫入補齊尾，以保證同一warp內(nèi)的線程數(shù)據(jù)滿足聯(lián)合讀取，再將補齊尾中的數(shù)據(jù)同步至原始數(shù)據(jù)中對應(yīng)的字段.譯碼判決時，只需舍棄對齊頭與補齊尾，便可進行譯碼判決.

圖4 Lk，t，v 聯(lián)合存儲信息更新模式

2.3 多幀并行處理

對于Fermi架構(gòu)的 GPU，每個流多處理器(SM，Streaming Multiprocessor)至少需運行576個線程才能隱藏算數(shù)流水延遲.而分層譯碼算法要求每一層的列重至多為1，這限制了GPU架構(gòu)下分層譯碼結(jié)構(gòu)的并行度，對GPU資源形成浪費.以本文在實驗中采用的40 960×24 576層寬為2048的QC-LDPC碼為例，單個碼字的最大并行度即為層寬，假設(shè)每個SM內(nèi)放置1 024個線程，則譯碼過程占用兩個 SM，僅為 GeForce GTX580提供的SM總數(shù)的12.5%.

對此，本文采用多幀并行處理，即在GPU內(nèi)并行進行多幀譯碼，以提高GPU資源利用率.文獻［14］中指出多幀處理會帶來大量條件分支，在GPU架構(gòu)下將導(dǎo)致warp內(nèi)的指令執(zhí)行延遲增加，降低譯碼吞吐量.本文采用減少控制流指令及謂詞執(zhí)行(predicate execution)的方式以減少條件分支對譯碼吞吐量的影響.謂詞執(zhí)行是指將分支中的指令作為代碼塊處理，并將其中指令與謂詞關(guān)聯(lián)，執(zhí)行時，謂詞為假的指令隨謂詞為真的指令共同執(zhí)行，但不將結(jié)果寫回.

表1以利用 GeForceGTX580GPU對40960×24576層寬為2048的LDPC碼進行譯碼為例，分別展示了采用8幀并行處理與單幀處理時GPU內(nèi)的資源的利用情況以及可用運算資源總量.

表1 單幀處理與8幀并行時GPU資源使用情況

由表1可得，采用多幀并行處理技術(shù)可以提高SM的使用效率，更好的利用GPU提供的資源.圖5展示了信噪比為1.1 dB時在不同并行幀數(shù)下相對于單幀處理時的譯碼吞吐量倍率.

根據(jù)圖5，在GPU架構(gòu)下采用多幀并行可以的提升LDPC碼譯碼的吞吐量.

圖5 不同并行幀數(shù)下譯碼吞吐量

3 實驗結(jié)果

3.1 硬件原則與編譯環(huán)境

表2顯示了本文采用并行譯碼結(jié)構(gòu)硬件環(huán)境.其中基于 GPU的 LDPC碼譯碼結(jié)構(gòu)采用Nvidia公司CUDA4.0版本編譯器編譯，基于CPU的LDPC碼譯碼結(jié)構(gòu)則采用Visual Studio 2010提供的標準的C編譯器編譯.

表2 硬件環(huán)境

3.2 測試結(jié)果

本文對所提出的分層譯碼結(jié)構(gòu)在兩種不同長度的QC-LDPC碼條件下分別進行測試，最大迭代次數(shù)設(shè)定為20次.H矩陣選取CCSDS標準［15］中的碼型.校驗矩陣的詳細參數(shù)參見表3.

在消息迭代過程中本文采用32 bit量化標準以及雙曲正切函數(shù)實時計算的方式，以獲得更優(yōu)的譯碼性能，相比FPGA譯碼實現(xiàn)平臺，GPU平臺具備更優(yōu)秀的高精度運算優(yōu)勢.

表3 校驗陣參數(shù)

表4、表5為對10 000幀進行譯碼所需時間以及吞吐量對比.其中表4是校驗矩陣為H1信噪比為1.8 dB對應(yīng)的測試結(jié)果，表5是校驗矩陣為H2信噪比為1.1 dB的測試結(jié)果.其中優(yōu)化方式Ⅰ代表global memory聯(lián)合訪問的優(yōu)化方式，優(yōu)化方式Ⅱ代表校驗陣壓縮與采用constant memory優(yōu)化方式.其中H1和H2分別采用并行度為32和8的多幀并行譯碼.

表4 檢驗矩陣為H1時譯碼時間與吞吐量

表5 檢驗矩陣為H2時譯碼時間與吞吐量

根據(jù)表4、表5，對于10000幀進行譯碼時，校驗矩陣為H1和H2的碼對應(yīng)的譯碼時間分別為2.38 s和15.4 s，而未優(yōu)化的譯碼時間則分別為80.97s和230.8s，優(yōu)化后的相對于未優(yōu)化的GPU譯碼吞吐量分別提升34.8倍和14.9倍.

分塊子矩陣的維數(shù)即碼字層寬較低時，吞吐量的提升較大，其主要原因是碼字層寬較低時采用多幀處理對吞吐量的提升較大.通過采用多幀并行處理可以分別提升校驗陣為H1的碼字和校驗陣為H2的碼字譯碼速度12.4倍和6.1倍，這是由于校驗陣為H1的碼字層寬即分塊子矩陣的維數(shù)為256，采用單幀處理時最高并行度為256，嚴重限制了GPU譯碼器的并行度.在采用多幀并行處理時對分塊子矩陣的維數(shù)較低的LDPC碼可采用較高的并行幀數(shù)，以獲得更大的吞吐量提升.由此可得對于利用分層譯碼算法對分塊子矩陣的維數(shù)較低的LDPC碼進行譯碼時采用多幀并行處理優(yōu)化效果優(yōu)于對分塊子矩陣的維數(shù)較高的LDPC碼進行分層譯碼算法，可以有效消除幀內(nèi)并行度不足對譯碼吞吐造成的限制.

采用global memory的聯(lián)合訪問的優(yōu)化方式對于譯碼速度的提升達到約1.8倍，這是由于未優(yōu)化的譯碼器在消息節(jié)點更新過程中由于訪存沖突導(dǎo)致極大地訪存延遲.

采用constant memory存儲校驗陣對于對校驗陣為H1和H2的碼字速度提升別為1.6倍和1.35倍.對于校驗陣為 H1的 LDPC碼采用constant memory存儲校驗陣優(yōu)化效果優(yōu)于校驗陣為H2的 LDPC碼，這是由于校驗陣為 H1的LDPC碼的平均行重和列重大于校驗陣為H2的LDPC碼，譯碼過程中對校驗陣讀取更加頻繁，因此采用此優(yōu)化方式效果相對更明顯.

4 結(jié)論

1)本文提出一種新的基于Fermi架構(gòu)GPU平臺下的QC-LDPC碼存儲器優(yōu)化并行譯碼結(jié)構(gòu)設(shè)計.本設(shè)計采用32 bit精度值的分層譯碼算法.實驗結(jié)果表明，相對于未優(yōu)化GPU平臺下分層算法譯碼結(jié)構(gòu)，本文提出譯碼結(jié)構(gòu)在校驗陣為7168×4096層寬為256和校驗陣為40960×24 576層寬為2048的QC-LCPC碼情況下分別可以獲得34.8倍和14.9倍的譯碼吞吐量提升.

2)通過采用多幀并行譯碼處理，可提高譯碼并行度，分塊子矩陣的維數(shù)較低時，GPU譯碼器的并行度受到限制，采用本文的多幀并行譯碼處理對譯碼速度提升效果尤為顯著.通過采用多幀并行處理可以分別提升子矩陣維度為256和2048的QC-LDPC碼譯碼吞吐量12.4倍和6.1倍.

3)在校驗陣為7168×4096層寬為256和校驗陣為40 960×24 576層寬為2 048的QC-LCPC碼情況下，采用global memory的聯(lián)合訪問以及constant memory存儲壓縮校驗陣兩種優(yōu)化方式分別可以提升譯碼吞吐量2.76倍和2.45倍.

References)

［1］ Gallager R G.Low-density-parity-check-codes［J］.IRE Trans-In-formation Theory，1962，18:21-28

［2］ Mansour M M，Shanbhag N R.Turbo decoder architectures for low-density parity-check codes［C］//Chi-kuo Mao.Global Telecommunications Conference.Taipei:Cornell University，2002:1383-1388

［3］ Mansour M M，Shanbhag N R.A 640-Mb/s 2048-bit programmable LDPC decoder chip［J］.IEEE Journal on Solid-State Circuits，2006，41(3):684-698

［4］ Zhang T，Parhi K.Joint(3，k)-regular LDPC code and decoder/encoder design［J］.IEEE Trans Signal Processing，2004，52(4):1065-1079

［5］ Dielissen J，Hekstra A.Low cost LDPC decoder for DVB-S2［C］//Cyprian Grassmann.Proc Conf Design，Automation and Test in Europe(DATE ’06).Munich，Germany:Designers’Forum，2006:130-136

［6］ Daesun Oh，Keshab K Parhi.Low-complexity switch network for reconfigurable LDPC decoders［J］.IEEE Transactions on Very Large Scale Integration Systems，2010，18(1):85-94

［7］ Blake G，Dreslinski R G，Mudge T.A survey of multicore processors［J］.IEEE Signal Processing Magazine，2009，26(6):26-37

［8］ Sanders J，Kandrot E.CUDA by example［M］.New Jersey，USA:Addison-Wesley，2010:4-6

［9］ Goodnight N，Wang R，Humphreys G.Computation on programmable graphics hardware［J］.IEEE Computer Graphics and Applications，2005，25(5):12-15

［10］ Falc?o G，Yamagiwa S，Silva V L.Parallel LDPC decoding on GPUs using a stream-based computing approach［J］.Journal of Computer Science and Technology，2006，24:913-924

［11］ Chang Chengchun，Chang Yanglang，Huang Minyu，et al.Accelerating regular LDPC code decoders on GPUs［J］.IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing September，2011，4(3):653-659

［12］ Gabriel Falc?o，Leonel Sousa，Vitor Silva.Massively LDPC decoding on multicore architectures［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22(2):309-322

［13］ Wang Guohui，Wu Michael，Sun Yang.A massively parallel implementation of QC-LDPC decoder on GPU［C］//Walid Najjar.2011 IEEE 9th Symposium on Application Specific Processors.San Diego，CA，USA:IEEE Computer Society，2011:82-85

［14］ Ji Hyunwoo，Cho Junho，Sung Wonyong.Memory access optimized implementation of cyclic and quasi-cyclic LDPC codes on a GPGPU ［J］.Journal of Signal Processing Systems，2010，64(1):149-159

［15］ CCSDS 131.1-O-2 Low density parity check codes for use in near-earth and deep space applications［S］