分布式流體系結(jié)構(gòu)及其編程模型與資源管理*

李　鑫，楊學(xué)軍，徐新海

(1.國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙　410073；

2.國(guó)防科技大學(xué) 高性能計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙　410073；

3.中國(guó)人民解放軍總參謀部第六十三研究所， 江蘇 南京　210007)

?

分布式流體系結(jié)構(gòu)及其編程模型與資源管理*

李鑫1,2,3，楊學(xué)軍1,2，徐新海1,2

(1.國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙410073；

2.國(guó)防科技大學(xué) 高性能計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙410073；

3.中國(guó)人民解放軍總參謀部第六十三研究所， 江蘇 南京210007)

摘要：利用互聯(lián)網(wǎng)資源提供大數(shù)據(jù)計(jì)算服務(wù)面臨著資源異構(gòu)性、動(dòng)態(tài)性與通信長(zhǎng)延遲等方面的挑戰(zhàn)，現(xiàn)有分布式計(jì)算模型仍存在一些不足。運(yùn)用流計(jì)算模型提出分布式流體系結(jié)構(gòu)，包括分布式流編程模型與資源管理等，能夠高效支持多種并行執(zhí)行模式。在10個(gè)CPU-GPU異構(gòu)結(jié)點(diǎn)上實(shí)現(xiàn)了原型系統(tǒng)，仿真實(shí)驗(yàn)驗(yàn)證了7個(gè)不同的測(cè)試用例。實(shí)驗(yàn)結(jié)果表明，與本地串行計(jì)算相比，分布式流體系結(jié)構(gòu)可以平均提高39倍計(jì)算性能，具有較大的應(yīng)用潛力。

關(guān)鍵詞：流體系結(jié)構(gòu)；大數(shù)據(jù)；編程模型；分布式計(jì)算

近年來(lái)，“大數(shù)據(jù)”已經(jīng)成為國(guó)際社會(huì)普遍關(guān)注的熱點(diǎn)，在金融、軍事、電信等領(lǐng)域引起了人們的高度重視。大數(shù)據(jù)具有數(shù)據(jù)量大、種類繁多、處理速度快與價(jià)值密度低等4V特征。利用互聯(lián)網(wǎng)資源構(gòu)建面向大數(shù)據(jù)計(jì)算的運(yùn)行環(huán)境具有較好的發(fā)展前景，這種方法不僅能降低計(jì)算成本與提高資源利用率，還能提供可擴(kuò)展的計(jì)算能力，但是卻需要應(yīng)對(duì)互聯(lián)網(wǎng)資源異構(gòu)性、動(dòng)態(tài)性、通信長(zhǎng)延遲與有限帶寬等挑戰(zhàn)。

目前，主流的分布式計(jì)算模型仍然存在一些不足。云計(jì)算[1]主要基于虛擬化技術(shù)等提供彈性可擴(kuò)展的快速服務(wù)部署能力，提供大數(shù)據(jù)架構(gòu)基礎(chǔ)設(shè)施的運(yùn)行環(huán)境。Hadoop等主流大數(shù)據(jù)技術(shù)能應(yīng)對(duì)多種應(yīng)用場(chǎng)景，如MapReduce[2]模型等特別適合松耦合的大規(guī)模數(shù)據(jù)處理應(yīng)用的批處理過(guò)程；Spark[3-4]等適合于機(jī)器學(xué)習(xí)等內(nèi)存迭代計(jì)算；Spark Streaming[5]等比較適合于數(shù)據(jù)規(guī)模龐大且不可預(yù)知或者實(shí)時(shí)動(dòng)態(tài)產(chǎn)生的流式數(shù)據(jù)處理；Dremel[6]與Impala[7]等交互式處理技術(shù)主要是在數(shù)據(jù)量非常大的情況下提供實(shí)時(shí)或準(zhǔn)實(shí)時(shí)的數(shù)據(jù)查詢分析能力；PowerGraph[8]等圖計(jì)算技術(shù)則是面向互聯(lián)網(wǎng)社交網(wǎng)絡(luò)等大規(guī)模圖相關(guān)的應(yīng)用場(chǎng)景，它們主要支持非結(jié)構(gòu)化數(shù)據(jù)與半結(jié)構(gòu)化數(shù)據(jù)的大規(guī)模處理，通常運(yùn)行在數(shù)據(jù)中心較穩(wěn)定的大規(guī)模同構(gòu)資源上，但是在支持互聯(lián)網(wǎng)資源異構(gòu)性以及動(dòng)態(tài)性上還存在一些不足。網(wǎng)格計(jì)算[9]采用類MPI編程模型，在支持動(dòng)態(tài)負(fù)載均衡上還有待改進(jìn)。P2P計(jì)算模型[10]提供的大數(shù)據(jù)處理方式較為簡(jiǎn)單，計(jì)算任務(wù)并行性較好，通常處理流程較簡(jiǎn)單。

近年來(lái)，流計(jì)算模型已經(jīng)成功應(yīng)用在高性能計(jì)算、媒體類應(yīng)用等領(lǐng)域[11-13]，并取得了“天河”等廣泛而有影響力的應(yīng)用成果[14-15]。流計(jì)算模型具有計(jì)算資源普適性、高度數(shù)據(jù)并行性、延遲計(jì)算綁定特性以及流水線并行性等特點(diǎn)，有很大的潛力應(yīng)對(duì)上述互聯(lián)網(wǎng)多方面的挑戰(zhàn)。因此，李鑫等基于流計(jì)算模型首次提出了一種新型的分布式流體系結(jié)構(gòu)(Distributed Stream Architecture，DSA)以試圖解決互聯(lián)網(wǎng)環(huán)境下大數(shù)據(jù)計(jì)算模型的科學(xué)問(wèn)題，并設(shè)計(jì)實(shí)現(xiàn)了分布式流體系結(jié)構(gòu)編程模型Brook#與資源管理。

1分布式流體系結(jié)構(gòu)

分布式流體系結(jié)構(gòu)首次將流處理思想引入分布式領(lǐng)域，擴(kuò)展了傳統(tǒng)流計(jì)算模型的概念，將可用的軟硬件計(jì)算對(duì)象定義為Kernel(計(jì)算核心)，同時(shí)將計(jì)算數(shù)據(jù)與控制狀態(tài)數(shù)據(jù)定義為Stream(流或數(shù)據(jù)流)，其基本概念如下：

控制數(shù)據(jù)流(ControlStream)：控制計(jì)算流程的數(shù)據(jù)或狀態(tài)數(shù)據(jù)；

計(jì)算數(shù)據(jù)流(ComputeStream)：封裝計(jì)算核心并行處理的數(shù)據(jù)；

軟計(jì)算核心(SoftKernel，SK)：封裝計(jì)算核心程序信息的對(duì)象，其元信息包括軟件共享庫(kù)名稱、網(wǎng)絡(luò)位置等；

硬計(jì)算核心(HardKernel，HK)：封裝結(jié)點(diǎn)內(nèi)可用計(jì)算結(jié)點(diǎn)硬件資源信息的對(duì)象，其元信息包括網(wǎng)絡(luò)地址、處理器類型、線程數(shù)目等；

應(yīng)用計(jì)算核心(ApplicationKernel，AK)：封裝應(yīng)用程序中主程序代碼相關(guān)信息的對(duì)象，負(fù)責(zé)申請(qǐng)獲取資源，管理與監(jiān)控計(jì)算任務(wù)運(yùn)行；

客戶管理計(jì)算核心(Client Management Kernel，CMK)：提供用戶查詢和請(qǐng)求服務(wù)的接口；

資源管理計(jì)算核心(Resource Management Kernel，RMK)：提供命令解釋器與執(zhí)行器的功能，負(fù)責(zé)向SMK注冊(cè)本地資源信息；

服務(wù)管理計(jì)算核心(Service Management Kernel，SMK)：提供應(yīng)用服務(wù)等功能，負(fù)責(zé)維護(hù)服務(wù)(查詢、添加、刪除、更新等)、Kernel(HK，SK，AK與RMK)與用戶(CMK)的元信息，并負(fù)責(zé)調(diào)度軟硬件資源。

如圖1所示，分布式流體系結(jié)構(gòu)的資源管理采用了主從架構(gòu)，SMK負(fù)責(zé)統(tǒng)一維護(hù)資源元信息與資源調(diào)度，RMK負(fù)責(zé)命令解釋與執(zhí)行，CMK用于提交應(yīng)用程序請(qǐng)求。運(yùn)行一個(gè)完整的分布式流應(yīng)用程序通常采用1個(gè)host結(jié)點(diǎn)用于管理執(zhí)行環(huán)境與多個(gè)device結(jié)點(diǎn)用于執(zhí)行計(jì)算核心程序。其中：host結(jié)點(diǎn)上運(yùn)行主程序(AK)，負(fù)責(zé)管理整個(gè)應(yīng)用執(zhí)行流程；device結(jié)點(diǎn)上運(yùn)行普通計(jì)算核心程序(SK)。AK與SK均由RMK負(fù)責(zé)啟動(dòng)執(zhí)行。MPEG2編碼應(yīng)用的復(fù)雜處理流程共包括1個(gè)AK與7個(gè)SK計(jì)算核心。

圖1　分布式流體系結(jié)構(gòu)基本概念與MPEG2編碼應(yīng)用Fig.1　Basic concepts of DSA and MPEG2 encoder application

host結(jié)點(diǎn)上的RMK負(fù)責(zé)啟動(dòng)一個(gè)線程來(lái)管理應(yīng)用主程序(AK)。當(dāng)該線程執(zhí)行到一個(gè)計(jì)算核心時(shí)，它會(huì)根據(jù)編譯指導(dǎo)命令劃分原計(jì)算任務(wù)為若干子任務(wù)并行執(zhí)行，創(chuàng)建管理該任務(wù)及其子任務(wù)的線程，并向SMK申請(qǐng)執(zhí)行該計(jì)算核心的軟硬件資源，通知計(jì)算結(jié)點(diǎn)RMK下載代碼與數(shù)據(jù)，計(jì)算完畢后由主程序(AK)更新維護(hù)數(shù)據(jù)一致性。主程序(AK)如此推進(jìn)計(jì)算過(guò)程直至完成整個(gè)任務(wù)。

2分布式流體系結(jié)構(gòu)編程模型Brook#

2.1　基本概念

Brook#在計(jì)算執(zhí)行過(guò)程中流與計(jì)算核心的并行度劃分為四種Kernel執(zhí)行模式，如圖2所示。

圖2　Kernel并行執(zhí)行模式劃分圖Fig.2　Parallel execution modes of Kernel

單個(gè)計(jì)算核心單個(gè)流(Single Kernel Single Stream，SKSS)：即在一個(gè)計(jì)算結(jié)點(diǎn)上執(zhí)行一個(gè)Kernel計(jì)算核心任務(wù)，處理單一流，依靠開(kāi)發(fā)結(jié)點(diǎn)內(nèi)處理器的并行性來(lái)提升計(jì)算能力；

單個(gè)計(jì)算核心多個(gè)流(Single Kernel Multiple Streams，SKMS)：即多個(gè)計(jì)算結(jié)點(diǎn)執(zhí)行相同的Kernel代碼以完成一個(gè)計(jì)算核心任務(wù)，并處理不同的流，通過(guò)空間并行(SKMS-S)或時(shí)間并行(SKMS-T)的方式提高性能；

多個(gè)計(jì)算核心單個(gè)流(Multiple Kernels Single Stream，MKSS)：即多個(gè)計(jì)算結(jié)點(diǎn)上執(zhí)行多個(gè)Kernel以流水線方式處理同一個(gè)流，通過(guò)時(shí)間并行的方式隱藏通信延遲，從而提高性能；

多個(gè)計(jì)算核心多個(gè)流(Multiple Kernels Multiple Streams，MKMS)：即多個(gè)計(jì)算結(jié)點(diǎn)上同時(shí)執(zhí)行不同的Kernel代碼且處理不同的流，包括空間并行性(MKMS-S)與時(shí)間并行性(MKMS-T)兩種并行方式。MKSS是MKMS的一種特例。

2.2　編譯指導(dǎo)語(yǔ)句

Brook#繼承了傳統(tǒng)流編程模型AMD ATI Stream SDK 1.4 Beta的Brook+編程模型全部語(yǔ)法規(guī)范，并開(kāi)發(fā)擴(kuò)充了具有分布式語(yǔ)義的語(yǔ)法元素。見(jiàn)表1，Brook#允許程序員使用編譯指導(dǎo)語(yǔ)句顯式的指明代碼區(qū)域Kernel執(zhí)行模式及相關(guān)屬性，采用C和C++標(biāo)準(zhǔn)提供的pragma機(jī)制，并提供三類形式：parallel_mode，distribute與barrier，同時(shí)無(wú)須關(guān)心資源異構(gòu)性、動(dòng)態(tài)負(fù)載均衡等底層細(xì)節(jié)。

表1　Brook#編譯指導(dǎo)語(yǔ)句表

①clause語(yǔ)法形式是in/out{streamName[(BLOCK/*(n),…), BLOCK/CYCLE(n)]}。

2.2.1parallel_mode語(yǔ)句

程序員可以使用兩個(gè)parallel_mode編譯指導(dǎo)語(yǔ)句包圍住代碼區(qū)域，并指明其單個(gè)或多個(gè)Kernel的并性執(zhí)行模式parallel_mode，即

#pragma brs parallel_mode(n) start

Kernel/Multiple Kernels

#pragma brs parallel_mode finish

其中，n表示子任務(wù)數(shù)。

2.2.2distribute語(yǔ)句

由于子任務(wù)映射到輸入流與輸出流上的數(shù)據(jù)在維度上可能是不同的，所以，每個(gè)子任務(wù)映射的數(shù)據(jù)劃分方式也可能不一樣。程序員需要根據(jù)經(jīng)驗(yàn)與實(shí)際情況靈活配置流的劃分方式與任務(wù)映射方式，達(dá)到高效計(jì)算的目的，即

#pragma brs distribute [clause, …]

Kernel

其中，clause的語(yǔ)法形式如表1中注釋①所示，它表示輸入輸出流的基本屬性，包括流輸入或輸出方向、流名稱、流劃分方式以及與子任務(wù)的映射方式。

Brook#中流劃分方式包括塊分布(BLOCK)和缺省不劃分(*)兩種方式，其中，塊分布(BLOCK)是指將流按照指定的維度均勻劃分為n塊。子任務(wù)映射方式包括塊分布(BLOCK)與循環(huán)分布(CYCLE)，其中塊分布(BLOCK)是指同一個(gè)數(shù)據(jù)塊映射到n個(gè)連續(xù)的子任務(wù)上，循環(huán)分布(CYCLE)則是將數(shù)據(jù)塊依次循環(huán)映射到下標(biāo)遞增的子任務(wù)上。如圖3所示，假設(shè)輸入流的劃分方式為BLOCK(4)，程序員指定啟動(dòng)8個(gè)子任務(wù)并行執(zhí)行該計(jì)算核心。若流映射任務(wù)的方式為BLOCK(2)，則第1個(gè)數(shù)據(jù)塊映射到子任務(wù)1與子任務(wù)2，說(shuō)明這兩個(gè)子任務(wù)的計(jì)算都需要輸入流的第1個(gè)數(shù)據(jù)塊，依次類推。若流映射任務(wù)的方式為CYCLE，則說(shuō)明子任務(wù)1與子任務(wù)5的計(jì)算需要第1個(gè)數(shù)據(jù)塊。數(shù)據(jù)塊映射子任務(wù)的方式是根據(jù)不同的程序執(zhí)行特點(diǎn)而靈活指定的，需要程序員了解應(yīng)用程序的執(zhí)行特點(diǎn)來(lái)配置完成。

圖3　流劃分方式與子任務(wù)映射方式示例Fig.3　Example of data division method and sub-tasks mapping method for analyzing input streams

2.2.3barrier語(yǔ)句

程序員可以使用barrier指定程序執(zhí)行的同步點(diǎn)，實(shí)現(xiàn)對(duì)單個(gè)或多個(gè)Kernel的同步操作，以確保該同步點(diǎn)之前所有Kernel或指定Kernel必須執(zhí)行完畢后才能繼續(xù)執(zhí)行程序，即

ProgramCode

2.3　Brook#編譯器運(yùn)行時(shí)

分布式流體系結(jié)構(gòu)編譯器運(yùn)行時(shí)的整體組織結(jié)構(gòu)示意圖如圖4所示。當(dāng)RMK接收到啟動(dòng)應(yīng)用程序AK計(jì)算核心(host主程序)的請(qǐng)求后，RMK會(huì)創(chuàng)建執(zhí)行線程(executor thread)負(fù)責(zé)執(zhí)行AK程序，并調(diào)用編譯器運(yùn)行時(shí)庫(kù)執(zhí)行已經(jīng)被翻譯成具有指定Brook#語(yǔ)義的多線程代碼序列。執(zhí)行線程負(fù)責(zé)創(chuàng)建任務(wù)工作線程(worker thread)與子任務(wù)工作線程(subworker thread)用于管理每個(gè)計(jì)算核心任務(wù)及其子任務(wù)的執(zhí)行流程，與遠(yuǎn)程計(jì)算結(jié)點(diǎn)RMK進(jìn)行交互，如流與代碼的下載與發(fā)送、任務(wù)啟動(dòng)等。遠(yuǎn)程device結(jié)點(diǎn)上RMK接收到啟動(dòng)任務(wù)請(qǐng)求后，創(chuàng)建執(zhí)行線程(SK代碼)啟動(dòng)子任務(wù)，調(diào)用本地設(shè)備(CPU或GPU等)的Kernel函數(shù)代碼進(jìn)行計(jì)算，一旦結(jié)束就通知host結(jié)點(diǎn)上本任務(wù)工作線程(AK程序)更新全局列表信息，以保證數(shù)據(jù)一致性。

圖4　編譯器Brook#運(yùn)行時(shí)整體組織結(jié)構(gòu)示例Fig.4　Example of entire organization 　　struture of Brook# runtime

圖4中分布式流程序包括matsum與matmul兩個(gè)計(jì)算核心，并分別被劃分為4個(gè)子任務(wù)與2個(gè)子任務(wù)，并采用MKMS-T執(zhí)行模式以流水線并行的方式執(zhí)行。因此，編譯器運(yùn)行時(shí)在host結(jié)點(diǎn)上創(chuàng)建了1個(gè)executor thread、2個(gè)worker thread與6個(gè)subworker thread以及在device結(jié)點(diǎn)上創(chuàng)建了6個(gè)subworker thread。

3分布式流體系結(jié)構(gòu)資源管理

分布式流體系結(jié)構(gòu)資源管理主要包括SMK，RMK，CMK，AK，SK等組件，如圖5所示，其采用了主從架構(gòu)以適應(yīng)大規(guī)模資源的管理，具有良好的可擴(kuò)展性，支持多任務(wù)獨(dú)立運(yùn)行。

SMK負(fù)責(zé)維護(hù)結(jié)點(diǎn)資源元信息，包括對(duì)硬件、軟件、服務(wù)以及用戶等元信息的查詢、添加、刪除、更新等操作。如圖5所示，RMK與CMK啟動(dòng)后主動(dòng)注冊(cè)到SMK上，包括本地可用硬件信息，用戶則將作業(yè)的計(jì)算核心代碼(AK與SK)以及數(shù)據(jù)上傳到資源結(jié)點(diǎn)并注冊(cè)到SMK。此外，SMK還負(fù)責(zé)管理作業(yè)的生命周期過(guò)程，對(duì)資源請(qǐng)求進(jìn)行合理的資源調(diào)度，以實(shí)現(xiàn)不同作業(yè)的安全隔離運(yùn)行。

RMK資源管理計(jì)算核心負(fù)責(zé)解釋與執(zhí)行請(qǐng)求的消息命令，是本地結(jié)點(diǎn)的資源管理器與任務(wù)執(zhí)行器，管理本地可用硬件資源、作業(yè)文件資源與數(shù)據(jù)資源，并提供資源請(qǐng)求服務(wù)，同時(shí)管理與監(jiān)控本地計(jì)算任務(wù)，周期性地向SMK匯報(bào)并更新本結(jié)點(diǎn)運(yùn)行狀態(tài)。

CMK客戶管理計(jì)算核心提供客戶端的功能，一般部署在用戶結(jié)點(diǎn)上，負(fù)責(zé)將程序代碼(AK或SK)以及數(shù)據(jù)提交到資源結(jié)點(diǎn)上，并將應(yīng)用程序或作業(yè)注冊(cè)到SMK，請(qǐng)求查詢作業(yè)運(yùn)行狀態(tài)，并從資源結(jié)點(diǎn)上接收結(jié)果數(shù)據(jù)。

AK應(yīng)用計(jì)算核心是封裝了作業(yè)主程序代碼信息的對(duì)象，負(fù)責(zé)每個(gè)應(yīng)用程序的具體任務(wù)執(zhí)行過(guò)程，并采用了一種中間列表法的方式來(lái)維護(hù)數(shù)據(jù)一致性。AK會(huì)維護(hù)記錄輸入輸出流結(jié)點(diǎn)信息的KernelList與記錄最近更新流的Kernel名的StreamList。當(dāng)主程序執(zhí)行線程(AK)執(zhí)行到一個(gè)計(jì)算核心時(shí)，AK會(huì)主動(dòng)向SMK申請(qǐng)資源分配給子任務(wù)，通過(guò)StreamList查詢更新輸入流的Kernel名，并在KernelList中查找其所在的結(jié)點(diǎn)信息，將這些信息發(fā)送給計(jì)算結(jié)點(diǎn)，通知RMK啟動(dòng)計(jì)算并監(jiān)控任務(wù)狀態(tài)。當(dāng)任務(wù)完畢后，AK 更新KernelList中輸出流的結(jié)點(diǎn)信息和StreamList中對(duì)應(yīng)流的Kernel名，從而維護(hù)數(shù)據(jù)一致性。

圖5　分布式流體系結(jié)構(gòu)資源管理架構(gòu)Fig.5　Framework of resource management of distributed stream architecture

4實(shí)驗(yàn)驗(yàn)證

整個(gè)實(shí)驗(yàn)評(píng)估過(guò)程是在10個(gè)結(jié)點(diǎn)組成的互連網(wǎng)絡(luò)(千兆以太網(wǎng))上完成的，每個(gè)結(jié)點(diǎn)由1個(gè)六核Intel Xeon X5670與1個(gè)AMD Radeon HD 4870×2 GPU組成，操作系統(tǒng)為64位Red Hat Enterprise Linux 5.4，內(nèi)存容量為24GB。

選取7個(gè)典型測(cè)試用例(輸入規(guī)模，用例來(lái)源)，包括MatrixMul(16 384×16 384矩陣規(guī)模，AMD)、Blackscholes(30 000 000個(gè)期權(quán)，PARSEC)、BinomialOption(8 192 000個(gè)期權(quán)，AMD)、N-Body(499 968個(gè)體，AMD)、MRI-Q(64組Large數(shù)據(jù)，Parboil)、CP(100 000個(gè)原子，Parboil)與MatrixMulAdd(16 384×16 384矩陣規(guī)模，AMD)，并采用Brook#將其移植到分布式流體系結(jié)構(gòu)原型系統(tǒng)上，分別簡(jiǎn)記為MM，BL，BO，NB，MQ，CP與MMA，均采用單精度浮點(diǎn)數(shù)。

實(shí)驗(yàn)采用的基準(zhǔn)時(shí)間是本地1個(gè)CPU程序版本的串行執(zhí)行時(shí)間，實(shí)驗(yàn)的對(duì)比程序設(shè)置了三組測(cè)試。第一組測(cè)試使用本地1個(gè)GPU的程序版本(LOCAL-1G)，第二組與第三組測(cè)試都使用移植到分布式流計(jì)算體系結(jié)構(gòu)上遠(yuǎn)程運(yùn)行的程序版本，其中，第二組測(cè)試采用多GPU程序版本(DSA-G)，第三組測(cè)試使用多CPU程序版本(DSA-C)或混合使用多CPU與多GPU的程序版本(DSA-C/G)。通過(guò)對(duì)比各組程序相對(duì)基準(zhǔn)程序時(shí)間的加速比來(lái)評(píng)估在互聯(lián)網(wǎng)模擬通信延遲與有限帶寬等環(huán)境下分布式流體系結(jié)構(gòu)的有效性。結(jié)點(diǎn)內(nèi)的通信方法主要是基于PCIE協(xié)議與GPU等設(shè)備進(jìn)行數(shù)據(jù)傳輸，結(jié)點(diǎn)間的通信方法是基于TCP/IP協(xié)議進(jìn)行互聯(lián)網(wǎng)模擬通信，其中，國(guó)際互聯(lián)網(wǎng)延時(shí)采用Internet Traffic Report網(wǎng)站統(tǒng)計(jì)的2015年五大洲延遲時(shí)間平均值100ms，國(guó)際互聯(lián)網(wǎng)帶寬采用Speedtest網(wǎng)站在2013年186個(gè)國(guó)家與地區(qū)測(cè)量帶寬的30天移動(dòng)平均值13.98Mbps。

實(shí)驗(yàn)結(jié)果如圖6與圖7所示， 圖6顯示了三組測(cè)試相對(duì)本地1個(gè)CPU的加速比實(shí)驗(yàn)結(jié)果，圖7顯示了第二組與第三組測(cè)試中測(cè)試用例通信時(shí)間、計(jì)算時(shí)間和其他時(shí)間開(kāi)銷與通信開(kāi)銷的歸一化時(shí)間統(tǒng)計(jì)情況。

第二組測(cè)試中的DSA-C或DSA-C/G版本平均加速比達(dá)到39倍，第三組測(cè)試中的DSA-G版本平均加速比達(dá)到58倍，分布式流體系結(jié)構(gòu)可以支持模擬互聯(lián)網(wǎng)環(huán)境下測(cè)試用例的運(yùn)行，能夠利用異構(gòu)資源與并行計(jì)算來(lái)提升性能，其中，第三組測(cè)試中的MMA采用了MKMS-T與SKMS-S執(zhí)行模式的DSA-C/G版本，其余測(cè)試用例都采用了SKMS-S執(zhí)行模式的DSA-C或DSA-C/G版本，以挖掘程序潛在的線程級(jí)并行性與任務(wù)級(jí)并行性。

圖6　相對(duì)本地1個(gè)CPU執(zhí)行時(shí)間的加速比實(shí)驗(yàn)結(jié)果Fig.6　Speedups of experimental results over execution time of a local CPU

圖7　測(cè)試用例通信時(shí)間、計(jì)算時(shí)間以及其他時(shí)間的歸一化實(shí)驗(yàn)結(jié)果Fig.7　Normalized experimental results of communication time, computing time and other time of benchmarks

基于多GPU的DSA-G或DSA-C/G版本的加速效果并不比LOCAL-1G版本顯著，這是由互聯(lián)網(wǎng)中通信問(wèn)題的復(fù)雜性等造成的。從實(shí)驗(yàn)結(jié)果看，DSA-G或DSA-C/G由于是遠(yuǎn)程運(yùn)行的應(yīng)用程序，在互聯(lián)網(wǎng)模擬環(huán)境有限帶寬和長(zhǎng)延遲等情況下，計(jì)算過(guò)程必然帶來(lái)不可忽視的通信開(kāi)銷，使得通信開(kāi)銷成為影響性能的因素。因此，這使得加速效果不如本地LOCAL-1G版本。

如圖6所示，7個(gè)典型測(cè)試用例在三組測(cè)試上的結(jié)果表現(xiàn)出三類特點(diǎn)：

1)一般情況下，應(yīng)用加速比呈現(xiàn)下降趨勢(shì)，如MM，NB，CP與MMA。其中，MM，NB與MMA加速比下降得較快。這是由于分布式環(huán)境引入了大量不可忽視的通信與控制開(kāi)銷，其中通信開(kāi)銷平均達(dá)到82%，顯著增加了執(zhí)行時(shí)間，這使得并行計(jì)算方式帶來(lái)的性能提升不足以補(bǔ)償通信開(kāi)銷造成的性能損失，從而造成加速比下降。

2)加速比呈上升趨勢(shì)，如BL與BO。其中，BL的DSA-G與DSA-C/G加速比分別增長(zhǎng)了3.2倍與4.8倍，BO的DSA版本與本地GPU版本具有相當(dāng)?shù)募铀俦?。雖然通信帶來(lái)較大開(kāi)銷，但在這些應(yīng)用中引入的通信開(kāi)銷與計(jì)算開(kāi)銷相當(dāng)，圖7中BL的通信開(kāi)銷比例平均達(dá)到50%，異構(gòu)資源強(qiáng)大的并行計(jì)算能力使得加速比保持上升。雖然BO通信開(kāi)銷比例較高，但是相對(duì)其他測(cè)試組并不大，因此，使得加速比保持緩慢上升。

3)MQ加速比在DSA-G版本中上升，但在DSA-C版本中下降。這是由于前者利用GPU并行計(jì)算能力帶來(lái)的性能優(yōu)勢(shì)能夠補(bǔ)償通信開(kāi)銷造成的損失，而DSA-C版本則不足以補(bǔ)償這些性能損失，增大的程序控制開(kāi)銷也影響了性能，造成加速比下降。

由此可見(jiàn)，在分布式流體系結(jié)構(gòu)中應(yīng)用程序的計(jì)算開(kāi)銷、通信開(kāi)銷與控制開(kāi)銷之間的優(yōu)化對(duì)于程序運(yùn)行性能有至關(guān)重要的影響。

5結(jié)論

分布式流體系結(jié)構(gòu)能夠較好地適應(yīng)互聯(lián)網(wǎng)資源特點(diǎn)，提供高效的分布式編程模型與資源管理，支持多種計(jì)算核心并行執(zhí)行模式，而無(wú)須關(guān)心資源異構(gòu)性、動(dòng)態(tài)資源綁定等細(xì)節(jié)，具有較大的大數(shù)據(jù)計(jì)算應(yīng)用潛力。

參考文獻(xiàn)(References)

[1]Mell P M, Grance T. The NIST definition of cloud computing[R]. NIST, 2011.

[2]Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters [C]// Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation, 2004: 147-152.

[3]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing [C]// Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, USENIX Association, 2012:2.

[4]Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets [C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. USENIX Association, 2010，10:10.

[5]Zaharia M, Das T, Li H, et al. Discretized streams: fault-tolerant streaming computation at scale [C]// Proceedings of the 24th ACM Symposium on Operating Systems Principles,ACM, 2013: 423-438.

[6]Melnik S, Gubarev A, Long J J, et al. Dremel: interactive analysis of web-scale datasets [C]// Proceedings of the VLDB Endowment, 2010, 3(1): 330-339.

[7]Erickson J. Impala: a modern SQL engine for Hadoop [R]. Tech Report, 2013.

[8]Gonzalez J, Low Y, Gu H. Power graph: distributed graph-parallel computation on natural graphs [C]// Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation,USENIX Association, 2012: 17-30.

[9]Foster I, Kesselman C. The grid 2: blueprint for a new computing infrastructure [M]. 2rd ed.USA:Morgan Kaufmann Publishers Inc., 2003.

[10]Kamvar S D, Schlosser M T, Garcia-Molina H. The EigenTrust algorithm for reputation management in P2P networks [C]// Proceedings of the 12th International World Wide Web Conference,ACM, 2003: 640-651.

[11]Yang X J, Yan X B, Xing Z C, et al. A 64-bit stream processor architecture for scientific applications [C]// Proceedings of the 34th Annual International Symposium on Computer Architecture,San Diego, USA, ACM, 2007: 210-219.

[12]Kapasi U J, Dally W J, Rixner S, et al. The imagine stream processor [C]// Proceedings of the 20th IEEE International Conference on Computer Design: VLSI in Computers and Processors,IEEE, 2002: 282-288.

[13]Ye Y, Li K L, Wang Y, et al. Parallel computation of Entropic Lattice Boltzmann method on hybrid CPU-GPU accelerated system [J]. Computers & Fluids, 2015, 110:114-121.

[14]Xue W, Yang C, Fu H H, et al. Ultra-scalable CPU-MIC acceleration of mesoscale atmospheric modeling on Tianhe-2[J]. IEEE Transactions on Computers, 2015, 64(8):2382-2393.

[15]Liao X K, Pang Z B, Wang K F, et al. High performance interconnect network for Tianhe System [J]. Journal of Computer Science and Technology, 2015, 30(2):259-272.

http://journal.nudt.edu.cn

Programming model and resource management of distributed stream architecture

LIXin1,2,3,YANGXuejun1,2,XUXinhai1,2

(1. College of Computer, National University of Defense Technology, Changsha 410073, China；

2. State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha 410073, China；

3. The 63rd Research Institute of PLA General Staff Headquarters, Nanjing 210007, China)

Abstract：While providing big data computing services using Internet resources, there remains a big challenge to researchers, including heterogeneity of Internet resources, dynamics of Internet resources and long latency of Internet communication. Current influent distributed computing models still have some shortage. A novel distributed stream computing model was proposed based on the traditional stream computing model, including the distributed stream programming model and resource management can efficiently support multiple parallel execution modes. The prototype system implemented on the 10 CPU-GPU heterogeneous nodes. Seven different benchmarks used in the simulation experiment. The experimental result shows that the distributed stream architecture can achieve the speedup of at least on average over the local serial computing, with significant potential for applications.

Key words：stream architecture; big data; programming model; distributed computing

中圖分類號(hào)：TP338.8

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-2486(2015)06-110-06

作者簡(jiǎn)介：李鑫(1984—)，男，安徽安慶人，博士研究生，E-mail：xinli@nudt.edu.cn；楊學(xué)軍(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail：xjyang@nudt.edu.cn

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61221491，61303071)

收稿日期：*2015-09-06

doi:10.11887/j.cn.201506021