唐紹華

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

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

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

唐紹華

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

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

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

1 引言

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

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

圖1 CUDA執(zhí)行模型

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

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

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

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

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

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

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

3.1 隨機(jī)線性編碼

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

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

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

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

3.2 片段編碼并行化

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

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

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

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

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

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

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

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

圖3 并行編碼

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

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

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

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

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

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

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

4.1 有效利用GPU存儲(chǔ)層次

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

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

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

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

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

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

4.3 基于紋理Cache并行解碼

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

圖4 基于紋理Cache并行解碼

5 實(shí)驗(yàn)評(píng)估與性能分析

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

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

5.1 基于紋理Cache并行解碼

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

圖5 片段大小對(duì)編碼時(shí)間的影響

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

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

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

圖6 編碼速度比較圖

表3 編碼速度比較表

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

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

圖7 解碼帶寬比較圖

表4 解碼帶寬比較表

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

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

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

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

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

6 結(jié)束語(yǔ)

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

[1]楊林，鄭剛，胡曉惠，等.網(wǎng)絡(luò)編碼的研究進(jìn)展[J].計(jì)算機(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ú)線網(wǎng)絡(luò)路由機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào)，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)化問(wèn)題研究[J].軟件學(xué)報(bào)，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的并行全搜索運(yùn)動(dòng)估計(jì)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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.

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

唐紹華（1980—），男，講師，工程師，研究領(lǐng)域?yàn)樾畔踩?，?jì)算機(jī)網(wǎng)絡(luò)，高性能計(jì)算。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