一種利用圖形處理器gpu實現的並行rs解碼方法
2023-08-09 03:53:01 2
專利名稱：一種利用圖形處理器gpu實現的並行rs解碼方法
技術領域：
本發明涉及一種利用圖形處理器GPU實現的並行RS解碼方法，適用於衛星地面接收系統高速數據通信中海量信息的實時處理。
背景技術：
衛星地面接收系統需要接收通過星地通信鏈路下傳的大量數據信息進行採集、傳輸、綜合分析、計算等處理。星地通信鏈路是一種不穩定的鏈路，在該鏈路上傳輸信息時存在大量的誤碼。為了抵抗星地通信鏈路的誤碼對數據的影響，衛星地面接收系統必須採用糾錯碼技術。糾錯碼技術是衛星地面接收系統抵抗信道誤碼的關鍵手段，是數據能夠被正確、及時處理的前提，在接收系統中具有較高的處理複雜度。RS碼作為常用的糾錯碼，其解碼 速度直接影響衛星地面接收系統的數據處理速度，進而決定了地面接收系統的最大接收能力。RS碼是一類具有很強糾錯能力的多進位BCH碼，也是一類典型的代數幾何碼。它首先由Reed和Solomon應用MS多項式於1960年構造出來。用MS多項式構造的RS碼是非系統碼，而用BCH碼構造方法能產生系統碼。由於線性碼的最大可能的最小距離是校驗元的個數加1，而RS碼恰好做到這一點，因此，稱RS碼為極大最小距離可分碼(MDS碼)。RS碼採用了 q進位，所以它是多進位調製時的自然和方便的編碼手段；RS碼特別適合於在衰落信道中使用，以克服突發性差錯。正由於其優越的性能，RS碼在深空通信、數字音視頻通信、磁記錄介質等領域取得廣泛應用，它是目前應用最為廣泛的糾錯編碼之一。根據對糾錯能力的要求不同，可以採用具有不同參數的RS碼。無論具有何種參數，RS碼所採用的解碼方法均相同。例如空間通信常用的RS碼為空間數據系統諮詢委員會(CCSDS)推薦的RS(255, 223)或RS(255，239)碼，這兩種碼的解碼方法相同，只是糾錯能力參數不同。RS解碼器的解碼過程通常包括三個計算步驟錯誤檢測、關鍵方程計算、錯誤糾正。三個計算步驟均需要進行大量的有限域運算，其中乘法、加法運算的數量龐大，對解碼速度的影響也最大。通用計算機只能順序的執行乘法或加法，因此採用通用計算機及配套軟體進行RS解碼的處理速度較低，無法滿足海量衛星數據處理的實時性要求。為了達到實時處理的要求，常用方案是設計專用RS解碼板卡，通過FPGA晶片實現解碼過程的高速處理。專用板卡的硬體設計、製造、維護成本高昂，軟體不具有通用性。隨著衛星下傳數據速率的飛速增加，對RS解碼的速率要求也在不斷提高。採用專用處理板卡可以滿足現有數據處理速度，但在處理速度需求超出當前板卡性能上限或者所使用的RS編碼參數變更時只能重新進行板卡硬體及其專用軟體的設計，造成設備升級難度大、成本高。
發明內容
本發明解決的技術問題是克服現有技術的不足，提供一種利用圖形處理器GPU實現的並行RS解碼方法，根據衛星地面接收系統的要求，採用連接有GPU的通用計算機作為硬體平臺，通過GPU內部計算核心的兩層並行結構實現高速並行RS解碼，在實現高速並行RS解碼的前提下經濟的實現解碼速率上限的升級，成本低，易於實現。本發明的技術方案是一種利用圖形處理器GPU實現的並行RS解碼方法，實現步驟如下(I)通用計算機首先根據編碼參數生成有限域與二進位數據轉換查找表、有限域加法查找表、有限域乘法查找表、有限域對偶基和自然基查找表，然後將上述各查找表寫入GPU紋理內存；(2)通用計算機檢測已連接的GPU個數及各個GPU的最大並行規模，根據已連接的所有GPU的最大並行規模讀入多個待解碼的RS碼字；(3)通用計算機將讀入的碼字寫入GPU內部的全局存儲器，啟動GPU解碼程序進行解碼，GPU中設計多個線程，線程數量遠大於讀入碼字的數量，利用線程實現多個碼字的並 行解碼；(4)通用計算機邊讀取後續碼字，邊等待GPU解碼結果；(5)GPU解碼和後續數據讀取都結束後，通用計算機從GPU內部的全局存儲器中讀出解碼後的數據，將後續碼字寫入GPU內部的全局存儲器，繼續進行後續碼字的解碼，直到所有數據解碼完成。所述步驟(2)中通用計算機讀入多個待解碼的RS碼字的步驟為(2. I)通過GPU程式語言的指令查詢所連接的GPU數量η ；(2. 2)通過GPU程式語言的指令逐個查詢η個GPU所支持的最大塊數量Β1;Β2，...，Bn以及每個塊支持的最大線程數量T1, T2, , Tn，根據所處理的RS碼字的碼長N，確定一次性讀入的RS碼字數量上限為(B1TJB2TJBnTnV(Wl)；(2. 3)通過通用程式語言讀入不超過(B1I^B2TfBnTnV(Wl)個RS碼字。所述步驟(3)中啟動GPU解碼程序進行解碼的步驟為(3. I)各GPU從全局存儲器中讀取待解碼的碼欄位，用每個線程處理一個RS碼字，各線程首先利用查找表將碼字從其所使用的有限域基低變換至自然基，然後再次利用查找表將數據變換至有限域；在有限域中將各碼字分別乘以相應的係數後，利用歸約求和方法將各個塊內的線程計算結果相加，得到多個碼字的伴隨式，若伴隨式全為O則結束解碼，否則繼續進行以下步驟；(3. 2)GPU使用多個塊對多個碼字進行關鍵方程的計算，計算方法為無需求逆的BM迭代算法，即RiBM算法；GPU利用多個線程進行計算，每個線程均計算一個迭代參數，計算後得到的關鍵方程係數存入全局存儲器；(3. 3)GPU中使用多個塊對誤碼進行糾正，糾正誤碼的方法為錢搜索和福尼算法；每個塊通過多個線程讀入關鍵方程係數，然後各線程分別對所讀入的關鍵方程係數進行乘積運算，隨後各線程的運算結果通過歸約求和的方法進行求和，根據和值判斷當前塊所對應的符號是否為錯誤符號；若當前塊所對應符號存在錯誤，則根據福尼算法計算錯誤值，並利用塊中某一線程執行糾正錯誤值的程序，得到解碼結果；解碼結果存儲在全局存儲器中。本發明與現有技術相比具有如下優點(I)傳統的地面接收系統採用專用處理板卡實現實時解碼，然而專用處理板卡本身不具備最大解碼速率可升級的能力以及自適應RS碼參數變化的能力，若需要提升最大解碼速率或更改RS碼參數，則必須重新設計專用處理板卡的軟、硬體，設計維護成本高昂。本發明對多個RS碼字進行並行解碼處理，可以在插有少量GPU的通用計算機上達到衛星地面接收系統所要求的解碼速率。用GPU實現錯誤檢測、關鍵方程計算、錯誤位置計算和錯誤值計算，使通用計算機可以將數據的讀入與RS解碼處理並行進行，可以提高衛星地面接收系統的解碼速率。(2)與使用專用解碼板卡的傳統方法相比，本發明的可擴展性更好。當系統性能需要擴展時簡單的增加GPU個數即可，而專用硬體板卡不具有此性質。(3)與使用專用解碼板卡的傳統方法相比，本發明的軟體設計更簡便。專用解碼板 卡的軟體需要燒入晶片，代碼修改和調試過程複雜所用軟體無需燒入處理，修改、調試方法與通用計算機軟體一樣簡便。
圖I為利用GPU實現的並行RS解碼示意圖。
具體實施例方式下面結合附圖I對本發明作進一步說明。GPU是一種可以連接在通用計算機上的並行處理設備，具有大量的並行計算核心，通常具有獨立的物理存儲器和高速存儲器讀取機制，可以在通用計算機上使大量數據的加法、乘法運算速度得到數十甚至數百倍的提升。在GPU中，軟體以程序核為單位順序執行，每個程序核均對數據進行並行處理。每個程序核的並行規模可以獨立設置。程序核內的並行結構分為兩個層次塊和線程。每個程序核軟體可以分為多個塊並行執行，每個塊獨立執行程序指令，塊與塊之間不能進行數據交互。每個塊又可以分為多個線程，每個線程獨立執行所在的塊收到的程序指令，線程之間可以通過每個塊內的共享內存進行通信。同時GPU的軟體無需燒入晶片等處理，調試開發簡便。在硬體結構上，GPU內部具有上百個硬體計算核心，各個計算核心均可以獨立進行運算。通常用一個硬體計算核心運行一個軟體線程，從而實現多個軟體線程的並行運行。GPU硬體計算核心與軟體線程的映射關係對軟體透明，因此同樣的軟體可以運行在具有不同指標的GPU硬體上。在存儲器結構上，GPU具有全局存儲器、共享存儲器和紋理存儲器，其中紋理存儲器可以通過高速緩存實現快速查表功能。利用GPU軟硬體的並行結構，可以實現並行RS解碼。由於GPU對數據的並行處理速率與其中包含的計算核心數量以及處理主頻約成正比，同樣的軟體可以通過增加硬體計算核心數量實現數據處理速率的提升。因此在性能需求提高時，僅需要增加GPU個數或者更換計算核心數量更多、處理主頻更高的GPU即可實現，無需對軟體進行更改。升級難度和成本遠低於使用專用解碼板卡。本發明採用通用計算機及GPU作為RS解碼的硬體平臺，通用計算機通過PCI-E接口連接一塊或多塊GPU ;將RS解碼過程分為數據初始化、並行解碼兩部分；通用計算機進行各塊GPU的任務分配、待解碼數據的讀取、解碼參數初始化、GPU內部存儲器中數據的讀寫和數據整理，GPU進行待解碼數據的並行解碼處理。GPU將多個碼字的解碼任務分配給多個硬體計算核心，通過多個計算核心的同時解碼實現並行解碼。通用計算機首先根據編碼參數生成有限域與二進位數據轉換查找表、有限域加法查找表、有限域乘法查找表、有限域對偶基和自然基查找表，將各查找表存入GPU紋理內存；然後檢測已連接的GPU個數及各GPU的最大並行規模，根據已連接的所有GPU的最大並行規模讀入多個待解碼的RS碼字；將讀入的碼字寫入GPU內部的全局存儲器，啟動GPU解碼程序進行解碼，GPU軟體中設計多個線程，線程數量遠大於讀入碼字的數量，利用線程實現多個碼字的並行解碼；隨後通用計算機一邊讀取後續碼字，一邊等待GPU解碼結果；待GPU解碼和後續數據讀取都結束後，從GPU內部的全局存儲器中讀出解碼後的數據；最後將後續碼字寫入GPU內部的全局存儲器，繼續進行後續碼字的解碼，直到所有數據解碼完成。GPU將RS解碼按順序分解為檢錯、關鍵方程計算、錯誤糾正三個步驟；為每個步驟
設計一個程序核，各個程序核具有不同的塊規模與線程規模，通過在GPU內的多個硬體計算核心上同時運行多個線程實現並行解碼；三個程序核順序依次執行，程序核之間通過全局存儲器進行數據傳遞；檢錯程序核通過多個塊和線程實現並行，塊數量等於單個RS碼字的伴隨式數量與RS碼字個數之積，每個塊內的線程數量與RS碼字長度相同；關鍵方程計算程序核通過多個塊和線程實現並行，塊數量為RS碼字個數，每個塊內的線程數量為關鍵方程係數個數；錯誤糾正程序核通過多個塊和線程實現並行，塊數量為RS碼字長度與RS碼字個數之積，每個塊內線程數量為RS碼字能夠糾正的最大錯誤字節數量。本發明具體實現步驟如下(I)通用計算機首先確定RS碼的碼字長度、糾錯能力、碼生成多項式、有限域生成多項式、本原元。隨後生成有限域與二進位數據轉換查找表、有限域加法查找表、有限域乘法查找表、有限域對偶基和自然基查找表，存儲在計算機內存中。各查找表根據有限域生成多項式進行計算，由程序自動生成。(2)通用計算機通過GPU程式語言的指令對其所連接的GPU進行檢測，檢測到2、
3、4等η個GPU。隨後通用計算機逐個查詢η個GPU所支持的最大塊數量BI，B2，...，Bn以及每個塊支持的最大線程數量Tl，Τ2，. . .，Τη，根據所處理的RS碼字的碼長N，確定一次性讀入的RS碼字數量上限為(B1TJB2TJBnTn)/(Ν+1)。根據讀入碼字數量的上限選取同時解碼的RS碼字數量k。(3)從待解碼的碼字I中連續讀入k個碼字至通用計算機內存。根據2、3、4等GPU所支持的並行規模將k個碼字分為多個碼欄位，碼欄位個數與GPU個數相同。通用計算機將各段碼字分別傳輸至各GPU的全局存儲器。隨後通用計算機讀入下面k個連續的碼字。(4)各GPU從全局存儲器中讀取待解碼的碼欄位，用程序核5對所有碼字進行檢錯。程序核5具有多個塊，塊數量等於讀入的碼欄位數量與單個碼字的伴隨式個數之積，即每個塊可以求得一個伴隨式。每個塊內的線程數量等於碼字長度，即每個線程對一個碼字進行處理。各線程首先利用查找表將各碼字從其所使用的有限域基低變換至自然基，然後再次利用查找表將數據變換至有限域。在有限域中將各碼字分別乘以相應的係數後，利用歸約求和方法將各個塊內的線程計算結果相加，得到多個碼字的伴隨式，將其存入全局存儲器並檢驗伴隨式中是否存在非零值，若存在非零值，則非零標誌位置位。(5)通用計算機對非零標誌位進行檢測，若置位則運行程序核5和程序核6，否則讀入的數據中不存在錯誤，讀入的碼字即為解碼結果，繼續進行後續碼字的解碼處理。 (6)若非零標誌位置位，則各GPU中程序核6從全局存儲器中讀入程序核5的計算結果進行關鍵方程計算。程序核6使用多個塊，塊數量等於RS碼字個數，即每個塊對一個碼字進行關鍵方程的計算，計算方法為無需求逆的BM迭代算法。GPU中每個塊內設計多個線程，線程數量與所使用的計算方法中迭代參數的個數相同，即每個線程對一個迭代參數進行計算。計算後得到的關鍵方程係數存入全局存儲器。 (7)各GPU中程序核7從全局存儲器中讀入程序核6的計算結果，同時讀入待糾錯的碼字，利用錢搜索和福尼算法對誤碼進行糾正。程序核7使用多個塊，塊數量等於RS碼字個數與單個RS碼字的伴隨式個數之積，即每個塊對碼字中的一個符號進行錯誤糾正。每個塊使用多個線程，線程數量等於RS碼字所能糾正的最大錯誤符號數量。每個塊首先通過多個線程讀入關鍵方程係數，然後各線程分別對所讀入的關鍵方程係數進行乘積運算，隨後各線程的運算結果通過歸約求和的方法進行求和，根據和值判斷當前塊所對應的符號是否為錯誤符號。若當前塊所對應符號存在錯誤，則根據福尼算法計算錯誤值，並利用塊中某一線程執行糾正錯誤值的程序，得到解碼結果。解碼結果存儲在全局存儲器中。(8)各GPU解碼後的碼欄位8分別存儲在各GPU的全局存儲器中。通用計算機在各GPU解碼結束後從各全局存儲器中讀取解碼後的RS碼欄位，在內存中將各碼欄位按順序進行拼接，得到解碼結果。(9)通用計算機將讀入的下k個碼字傳輸至GPU，開始下k個碼字的解碼，直到所有待解碼碼字均被解碼完畢。本發明未詳細闡述部分屬於本領域公知技術。
權利要求
1.一種利用圖形處理器GPU實現的並行RS解碼方法，其特徵在於實現步驟如下 (1)通用計算機首先根據編碼參數生成有限域與二進位數據轉換查找表、有限域加法查找表、有限域乘法查找表、有限域對偶基和自然基查找表，然後將上述各查找表寫入GPU紋理內存； (2)通用計算機檢測已連接的GPU個數及各個GPU的最大並行規模，根據已連接的所有GPU的最大並行規模讀入多個待解碼的RS碼字； (3)通用計算機將讀入的碼字寫入GPU內部的全局存儲器，啟動GPU解碼程序進行解碼，GPU中設計多個線程，線程數量遠大於讀入碼字的數量，利用線程實現多個碼字的並行解碼； (4)通用計算機邊讀取後續碼字，邊等待GPU解碼結果； (5)GPU解碼和後續數據讀取都結束後，通用計算機從GPU內部的全局存儲器中讀出解碼後的數據，將後續碼字寫入GPU內部的全局存儲器，繼續進行後續碼字的解碼，直到所有數據解碼完成。
2.根據權利要求I所述的一種利用圖形處理器GPU實現的並行RS解碼方法，其特徵在於所述步驟(2)中通用計算機讀入多個待解碼的RS碼字的步驟為 (2. I)通過GPU程式語言的指令查詢所連接的GPU數量η ； (2. 2)通過GPU程式語言的指令逐個查詢η個GPU所支持的最大塊數量B1, B2, . . .，Bn以及每個塊支持的最大線程數量T1, T2，. . .，Tn，根據所處理的RS碼字的碼長N，確定一次性讀入的RS碼字數量上限為(B1TJB2TJBnTn)/(Ν+1)； (2. 3)通過通用程式語言讀入不超過(B1TAB2TdBnTnV(Wl)個RS碼字。
3.根據權利要求I所述的一種利用圖形處理器GPU實現的並行RS解碼方法，其特徵在於所述步驟(3)中啟動GPU解碼程序進行解碼的步驟為 (3. I)各GPU從全局存儲器中讀取待解碼的碼欄位，用每個線程處理一個RS碼字，各線程首先利用查找表將碼字從其所使用的有限域基低變換至自然基，然後再次利用查找表將數據變換至有限域；在有限域中將各碼字分別乘以相應的係數後，利用歸約求和方法將各個塊內的線程計算結果相加，得到多個碼字的伴隨式，若伴隨式全為O則結束解碼，否則繼續進行以下步驟； (3. 2) GPU使用多個塊對多個碼字進行關鍵方程的計算，計算方法為無需求逆的BM迭代算法，即RiBM算法；GPU利用多個線程進行計算，每個線程均計算一個迭代參數，計算後得到的關鍵方程係數存入全局存儲器； (3. 3)GPU中使用多個塊對誤碼進行糾正，糾正誤碼的方法為錢搜索和福尼算法；每個塊通過多個線程讀入關鍵方程係數，然後備線程分別對所讀入的關鍵方程係數進行乘積運算，隨後各線程的運算結果通過歸約求和的方法進行求和，根據和值判斷當前塊所對應的符號是否為錯誤符號；若當前塊所對應符號存在錯誤，則根據福尼算法計算錯誤值，並利用塊中某一線程執行糾正錯誤值的程序，得到解碼結果；解碼結果存儲在全局存儲器中。
全文摘要
一種利用圖形處理器GPU實現的RS並行解碼方法，以連接有一個或多個GPU的通用計算機作為硬體平臺，將RS解碼分為數據讀寫與初始化、並行解碼兩部分，利用GPU內具有大量計算核心的特點，同時對多個RS碼字進行解碼，實現並行解碼。並行解碼被分解為4個步驟，對每個步驟均設計並行處理方法，使整個解碼過程實現並行化，提高RS解碼的速率。當解碼速率上限不足時可以通過增加GPU計算核心數量實現經濟的升級。本發明根據衛星地面接收系統的要求，採用連接有GPU的通用計算機作為硬體平臺，通過GPU內部計算核心的兩層並行結構實現高速並行RS解碼，在實現高速並行RS解碼的前提下經濟的實現解碼速率上限的升級，成本低，易於實現。
文檔編號H03M13/15GK102938653SQ201210453928
公開日2013年2月20日 申請日期2012年11月13日 優先權日2012年11月13日
發明者魏耀都, 張拯寧, 朱翔宇, 戰勇傑 申請人:航天恆星科技有限公司