面向眾核GPU加速系統(tǒng)的網(wǎng)絡(luò)編碼并行化及優(yōu)化

唐紹華

湖南工程職業(yè)技術(shù)學(xué)院信息工程系，長沙 410151

◎網(wǎng)絡(luò)、通信、安全◎

面向眾核GPU加速系統(tǒng)的網(wǎng)絡(luò)編碼并行化及優(yōu)化

唐紹華

湖南工程職業(yè)技術(shù)學(xué)院信息工程系，長沙 410151

網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)節(jié)點在數(shù)據(jù)存儲轉(zhuǎn)發(fā)的基礎(chǔ)上參與數(shù)據(jù)處理，已成為提高網(wǎng)絡(luò)吞吐量、均衡網(wǎng)絡(luò)負載和提高網(wǎng)絡(luò)帶寬利用率的有效方法，但是網(wǎng)絡(luò)編碼的計算復(fù)雜性嚴重影響了系統(tǒng)性能?；诒姾薌PU加速的系統(tǒng)可以充分利用眾核GPU強大的計算能力和有效利用GPU的存儲層次結(jié)構(gòu)來優(yōu)化加速網(wǎng)絡(luò)編碼?；贑UDA架構(gòu)提出了以片段并行的技術(shù)來加速網(wǎng)絡(luò)編碼和基于紋理Cache的并行解碼方法。利用提出的方法實現(xiàn)了線性隨機編碼，同時結(jié)合體系結(jié)構(gòu)對其進行優(yōu)化。實驗結(jié)果顯示，基于眾核GPU的網(wǎng)絡(luò)編碼并行化技術(shù)是行之有效的，系統(tǒng)性能提升顯著。

網(wǎng)絡(luò)編碼；圖形處理器（GPU）；并行；計算統(tǒng)一設(shè)備架構(gòu)（CUDA）；優(yōu)化

1 引言

網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量、改善負載均衡、減小傳輸延遲、節(jié)省節(jié)點能耗、增強網(wǎng)絡(luò)魯棒性等方面均顯示出其優(yōu)越性[1]。因此，網(wǎng)絡(luò)編碼一經(jīng)提出便引起了國際學(xué)術(shù)界的廣泛關(guān)注，其理論和應(yīng)用已廣泛應(yīng)用于分布式文件存儲[2]、P2P系統(tǒng)[3-4]、無線網(wǎng)絡(luò)[5]。然而，現(xiàn)實網(wǎng)絡(luò)環(huán)境的非確定性[6]、網(wǎng)絡(luò)編碼的計算復(fù)雜性[7]等因素嚴重影響了系統(tǒng)整體性能，使得網(wǎng)絡(luò)編碼技術(shù)的實用性不強。因此，網(wǎng)絡(luò)編碼優(yōu)化成為推動網(wǎng)絡(luò)編碼技術(shù)更具實用性的重要手段[8-9]，其中，優(yōu)化網(wǎng)絡(luò)編碼的計算通信開銷更是研究的熱點，包括網(wǎng)絡(luò)編碼算法的構(gòu)造設(shè)計以及基于硬件的網(wǎng)絡(luò)編碼加速[7，10-12]。

雖然研究者在利用GPU加速網(wǎng)絡(luò)編碼方面進行了較為深入的研究，也取得了可喜的成績。但是，他們的工作都傾向于最大化GPU計算資源的利用率，GPU計算資源耗費不少，然而并行網(wǎng)絡(luò)編碼系統(tǒng)的效率并不高；同時，對結(jié)合GPU體系結(jié)構(gòu)和存儲層次而展開的優(yōu)化工作也尚有不足。本文的工作將致力于結(jié)合眾核GPU體系結(jié)構(gòu)設(shè)計高效的并行網(wǎng)絡(luò)編碼算法和面向GPU存儲層次對并行網(wǎng)絡(luò)編碼進行優(yōu)化。

圖1 CUDA執(zhí)行模型

2 眾核GPU體系結(jié)構(gòu)及CUDA編程模型

CUDA（Computing Unified Device Architecture，CUDA）是NVidia為適應(yīng)GPU通用計算而推出的一種高性能GPU體系架構(gòu)，支持CUDA的GPU是一塊具有可擴展處理器數(shù)量的處理器陣列，與傳統(tǒng)GPU最大的區(qū)別在于，它擁有片內(nèi)共享存儲空間用以減小片外訪存延遲[13]。CUDA執(zhí)行模型以CUDA硬件架構(gòu)為基礎(chǔ)，如圖1所示。

CUDA源程序由運行于host（CPU）上的控制程序和運行于device（GPU）上的計算核心（kernel）兩部分組成。每一個kernel由一組相同大小的線程塊（thread block）來并行執(zhí)行，同一線程塊里面的線程通過共享存儲空間來協(xié)作完成計算，線程塊之間是相互獨立的。運行時，每一個線程塊會被分派到一個流多處理器（Streaming Multi-processor，SM）上運行，一個SM包括8個線程處理器（Threaded Processor，TP）和一段大小為16 KB的共享存儲空間（Shared Memory），另外，GPU還提供了一定數(shù)量的全局的只讀的紋理Cache和常量Cache[14]。

3 基于CUDA架構(gòu)的并行網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼的本質(zhì)是賦予節(jié)點計算能力以提高鏈路帶寬的利用率。圖2（b）闡述了網(wǎng)絡(luò)編碼的基本原理，圖中s是信源，x和y是信宿，假設(shè)各邊的帶寬均為1 bit/s，現(xiàn)要將2比特數(shù)據(jù)a和b同時從s傳到x和y。s與x和y之間均分別存在兩條獨立路徑，若采用傳統(tǒng)路由方法，如圖2（a）所示，由于存在共有鏈路wz，a和b不能同時在wz上傳輸；若采用網(wǎng)絡(luò)編碼方法，在節(jié)點w上對a和b執(zhí)行異或操作并轉(zhuǎn)發(fā)，則節(jié)點x可以通過a⊕b⊕a計算解碼得到b，同理y也可以解碼得到a，從而提高了帶寬利用率。

圖2 路由分發(fā)與網(wǎng)絡(luò)編碼比較

網(wǎng)絡(luò)編碼按照節(jié)點輸出和輸入的關(guān)系可劃分為線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼，根據(jù)編碼系數(shù)生成的隨機性可劃分為隨機網(wǎng)絡(luò)編碼和確定網(wǎng)絡(luò)編碼[1]，實用的網(wǎng)絡(luò)編碼系統(tǒng)大多采用隨機線性編碼[2-3，6-7，9-12]。然而，隨機網(wǎng)絡(luò)編碼計算復(fù)雜度較高，嚴重影響了編碼系統(tǒng)的性能，為此，本文基于眾核GPU加速的系統(tǒng)設(shè)計并實現(xiàn)了并行的隨機網(wǎng)絡(luò)編碼算法，并且有效利用GPU存儲層次對其進行優(yōu)化，使得隨機網(wǎng)絡(luò)編碼系統(tǒng)的性能有了顯著性的提升。

3.1 隨機線性編碼

所謂線性網(wǎng)絡(luò)編碼就是將節(jié)點傳送信息線性映射到一個有限域內(nèi)，利用線性關(guān)系實現(xiàn)編譯碼的過程[9]。通信網(wǎng)絡(luò)G(V，E)中，信源s∈V的輸入數(shù)據(jù)b被分割為n個數(shù)據(jù)片段b1b2…bn，每個片段含有k個字節(jié)。一個網(wǎng)絡(luò)節(jié)點可以在有限域內(nèi)獨立地選擇一組隨機編碼系數(shù)c1c2…cn，生成一個k字節(jié)的編碼片段X，即

由于每個編碼片段X是原始數(shù)據(jù)片段的一個線形組合，因此編碼片段可以由線形組合中的參數(shù)集唯一確定。當(dāng)一個節(jié)點接收到n個線性無關(guān)的編碼片段[X1，X2，…，Xn]T，就可以進行解碼。

根據(jù)每個原始片段的系數(shù)構(gòu)造一個n×n的系數(shù)矩陣C，C的每一行對應(yīng)于一個編碼片段的系數(shù)，然后利用C解碼得出原始片段。

在方程（2）中，可以利用高斯消元法計算矩陣C的逆，再與X相乘，其復(fù)雜度為ο(n2·k)。其中，當(dāng)C是行線性無關(guān)時，C的逆存在。

3.2 片段編碼并行化

正如文獻[7，10-12]中歸納的：線性編碼的主要性能瓶頸集中于有限域上的乘法操作和循環(huán)計算每個片段中n×k個字節(jié)的乘加操作。因此，優(yōu)化加速有限域上的乘法、循環(huán)乘加操作對提高網(wǎng)絡(luò)編碼的性能至關(guān)重要。文獻[7，10-12]都采用將有限域上的乘法操作轉(zhuǎn)換為基于對數(shù)和指數(shù)的并行查表，即

將有限域上的對數(shù)和指數(shù)預(yù)先計算好存儲起來，將有限域上的一次乘法操作轉(zhuǎn)換為三次查表和一次加法操作。

在計算受限的系統(tǒng)中，上述過程將昂貴的乘法操作轉(zhuǎn)換為相對廉價的查表和加法操作，對系統(tǒng)的性能有一定的提升。但是，在存儲受限的GPU結(jié)構(gòu)中，訪存查表很可能比乘法計算的延遲更大，并且，將有限域上的對數(shù)表和指數(shù)表緩存起來對共享存儲空間的壓力太大并且訪存沖突、復(fù)用率等因素也值得考慮；即使在計算受限的結(jié)構(gòu)中，可以更加激進地將有限域上的一次乘法操作轉(zhuǎn)換為一次查表完成。

支持CUDA的GPU雖然擁有一定的片內(nèi)共享存儲空間用以減小片外訪存延遲，但是共享存儲空間受限只有16 KB，并且顯式地分派管理數(shù)據(jù)極易引起訪存沖突。但是，支持CUDA的GPU擁有數(shù)以百計的計算核，計算比訪存更有優(yōu)勢。因此，基于片段的并行編碼將采用啟動數(shù)以千記的線程同時編碼的方法來分攤昂貴的乘法開銷。

在支持CUDA架構(gòu)的GPU上，最直接的并行算法就是將每一個數(shù)據(jù)片段都交付給一個獨立的線程去處理，這樣只要數(shù)據(jù)片段足夠多，就可以啟動大量的線程來同時執(zhí)行，因此，可以將片段劃分得足夠小，以獲得啟動更多的線程。片段的大小為1 bit不合適，數(shù)據(jù)片段沒有實際意義；數(shù)據(jù)通常以字節(jié)為單位，那么以字節(jié)為單位似乎更合理。但是片段太小只會浪費計算資源，更重要的是會增加線程之間的通訊開銷。由于現(xiàn)有的支持CUDA的GPU計算核的字長為32位，因此，選擇片段的大小為2個字節(jié)，不夠的可以在末尾補0，這樣兩個大小為2個字節(jié)的數(shù)據(jù)相乘，其結(jié)果在有效范圍內(nèi)，并且數(shù)據(jù)精確度高。

設(shè)輸入數(shù)據(jù)b被可以分割為n個大小為2個字節(jié)數(shù)據(jù)片段b1b2…bn，將每一個片段都分派給一個線程來處理，則所需要的線程數(shù)目為：

若設(shè)置每個線程塊包含512個線程，則所需要的線程塊的數(shù)目為：

并行編碼的流組織過程如圖3所示。圖3中演示了一個線程塊中512個線程并行加載數(shù)據(jù)和進行數(shù)據(jù)編碼的過程。在CUDA架構(gòu)中同一個線程塊內(nèi)的線程在編譯調(diào)度時會被分派到同一個流多處理器上，因此它們共享一個大小為16 KB的共享存儲空間（Shared Memory）。在并行編碼中使用共享存儲空間加載原始數(shù)據(jù)片段，處理完后直接存放在共享存儲空間，通過有效使用共享存儲空間可以減少數(shù)據(jù)的存取訪問時間。

圖3 并行編碼

3.3 主機協(xié)作并行解碼

正如文獻[7]中歸納的：解碼過程與編碼相比具有更高的計算復(fù)雜度，最為關(guān)鍵的是解碼過程內(nèi)在的并行性更少，后面節(jié)點的解碼依賴于前面節(jié)點的解碼結(jié)果，因此節(jié)點之間還必須同步。文獻[10]提出了一種漸進式的高斯-約當(dāng)消元法來提高解碼效率；Shojania等人在文獻[7，11]中也是采用高斯-約當(dāng)消元法來解碼，不同的是，他們建議將GPU與CPU協(xié)作起來進行解碼?；痉椒ㄊ牵河蒀PU生成隨機系數(shù)，在GPU上計算矩陣的逆并解碼。

表1 支持CUDA的GPU存儲結(jié)構(gòu)

CPU與GPU協(xié)作進行解碼是一個明智的選擇，但是，CPU還可以承擔(dān)系數(shù)矩陣求逆的任務(wù)，然后將C-1傳遞給顯存，因為矩陣求逆和GPU計算kernel可以異步執(zhí)行，即，CPU將編碼kernel啟動后可以執(zhí)行主機上的矩陣求逆，等待編碼結(jié)束后可以在最短時間內(nèi)將CPU計算的逆矩陣傳遞給顯存?？紤]到C-1的復(fù)用性高，還可以進一步將其緩存起來，在支持CUDA的GPU中，紋理Cache專門為二維空間位置而優(yōu)化過并且C-1無需更新，所以將C-1直接綁定緩存至紋理存儲空間。

考慮到網(wǎng)絡(luò)解碼過程內(nèi)在并行性的特點，并行網(wǎng)絡(luò)解碼將參考文獻[13]中tiled模式的矩陣乘法來解碼。

4 面向體系結(jié)構(gòu)的并行編碼優(yōu)化

面向GPU結(jié)構(gòu)的編程需要顯式管理分派數(shù)據(jù)，因此結(jié)合GPU體系結(jié)構(gòu)，尤其是有效利用GPU的存儲層次進行優(yōu)化對整個系統(tǒng)的性能提升尤為重要，因此，下面將面向GPU的體系結(jié)構(gòu)對并行網(wǎng)絡(luò)編碼系統(tǒng)進行優(yōu)化。

4.1 有效利用GPU存儲層次

CUDA線程可在執(zhí)行過程中訪問多個存儲器空間的數(shù)據(jù)，如表1所示。

共享存儲空間（Shared Memory）的有效使用是CUDA應(yīng)用優(yōu)化最常用、最容易想到的存儲優(yōu)化技術(shù)，這是因為共享存儲器位于流多處理器片上，并且它為一個線程塊內(nèi)的線程共享，為同一線程塊內(nèi)的線程之間的通信提供了便利，同時，與全局存儲器相比，其速度要快得多。但是，共享存儲器的存儲空間大小有限，并且對數(shù)據(jù)的分派管理不當(dāng)，會引起存儲體沖突，這時訪存就必須序列化，降低了有效帶寬。因此，并行編譯碼時，謹慎使用共享存儲器很有必要。

并行編碼過程中，使用共享存儲空間存放中間數(shù)據(jù)結(jié)果，為后面的數(shù)據(jù)處理做準(zhǔn)備，可以避免數(shù)據(jù)在全局存儲空間來回傳遞，有效減少了訪存延遲，并且簡化了中間流的管理；并行解碼過程中，可以將系數(shù)矩陣的逆復(fù)制給每一個流多處理的共享存儲器，可以避免同一個線程塊里面的線程重復(fù)訪問全局存儲器。考慮到共享存儲器的空間受限并且作用廣泛，解碼過程將求助于其他優(yōu)化方法。

4.2 基于設(shè)備運行時組件加速乘法操作

如前面所述，文獻[7，10-12]都采用將有限域上的乘法操作轉(zhuǎn)換為基于對數(shù)和指數(shù)的并行查表來避免乘法操作，本文通過大量線程并行來分攤乘法操作的開銷。同時，CUDA運行時庫支持的設(shè)備運行時組件中包括了幾乎所有的數(shù)學(xué)標(biāo)準(zhǔn)庫函數(shù)[11]。這些設(shè)備運行時組件會被映射到GPU上的一條指令或一個指令系列，這些設(shè)備組件內(nèi)部的數(shù)學(xué)函數(shù)是標(biāo)準(zhǔn)庫函數(shù)精確度較低但速度更快的版本，但是，加法和乘法是符合IEEE規(guī)范的[11]，因此精度與標(biāo)準(zhǔn)庫函數(shù)相同。

因此，設(shè)備運行組件支持的數(shù)學(xué)函數(shù)__fmul_（x，y）和__fadd_（x，y）將嘗試應(yīng)用于網(wǎng)絡(luò)編碼計算中以進一步改善系統(tǒng)性能。

4.3 基于紋理Cache并行解碼

紋理Cache其實就是全局存儲器的一個特定區(qū)域。但是，紋理Cache空間是被緩存的，因此紋理獲取僅需在緩存內(nèi)容失效時才讀取一次全局存儲器，否則只需讀取紋理緩存即可。同時，紋理緩存已為二維空間位置而優(yōu)化過，通過只讀的紋理Cache也可以緩存無需更新的系數(shù)矩陣的逆，并且紋理Cache專門為二維空間位置而優(yōu)化過[11]，有利于存儲二維的數(shù)據(jù)結(jié)構(gòu)。因此，并行解碼過程中，將主機計算好的系數(shù)矩陣的逆存儲在紋理Cache中，可以充分利用紋理Cache的優(yōu)勢，加快各個線程對系數(shù)矩陣逆的訪問，基于紋理Cache的并行解碼過程如圖4所示。

圖4 基于紋理Cache并行解碼

5 實驗評估與性能分析

為了驗證基于GPU架構(gòu)的并行網(wǎng)絡(luò)編碼系統(tǒng)的有效性和高效性，在Nvidia GTX280實驗平臺上模擬了網(wǎng)絡(luò)編碼過程，其中GTX280的主要參數(shù)如表2所示。測試的原數(shù)據(jù)大小包括16 KB、32 KB、64 KB和128 KB；評估了并行編碼速度和基于紋理Cache解碼帶寬兩個主要的性能指標(biāo)。

表2 Nvidia GTX280的相關(guān)配置

5.1 基于紋理Cache并行解碼

圖5顯示了編碼片段大小對編碼運行速度的影響，由圖5可以發(fā)現(xiàn)，片段越?。? Byte），雖然可開發(fā)的并行性越多，但是編碼速度卻遠低于期望值；編碼片段大小選擇為2個Byte，雖然可開發(fā)的并行性似乎減少了，但是性能卻表現(xiàn)較好；編碼片段大小選擇為4個Byte時所表現(xiàn)出來的性能與選擇為2個Byte時差別不大，同時，由于受到GPU計算核字長的限制，片段大小超過2個Byte后，計算的精確度就很難保證了。由圖5可以得出，片段并不是越大越好，也不是越小越好，這是因為，并行粒度的大小與計算資源的利用率以及線程間的通信息息相關(guān)，只要充分利用計算資源就好，并不是所有計算資源都忙起來就好，當(dāng)然也不能讓它們處于空閑。因此，實驗數(shù)據(jù)也說明選擇片段大小為2個Byte是正確的、高效的。

圖5 片段大小對編碼時間的影響

5.2 基于片段的并行編碼速度

為了驗證基于片段的并行網(wǎng)絡(luò)編碼的高效性，標(biāo)識文獻[7，10-12]采用將有限域上的乘法操作轉(zhuǎn)換為基于對數(shù)和指數(shù)的并行查表的技術(shù)進行編碼的方法為TB（Table-Based）；標(biāo)識本文提出的基于片段并行編碼的方法為Frag；Frag方法是一個原生的并行技術(shù)，并沒有對其結(jié)合GPU結(jié)構(gòu)進行優(yōu)化；因此，標(biāo)識經(jīng)過優(yōu)化的片段并行方法為Frag+Opt，這些優(yōu)化方法主要包括面向GPU體系結(jié)構(gòu)的一些優(yōu)化技術(shù)，主要包括：基于設(shè)備運行時組件加速乘法操作和有效利用共享存儲空間優(yōu)化線程間通信和簡化中間流管理。

圖6和表3顯示了基于片段的并行編碼及其優(yōu)化技術(shù)對編碼性能提升的影響，基于片段的并行編碼與基于查表的編碼方法相比較，性能提升顯著，但是面向GPU體系結(jié)構(gòu)的優(yōu)化對編碼速度的提升并不是很明顯，這是因為并行編碼的性能瓶頸不在于乘法操作到底是多少個周期內(nèi)完成，同時，由于選擇的片段大小為2 Byte，其乘法操作符合GPU字長的要求，因此不需要分割數(shù)據(jù)進行循環(huán)乘加運算，也減少了進程間通信的機會。因此，面向GPU結(jié)構(gòu)的優(yōu)化在此對性能的提升不明顯，但是這些優(yōu)化方法可以推廣至其他GPU應(yīng)用中。

圖6 編碼速度比較圖

表3 編碼速度比較表

5.3 基于紋理Cache的并行解碼帶寬

圖7和表4顯示了紋理Cache對并行解碼性能的提升是顯著的。在不引入紋理Cache進行緩存優(yōu)化的情況下，在平臺Nvidia GTX280下，每個線程塊運行512個線程時，其帶寬利用率與Shojania等人在文獻[11]中的相同配置下的表現(xiàn)相當(dāng)；引入紋理Cache對系數(shù)矩陣的逆進行緩存優(yōu)化后性能攀升顯著。性能提升的另外一個重要原因就是本文將隨機系數(shù)生成、矩陣求逆等任務(wù)都交給了主機，也減少了GPU的處理時間，主機協(xié)作對帶寬利用率的提升貢獻也不少。而Shojania等人在文獻[11]中只是將部分任務(wù)交給了主機。因此，紋理Cache緩存以及主機協(xié)作計算等都是并行解碼過程中帶寬利用率提升的重要原因。

圖7 解碼帶寬比較圖

表4 解碼帶寬比較表

5.4 系統(tǒng)性能分析

分析圖6和圖7的實驗數(shù)據(jù)可以發(fā)現(xiàn)，F(xiàn)rag方法與TB方法比較，編碼的速度提升了2倍之多；基于紋理Cache的并行解碼的帶寬利用率也提升了近2倍。雖然這個加速比不是很高，但是它比較的對象是網(wǎng)絡(luò)編碼在GPU上優(yōu)化后的實現(xiàn)版本，并不是與單核或多核CPU比較的結(jié)果，因此這個性能加速比還是可以接受的。

但是，從圖6還可以發(fā)現(xiàn)Frag+Opt方法與Frag方法比較，性能提升不明顯，這與設(shè)計的初衷是不統(tǒng)一的。為了充分發(fā)揮Shared Memory的效用，減輕Shared Memory的壓力而求助紋理Cache優(yōu)化并行解碼，但是Shared Memory最后發(fā)揮的效用甚微，因此，Shared Memory可以嘗試用來緩存系數(shù)矩陣，因為訪問Shared Memory比訪問紋理Cache更有優(yōu)勢。當(dāng)然，基于紋理Cache緩存系數(shù)矩陣也有自己的優(yōu)勢，它的空間比較大，可以緩存較大量的數(shù)據(jù)集，這是Shared Memory所不能比的。

同時，比較表2和圖6還可以發(fā)現(xiàn)，即使是基于紋理Cache優(yōu)化后的帶寬利用率也是很低的，當(dāng)然，這個帶寬利用率不能僅僅只與GPU內(nèi)部的最大的可用帶寬比較，因為它還受限從CPU到GPU的數(shù)據(jù)傳輸速率。但是，比較表2和圖6至少可以說明基于GPU的并行網(wǎng)絡(luò)編碼系統(tǒng)的性能瓶頸在于存儲帶寬。如何進一步提高GPU存儲帶寬的利用率將會成為研究的難點。

總之，基于眾核GPU加速應(yīng)用必須深入理解GPU的體系結(jié)構(gòu)及存儲層次，權(quán)衡技術(shù)的利弊及相互影響，最大限度開發(fā)利用GPU的資源。

6 結(jié)束語

網(wǎng)絡(luò)編碼一經(jīng)提出便引起了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注和認同，但是現(xiàn)實中網(wǎng)絡(luò)編碼的應(yīng)用還遠未普及，在很大程度上是因為網(wǎng)絡(luò)編碼引入的計算開銷。基于眾核GPU加速的系統(tǒng)來優(yōu)化加速網(wǎng)絡(luò)編碼可以有效緩解上述難題，但是，GPU結(jié)構(gòu)是一種新涌現(xiàn)的高性能體系結(jié)構(gòu)，如何更好地利用其強大的計算資源和可用的存儲帶寬、GPU與主機之間的通訊協(xié)作、GPU應(yīng)用的自動優(yōu)化技術(shù)等亟需更深入的研究。

[1]楊林，鄭剛，胡曉惠，等.網(wǎng)絡(luò)編碼的研究進展[J].計算機研究與發(fā)展，2008，45（3）：400-407.

[2]Dimakis A G，Godfrey P B，Wainwright M，et al.Network coding for distributed storage systems[C]//Proceedings of the 26th Annual IEEE Conference on Computer Communications（INFOCOM 2007），Anchorage，USA，2007：2000-2008.

[3]Jafarisiavoshani M，F(xiàn)ragouli C，Diggavi S.Bottleneck discovery and overlay management in network coded Peerto-Peer systems[C]//Proceedings of the SIGCOMM Workshop on Internet Network Management，Kyoto，Japan，2007：293-298.

[4]Gkantsidis C，Miller J，Rodriguez P.Comprehensive view of a live network coding P2P system[C]//Proceedings of the 6th ACM SIGCOMM on Internet Measurement，New York，NY，2006：177-188.

[5]汪洋，林闖，李泉，等.基于非合作博弈的無線網(wǎng)絡(luò)路由機制研究[J].計算機學(xué)報，2009，32（1）：54-68.

[6]Chou P.Practical network coding[C]//Proceedings of the Allerton Conference on Communication，Control，and Computing，Monticello，IL，2003：63-68.

[7]Shojania H，Li Baochun.Pushing the envelope：extreme network coding on the GPU[C]//Proceedings of the 29th IEEE International Conference on Distributed Computing Systems，Montreal，QC，2009.

[8]黃政，王新，Huang Z.網(wǎng)絡(luò)編碼中的優(yōu)化問題研究[J].軟件學(xué)報，2009，20（5）：1349-1360.

[9]Ho T，Medard M，Koetter R，et al.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory，2006，52（10）：4413-4430.

[10]Shojania H，Li Baochun.Parallelized network coding with hardware acceleration[C]//Proceedings of the 15th IEEE International Workshop on Quality of Service，Chicago，IL：2007：1-9.

[11]Shojania H，Li Baochun，Xin W.Nuclei：GPU-accelerated many-core network coding[C]//Proceedings of the INFOCOM，Rio de Janeiro，Brazil，2009：459-467.

[12]Chu X W，Zhao K Y，Wang M.Massively parallel network coding on GPUs[C]//Proceedings of the IEEE Performance，Computing and Communications Conference，Austin，Texas，2008：144-151.

[13]NVIDIA.CUDA programming guide 2.0[S].NVIDIA Corporation，2008.

[14]甘新標(biāo)，沈立，王志英.基于CUDA的并行全搜索運動估計算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2010，22（3）：457-460.

TANG Shaohua

Department of Information Engineering,Hunan Engineering Polytechnic,Changsha 410151,China

It is well known that network coding has emerged as a promising technique to improve network throughput, balance network loads as well as better utilization of the available bandwidth of networks,in which intermediate nodes are allowed to perform processing operations on the incoming packets other than forwarding packets.But,its potential for practical use has remained to be a challenge,due to its high computational complexity which also severely damages its performance.However,system accelerated by many-core GPU can advance network coding with powerful computing capacity and optimized memory hierarchy from GPU.A fragment-based parallel coding and texture-based parallel decoding are proposed on CUDA-enable GPU.Moreover,random linear coding is parallelizing using CUDA with optimization based on proposed techniques.Experimental results demonstrate a remarkable performance improvement,and prove that it is extraordinarily effective to parallelize network coding on many-core GPU-accelerated system.

network coding;Graphic Processing Unit（GPU）;parallelizing;Compute Unified Device Architecture（CUDA）; optimization

A

TP338.6

10.3778/j.issn.1002-8331.1403-0071

TANG Shaohua.Parallelizing network coding on manycore GPU-accelerated system with optimization.Computer Engineering and Applications,2014,50（21）：79-84.

國家高技術(shù)研究發(fā)展計劃（863）（No.2012AA010905）；國家自然科學(xué)基金（No.60803041，No.61070037）；湖南省教育廳2012年度科技項目（No.12C1024）。

唐紹華（1980—），男，講師，工程師，研究領(lǐng)域為信息安全，計算機網(wǎng)絡(luò)，高性能計算。E-mail：tsh1181@163.com

2014-03-10

2014-04-28

1002-8331（2014）21-0079-06

CNKI出版日期：2014-07-11，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0071.html