基于GPU的低密度奇偶校驗碼譯碼加速技術

徐啟迪，劉爭紅，鄭 霖

（廣西無線寬帶通信與信號處理重點實驗室（桂林電子科技大學），廣西 桂林 541004）

0 引言

軟件無線電就是采用軟件的方式來實現(xiàn)無線通信系統(tǒng)中的各種功能，是繼無線通信技術從模擬制式過渡到數(shù)字后的又一次革命性的飛躍。目前，存在有多種主流的軟件定義無線電（Software Defined Radio，SDR）硬件平臺結構。基于現(xiàn)場可編程邏輯門陣列（Field Programmable Gate Array，F(xiàn)PGA）架構的SDR 結構由中心處理器進行全部資源調配和邏輯控制，由FPGA 完成計算量較大的基帶信號處理，其架構特點傾向于多指令單數(shù)據(jù)（Multiple Instruction Single Data，MISD）方式，而實際上無線通信信號更合適用單指令多數(shù)據(jù)（Single Instruction Multiple Data，SIMD）方式處理。另外一種基于中央處理器（Central Processing Unit，CPU）的SDR 結構則是通過CPU 來運行信號處理系統(tǒng)，雖然此類SDR結構對通信系統(tǒng)的開發(fā)與維護提供了更便利的實現(xiàn)方式，但無線通信運行過程中常伴隨著大量的數(shù)據(jù)并行運算，CPU 流式架構的指令執(zhí)行方式難以滿足寬帶通信系統(tǒng)的實時性要求。

圖形處理器（Graphic Processing Unit，GPU）由數(shù)量眾多的計算單元和超長的流水線組成，適合處理數(shù)據(jù)類型高度一致、相互無依賴的大規(guī)模數(shù)據(jù)。GPU 作為高并行度的運算設備，相較于FPGA 更易于編程實現(xiàn)與修訂，且在邏輯資源的拓展中更具有優(yōu)勢，成本也更低。與CPU 相比，GPU 代表的眾核架構一般存在數(shù)千個運算核心，這使得GPU 在應對信號處理中超大的數(shù)據(jù)時比CPU 更具有超高速計算能力和超大數(shù)據(jù)處理帶寬，如NVIDIA TITAN RTX 系列GPU 峰值吞吐量為16.3 TFLOPS（參考網(wǎng)址https：//developer.nvidia.com/cuda-gpus），該吞吐量是目前主流CPU 的數(shù)十倍到數(shù)百倍以上，其主流設計平臺是以C/C++語言為基礎的計算統(tǒng)一設備架構（Compute Unified Device Architecture，CUDA）。

低密度奇偶校驗（Low Density Parity Check，LDPC）碼具有誤碼率低、低時延和校驗矩陣構造簡單的特點，糾錯能力接近香 農極限。它 于1962 年 被Gallager［1］和Tanner［2］發(fā) 明，并隨之提出了相應的迭代譯碼算法。1996 年LDPC 碼受到Tanner［2］和MacKay 等［3］重視，并在其基礎上提出了優(yōu)化后的置信傳播（Belief Propagation，BP）譯碼算法。之后，Chen 等［4］將BP 算法的復雜度進一步降低，在犧牲一定譯碼性能的情況下提出了最小和（Min-Sum，MS）譯碼算法，該算法極大地簡化了關于LDPC 譯碼中節(jié)點更新的計算復雜度，并且不需要對加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道進行噪聲功率估計。近年來，也有不少專家致力于LDPC 碼的研究，文獻［5］中基于BP 算法的LDPC 卷積碼的窗口解碼方案，提出了對于BP 解碼器和加窗解碼器，探討在無記憶擦除信道上獲得接近理論極限的性能。文獻［6］中則通過將多個不相交或未耦合的LDPC 碼Tanner 圖耦合到一個耦合鏈中，用一種新的方式利用低復雜度譯碼在無內存的二進制輸入對稱輸出通道上構建實現(xiàn)代碼。文獻［7-8］中提出的空間耦合LDPC 碼構建方式在相應的應用場景有著更優(yōu)秀的性能。與此同時，非二進制（Non-Binary）LDPC 碼也在飛速地更新發(fā)展，文獻［9］中在考慮了非二進制的準循環(huán)LDPC 碼特征的情況下，提出了早期分層解碼調度方案，實現(xiàn)了比以往更大更高的吞吐量和效率；文獻［10］中則將有限域上的非二進制低密度奇偶校驗（Non Binary-Low Density Parity Check，NB-LDPC）碼視為子域上的碼，在略微損失性能的情況下降低了解碼復雜度。

LDPC 譯碼器常用的主流框架為FPGA 架構，隨著GPU設計理念的不斷更新迭代，研究者也開始探尋基于GPU 架構設計譯碼器的可能性。文獻［11］中提出了一種在CUDA平臺的并行滑動窗口置信傳播（Sliding Window Belief Propagation）算法來解碼LDPC 碼字，提出的基于CPU+GPU的異構并行算法相比CPU 架構獲得了14～118 倍的加速比。文獻［12］中分析了FPGA 架構的缺點，探討了GPU 架構以更短的部署周期、靈活開發(fā)且可擴展成本更低的優(yōu)點作為替代方案的可能，并且在高碼率、采用提前中止策略的情況下獲得了較高的吞吐量。文獻［13］中實現(xiàn)了基于GPU 的加權比特可靠性（weighted Bit Reliability Based，wBRB）解碼器，并探討了在列度較大、速率較高情況下所提出譯碼器平衡誤碼性能和吞吐量性能的方法。文獻［14］中額外使用了GPU 的高速片上內存，使得普通GPU 譯碼器的性能提升了5.32～10.41 倍，文獻［15］中的GPU 增強準最大似然（Enhanced Quasi-Maximum Likelihood，EQML）譯碼器則在保持糾錯性能的同時譯碼速度相較于CPU 提升了約2 個數(shù)量級。

1 LDPC譯碼原理

1.1 NMS譯碼算法

LDPC 的BP 譯碼算法的主要思路是通過消息傳播將當前節(jié)點的概率分布狀態(tài)傳遞給相鄰的節(jié)點，并且更新相鄰某節(jié)點的概率分布狀態(tài)，進而讓節(jié)點的概率分布狀態(tài)在多次更新中得到收斂；但由于算法雙曲正切（tanh）函數(shù)的存在，使得譯碼過程中的計算極為復雜。歸一化最小和（Normalized Min Sum，NMS）算法是在BP 算法的基礎上對復雜的運算操作進行簡化的一種算法，如式（2）所示，用和積運算替換了tanh 操作，從而降低了計算的復雜度。NMS 算法的另一個優(yōu)勢在于初始化軟信息時不需要相關的信道信息，算法步驟如下所示：

1）初始化。

其中：L(rij)為校驗節(jié)點i傳給變量節(jié)點j的信息，Lj為信號的初始信息，yj為實際接收碼字，L(qji)表示變量節(jié)點j傳給校驗節(jié)點i的信息。

2）更新校驗節(jié)點、變量節(jié)點信息。

式（2）中Rij表示與校驗節(jié)點i相連的變量節(jié)點的集合Ri與第j變量節(jié)點的差集，式（3）中Cji表示與變量節(jié)點j相連的變量節(jié)點的集合Cj與第i校驗節(jié)點的差集。

3）信息更新并判決。

式（4）中表示每次迭代更新后的軟信息。式（5）則根據(jù)線性分組碼的特性，判斷是否滿足HcT=0 或譯碼循環(huán)迭代次數(shù)是否達到最大：是則停止迭代并直接輸出譯碼碼字c；否則跳轉到步驟2 重新迭代，其中H為校驗矩陣。

NMS 算法優(yōu)化了迭代中節(jié)點信息的更新方式，同時在譯碼迭代過程中加入了系數(shù)α(0 ＜α＜1)來彌補譯碼過程中因簡化計算方式而導致的性能損失。

1.2 分層譯碼算法

LDPC 譯碼方法中消息的傳遞方式主要分為兩種形式：泛洪式（Flooding）譯碼方案和分層（Layered）譯碼方案。泛洪式譯碼作為傳統(tǒng)的譯碼方案，其譯碼過程如上述NMS 譯碼算法所示，在迭代過程中通過依照H的非零項順序逐行更新變量節(jié)點，然后逐列更新變量節(jié)點來完成譯碼。分層式歸一化最小和（Layered Normalized Min Sum，LNMS）方案則與前者不同，主要是將H矩陣按某種特定的規(guī)則在行層面分層，按層結構對每一層的節(jié)點信息進行更新，然后將更新好的消息直接傳入下一層作為已知參數(shù)繼續(xù)更新消息。以NMS 算法為例，其分層譯碼過程如下所示：

1）初始化。

2）分層更新。

分層譯碼方案的優(yōu)勢在于能將本次迭代中已經(jīng)計算出的校驗節(jié)點信息及時地更新到總的節(jié)點信息中，使其可以用于計算下一個校驗節(jié)點的校驗信息，這將極大地提高譯碼的收斂速度。通過Matlab 仿真證明，分層消息傳遞機制的平均譯碼迭代次數(shù)在相同的信道環(huán)境下是泛洪式消息傳遞機制的一半，且分層譯碼機制的優(yōu)勢在于較少的中間變量更加適合通過硬件實現(xiàn)，節(jié)省硬件資源。

圖1 展示了基于NMS 算法IEEE 802.16 標準下各算法性能對比，其中，所有算法的迭代次數(shù)上限為10 次，并添加了迭代的提前終止條件。可以看出，在泛洪式和分層譯碼結構下，BP 算法性能最佳，NMS 算法次之，硬判決算法性能最差；對比兩種結構的譯碼方案，分層譯碼方案能在更少的迭代次數(shù)下取得更好的譯碼性能。

圖1 LDPC譯碼算法性能對比Fig.1 Performance comparison of LDPC decoding algorithms

2 并行譯碼方案

LDPC 碼的譯碼過程中涉及多次且復雜的運算，這導致流式的LDPC 譯碼器在高速無線通信系統(tǒng)中無法滿足系統(tǒng)的實時性要求，造成較大時延。分析LDPC 的譯碼流程可看出，迭代過程中各校驗節(jié)點與變量節(jié)點軟信息的更新之間并無依賴關系，因此等信息的迭代更新可以采用GPU 進行加速，利用GPU 的多線程和高并行性將會極大地提高LDPC 譯碼器的譯碼效率和減小譯碼延遲。

2.1 并行框架

本文采用的并行方式為以分層譯碼機制為基礎的針對準循環(huán)低密度奇偶校驗（Quasi Cyclic-Low Density Parity Check，QC-LDPC）碼的部分并行譯碼。LDPC 譯碼算法的流程如圖2 所示，分別使用基于CPU 的流串行式和基于CPU+GPU 的異構并行式對譯碼算法中的部分流程進行處理。

圖2 LNMS譯碼算法流程Fig.2 Flow chart of LNMS decoding algorithm

設DataNums為檢驗矩陣H的基矩陣Hb中的非零項數(shù)量，Zc為H的擴展因子，M為Hb的行數(shù)，RowDegree為H的最大行重。從LDPC 碼的譯碼過程可知，傳統(tǒng)串行譯碼在每一次更新校驗節(jié)點或變量節(jié)點時需遍歷DataNums個的數(shù)據(jù)，在分層譯碼機制下，這些數(shù)據(jù)的更新只與上一層傳遞的消息有關；因此，可將QC-LDPC 碼的校驗矩陣以基矩陣Hb的形式，按Zc行劃分M個子矩陣，則每個子矩陣是維度為Zc×N、列重不大于1 的稀疏矩陣，并分配Zc×RowDegree個線程對每一層的子矩陣進行譯碼。具體的和等信息更新的并行策略如圖3 所示，以行重、列重分別為3、1，Zc為6 的子矩陣為例，則總共需要分配18 個線程進行計算。

圖3 并行策略Fig.3 Parallel strategy

根據(jù)圖3 的并行策略可以擴展到實際的LDPC 碼并行分層NMS 譯碼算法設計。現(xiàn)考慮一個序號為id的線程，有：

其中：blockId為當前線程（thread）所處的線程塊索引，threadId則為所處線程塊中的線程索引，threadNum為單個線程塊擁有的線程數(shù)。將id代入式（7）～（10）中的j變量，變量i則對應校驗矩陣H第m層中第id列非0 位置的行數(shù)索引。

LNMS 的GPU 并行思路是在不同層迭代時調用不同數(shù)量的線程以完成分層NMS 算法的并行實現(xiàn)，具體流程如算法1 所示。

算法1 基于GPU 的LNMS 算法。

算法1 中MaxIter為最大迭代次數(shù)，chunkNum為校驗矩陣的行子矩陣數(shù)量，RowNum為基矩陣對應行的行度，由于本文使用的是非規(guī)則LDPC 碼，所以RowNum的大小是擴展因子Zc與基矩陣各行行重的乘積，Syncthreads 和threadfence均為CUDA 內置函數(shù)。對接收的信號進行初始化后，依據(jù)校驗矩陣H對其進行分層譯碼，考慮到校驗矩陣存在非規(guī)則的情況，即每一層的行度可能不一致，因此事先將每一子矩陣行度儲存在RowNum矩陣中，該算法的并行部分主要體現(xiàn)在更新第m行節(jié)點信息時都使用RowNum［m］個線程進行處理。

2.2 全局同步

LDPC 碼的譯碼步驟之間存在著依賴關系，即當前步驟計算所需的數(shù)據(jù)依賴于上一步所得數(shù)據(jù)，且在程序初始化的并行配置中需要用到多個線程塊；因此，在CUDA 核函數(shù)中間有必要適當?shù)貙PU 設備中的全局內存進行數(shù)據(jù)同步，即需要每個線程塊在完成上一步驟之后對所有的線程塊進行全局同步，以統(tǒng)籌、更新數(shù)據(jù)。常見的處理方式為使用多個核函數(shù)進行串行處理，但是會造成額外的時間損耗。因此本文采用的方式是在單個核函數(shù)上進行數(shù)據(jù)同步。CUDA編程中雖然沒有針對網(wǎng)格之間同步的函數(shù)，但是譯碼數(shù)據(jù)的全局同步可以采用如圖4 所示的方式實現(xiàn)。

Syncthreads 函數(shù)為程序中的顯式柵欄，要求塊內的線程必須等待直到所有線程完成先前的操作。threadfence 函數(shù)將阻塞調用線程，直到當前線程對全局內存或共享內存的寫入對其他線程可見為止。atomicAdd 為CUDA 原子操作，保證了在同一個顯存變量依次進行“讀-計算-寫”操作時的連貫執(zhí)行，而不會被其他線程進行中斷。

如圖4 所示，實線箭頭為該線程實際的運行時間，虛線箭頭為該線程的等待時間，可以看出每個線程塊（Block）中的所有線程在完成任務后首線程進入while 循環(huán)，并等待其他線程塊是否到達障礙點。若所有的線程塊完成操作，則進入下一階段運算。這種全局內存同步方式可實現(xiàn)憑單個核函數(shù)就能完成單個碼字的譯碼，并可以拓展到多個碼字的情況。

圖4 同步實現(xiàn)方式Fig.4 Synchronization implementation method

2.3 矩陣壓縮

LNMS 算法在譯碼過程中需要頻繁地使用校驗矩陣H，如果將校驗矩陣信息直接儲存在GPU 內存會導致顯存空間的大量占用，同時也不利于數(shù)據(jù)的位置索引與調度。本文在參考文獻［16］中構造壓縮矩陣的基礎上，給出一種不規(guī)則LDPC 碼的校驗矩陣壓縮存儲方案：將校驗矩陣H分解為1個二維矩陣HRow和1 個一維矩陣RowNum，其中HRow存儲著H矩陣中每行的非0 項元素的列索引，RowNum存放著H矩陣每行的非0 項元素的數(shù)量，這兩個矩陣中包含了譯碼過程中所需的所有校驗矩陣信息。可以看出，由于校驗矩陣的稀疏性，一個M行N列、行重和列重分別為m和n的矩陣H，m和n遠遠小于M和N，經(jīng)壓縮后只需要M（m+1）個數(shù)據(jù)即可完整表示H矩陣的所有所需信息，矩陣的壓縮效率與m有關。此外，譯碼迭代中的等概率信息也將以這種方式構建，矩陣內元素的位置索引可直接從壓縮后的矩陣獲得，而無需額外的內存空間儲存信息；同樣地，在對節(jié)點信息進行更新時也能調用更少的線程，進而節(jié)省GPU 設備資源。與此相同，規(guī)則LDPC 碼這種壓縮方式也適用于本文所使用的非規(guī)則LDPC 碼。

2.4 優(yōu)化策略

CUDA 程序運行前后需要先在CPU 和GPU 之間通過PCI-E 總線進行數(shù)據(jù)通信，數(shù)據(jù)的傳輸速度取決于總線的帶寬，這一部分數(shù)據(jù)通信的時間是除了kernel 執(zhí)行函數(shù)之外額外的時間損耗。因此，為了優(yōu)化CPU 與GPU 之間的數(shù)據(jù)調度機制，引入了CUDA 的流并行機制對多個輸入碼字進行并行處理。

常量內存（Constant memory）在每個SM 中有專用的片上緩存，大小一般限制為64 KB，在常量緩存中讀取內存比直接在全局內存中讀取的延遲要小得多；因此可將類似校驗矩陣H經(jīng)壓縮后的HRow和RowNum等不需要改寫的數(shù)據(jù)放入常量內存中，以減少譯碼延遲。

3 實驗與結果分析

3.1 實驗環(huán)境

本文實驗所用的CPU 為Intel Xeon Gold 5122 CPU @3.60 GHz，GPU 為Quardro RTX 5000，該顯卡 全局內存為16 GB，計算機內存為64 GB，操作系統(tǒng)為Ubuntu 18.04.5 LTS，64 bit，編程環(huán)境為CUDA 11.0，GCC 版本為gcc 7.5.0，Cmake 版本為cmake 3.19.2 Linux。本文實驗的GPU 端代碼使用CUDA C 編寫，CPU 端代碼使用C/C++編寫，編譯、調試方式采用CMake 工具。

3.2 性能分析

并行算法的加速性能一般使用加速比表示，加速比的大小取決于算法中串行與并行部分的占比和GPU 的處理器數(shù)量，如式（10）所示，可通過計算譯碼時延獲得加速比：

其中：CPU_version_run_time為LDPC 譯碼程序在CPU 上運行的實際時間；GPU_version_run_time則是程序在GPU+CPU 異構平臺上運行的實際時間。圖5 為各種并行碼字數(shù)量下加速比的性能曲線，縱軸已進行對數(shù)處理。對于譯碼器的性能常用吞吐量衡量，如式（11）所示：

圖5 多碼字并行度下的加速比性能Fig.5 Speedup performance under multi-codeword parallelism

其中：Throughput為吞吐量（b/s），N為碼字的位數(shù)（bit），Cn為并行的碼字數(shù)量，Tp為迭代次數(shù)，T為單次迭代時延（s）。在實際測試中，根據(jù)碼字并行的數(shù)量不同，吞吐量性能如圖6所示，其中使用的碼字結構為（2 034，1 152）的QC-LDPC，調制方式為BPSK 調制，信道為高斯白噪聲信道。譯碼器未設置迭代提前結束條件，因此，所使用的算法一直持續(xù)到最大迭代次數(shù)；同時，為了查看所提出譯碼的實際性能，本文經(jīng)過多次測量得出了保證最佳誤碼率結果所需的迭代次數(shù)，固定為10 次，所測并行碼字數(shù)量為1～10 000。由于GPU 設備的設置時間與譯碼器實際性能無關且會影響吞吐量的計算，因此測試中忽略了GPU 設備的初始化時間。本文所進行的測試均在移植了譯碼CUDA 程序的GNU Raido 平臺上進行。

圖6 多碼字并行度下的吞吐量性能對比Fig.6 Comparison of throughput performance under multi-codeword parallelism

由圖5 可知，隨著并行碼字的增加，加速比逐漸增加，并在約4 000 個碼字并行時達到峰值，隨后譯碼器的加速比穩(wěn)定維持在200 倍左右。經(jīng)驗證，該譯碼器的誤碼率性能與圖1 中Matlab 仿真的結果基本相同，無額外的譯碼性能損失。值得注意的是，在碼字并行度較小的情況下（＜5），GPU對于譯碼程序性能收益較小，這是由于在程序調用核函數(shù)時GPU 設備和上下文初始化的開銷較大，為10 ms 左右，然而這部分性能開銷一般是固定的，不會隨著數(shù)據(jù)量的增加而變化。因此，在小并行度時，該部分時延占據(jù)了大部分的性能開銷，從而導致性能收益不大甚至負收益。但是隨著數(shù)據(jù)量的上升，該部分耗時占比逐漸下降到可以忽略的程度，而程序運行時間占比逐漸上升并占據(jù)主要開銷，使得GPU 加速的性能優(yōu)勢得以顯現(xiàn)并最終保持穩(wěn)定。

由圖6 可看出，隨著碼字并行數(shù)量的增加，譯碼器的吞吐量隨之上升，在碼字數(shù)量為3 000 左右時變化逐漸穩(wěn)定，與圖5 相比提前1 000 碼字就趨于平穩(wěn)，原因是計算加速比時還考慮了GPU 設備和CUDA 流的初始化時間。最終譯碼器的延遲僅維持在2.1 μs 左右，吞吐量的維持在1 Gb/s 左右，上下浮動誤差不超過10 Mb/s。通過分析可知，吞吐量趨于穩(wěn)定的原因可以歸納為當前GPU 硬件資源的占用率已經(jīng)達到上限，即并行譯碼碼字數(shù)量和GPU 的處理效率達到峰值，使得吞吐量不再變化；若想進一步提高性能，可考慮將單個GPU 換為多個GPU 集群。

本文同時參考了其他文獻所設計的LDPC 譯碼器，并與它能到達的吞吐量性能進行對比，如表1 所示。理論上，對于相同設計框架的并行譯碼器來說，碼率越大，吞吐量會隨之增加，但譯碼性能也會隨之降低。可以注意到，與其他基于GPU 的LDPC 解碼器相比，本文提出的譯碼架構在同等條件下實現(xiàn)了更低的譯碼延遲。

表1 不同譯碼器的對比Tab.1 Comparison of different decoders

4 結語

本文通過提出一種能運行在GNU Radio 平臺上的基于GPU 的并行LNMS 譯碼方法對非規(guī)則LDPC 碼進行加速譯碼，并在GPU 設備底層原理基礎上提出了一些優(yōu)化策略以提高加速性能。本文算法由NVIDIA RTX 5000 GPU 加速，與串行順序的LNMS 算法流程不同，并行LNMS 算法流程中通過同時調用數(shù)千個CUDA 線程來完成各節(jié)點的信息交換與更新，并通過妥善處理GPU 的內存體系結構減少了線程對于全局內存的讀寫次數(shù)與讀寫時間。為了研究加速效應，本文在GNU Radio 平臺上分別構建了串行順序LNMS 算法譯碼器和并行順序LNMS 算法譯碼器。實驗結果表明，非規(guī)則LDPC 碼的并行LNMS 譯碼器能達到約200 倍的加速比，在多碼字并行的情況下吞吐量穩(wěn)定在1 Gb/s 以上。后續(xù)，可針對當前算法中CPU 與GPU 通信時間仍然較大的缺點進行優(yōu)化，進一步減少通信時間在總流程中的占比，以提高實際的吞吐量性能。