侯毅，劉榮科，彭皓，趙嶺，熊慶旭

適用于空間通信的LDPC碼GPU高速譯碼架構(gòu)

侯毅，劉榮科＊，彭皓，趙嶺，熊慶旭

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

鑒于目前空間通信對高速、可重配置信道譯碼器的需求，利用圖形處理器（GPU）的并行化運(yùn)算特點(diǎn)，提出了一種低密度奇偶校驗(yàn)（LDPC）碼軟件高速譯碼架構(gòu)。通過優(yōu)化Turbo消息傳遞譯碼（TDMP）算法節(jié)點(diǎn)更新運(yùn)算線程塊內(nèi)和塊間并行度、減少非規(guī)則行重造成的線程分支、降低線程對節(jié)點(diǎn)更新信息存儲資源的訪問延時以及合理量化譯碼器存儲信息來提升譯碼內(nèi)核函數(shù)的執(zhí)行效率。并在此基礎(chǔ)上引入異步統(tǒng)一計(jì)算設(shè)備構(gòu)架（CUDA）流處理機(jī)制，設(shè)計(jì)優(yōu)化的譯碼器輸入輸出數(shù)據(jù)傳輸和內(nèi)核函數(shù)之間的執(zhí)行調(diào)度方式以及CUDA流上的譯碼線程資源配置方式，最大化譯碼吞吐率的同時降低譯碼延時。在Nvidia最新的Tesla K20和GTX980平臺上對國際空間數(shù)據(jù)系統(tǒng)咨詢委員會（CCSDS）遙測標(biāo)準(zhǔn)LDPC碼進(jìn)行的TDMP譯碼實(shí)驗(yàn)結(jié)果表明，本架構(gòu)進(jìn)行10次迭代譯碼的吞吐率最高可達(dá)約500Mbps，平均譯碼延時約為2ms左右。與現(xiàn)有結(jié)果相比，本架構(gòu)在保持軟件架構(gòu)配置靈活性的同時更加有效的兼顧了譯碼吞吐率和延時性能。

低密度奇偶校驗(yàn)碼；圖形處理器；軟件譯碼架構(gòu)；Turbo消息傳遞譯碼算法；高吞吐率；低延時

低密度奇偶校驗(yàn)（Low－Density Parity－Check，LDPC）碼［1］由于近香農(nóng)限的優(yōu)異糾錯性能而被包括國際空間數(shù)據(jù)系統(tǒng)咨詢委員會（CCSDS）、DVB－S2在內(nèi)的多種空間通信標(biāo)準(zhǔn)所采用，其譯碼器日益成為該領(lǐng)域?qū)W術(shù)界和工業(yè)界研究的熱點(diǎn)。當(dāng)前，隨著空間通信的多任務(wù)、寬帶化趨勢，譯碼器作為通信接收系統(tǒng)的關(guān)鍵組成部分為了滿足高速、靈活可重配置的性能需求，在逐步向軟件化發(fā)展。美國宇航局（NASA）最新的空間通信無線電系統(tǒng)（STRS）架構(gòu)標(biāo)準(zhǔn)［2］以及噴氣推進(jìn)實(shí)驗(yàn)室（JPL）近期的報告［3－4］都將適應(yīng)多種編碼模式的高速軟件譯碼器作為星載或地面接收系統(tǒng)的重要環(huán)節(jié)之一。

圖 形 處 理 器 （Graphics Processing Units，GPU）是近年得到快速發(fā)展的具備大規(guī)模并行處理能力的單指令流多線程流（SIMT）架構(gòu)通用運(yùn)算處理器。GPU用于軟件譯碼器實(shí)現(xiàn)相比采用現(xiàn)場可編程門陣列（FPGA）的方式［5］在配置上更為靈活，更適應(yīng)未來空間通信的多任務(wù)模式；比基于數(shù)字信號處理器（DSP）的實(shí)現(xiàn)方式［6］擁有更多并行運(yùn)算資源，更適應(yīng)寬帶化通信應(yīng)用。與現(xiàn)有采用單指令流多數(shù)據(jù)流（SIMD）架構(gòu)的通用處理器 CPU、ARM 的實(shí)現(xiàn)方式［7－8］相比，GPU 的并行線程寄存器資源更多，對緩存命中率的依賴較低，因此更適合作為空間通信標(biāo)準(zhǔn)里中長LDPC碼的可重配高速實(shí)現(xiàn)平臺。

國際上現(xiàn)有的GPU軟件譯碼架構(gòu)研究成果根據(jù)其優(yōu)化實(shí)現(xiàn)方式大致可分為兩類：存儲訪問優(yōu)化［9－12］和運(yùn)算并行優(yōu)化［13－15］。在存儲優(yōu)化方面目前主要利用GPU片上的高速共享內(nèi)存，以降低譯碼算法行列更新中的節(jié)點(diǎn)信息訪存延時為目的。受限于GPU片上有限的存儲資源，該設(shè)計(jì)僅能滿足LDPC短碼的節(jié)點(diǎn)更新信息存儲需求，對于應(yīng)用于空間通信的中長LDPC碼，則難以通過共享內(nèi)存提升節(jié)點(diǎn)更新的存儲訪問速度。在運(yùn)算并行優(yōu)化方面現(xiàn)有方法主要是提升LDPC譯碼器的幀間并行度，通過加大可執(zhí)行的譯碼線程數(shù)，將大量接收碼字加入GPU運(yùn)算核心調(diào)度處理的隊(duì)列，使得GPU飽和運(yùn)行以獲得高的譯碼吞吐率。其代價是譯碼延時大幅提升，尤其是使用空間通信標(biāo)準(zhǔn)中非規(guī)則中長碼時延時問題更為嚴(yán)重，并加重了譯碼器輸入緩存處理的負(fù)擔(dān)。此外，上述GPU譯碼架構(gòu)主要針對節(jié)點(diǎn)同時更新的兩階段消息傳遞（TPMP）算法［16］，而對于譯碼收斂速度更快更適合中長LDPC碼采用的節(jié)點(diǎn)順序更新消息傳遞算法［17－18］則缺乏有效的優(yōu)化實(shí)現(xiàn)設(shè)計(jì)方法。

本文提出的LDPC碼GPU軟件譯碼架構(gòu)面向空間通信應(yīng)用，以高吞吐率和低延時為設(shè)計(jì)目標(biāo)。鑒于目前空間通信標(biāo)準(zhǔn)采用的準(zhǔn)循環(huán)LDPC（QC－LDPC）碼大多具有校驗(yàn)矩陣子矩陣行列重為1的特點(diǎn)，利于譯碼器以分層部分并行的方式進(jìn)行處理，故本文采用了按校驗(yàn)節(jié)點(diǎn)順序分層更新的 Turbo消息傳遞譯碼（TDMP）算法［17］，相比傳統(tǒng)TPMP算法，TDMP算法由于在每次迭代內(nèi)部利用了節(jié)點(diǎn)的即時更新信息從而擁有更快的譯碼收斂速度。本文根據(jù)TDMP算法迭代過程的分層特點(diǎn)，致力于提升譯碼線程對層內(nèi)和層間信息的更新處理效率，利用統(tǒng)一計(jì)算設(shè)備構(gòu)架（CUDA）流異步執(zhí)行機(jī)制隱藏譯碼器數(shù)據(jù)傳輸延時，通過單幀內(nèi)部多節(jié)點(diǎn)并行更新與多幀之間譯碼并行處理相結(jié)合的方式，在最大化GPU運(yùn)算及存儲資源利用率的同時避免了在現(xiàn)有實(shí)現(xiàn)方法中因單純依靠大規(guī)模幀間并行處理而導(dǎo)致的譯碼延時過高的問題。與現(xiàn)有實(shí)現(xiàn)結(jié)果的對比表明，本譯碼架構(gòu)能夠有效兼顧高吞吐率和低延時性能。

1 LDPC碼TDMP譯碼算法

TDMP譯碼算法將LDPC碼校驗(yàn)矩陣H分解為L層，即HT＝ ［…］，每層列重至多為1。TDMP算法在層與層之間傳遞節(jié)點(diǎn)的更新信息，設(shè)定表示在第k次迭代第t層中從校驗(yàn)節(jié)點(diǎn)c傳遞到變量節(jié)點(diǎn)v的更新信息，表示在第k次迭代第t層中從變量節(jié)點(diǎn)v傳遞到校驗(yàn)節(jié)點(diǎn)c的更新信息，表示第k次迭代中從第t層傳遞到下一層的變量節(jié)點(diǎn)v的層傳遞信息，N （c）＼v表示與校驗(yàn)節(jié)點(diǎn)c相連的變量節(jié)點(diǎn)中除去變量節(jié)點(diǎn)v的集合。具體譯碼過程如下：

步驟3 校驗(yàn)節(jié)點(diǎn)c到變量節(jié)點(diǎn)v的更新（為了簡化運(yùn)算，本文采用修正最小和（Min－Sum）算法，修正系數(shù)為α）：

步驟5 判決：對于所有的變量節(jié)點(diǎn)v，按如下方法進(jìn)行判決得到硬判決信息＾v：

2 基于GPU的LDPC碼譯碼架構(gòu)優(yōu)化設(shè)計(jì)

LDPC碼TDMP譯碼器在GPU平臺的實(shí)現(xiàn)架構(gòu)如圖1所示。該譯碼架構(gòu)發(fā)揮軟件實(shí)現(xiàn)靈活可重配置的優(yōu)勢，在譯碼器啟動時將碼字校驗(yàn)矩陣數(shù)據(jù)從系統(tǒng)內(nèi)存?zhèn)鬟f到GPU中具備緩存區(qū)的只讀常量內(nèi)存（Constant Memory）里，以應(yīng)對不同任務(wù)的譯碼配置需求。該架構(gòu)的性能主要取決于兩個方面：GPU硬件資源對譯碼算法的執(zhí)行效率以及主機(jī)（Host）與GPU之間通過PCI－E總線進(jìn)行數(shù)據(jù)交互的傳輸效率。GPU硬件主要由流處理器簇（Stream Multiprocessor，SM）運(yùn)算陣列以及多種存儲單元組成。譯碼過程依照TDMP算法通過Nvidia CUDA內(nèi)核函數(shù)（Kernel）控制線程塊（Block）調(diào)用并訪問SM上的運(yùn)算資源和存儲資源來實(shí)現(xiàn)。譯碼器輸入輸出數(shù)據(jù)的傳輸過程以及譯碼內(nèi)核函數(shù)的執(zhí)行過程均在CUDA流上完成，不同的流執(zhí)行模式以及流上的資源配置方式會帶來不同的實(shí)現(xiàn)性能。

本文將從內(nèi)核函數(shù)優(yōu)化以及異步CUDA流優(yōu)化兩個方面提升LDPC譯碼架構(gòu)的吞吐率和延時性能。

2．1 基于GPU的LDPC碼譯碼架構(gòu)內(nèi)核函數(shù)優(yōu)化

內(nèi)核函數(shù)是LDPC碼軟件譯碼架構(gòu)的核心組成部分，它以線程束（Warp）的方式調(diào)用GPU內(nèi)部的運(yùn)算和存儲資源來完成迭代譯碼的各個步驟。內(nèi)核函數(shù)的執(zhí)行效率直接影響譯碼的吞吐率和延時性能，本文所設(shè)計(jì)的譯碼架構(gòu)將從內(nèi)核函數(shù)中線程塊資源配置優(yōu)化、線程分支優(yōu)化、線程對存儲資源的訪問優(yōu)化以及線程運(yùn)算量化方式優(yōu)化4個方面提升內(nèi)核函數(shù)執(zhí)行效率。

2．1．1 線程塊資源配置優(yōu)化

在本文提出的架構(gòu)中，TDMP譯碼過程的幀內(nèi)和幀間并行執(zhí)行程度分別對應(yīng)于譯碼內(nèi)核函數(shù)線程塊內(nèi)部和塊間的并行度。盡管GPU硬件提供了大量可并行處理的運(yùn)算資源，但片上存儲資源對于中長LDPC碼的譯碼節(jié)點(diǎn)更新運(yùn)算過程中間信息存儲需求而言依然十分有限，需要設(shè)計(jì)優(yōu)化的線程塊內(nèi)和塊間并行度。

根據(jù)TDMP譯碼的節(jié)點(diǎn)更新方式，若選用的LDPC碼行重為w，則每個線程執(zhí)行所需的寄存器數(shù)目如下：存儲變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的更新信息Lk，tvc以及變量節(jié)點(diǎn)所對應(yīng)的列地址共需要2×w個寄存器資源，每個Lk，tvc符號值在讀取時所需的緩存、各節(jié)點(diǎn)符號值的按位拼接存儲、符號值乘積存儲、最小值存儲、次小值存儲各需要1個寄存器資源，此外的存儲均通過全局內(nèi)存完成，因此每個線程所需寄存器總數(shù)Q＝2×w＋5。如果線程塊內(nèi)部并行度過高，受限于SM中有限的寄存器資源，每個譯碼線程將無法分配到足夠的寄存器而導(dǎo)致執(zhí)行效率低下。過低的線程塊內(nèi)部并行度則無法通過維持一定數(shù)目的激活線程來隱藏譯碼節(jié)點(diǎn)信息訪問以及節(jié)點(diǎn)更新算術(shù)運(yùn)算帶來的延遲，導(dǎo)致譯碼吞吐率下降。此外，線程塊間的并行度會影響SM工作負(fù)荷情況，需要與硬件資源參數(shù)相匹配，否則會引發(fā)運(yùn)算負(fù)載失衡造成部分SM運(yùn)算資源閑置。設(shè)定在內(nèi)核函數(shù)調(diào)用執(zhí)行過程中，線程塊間并行度為Nbl，分配到SM的線程塊數(shù)最小為B，線程塊內(nèi)并行度為Nth，GPU硬件擁有的SM個數(shù)為Nsm，每個SM擁有的寄存器數(shù)為Nreg，每個SM隱藏運(yùn)算延時所需的最小線程數(shù)為NTH，TDMP算法分層中每一層校驗(yàn)節(jié)點(diǎn)數(shù)目為Nrpl，則譯碼線程塊并行度的選取需要滿足以下4個條件以獲得較高的內(nèi)核函數(shù)線程執(zhí)行效率：① Nth×B×Q≤Nreg；② Nth×B≥NTH；

2．1．2 線程分支優(yōu)化

在線程級的并行能夠完全隱藏存儲訪問和算術(shù)運(yùn)算延時的條件下，譯碼內(nèi)核函數(shù)的執(zhí)行效率將會達(dá)到一個瓶頸值，若要繼續(xù)降低內(nèi)核函數(shù)的執(zhí)行時間，需要通過引入線程中指令級的并行來實(shí)現(xiàn)?？紤]到指令級并行度受限于GPU片內(nèi)的寄存器資源、指令相關(guān)性以及譯碼過程的分支程度，其中寄存器的消耗和指令相關(guān)性受限于TDMP算法，難以做到顯著的降低，因此本文所設(shè)計(jì)的譯碼架構(gòu)通過線程分支優(yōu)化來提升指令級并行度，進(jìn)而提高譯碼吞吐率。

鑒于采用的Nvidia GPU是基于SIMT模型，線程束中所有線程在同一時間只能獲取一條指令。當(dāng)一個線程束執(zhí)行中出現(xiàn)不同分支時，不滿足分支條件的線程將會被阻塞并閑置。由于GPU缺乏類似于CPU具備的復(fù)雜分支預(yù)測功能，因此較多的程序分支將大幅降低譯碼內(nèi)核函數(shù)的執(zhí)行效率。對于空間通信標(biāo)準(zhǔn)中大多采用的非規(guī)則LDPC碼而言，其校驗(yàn)矩陣行列重的差異性將導(dǎo)致不同行重（列重）的行（列）信息更新時，調(diào)用內(nèi)核函數(shù)的資源消耗及計(jì)算量不同?，F(xiàn)有的LDPC碼譯碼架構(gòu)在執(zhí)行非規(guī)則碼譯碼時，是用單一的內(nèi)核函數(shù)根據(jù)存儲器中讀出的行（列）重值分配相應(yīng)的寄存器資源，并以循環(huán)的形式進(jìn)行譯碼所需行列更新計(jì)算。然而，循環(huán)處理的指令順序執(zhí)行特性需要較大的開銷，為了達(dá)到減少分支以便進(jìn)行循環(huán)展開的目的，本文所設(shè)計(jì)譯碼架構(gòu)為不同行重的分層更新采用不同的內(nèi)核函數(shù)。舉例來說，假設(shè)TDMP譯碼各層的行重有3種：w1，w2，w3，則在行信息更新過程中，分別調(diào)用不同的內(nèi)核函數(shù) Kernel＿w1，Kernel＿w2，Kernel＿w3，如圖2所示。雖然該方法會增加少許內(nèi)核函數(shù)啟動的開銷，但能有效避免分支所造成的線程束運(yùn)算資源浪費(fèi)，從而降低內(nèi)核函數(shù)的執(zhí)行所需時間。

2．1．3 線程存儲資源訪問優(yōu)化

在LDPC碼的TDMP譯碼內(nèi)核函數(shù)處理過程中需要對大量節(jié)點(diǎn)更新信息以及校驗(yàn)矩陣地址數(shù)據(jù)進(jìn)行訪問，由于GPU存儲器的訪問速度遠(yuǎn)低于其運(yùn)算速度，因此進(jìn)行存儲資源訪問優(yōu)化設(shè)計(jì)對于提升內(nèi)核函數(shù)的執(zhí)行效率至關(guān)重要。GPU中存儲資源的訪問是以線程束為單位進(jìn)行的，在當(dāng)前Nvidia GPU的架構(gòu)版本中，線程束由32個線程組成，能夠同時訪問最多128字節(jié)的存儲地址空間。當(dāng)線程束中所有線程的訪問地址連續(xù)且與存儲地址以32字節(jié)為單位對齊時，僅需要進(jìn)行一次存儲訪問事務(wù)（Transaction）即可將線程束中所需數(shù)據(jù)全部讀取或?qū)懭氪鎯ζ?，否則將需要進(jìn)行多次存儲訪問事務(wù)?？紤]到適用于空間通信的中長LDPC碼的節(jié)點(diǎn)更新信息數(shù)據(jù)量大，只能存儲到片外的全局內(nèi)存（Global Memory）中，而GPU全局內(nèi)存的訪問延時長達(dá)600～800個時鐘周期，因此不滿足連續(xù)和對齊要求的存儲訪問操作將造成內(nèi)核函數(shù)效率的嚴(yán)重下降。

為了保證TDMP譯碼過程中譯碼線程對存儲空間中校驗(yàn)矩陣非零位置地址值訪問的連續(xù)性，LDPC碼的校驗(yàn)矩陣需要按行順序進(jìn)行存儲。鑒于目前LDPC碼校驗(yàn)矩陣均為準(zhǔn)循環(huán)結(jié)構(gòu)，為了節(jié)省常量內(nèi)存空間，本譯碼架構(gòu)將校驗(yàn)矩陣的非零子矩陣位置按行塊壓縮存儲為一維數(shù)組的形式，數(shù)組中每個元素包含2個數(shù)值，即非零子矩陣所在的列塊絕對位置編號C和非零子矩陣的首行偏移量P。校驗(yàn)矩陣存儲圖樣示例如圖3所示，假設(shè)校驗(yàn)矩陣循環(huán)子矩陣規(guī)模為Z×Z，校驗(yàn)矩陣行塊、列塊數(shù)目分別為4和8，其中8個非零子矩陣的首行偏移量分別為P1，P2，…，P8，非零子矩陣位置如圖，則在常量內(nèi)存中壓縮存儲后的校驗(yàn)矩陣為包含4個元素的一維數(shù)組Row［0］到 Row［3］。本譯碼架構(gòu)將TDMP算法中校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)的更新信息Rcv存儲于GPU片外的全局內(nèi)存中。Rcv的存儲圖樣采用二維數(shù)組如圖4所示。其中M為LDPC碼校驗(yàn)矩陣的行數(shù)，即譯碼更新處理的校驗(yàn)節(jié)點(diǎn)數(shù)，Wrow＿max為校驗(yàn)矩陣的最大行重。當(dāng)?shù)趌層譯碼時，對應(yīng)層內(nèi)第r個非零子矩陣節(jié)點(diǎn)更新的譯碼線程塊中編號為ntid的線程所訪問的Rcv取值為該二維存儲空間里第l×Z＋ntid行第r列的數(shù)值。在該存儲方式下，線程塊編號的連續(xù)性保證了譯碼線程對節(jié)點(diǎn)更新信息訪問地址的連續(xù)性，避免了額外的存儲訪問開銷。

本譯碼架構(gòu)中變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的更新信息存儲于片外全局內(nèi)存的一維數(shù)組中。利用從壓縮校驗(yàn)矩陣中讀取的更新節(jié)點(diǎn)所在列塊的絕對位置C以及節(jié)點(diǎn)所處的非零子矩陣首行偏移量P，可獲得節(jié)點(diǎn)更新線程ntid所對應(yīng)的一維數(shù)組存儲空間中的位置索引值C×Z＋［（P＋ntid）mod（Z）］。該存儲訪問過程僅在線程束跨越校驗(yàn)矩陣非零子矩陣邊界位置時會發(fā)生因地址跳變而造成的一次額外訪問事務(wù)，其余情況下均能保證訪問的連續(xù)性。

2．1．4 線程運(yùn)算量化方式優(yōu)化

GPU的處理核心對片外全局內(nèi)存的訪問能力相比其運(yùn)算處理能力而言十分有限，如何更加有效利用有限的存儲訪問帶寬是提升譯碼內(nèi)核函數(shù)執(zhí)行效率的關(guān)鍵之一。當(dāng)前GPU架構(gòu)的處理單元只支持最低32位單精度浮點(diǎn)型或整型運(yùn)算，然而對于LDPC碼TDMP最小和譯碼算法而言，其節(jié)點(diǎn)更新信息通常只需要較低的量化精度即可獲得與32位精度量化相當(dāng)?shù)恼`碼率性能，譯碼架構(gòu)可以通過減少存儲節(jié)點(diǎn)信息的精度達(dá)到提高內(nèi)核函數(shù)存儲訪問效率的目的，如采用8位整型量化或16位半精度浮點(diǎn)型量化。然而需要注意的是，8位量化方式由于值域偏小，LDPC譯碼過程中節(jié)點(diǎn)更新運(yùn)算的32位整型結(jié)果需要進(jìn)行限幅處理后進(jìn)行存儲，增加了譯碼線程的分支判斷。此外，由于目前GPU對整型運(yùn)算的處理能力較弱（如主流Kepler架構(gòu)的整型運(yùn)算能力約為浮點(diǎn)型的1／6［19］），8位整型量化在提升內(nèi)核函數(shù)存儲訪問能力的同時會造成其運(yùn)算能力的下降。因此，8位整型量化存儲方式僅適于對內(nèi)核函數(shù)運(yùn)算耗時不敏感，存儲訪問帶寬嚴(yán)重受限的譯碼應(yīng)用。對于需要同時兼顧內(nèi)核函數(shù)執(zhí)行效率和存儲訪問帶寬利用效率的譯碼應(yīng)用，本文選擇采用16位半精度浮點(diǎn)型進(jìn)行節(jié)點(diǎn)更新信息的量化存儲，譯碼線程讀取節(jié)點(diǎn)信息后轉(zhuǎn)換為單精度浮點(diǎn)型后進(jìn)行迭代更新運(yùn)算。半精度浮點(diǎn)型對于TDMP最小和算法的節(jié)點(diǎn)更新結(jié)果具有足夠的值域空間，不需要在運(yùn)算和存儲轉(zhuǎn)換時進(jìn)行限幅處理，保證了譯碼內(nèi)核函數(shù)運(yùn)算和存儲訪問的高效性。

2．2 基于GPU的LDPC碼譯碼架構(gòu)CUDA流執(zhí)行效率優(yōu)化

LDPC碼軟件譯碼架構(gòu)在GPU平臺上運(yùn)行所消耗的時間中，除去譯碼內(nèi)核函數(shù)執(zhí)行時間以外，其余大部分是用于在主機(jī)系統(tǒng)內(nèi)存和GPU片外全局內(nèi)存之間經(jīng)由PCI－E總線傳輸譯碼輸入軟信息和硬判決輸出信息。若要提高譯碼吞吐率性能，需要引入異步CUDA流機(jī)制，在提升內(nèi)核函數(shù)自身執(zhí)行效率的同時優(yōu)化數(shù)據(jù)傳輸和譯碼內(nèi)核函數(shù)之間的調(diào)度機(jī)制，最大化GPU硬件運(yùn)算資源的利用率。此外，在多流處理方式中需要合理配置線程塊資源數(shù)以便能同時獲得更優(yōu)的譯碼吞吐率和延時性能。因此，本文從異步調(diào)度方式和流上的線程資源配置準(zhǔn)則兩個方面優(yōu)化譯碼架構(gòu)的CUDA流執(zhí)行效率和降低譯碼延時。

2．2．1 異步CUDA流調(diào)度優(yōu)化

相比于GPU運(yùn)算處理能力在近年來的不斷提升，主機(jī)與GPU之間通過PCI－E總線的數(shù)據(jù)傳輸能力卻沒有顯著增加，造成數(shù)據(jù)傳輸日益成為GPU軟件譯碼架構(gòu)吞吐率性能提升的瓶頸。此外，內(nèi)核函數(shù)在執(zhí)行過程中會出現(xiàn)譯碼線程間由于數(shù)據(jù)依賴造成的阻塞，影響執(zhí)行效率。本文所設(shè)計(jì)譯碼架構(gòu)采用Nvidia在Kepler架構(gòu)（GK110）之后引入的 Hyper－Q技術(shù)，通過異步CUDA流實(shí)現(xiàn)多幀譯碼內(nèi)核函數(shù)之間以及內(nèi)核函數(shù)與數(shù)據(jù)傳輸之間的交疊執(zhí)行，如圖5（a）所示，其中H2D和D2H部分分別表示數(shù)據(jù)從主機(jī)到GPU以及從GPU到主機(jī)的傳輸過程，Decoding Kernel部分表示譯碼過程的執(zhí)行時間，可見異步執(zhí)行模式相比于圖5（b）所示傳統(tǒng)譯碼器的同步執(zhí)行模式有效降低了GPU運(yùn)算資源在PCIE總線數(shù)據(jù)傳輸時的空閑等待時間，同時通過多內(nèi)核函數(shù)交疊對SM運(yùn)算資源的復(fù)用來緩解譯碼過程中由于校驗(yàn)節(jié)點(diǎn)以最小和方式更新的運(yùn)算相關(guān)性以及線程對全局內(nèi)存中更新信息訪問的長延時所造成的硬件資源利用率較低的問題。此外，本架構(gòu)對譯碼輸出的硬判決信息以32位整型方式進(jìn)行了按位拼接存儲，大幅減少了D2H過程中的傳輸數(shù)據(jù)量，進(jìn)一步降低了譯碼所需的延時。

2．2．2 異步CUDA流線程資源配置優(yōu)化

GPU的SIMT架構(gòu)特點(diǎn)決定了其需要大量的線程以達(dá)到隱藏算術(shù)延時提高吞吐率的目的，在現(xiàn)有文獻(xiàn)所提出的譯碼架構(gòu)設(shè)計(jì)中，多數(shù)即通過同時進(jìn)行數(shù)百甚至上千幀的迭代譯碼過程來最大化吞吐率性能，例如在文獻(xiàn)［14－15］中達(dá)到最大譯碼吞吐率時的最低并行譯碼幀數(shù)設(shè)置分別為4 096和4 480。大量的并行譯碼幀數(shù)不可避免的帶來譯碼延時過大的問題，尤其是對于空間通信應(yīng)用中的中長LDPC碼更是如此。Nvidia GPU的核心將全部SM劃分為多個圖形處理集群（Graphics Processor Cluster，GPC），每個 GPC所包含的SM數(shù)目有可能不同，GPU在不同SM中分配譯碼線程塊時遵循大致上的輪轉(zhuǎn)次序，但優(yōu)先分配SM數(shù)目較多的GPC。因此當(dāng)每個SM中分配的線程塊數(shù)滿足激活線程塊數(shù)的整數(shù)倍關(guān)系時，SM之間才能夠達(dá)到運(yùn)算負(fù)載的平衡，使得譯碼吞吐達(dá)到峰值?；诖?，本文所提出的譯碼架構(gòu)盡可能減少單線程塊中運(yùn)行譯碼的幀數(shù)，并且設(shè)置所有異步CUDA流上運(yùn)行的總線程塊數(shù)為SM上激活線程塊數(shù)與SM總數(shù)乘積的較小整數(shù)倍，以便在獲得譯碼吞吐峰值的同時減小譯碼幀數(shù)，縮短譯碼延時。

3 仿真實(shí)驗(yàn)及分析

實(shí)驗(yàn)測試所用硬件平臺如表1所示。本文所提出的基于GPU的LDPC碼TDMP譯碼架構(gòu)在 Nvidia CUDA 6．5工具包下進(jìn)行編譯，編譯環(huán)境是 Visual Studio 2013，Windows 7 64位操作系統(tǒng)。硬件平臺選取的主板為Intel的Z97芯片組，Tesla K20GPU使用PCI－E 2．0X16總線接口，GTX980GPU使用PCI－E 3．0X16總線接口。

實(shí)驗(yàn)所選取的LDPC碼為CCSDS遙測同步和信道編碼標(biāo)準(zhǔn)［20］中所提供的4 096信息位1／2碼率（碼1）和2／3碼率（碼2）的兩種非規(guī)則AR4JA LDPC碼。其中碼1的平均行重為5，校驗(yàn)矩陣子矩陣規(guī)模為512×512，碼2的平均行重為7．67，子矩陣規(guī)模為256×256。譯碼采用TDMP最小和算法，迭代10次。最小和修正系數(shù)α在32位單精度和16位半精度浮點(diǎn)型量化的兩種碼譯碼實(shí)現(xiàn)中均設(shè)置為0．8，在8位整型量化（其中5比特代表整數(shù)位、2比特代表小數(shù)位、1比特代表符號位）的碼1中設(shè)置為0．77，碼2中設(shè)置為0．7。不同量化方式的誤碼性能在GPU平臺上測試結(jié)果如圖6所示，誤碼率（BER）和誤幀率（FER）是譯碼出現(xiàn)50誤幀數(shù)時的統(tǒng)計(jì)結(jié)果?？梢奣DMP最小和算法誤碼性能對量化不敏感，32位、16位浮點(diǎn)型量化以及8位整型量化的譯碼性能基本一致。

表1 仿真實(shí)驗(yàn)硬件環(huán)境Table 1 Hardware simulation environments

表2為同步模式下兩種碼采用本文所提出的內(nèi)核函數(shù)優(yōu)化方法使用不同量化方式獲得的譯碼吞吐率以及延時性能。譯碼內(nèi)核函數(shù)中線程塊內(nèi)并行度根據(jù)2．1．1節(jié)的選取準(zhǔn)則設(shè)置碼1為512、碼2為256。且內(nèi)核函數(shù)均根據(jù)非規(guī)則行重的特點(diǎn)減少了線程分支并采用存儲聯(lián)合訪問圖樣?？梢娫趦?yōu)化后的內(nèi)核函數(shù)中使用16位半精度浮點(diǎn)型和8位整型量化得益于利用相同的存儲訪問帶寬獲取更多的譯碼更新節(jié)點(diǎn)信息，在兩種GPU平臺上的譯碼吞吐率均比32位單精度浮點(diǎn)型量化方式有較大提升。由于Tesla K20平臺與GTX980平臺的PCI－E總線傳輸平均帶寬分別為二代16通道的5GBps和三代16通道的10GBps左右，因此在較低數(shù)據(jù)傳輸速率的K20平臺上，量化對于有限帶寬下碼字傳輸能力的改善相比GTX980平臺更為顯著。需要注意的是，在兩種GPU平臺上碼2的8位整型量化譯碼吞吐率均低于16位浮點(diǎn)型量化，其原因是8位整型量化方式在譯碼更新過程中需要頻繁進(jìn)行限幅運(yùn)算，校驗(yàn)矩陣行重越大，限幅造成的運(yùn)算開銷越大，使得在對碼2進(jìn)行譯碼時內(nèi)核函數(shù)運(yùn)算時間過長，吞吐率相比16位量化方式下降的同時譯碼延時也大幅增加。

表2 內(nèi)核函數(shù)優(yōu)化后同步模式譯碼吞吐率及延時性能Table 2 Throughput and latency performance of proposed architecture with optimized Kernel functions under synchronous mode

表3為異步模式下兩種碼采用本文所設(shè)計(jì)的CUDA流優(yōu)化方法后使用不同量化方式獲得的譯碼吞吐率以及延時性能。異步CUDA流均設(shè)置為3個。可見在異步模式下得益于有效隱藏了GPU與主機(jī)之間的數(shù)據(jù)傳輸延時，譯碼吞吐率相比表2中的同步模式有較大幅度的提升。譯碼延時因?yàn)楫惒紺UDA流交疊所造成的單個內(nèi)核函數(shù)執(zhí)行時間上升而略有增加。采用本文所提出的線程資源優(yōu)化配置方法后，在達(dá)到譯碼吞吐率峰值的同時減少了幀間并行度，使得譯碼延時仍能夠基本保持在2～3ms左右。與同步模式的實(shí)驗(yàn)結(jié)果類似，碼2的8位整型量化實(shí)現(xiàn)由于其校驗(yàn)矩陣行重較大帶來大量限幅運(yùn)算開銷導(dǎo)致兩種GPU平臺上吞吐率均嚴(yán)重降低并且譯碼延時大幅增大。Tesla K20平臺在異步模式譯碼實(shí)現(xiàn)上的瓶頸主要為有限的PCI－E總線傳輸帶寬，因此行重較少的碼1在8位整型實(shí)現(xiàn)時由于傳輸效率的大幅提升且內(nèi)核函數(shù)限幅運(yùn)算開銷較小，從而吞吐率獲得較大的提高。而GTX980平臺在異步模式譯碼上的瓶頸主要為內(nèi)核函數(shù)運(yùn)算開銷，所以不需要限幅運(yùn)算開銷并且兼顧總線傳輸效率的16位浮點(diǎn)型量化實(shí)現(xiàn)方式能取得較理想的吞吐率和延時性能。

表4為本文所提出的GPU譯碼架構(gòu)（選取Tesla K20平臺實(shí)現(xiàn)結(jié)果）與現(xiàn)有文獻(xiàn)中同類方法的性能比較。在比較過程中采用了歸一化吞吐率（Normalized Throughput）的概念，即單位運(yùn)算核心每MHz頻率的譯碼吞吐率，以消除平臺差異對比較結(jié)果的影響。

表3 CUDA流優(yōu)化后異步模式譯碼吞吐率及延時性能（CUDA流數(shù)為3）Table 3 Throughput and latency performance of proposed architecture with optimized CUDA stream execution under asynchronous mode（3CUDA streams）

表4 與現(xiàn)有譯碼架構(gòu)的性能比較Table 4 Comparison with performance of existing decoder architectures

可以看到，相比文獻(xiàn)［11］和文獻(xiàn)［14］的方法，本文所提譯碼架構(gòu)的歸一化吞吐率分別提升了106%和47．6%。鑒于文獻(xiàn)［11］的GTX Titan平臺傳輸總線為PCI－E 3．0，而本文的Tesla K20為傳輸帶寬減半的 PCI－E 2．0，因此本文方法的譯碼延時與文獻(xiàn)［11］相當(dāng)。文獻(xiàn)［14］中沒有給出譯碼延時的數(shù)據(jù)，但是根據(jù)其并行處理4 096碼字的方式可以判斷延時相較本文方法會大幅增加。在表4中本文的譯碼歸一化吞吐率約為文獻(xiàn)［15］所提方法的67．5%，考慮到文獻(xiàn)［15］采用的譯碼算法是TPMP，在得到相同誤碼性能時所需的譯碼迭代次數(shù)接近本文所采用的TDMP算法所需次數(shù)的兩倍，因此若從相同誤碼性能角度衡量，兩種方法所能達(dá)到的吞吐率相當(dāng)。但由于文獻(xiàn)［15］的譯碼幀間并行度過高，本文方法的譯碼延時僅為文獻(xiàn)［15］的1．3%。綜上所述可知，本文所提出的譯碼架構(gòu)在獲得較高譯碼吞吐率的同時兼顧了低譯碼延時的性能。

4 結(jié) 論

1）提出了一種基于GPU的LDPC碼軟件譯碼架構(gòu)，采用TDMP最小和譯碼算法，從內(nèi)核函數(shù)優(yōu)化以及異步CUDA流執(zhí)行優(yōu)化兩個方面提升了譯碼架構(gòu)的吞吐率和延時性能。

2）實(shí)驗(yàn)結(jié)果表明，本文所提出的GPU軟件譯碼架構(gòu)對CCSDS標(biāo)準(zhǔn)所建議的中長LDPC碼在10次譯碼迭代時吞吐率最高可達(dá)500Mbps左右，譯碼延時約為2ms左右。相比現(xiàn)有方法，本架構(gòu)能更有效兼顧高譯碼吞吐率和低延時性能。

［1］ MACKAY D J C，NEAL R M．Near Shannon limit performance of low density parity check codes［J］．Electronics Letters，1996，32（18）：1645－1646．

［2］ NASA．Space telecommunications radio system （STRS）architecture standard：NASA－STD－4009［S］．Washington，D．C．：NASA，2014．

［3］ LAY N，ARGUETA A，TKACENKO A，et al．Reconfigurable wideband ground receiver field testing：IPN progress report 42－191［R］．Pasadena：Jet Propulsion Laboratory，2012．

［4］ CHEUNG K M，ABRAHAM D，ARROYO B，et al．Next－generation ground network architecture for communications and tracking of interplanetary smallsats：IPN progress report 42－202［R］．Pasadena：Jet Propulsion Laboratory，2015．

［5］ WANG Y Q，LIU D L，SUN L，et al．Real－time implementation for reduced－complexity LDPC decoder in satellite communication［J］．China Communications，2014，11（12）：94－104．

［6］ LECHNER G，SAYIR J，RUPP M．Efficient DSP implementation of an LDPC decoder［C］／IEEE International Conference on Acoustics，Speech，and Signal Processing（ICASSP）．Piscataway，NJ：IEEE Press，2004：iv－665－iv－668．

［7］ GAL B L，JEGO C．High－throughput multi－core LDPC decoders based on x86processor［J／OL］．IEEE Transactions on Parallel and Distributed Systems，（2015－05－20）［2016－01－11］．http：／doi．ieeecomputersociety．org／10．1109／TPDS．2015．2435787．

［8］ GAL B L，JEGO C．High－throughput LDPC decoder on low－power embedded processors［J］．IEEE Communications Letters，2015，19（11）：1861－1864．

［9］ FALCAO G，SOUSA L，SILVA V．Massively LDPC decoding on multicore architectures［J］．IEEE Transactions on Parallel and Distributed Systems，2011，22（2）：309－322．

［10］ JI H W，CHO J H，SUNG W Y．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．

［11］ WANG G H，WU M，YIN B，et al．High throughput low latency LDPC decoding on GPU for SDR systems［C］／Proceedings of 2013IEEE Global Conference on Signal and Information Processing （GlobalSIP）．Piscataway，NJ：IEEE Press，2013：1258－1261．

［12］ HONG J H，CHUNG K S．Parallel LDPC decoding on a GPU using OpenCL and global memory for accelerators［C］／Proceedings of 2015IEEE International Conference on Networking，Architecture and Storage（NAS）．Piscataway，NJ：IEEE Press，2015：353－354．

［13］ FALCAO G，ANDRADE J，SILVA V，et al．GPU－based DVB－S2LDPC decoder with high throughput and fast error floor detection［J］．Electronics Letters，2011，47（9）：542－543．

［14］ XIE W，JIAO X J，PEKKA J，et al．A high throughput LDPC decoder using a mid－range GPU［C］／Proceedings of 2014IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP）．Piscataway，NJ：IEEE Press，2014：7515－7519．

［15］ LIN Y，NIU W S．High throughput LDPC decoder on GPU［J］．IEEE Communications Letters，2014，18（2）：344－347．

［16］ GALLAGER R．Low－density parity－check codes［J］．IRE Transactions on Information Theory，1962，8（1）：21－28．

［17］ MANSOUR M，SHANBHAG N．Turbo decoder architectures for low－density parity－check codes［C］／Proceedings of 2002IEEE Global Telecommunications Conference（GLOBECOM）．Piscataway，NJ：IEEE Press，2002：1383－1388．

［18］ ZHANG J T，F(xiàn)OSSORIER M P C．Shuffled iterative decoding［J］．IEEE Transactions on Communications，2005，53（2）：209－213．

［19］ NVIDIA Corporation．CUDA C programming guide version 7．5［EB／OL］．（2015－09－01）［2016－01－11］．http：／docs．nvidia．com／cuda／cuda－c－programming－guide．

［20］ CCSDS．Synchronization and channel coding，Issue 2：131．0－B－2TM［S］．Washington，D．C．：CCSDS，2011．

High－throughput GPU－based LDPC decoder architecture for space communication

HOU Yi，LIU Rongke＊，PENG Hao，ZHAO Ling，XIONG Qingxu
School of Electronics and Information Engineering，Beihang University，Beijing 100083，China

In view of the current requirements for high－speed reconfigurable channel decoder for space communications，a high－throughput low－density parity－check（LDPC）software decoding architecture is proposed by exploiting the graphics processing units（GPU）’s parallel operating characteristics．The efficiency of the decoding kernel functions is improved by optimizing the inter－block and intra－block thread parallelism for the nodes’updating operations in software decoding architecture；turbo－decoding message passing （TDMP）algorithm，reducing the thread branch induced by the irregularity of rowweight，lowering the memory access latency for the updating information by threads，and reasonably quantizing the stored information to．The asynchronous compute unified device architecture（CUDA）stream processing mechanism，which includes designing an optimized execution scheduling between decoder’s input／output data transfers and kernel functions，and setting a thread resource allocation method on CUDA streams，is also introduced to maximize the decoding throughput and at the same time reduce the decoding latency．The experimental results from the decoding simulations of the Consultative Committee for Space Data System （CCSDS）telemetry standard’s LDPC codes on the Nvidia’s latest Tesla K20and GTX980platforms demonstrate that the proposed architecture achieves about 500Mbps maximum throughput and about 2ms average latency by using TDMP algorithm with 10iterations．In comparison with the existing results，the proposed architecture can improve both the decoding throughput and latency performance，and maintain the configuration flexibility of software architecture．

low－density parity－check codes；graphics processing units；software decoding architecture；Turbo－decoding message passing algorithm；high－throughput；low latency

2016－01－25；Revised：2016－04－08；Accepted：2016－04－25；Published online：2016－05－05 15：07

URL：www．cnki．net／kcms／detail／11．1929．V．20160505．1507．004．html

National Natural Science Foundation of China（91438116）

V443＋．1；TN911．22

A

1000－6893（2017）01－320107－10

http：／hkxb．buaa．edu．cn hkxb＠buaa．edu．cn

10．7527／S1000－6893．2016．0126

2016－01－25；退修日期：2016－04－08；錄用日期：2016－04－25；網(wǎng)絡(luò)出版時間：2016－05－05 15：07

www．cnki．net／kcms／detail／11．1929．V．20160505．1507．004．html

國家自然科學(xué)基金 （91438116）

＊通訊作者 ．E－mail：rongke＿liu＠buaa．edu．cn

侯毅，劉榮科，彭皓，等．適用于空間通信的LDPC碼GPU高速譯碼架構(gòu)［J］．航空學(xué)報，2017，38（1）：320107．HOU Y，LIU R K，PENG H，et al．High－throughput GPU－based LDPC decoder architecture for space communication［J］．Acta Aeronautica et Astronautica Sinica，2017，38（1）：320107．

（責(zé)任編輯：蘇磊）

＊Corresponding author．E－mail：rongke＿liu＠buaa．edu．cn