GPU并行計算技術的惡碼檢驗范文

本站小編為你精心準備了GPU并行計算技術的惡碼檢驗參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

《無線通信技術雜志》2014年第二期

1現(xiàn)有的檢驗卷積碼編碼器的方法

Massey和Sain［4］通過數(shù)學推導驗證卷積碼編碼器生成多項式對于一個(n，1，m)卷積碼編碼器，生成矩陣G(D)有前饋逆G－1(D)，當且僅如果該碼字在BSC上傳播，其中三個非零比特被信道噪聲變?yōu)榱悖瑒t接收序列全是零。最大似然譯碼器則會產生全零碼字作為其估計，因為這是一個有效碼字，并且正好和接收序列相同。因此，估計的信息序列式v(D)=0(D)，意味著有限數(shù)量(這里僅有三個)的信道錯誤引起了無數(shù)的譯碼錯誤。明顯地這是不希望的，譯碼器被稱為遭受了惡性誤碼擴散，即它是一個惡性編碼器［5］。因此，在選擇編碼器用于差錯控制編碼系統(tǒng)時，避免選擇惡性編碼器是非常重要的。數(shù)學推導的方法偏重于計算約束長度較小的卷積碼編碼器。現(xiàn)有的惡碼檢驗方法是使用數(shù)學工具Matlab的檢驗方法。該方法首先要構造出一種柵格型結構，在柵格結構中找到輸出為零重量的結點，然后以此結點作為運算的起點。遍歷碼樹中每一個零重量的結點。尋找柵格結構中的零重量環(huán)。首先尋找長度為2的零重量環(huán)，再尋找長度為3的零重量環(huán)……，直到找完長度為約束長度的零重量環(huán)。這種柵格結構主要用于建立各種狀態(tài)之間的轉換，實際上就是一個矩陣，將所有的狀態(tài)轉換關系在矩陣中表示出來。首先需構造2m－1*2m－1(m為約束長度)個元素構成的矩陣。這樣做的好處是可以根據(jù)當前的狀態(tài)以及輸入變量確定下一刻的狀態(tài)，但有一個很大的缺點就是隨著約束長度的增加，需要存儲的數(shù)據(jù)在急劇的膨脹，最終會因為需要存儲的數(shù)據(jù)量過大超過計算機的內存存儲范圍而無法進行正常的檢驗。現(xiàn)有的工具進行檢驗惡碼的方法有二個突出特點:(1)運算量大，每一次循環(huán)都要做一次矩陣乘，總共需做2m－1次矩陣乘法，當約束長度較大時，計算量是非常驚人的。實驗仿真有效的見證了這一點。(2)進行檢驗所需的內存過大。

2適用于檢驗卷積碼生成

多項式的并行計算方法假定編碼器開始在開始狀態(tài)S0(全零狀態(tài))，通過在狀態(tài)圖中沿著信息序列決定的路徑且記錄分支上的相應輸出，我們可以得到對應于任何給定信息序列的碼字。沿著最后的信息分組，收尾的編碼器通過一個附加到信息序列的m個輸入分組序列回到狀態(tài)S0。圖2給出了圖1所示的卷積碼編碼器的狀態(tài)圖。一個編碼器是惡性的，當且僅當狀態(tài)圖除了有一個圍繞狀態(tài)S0的零重量圈之外，還包含一個零輸出重量圈。圖2所示(2，1，3)編碼器的狀態(tài)圖中，我們注意到，圍繞狀態(tài)S7的單個分支圈有零重量輸出［6］。為了對約束大長度的卷積碼編碼多項式進行檢驗，我們必須運用一種能夠克服現(xiàn)有檢驗方法自身不足的新方法對計算機搜索到的大約束長度的卷積碼編碼器進行檢驗。考慮到惡性卷積碼編碼器有一個圍繞初始狀態(tài)(S0)的零重量環(huán)之外還有至少一個零重量環(huán)的這一特性，我們借助于計算機對卷積碼編碼器的所有狀態(tài)都進行遍歷，可以得到基于這一特性的一個卷積碼編碼多項式檢驗算法。(n，1，m)卷積碼編碼器的單個狀態(tài)檢驗算法的步驟如下:(1)任意選擇當前寄存器中的狀態(tài)為開始時的狀態(tài)放到長度為m的移位寄存器;(2)每次左移一位，判斷是否回到了開始時狀態(tài)，移出寄存器的最高位放到寄存器的末位，計算輸出的碼重，根據(jù)輸出的碼重判定是否進行下一次操作;(3)如果編碼器輸出的碼字重為0，則重復(2)中的操作直到m次，使寄存器中的狀態(tài)在經過m次循環(huán)移位后回到開始時的狀態(tài)，移位操作結束，跳出循環(huán);否則移位結束，跳出循環(huán);(4)當移位操作結束時，如果輸出的碼字重為0，則該編碼器是惡性編碼器，否則該狀態(tài)不能說明編碼器是惡性的。(n，1，m)卷積碼編碼器的全狀態(tài)檢驗算法的步驟如下:(1)從初始狀態(tài)開始;(2)對每個狀態(tài)分別進行單個檢驗;(3)如果檢驗的結果能說明編碼器是惡性的，跳出循環(huán)，否則讓狀態(tài)加一進入下一個狀態(tài);(4)重復(2)和(3)中的操作，直至當寄存器中的狀態(tài)為全一仍未跳出循環(huán)，則跳出循環(huán)。圖3給出了檢驗卷積碼編碼器是否是惡性編碼器的流程圖。

3基于gpu的惡性編碼器檢驗

當卷積碼編碼器的約束長度是m時，則該編碼器中共有2m個狀態(tài)，隨著約束長度的增加狀態(tài)的數(shù)量呈幾何倍數(shù)的增加，檢驗編碼器的生成多項式的計算量在指數(shù)倍增加，如果這些計算量全部由一個順序執(zhí)行的程序完成，則耗費的時間會隨著長度的增加急劇的增加，針對這一問題的解決辦法只能是并行處理所有的狀態(tài)。進行并行處理時由于單個的計算單元之間不能進行通信，并且進行并行處理的初始的數(shù)據(jù)結構應該是一致的。由于所需檢驗的編碼器的所有狀態(tài)在一定的程度上可以認為是一樣的，并且單個狀態(tài)之間互不影響，這為我們進行并行處理提供了前提條件。如果把需要處理的所有狀態(tài)均分到N個線程中進行并行處理，將會獲得巨大的性能提升，這在實際應用中是十分可觀的。GPU進行科學運算時，事實上采用的是一種GPU/CPU協(xié)同的工作模式:CPU負責邏輯判斷和數(shù)據(jù)調配;GPU則完成數(shù)據(jù)量大、線性度高的并行任務。GPU采用的是SIMT(singleinstruction，multiplethread)執(zhí)行模型。從硬件上看GPU上的計算核心為SM流處理器，每個SM中包括8個標量流處理器(SP)，SP只是執(zhí)行單元。SM包括取指、解碼、分發(fā)邏輯執(zhí)行單元和存儲器，是一個完整的計算單元。從編程邏輯上看，GPU上的并行程序采用雙層并行，即網(wǎng)格中的線程塊并行和block間的線程并行。CUDA［6］(UnifiedDeviceArchitecture，統(tǒng)一計算設備架構)是一種將GPU作為并行計算設備的軟硬件架構。在CUDA編程環(huán)境中，CPU作為主機(Host)，負責進行邏輯性強的事務處理和串行計算，以及GPU上線程的創(chuàng)建、顯存的申請與數(shù)據(jù)存取等工作［7，8］;GPU作為設備(Device)，專用于執(zhí)行高度線程化的并行運算。在GPU上運行的并行計算函數(shù)稱為Kernel。Kernel是以線程塊(Block)為單位執(zhí)行的。Block之間并行、無序執(zhí)行，且各Block之間無法進行通信。每個Block可以由1～512個線程(Thread)組成，但是具體分配多少個線程要根據(jù)實際情況來定。合理的線程劃分對程序的執(zhí)行效率具有很大影響。我們按照GPU的構架特點把需要處理的數(shù)據(jù)進行了等量的分配。把等量的狀態(tài)分配給GPU內核進行處理，CPU起到控制的作用，等到所有的處理完成后，GPU再把處理的結果反饋給CPU。例如，當我們要驗證約束長度為32的卷積碼編碼器時，我們可以在GPU內核上開512個線程塊，在其中每個線程塊中啟動512個線程，分配到每個線程需要檢驗的狀態(tài)由232下降到216，得到的性能提升時相當?shù)目捎^的。

4實驗仿真

GPU計算實驗平臺參數(shù)如下:CPU為Intel(R)Xeon(R)CPUE56202．40GHz;內存4G;GPU采用GeForce210，核心頻率589MHz，流處理單元數(shù)16個;CUDAToolkit3．2版本;操作系統(tǒng)Win-dowsServer2003;編譯環(huán)境VisualStudio2008(．NETFramework3．5)。我們將GPU和CPU在驗證相同約束長度的編碼器所耗費的時間上進行比較。表1給出了各自的在等量的計算下所耗費的時間。實驗仿真的結果表明當編碼器的約束長度較小時，GPU的高效并行運算能力并沒有得到發(fā)揮，甚至其性能尚沒有CPU表現(xiàn)出的性能好，但是隨著約束長度的增加GPU的高效并行運算效能逐漸顯露出來。在使用GPU進行并行計算時由于GPU和主機之間有數(shù)據(jù)的交互，也就是主機要對GPU進行控制，當數(shù)據(jù)量較大時，主機給GPU分配數(shù)據(jù)時所耗費的時間較長，如果我們能夠進一步的壓縮主機和GPU之間所傳遞的數(shù)據(jù)量，而盡量把數(shù)據(jù)放到GPU上進行處理，則運算的速度將會在一定程度上得到提高，所耗費的時間將進一步的降低。

作者：葛勤革徐大勇張濤濤單位：海軍司令部信息化部科研辦 海軍工程大學電子工程學院