黃　磊，支小莉，鄭圣安（.上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院，上海00444；.上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海0040）

面向大數(shù)據(jù)應(yīng)用的多層次混合式并行方法

黃磊1，支小莉1，鄭圣安2
（1.上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院，上海200444；2.上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海200240）

基于很多大數(shù)據(jù)應(yīng)用存在對數(shù)據(jù)進(jìn)行多種并行處理的需求，提出兩層混合式并行方法，即執(zhí)行單元的混合并行和計(jì)算模型的混合并行.通過在同一個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行單元的混合并行，充分挖掘基礎(chǔ)設(shè)施的計(jì)算能力，從而提高數(shù)據(jù)處理性能；采用在同一個(gè)執(zhí)行引擎中集成多個(gè)計(jì)算模型的并行方法，以適合應(yīng)用多樣異質(zhì)處理模式.不同的混合并行方法可以契合不同的數(shù)據(jù)和計(jì)算特點(diǎn)，以滿足不同的并行目標(biāo).介紹了混合式并行方法的基本思想，并以前期開發(fā)的并行編程模型BSPCloud為基礎(chǔ)，闡述了進(jìn)程和線程混合并行、BSP和MapReduce混合并行的主要實(shí)現(xiàn)機(jī)制.

混合并行；編程模型；整體同步并行（bulk synchronous parallel，BSP）；MapReduce

在物聯(lián)網(wǎng)、電子商務(wù)、電信、醫(yī)療和金融等諸多應(yīng)用領(lǐng)域，數(shù)據(jù)已經(jīng)從TB級迅速發(fā)展到PB級甚至更高的數(shù)量級，且仍以指數(shù)速度增長，信息數(shù)量及復(fù)雜程度與日俱增［1-2］.通過對數(shù)據(jù)的分析和處理掌握未來的發(fā)展趨勢，使數(shù)據(jù)創(chuàng)造出更大的價(jià)值已經(jīng)成為一個(gè)亟需解決的問題［3-6］.

大數(shù)據(jù)的并行處理需求催生了以Hadoop，Dryad，Pregel，Hama，All Pairs，Oivos，KPNs，Storm和Spark等為代表的并行處理平臺.每一種大數(shù)據(jù)并行處理平臺適合于特定的數(shù)據(jù)類型，能高效地處理某一類數(shù)據(jù)［7］，例如Hadoop適合處理易于用鍵值對表示的數(shù)據(jù)密集型數(shù)據(jù)，Storm適合于處理流數(shù)據(jù)，Pregel適合于處理大規(guī)模圖數(shù)據(jù)，Hama適合于處理大規(guī)?？茖W(xué)計(jì)算.

隨著大數(shù)據(jù)應(yīng)用的擴(kuò)展及其處理要求的變化，計(jì)算模型也隨之不斷創(chuàng)新和優(yōu)化，不斷產(chǎn)生新的各種面向領(lǐng)域的處理技術(shù)和處理平臺［8］.從橫向上看，針對不同的數(shù)據(jù)類型，計(jì)算模型呈現(xiàn)出不斷擴(kuò)散的趨勢，基于這些模型的Dryad，Pregel，All Pairs，Orleans平臺均適合于處理某一領(lǐng)域的數(shù)據(jù)；從縱向上看，處理平臺呈現(xiàn)出不斷演化的趨勢，HadoopDB，Pig Latin，Sawzall，Oivos，KPNs和Spark等平臺皆由MapReduce模型演化而來，Pregel和Hama等平臺則是基于整體同步并行（bulk synchronous parallel，BSP）模型發(fā)展而來的.

由于應(yīng)用領(lǐng)域的多元性、數(shù)據(jù)類型的復(fù)雜性、數(shù)據(jù)處理方式以及流程等的多樣性，研究混合并行計(jì)算方法，以適應(yīng)大數(shù)據(jù)應(yīng)用的處理方式多樣性和異構(gòu)性，已成為一個(gè)迫切需要解決的問題.需要使用不同的技術(shù)手段、利用異構(gòu)的基礎(chǔ)設(shè)施和異質(zhì)的計(jì)算特征來獲取性能優(yōu)勢.

1　研究現(xiàn)狀

已有的關(guān)于混合并行計(jì)算的研究基本上是在異構(gòu)多核的硬件架構(gòu)上的混合并行，例如CPU和GPU的并行執(zhí)行、多CPU系統(tǒng)中的進(jìn)程級和線程級的并行［9］.這類混合并行方法已在各領(lǐng)域的計(jì)算密集型應(yīng)用中獲得廣泛使用.從本質(zhì)上說，這種混合計(jì)算主要從硬件角度來觀察，將同一個(gè)并行計(jì)算模型的不同實(shí)現(xiàn)方法或?qū)崿F(xiàn)機(jī)制進(jìn)行混合，或者利用硬件組成部分的異構(gòu)性來實(shí)現(xiàn)異質(zhì)的并行.例如，基于消息的分布內(nèi)存的消息傳遞接口（message passing interface，MPI）并行和共享內(nèi)存的線程級OpenMP的混合并行.文獻(xiàn)［10］認(rèn)為未來的系統(tǒng)是混合系統(tǒng)，即同構(gòu)多核處理器+GPU+其他加速器.從程序執(zhí)行角度看，這種混合并行通常體現(xiàn)為多重硬件所支持的多種或多個(gè)執(zhí)行單元（execution unit）的并行，例如多進(jìn)程和多線程的并行.

本研究側(cè)重于更高層次的混合并行，即計(jì)算模型的混合并行.目前，國內(nèi)外相關(guān)研究主要集中在對單一并行編程模型的創(chuàng)新或改進(jìn)，對混合計(jì)算模型及混合式編程模型的研究比較鮮見.孟丹等［11］提出一種Transformer編程架構(gòu)，該架構(gòu)基于兩個(gè)簡單的主類型send（）和receive（）范式建立程序模型，試圖以一種統(tǒng)一的方式來構(gòu)建不同的并行編程模型.Pace［12］對MapReduce模型和BSP模型進(jìn)行了分析，指出MapReduce模型本身缺乏堅(jiān)實(shí)的理論基礎(chǔ)，并需要與其他模型（如BSP，PRAM等）建立關(guān)系，同時(shí)指出用MapReduce來實(shí)現(xiàn)BSP是可行的，但沒有考慮MapReduce和BSP混合并行的問題.潘巍等［13］介紹了為分布式大圖算法設(shè)計(jì)的一個(gè)改進(jìn)的MapReduce并行計(jì)算框架，將BSP嵌入到Map或Reduce階段.通過將迭代過程內(nèi)化到Map或Reduce階段的BSP超級步間，從而減少多輪作業(yè)調(diào)度的開銷.本研究的編程模型中沒有把BSP限制到MapReduce的內(nèi)部，而是由應(yīng)用自行決定BSP和MapReduce這兩種模式的關(guān)系.同時(shí)本研究還修改了一些BSP和MapReduce對輸入輸出和中間數(shù)據(jù)的處理方式，使其能靈活選擇內(nèi)存或文件形式，從而改善編程模型對更多應(yīng)用的支持能力.Fegaras［14］提出一個(gè)新的框架，將數(shù)據(jù)分析應(yīng)用的描述性查詢翻譯成MapReduce和BSP的評估計(jì)劃，根據(jù)運(yùn)行時(shí)的資源決定采用哪個(gè)模型.若資源足夠，就采用BSP模型，完全在內(nèi)存中計(jì)算查詢，否則，采用MapReduce模型.這項(xiàng)工作給本研究帶來一定啟示：BSP和MapReduce在內(nèi)存數(shù)據(jù)是否能跨越迭代步這一點(diǎn)上，截然不同的做法會對不同特點(diǎn)的應(yīng)用產(chǎn)生很大的性能影響.

目前的大數(shù)據(jù)并行編程模型大多是針對特定類型的數(shù)據(jù)進(jìn)行某種模式的處理，缺乏有效的混合方案，難以適應(yīng)大數(shù)據(jù)應(yīng)用的異構(gòu)數(shù)據(jù)處理的需求.

2　兩層混合式并行方法

由于應(yīng)用存在復(fù)雜多樣的并行計(jì)算特征，使得多種并行方式共存成為必需.這些混合并行方式能夠在同一個(gè)編程模型中實(shí)現(xiàn)，可以更靈活方便地支持應(yīng)用開發(fā).混合并行主要從以下兩個(gè)層次來實(shí)現(xiàn)：①執(zhí)行單元（execution unit）的混合，以挖掘異構(gòu)多核硬件的計(jì)算能力；②計(jì)算模型的混合，以適合應(yīng)用的多樣化數(shù)據(jù)處理模式.

2.1執(zhí)行單元層次的混合并行

一個(gè)并行任務(wù)，可以實(shí)現(xiàn)為進(jìn)程或線程等形式在處理器上執(zhí)行.執(zhí)行單元的混合并行主要體現(xiàn)為多進(jìn)程和多線程的混合執(zhí)行.通過充分利用多核異構(gòu)硬件的計(jì)算資源，合理安排節(jié)點(diǎn)內(nèi)和節(jié)點(diǎn)外的數(shù)據(jù)使用策略，能夠顯著加快數(shù)據(jù)處理速度.特別是目前多核處理器在集群中的普遍使用，使得這種對計(jì)算密集型應(yīng)用效果明顯的混合并行成為必然的趨勢.

集群是大數(shù)據(jù)應(yīng)用通常采用的基礎(chǔ)設(shè)施，集群中的節(jié)點(diǎn)可以是普通物理機(jī)，或者是云（虛擬）主機(jī).集群一般具有如圖1所示的邏輯結(jié)構(gòu).每個(gè)節(jié)點(diǎn)機(jī)本身可以是一個(gè)異構(gòu)系統(tǒng)，可能具有多個(gè)同質(zhì)的CPU核和若干異質(zhì)核（如GPU，DSP等）（見圖2）.

圖1　集群的邏輯結(jié)構(gòu)Fig.1　Logical structure of the cluster

圖2　節(jié)點(diǎn)機(jī)的異構(gòu)多核架構(gòu)Fig.2　Heterogeneous and reconfigurable computer architecture

多核硬件的存在使單個(gè)節(jié)點(diǎn)內(nèi)可以存在多層次的線程級并行任務(wù).圖3（a）是適用于同質(zhì)處理器核的兩級并行.圖3（b）是異質(zhì)處理器核CPU+GPU的兩級并行，CPU線程可以等待GPU線程執(zhí)行完畢，也可以與之同時(shí)執(zhí)行.基于此，集群很方便就能實(shí)現(xiàn)至少兩級的混合并行：進(jìn)程級的并行和線程級的并行（見圖4）.這兩級并行實(shí)質(zhì)上是分布內(nèi)存級的并行和共享共存級的并行.在共享共存級的并行中，并行任務(wù)（線程）共享一個(gè)全局地址空間，數(shù)據(jù)交換接近零代價(jià)；在分布內(nèi)存級的并行中，并行任務(wù)（進(jìn)程）行為獨(dú)立，需要顯式通信.

圖3　多線程并行Fig.3　Multi-threaded parallel

圖4　多進(jìn)程與多線程并行Fig.4　Multi-process and multi-threaded parallel

進(jìn)程級和線程級的混合并行在傳統(tǒng)高性能計(jì)算中應(yīng)用較多，例如MPI/OpenMP混合編程模型，雖然在大數(shù)據(jù)應(yīng)用中易被忽視，但這種混合并行對大數(shù)據(jù)應(yīng)用也具有普遍的提升處理速度的效果.

2.2計(jì)算模型層次的混合并行

并行計(jì)算模型通常代表某類典型的數(shù)據(jù)處理模式.計(jì)算模型的混合能滿足同一個(gè)應(yīng)用的處理模式的多樣化需求，使應(yīng)用開發(fā)更自然流暢.每個(gè)并行編程模型中都蘊(yùn)涵了某種計(jì)算模型，最普遍的是MapReduce，BSP和有向無環(huán)圖DAG等.下面首先研究BSP和MapReduce混合的可能性和實(shí)現(xiàn)機(jī)制，然后再考慮其他計(jì)算模型如有向圖或數(shù)據(jù)流模型的混合.

MapReduce是目前使用最廣泛的大數(shù)據(jù)計(jì)算模型［15-16］，其優(yōu)點(diǎn)在于借用函數(shù)式語言的Map和Reduce原語，使得底層復(fù)雜的并行處理細(xì)節(jié)被屏蔽，應(yīng)用開發(fā)者只需關(guān)注Map和Reduce的處理邏輯本身，其余復(fù)雜的并行事務(wù)交由系統(tǒng)來完成，因此系統(tǒng)的可拓展性較好，并且可在廉價(jià)的集群上高效運(yùn)行.但MapReduce采用單輸入單輸出、基于鍵值對的計(jì)算模式，對應(yīng)用存在較強(qiáng)的限制性，不適合需要迭代、重復(fù)的控制流程的應(yīng)用.MapReduce的另一個(gè)主要缺點(diǎn)是不在內(nèi)存中保存跨越連續(xù)的MR任務(wù)數(shù)據(jù)，這在復(fù)雜MR工作流中會引起不能容忍的高開銷.

BSP模型是由Valiant［17］提出的一種并行計(jì)算模型，該模型由很多被稱為超步的計(jì)算過程組成，一個(gè)超步由計(jì)算階段、全局通信階段和路障同步階段組成，其優(yōu)點(diǎn)在于模型簡單易編程、性能可預(yù)測、能避免死鎖等.由于BSP在內(nèi)存中保留了中間數(shù)據(jù)，且超步內(nèi)各任務(wù)可以進(jìn)行通信，故BSP可用于具有復(fù)雜迭代過程的圖、矩陣等計(jì)算.除了用于傳統(tǒng)的高性能并行計(jì)算，BSP還可用于面向大數(shù)據(jù)應(yīng)用的并行計(jì)算，例如Google的Pregel［18］，Apache HAMA［19］和Yahoo Giraph［20］.

BSP和MapReduce各具優(yōu)勢，可以根據(jù)數(shù)據(jù)處理特點(diǎn)結(jié)合使用（combined use），發(fā)揮各自所長（見圖5）.

圖5　BSP和MapReduce的執(zhí)行模型Fig.5　Execution models of BSP and MapReduce

3　HyBSPCloud的實(shí)現(xiàn)機(jī)制

目前已出現(xiàn)很多大數(shù)據(jù)并行編程模型，但支持混合式并行的模型較少.雖然HAMA可以支持BSP引擎和MapReduce引擎，但這兩個(gè)引擎是獨(dú)立的，基本上沒有關(guān)注BSP和MapReduce的有機(jī)結(jié)合的相關(guān)研究.本研究在前期開發(fā)的并行編程模型BSPCloud［21］的基礎(chǔ)上，探索混合式并行方法的實(shí)現(xiàn)機(jī)制，并改善編程模型對大數(shù)據(jù)的支持.

與已有的編程模型相比，BSPCloud具有以下優(yōu)點(diǎn)：

（1）性能可預(yù)測，開發(fā)人員在編寫應(yīng)用時(shí)，有一個(gè)可依賴的性能消耗模型，可以預(yù)先對應(yīng)用程序的時(shí)間復(fù)雜度等進(jìn)行分析；

（2）不僅適合計(jì)算密集型計(jì)算，也適合數(shù)據(jù)密集型計(jì)算；

（3）應(yīng)用的執(zhí)行進(jìn)度可動態(tài)顯示，可以對總執(zhí)行時(shí)間和剩余時(shí)間進(jìn)行預(yù)測.

BSPCloud包含能實(shí)現(xiàn)管理、計(jì)算、通信、進(jìn)度等功能的22個(gè)類的源代碼.本研究在BSPCloud的基礎(chǔ)上，將之改進(jìn)成為HyBSPCloud，使其增加了以下優(yōu)點(diǎn)：①支持兩個(gè)層次上的混合并行；②改善處理大數(shù)據(jù)的能力.

3.1進(jìn)程級和線程級混合并行

HyBSPCloud采用如圖6所示的分布式內(nèi)存和共享內(nèi)存混合并行模型（即進(jìn)程級和線程級的混合并行）.實(shí)現(xiàn)結(jié)構(gòu)如圖7所示.

圖6　HyBSPCloud的進(jìn)程級和線程級混合并行模型Fig.6　Mixture parallel model of process-level and thread-level in HyBSPCloud

圖7　HyBSPCloud中進(jìn)程級和線程級混合并行的實(shí)現(xiàn)Fig.7　Hybrid parallel implementation of process-level and thread-level in HyBSPCloud

圖7中的BspJobTracker負(fù)責(zé)作業(yè)的調(diào)度和控制作業(yè)的運(yùn)行，當(dāng)用戶提交一個(gè)作業(yè)到云平臺后，由調(diào)度器Schedule模塊負(fù)責(zé)調(diào)度作業(yè)運(yùn)行.當(dāng)調(diào)度器取出一個(gè)作業(yè)后，BspJobTracker將作業(yè)劃分成若干子任務(wù)，并將這些子任務(wù)分配到節(jié)點(diǎn)機(jī)（虛擬機(jī)或物理機(jī)），由BulkTracker負(fù)責(zé)調(diào)度運(yùn)行.

BulkTracker啟動若干個(gè)線程，由這些線程完成細(xì)粒度任務(wù)計(jì)算.異構(gòu)處理器（如GPU）的線程由BulkTracker啟動的線程來管理.各個(gè)節(jié)點(diǎn)上的Control負(fù)責(zé)實(shí)現(xiàn)節(jié)點(diǎn)間的同步、負(fù)載均衡、容錯(cuò)等功能.Monitor負(fù)責(zé)向BspJobTracker報(bào)告節(jié)點(diǎn)內(nèi)的運(yùn)行狀態(tài).

BulkTracker之間是進(jìn)程級并行.如圖8所示，進(jìn)程間通信（inter process communication，IPC）可以采用消息傳遞、同步、共享內(nèi)存和遠(yuǎn)程過程調(diào)用等技術(shù).HyBSPCloud使用socket實(shí)現(xiàn)節(jié)點(diǎn)間并行任務(wù)的通信，對節(jié)點(diǎn)內(nèi)的并行進(jìn)程也支持共享內(nèi)存的通信方式.BulkThread之間是線程級并行.HyBSPCloud使用全局變量、消息傳遞、參數(shù)傳遞和線程同步這4種方式實(shí)現(xiàn)線程間通信（inter thread communication，ITC），從而實(shí)現(xiàn)線程級并行管理.對于應(yīng)用開發(fā)者，一般采用全局變量方式就可達(dá)到線程間交換數(shù)據(jù)的目的.

3.2BSP和MapReduce的混合并行

HyBSPCloud在原來的BSP基礎(chǔ)上，增加了MapReduce的實(shí)現(xiàn).BSP和消息傳遞功能不嵌入在Map和Reduce（縮寫為MR）內(nèi)部，MR也不嵌入在BSP的超步中實(shí)現(xiàn).而是由應(yīng)用開發(fā)者決定BSP和MapReduce這兩種模型在執(zhí)行時(shí)的關(guān)系：BSP可以嵌入在MR內(nèi)，MR也可以嵌入到BSP的bulk中.圖9為BSP和MR運(yùn)行時(shí)3種關(guān)系的示例：①將MR嵌入在BSP超步中的計(jì)算階段（算法見表1）；②將BSP嵌入在Map階段（算法見表2），此方法與文獻(xiàn)［13］類似；③先執(zhí)行MR，再執(zhí)行BSP.

圖8　HyBSPCloud的并行任務(wù)間的通信Fig.8　Communication between parallel tasks in HyBSPCloud

圖9　BSP和MapReduce運(yùn)行時(shí)的三種關(guān)系Fig.9　Three relationships of BSP and MapReduce when running

表1　MR嵌入在BSP超步中的計(jì)算階段Table 1　Embed MR into calculation stage of BSP

表2　BSP嵌入在Map階段Table 2　Embed BSP into Map stage

另外，HyBSPCloud的BSP的中間結(jié)果不局限于內(nèi)存，其輸入輸出和中間數(shù)據(jù)均可使用分布式文件系統(tǒng).同時(shí)，為了更好地支持復(fù)雜計(jì)算并行應(yīng)用，提供MR的變形版本，即MR的中間結(jié)果可以“粘”在內(nèi)存中，而不是必須導(dǎo)出來持久化到分布式文件系統(tǒng)中.

3.3HyBSPCloud對大數(shù)據(jù)的支持

本研究采用3種方案來改善HyBSPCloud對大數(shù)據(jù)的支持.

（1）利用開源分布式文件系統(tǒng)來存放輸入數(shù)據(jù)、輸出數(shù)據(jù)，允許計(jì)算的中間數(shù)據(jù)自動持久化到文件中，這是目前支持大數(shù)據(jù)處理最通用的方法.若待處理數(shù)據(jù)不用分布式文件系統(tǒng)支持，完全加載于分布式內(nèi)存，會導(dǎo)致無法滿足海量數(shù)據(jù)的實(shí)際應(yīng)用需求.開源分布式文件系統(tǒng)及其特點(diǎn)如表3所示.從開放性和成熟性來看，首選HDFS作為HyBSPCloud的文件系統(tǒng).為支持大量并發(fā)訪問的應(yīng)用，HyBSPCloud也支持PVFS作為數(shù)據(jù)存儲系統(tǒng).

表3　開源分布式文件系統(tǒng)及其特點(diǎn)Table 3　Open source distributed file systems with their characteristics

（2）虛擬內(nèi)存數(shù)據(jù)結(jié)構(gòu)（vmstruct）.HyBSPCloud提供應(yīng)用運(yùn)行時(shí)對vmstruct的源碼解釋支持.應(yīng)用將vmstruct作為一般的全局?jǐn)?shù)組來使用，但不同的是，vmstruct將大部分?jǐn)?shù)據(jù)存放在外存，而只占用小部分內(nèi)存堆空間，根據(jù)需要再進(jìn)行新舊數(shù)據(jù)的替換.這種結(jié)構(gòu)在一次性順序地操作少量數(shù)據(jù)的應(yīng)用中，可以解決由于內(nèi)存限制導(dǎo)致大數(shù)據(jù)應(yīng)用不能執(zhí)行的問題.

（3）網(wǎng)絡(luò)數(shù)據(jù)流（netdataflow）.HyBSPCloud支持應(yīng)用運(yùn)行時(shí)訪問netdataflow對象，將其作為一個(gè)不斷流出或流入新數(shù)據(jù)的通道.數(shù)據(jù)的另一端點(diǎn)可以設(shè)置為持久化的文件、網(wǎng)絡(luò)信道.

在現(xiàn)有的集群環(huán)境下，增加硬件存儲容量并部署高性能的文件系統(tǒng)是解決并行大數(shù)據(jù)處理的基本方式.由于這種方式依靠文件系統(tǒng)的操作來訪問數(shù)據(jù)，因此時(shí)間開銷較大.若關(guān)于新型非易失存儲介質(zhì)、大容量新型混合內(nèi)存體系結(jié)構(gòu)等的內(nèi)存計(jì)算技術(shù)能取得關(guān)鍵性進(jìn)展，則大數(shù)據(jù)的并行處理技術(shù)也會得到突破.

3.4實(shí)驗(yàn)測試

為了檢驗(yàn)所提出的兩層混合并行的可行性，本研究設(shè)計(jì)了一個(gè)混合并行的綜合實(shí)驗(yàn).假設(shè)兩個(gè)矩陣相乘C=A×B，且B的值已知，A的值需要通過分類統(tǒng)計(jì)數(shù)據(jù)集X得到.本例的一個(gè)應(yīng)用解釋如下：某地區(qū)有若干個(gè)工廠，每個(gè)工廠生產(chǎn)一種以上產(chǎn)品；每個(gè)工廠生產(chǎn)每種產(chǎn)品的月產(chǎn)量的信息存放在數(shù)據(jù)集X中，通過X可以得到該工廠生產(chǎn)每種產(chǎn)品的年產(chǎn)量A；每種產(chǎn)品的單價(jià)和單位利潤存放在矩陣B中；求各工廠的總收入和總利潤，即C.

為實(shí)驗(yàn)方便，假設(shè)A和B是浮點(diǎn)方陣，X中的值也默認(rèn)為浮點(diǎn)數(shù)，X和B中的值都由隨機(jī)函數(shù)生成.實(shí)驗(yàn)使用了如表4所示的硬件資源，程序采用HyBSPCloud并行編程庫來開發(fā).

表4　硬件參數(shù)Table 4　Hardware parameters

所有物理機(jī)運(yùn)行版本為ubuntu 12.04的64位操作系統(tǒng)，虛擬化軟件采用Xen hypervisor 4.1.2，客戶操作系統(tǒng)采用ubuntu 10.04.4的32位操作系統(tǒng).

從Host1上申請2個(gè)虛擬機(jī)（virtual machine，VM），Host2和Host3分別申請一個(gè)VM，每個(gè)虛擬機(jī)的vCPU為4個(gè).為了更好地反映硬件資源的利用情況，實(shí)驗(yàn)中特別指定從特定物理機(jī)申請的虛擬機(jī)數(shù)量.

對于C=A×B的計(jì)算，有兩種BSP程序版本：①用4個(gè)VM，每個(gè)VM上用1個(gè)thread來計(jì)算，即進(jìn)程級并行；②用4個(gè)VM，每個(gè)VM上用4個(gè)thread來計(jì)算，即進(jìn)程和線程混合并行.

版本①和②代碼的不同點(diǎn)僅在于前者在每個(gè)VM上用直接法（單線程處理）計(jì)算子陣At×Bt（At，Bt分別是矩陣A和B的子陣），而后者在每個(gè)VM上把子陣At和Bt再分塊后用4個(gè)線程并行計(jì)算.版本②使用了表5中的函數(shù)來管理多線程.

表5　共享內(nèi)存模型主要函數(shù)Table 5　Main operational functions of shared memory model

用上述兩種計(jì)算矩陣乘的BSP版本，分別進(jìn)行規(guī)模2000×2000和4000×4000的實(shí)驗(yàn)，運(yùn)行時(shí)間如圖10所示.

圖1　0進(jìn)程和線程混合并行的運(yùn)行時(shí)間Fig.10　Running time of processes and hybrid parallel threads

上述計(jì)算A×B的BSP程序是完整計(jì)算C=A×B過程的一部分，該過程有以下3種版本.

（1）用MapReduce計(jì)算矩陣A的元素值，再用BSP計(jì)算A×B.

（2）調(diào)用BSP分塊計(jì)算A×B，在BSP超步中，當(dāng)用到每個(gè)A子塊時(shí)，用MapReduce計(jì)算A子塊的元素值.

（3）調(diào)用MapReduce計(jì)算A′（A′為A的部分值），在每個(gè)Map步后，調(diào)用BSP計(jì)算C′= A′×B，再對C′進(jìn)行加操作的Reduce，最終得到C.

通過對上述3種版本產(chǎn)生的矩陣C進(jìn)行比較，最終結(jié)果是一致的.由實(shí)驗(yàn)結(jié)果可以得出，兩層混合并行是可行的、方便易用的.混合并行的性能分析和比較將是下一步的研究內(nèi)容.

4　結(jié)束語

本研究針對同一個(gè)大數(shù)據(jù)應(yīng)用的異質(zhì)并行計(jì)算問題，提出兩個(gè)層次上的混合并行方法.在執(zhí)行單元層次的混合并行，即進(jìn)程和線程的混合并行時(shí)，可以充分利用多核同構(gòu)/異構(gòu)硬件的計(jì)算資源，顯著加快數(shù)據(jù)處理速度，這種混合并行對于具有密集計(jì)算的應(yīng)用效果明顯.計(jì)算模型層次的混合并行能適合應(yīng)用的多樣異構(gòu)處理模式，使開發(fā)和部署運(yùn)行過程更自然簡潔.BSP 和MapReduce這兩種計(jì)算模型在同一個(gè)編程框架HyBSPCloud上的實(shí)現(xiàn)，表明在充分考慮模型之間并行計(jì)算的流程連續(xù)和動態(tài)數(shù)據(jù)傳遞的前提下，計(jì)算模型混合并行是可行的.

另外，本研究還提出了3種方案以改善HyBSPCloud對大數(shù)據(jù)應(yīng)用的支持，包括用分布式文件系統(tǒng)來存放中間輸入/輸出數(shù)據(jù)、采用虛擬內(nèi)存數(shù)據(jù)結(jié)構(gòu)來解決內(nèi)存限制、通過網(wǎng)絡(luò)數(shù)據(jù)流（netdataflow）來封裝流動的數(shù)據(jù)通道.目前，本研究主要關(guān)注BSP和MapReduce這兩種典型的大數(shù)據(jù)計(jì)算模型混合并行的可行性，下一步將進(jìn)行這種混合方法的性能分析和性能優(yōu)化技術(shù)研究，還將對其他計(jì)算模型的混合并行甚至統(tǒng)一并行模型的可能性進(jìn)行探索.

［1］LYNCH C.Big data：how do your data grow？［J］.Nature，2008，455（4）：28-29.

［2］GOLDSTON D.Big data：data wrangling［J］.Nature，2008，455（4）：15.

［3］WANG S，WANG H J，QIN X P，et al.Architecting big data：challenges，studies and forecasts［J］.Chinese Journal of Computers，2011，34（10）：1741-1752.

［4］QIN X P，WANG H J，LI F R，et al.New landscape of data management technologies［J］.Journal of Software，2013，24（2）：175-197.

［5］ZHANG Y S，JIAO M，WANG Z W，et al.One-size-fits-all OLAP technique for big data analysis［J］.Chinese Journal of Computers，2011，34（10）：1936-1946.

［6］GONG X Q，JIN C Q，WANG X L，et al.Data-intensive science and engineering：requirements and challenges［J］.Chinese Journal of Computers，2012，35（8）：1563-1578.

［7］MA K，YANG B.Log-based change data capture from schema-free document stores using Map-Reduce［C］//2015InternationalConferenceonCloudTechnologiesandApplications （CloudTech）.2015：1-6.

［8］JUNG G，GNANASAMBANDAM N，MUKHERjEE T.Synchronous parallel processing of bigdata［C］//2012 IEEE fifth International Conference on Cloud Computing.2012：811-818.

［9］LIU X，GAO W，HU Z Y.Hybrid parallel bundle adjustment for 3D scene reconstruction with massive points［J］.Journal of Computer Science and Technology，2012，27（6）：1269-1280.

［10］FEINBUBE F，SOBANIA J A，TR¨OGER P，et al.Light-weight programming of hybrid systems［J］. Parallel&Cloud Computing，2012，1（2）：34-44.

［11］WANG P，MENG D，HAN J Z，et al.Transformer：a new paradigm for building data-parallel programming models［J］.Micro IEEE，2010，30（4）：55-64.

［12］PACE M F.BSP vs.MapReduce［J］.Procedia Computer Science，2012，9：246-255.

［13］潘巍，李戰(zhàn)懷，伍賽，等.基于消息傳遞機(jī)制的MapReduce圖算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1768-1784.

［14］FEGARAS L.Supporting bulk synchronous parallelism in Map-Reduce queries［C］//High Performance Computing，Networking，Storage and Analysis（SCC）.2012：1068-1077.

［15］QIN X P，WANG H J，DU X Y，et al.Big data analysis-competition and symbiosis of RDBMS and MapReduce［J］.Journal of Software，2012，23（1）：32-45.

［16］DING L L，XIN J C，WANG G R，et al.Efficient skyline query processing of massive data based on MapReduce［J］.Chinese Journal of Computers，2011，34（10）：1785-1796.

［17］VALIANT L G.A bridging model for parallel computation［J］.Communication of the ACM，1990，33（8）：103-111.

［18］MALEWICZ G，AUSTERN M H，BIK A J C，et al.Pregel：a system for large-scale graph processing［C］//Proceedings of the 2010 International Conference on Management of Data.2010：135-145.

［19］HAMA-a general BSP framework on top of Hadoop［EB/OL］.［2015-10-20］.http：//hama. apache.org.

［20］AVERY C.Giraph：large-scale graph processing infrastructure on Hadoop［C］//Proceedings of the Hadoop Summit.2011：1-8.

［21］LIU X D，TONG W Q，F(xiàn)U Z R，et al.BSPCloud：a hybrid distributed-memory and sharedmemory programming model［J］.International Journal of Grid and Distributed Computing，2013，6（1）：87-98.

Multilevel hybrid parallel method for big data applications

HUANG Lei1，ZHI Xiaoli1，ZHENG Shengan2
（1.School of Computer Engineering and Science，Shanghai University，Shanghai 200444，China；2.Department of Computer Science and Engineering，Shanghai Jiao Tong University，Shanghai 200240，China）

Many large data applications require a variety of parallel data processing.This paper presents a two-layer hybrid parallel method，i.e.，hybrid parallel of execution units and hybrid parallel of computing model.By hybrid parallel of execution units on the same computing node.The computing power of infrastructure can be fully taped，and thus data processing performance can be improved.By integrating several calculation models into the same execution engine in a parallel way，diverse heterogeneous processing modes may be applied.Different hybrid parallel ways can meet different data and calculation characteristics，and meet different parallel objectives as well.This paper introduces the basic ideas of hybrid parallel methods，and describes main implementation mechanisms of hybrid parallelism.

hybrid parallelism；programming model；bulk synchronous parallel（BSP）；MapReduce

TP 391

A

1007-2861（2016）01-0069-12

10.3969/j.issn.1007-2861.2015.04.017

2015-11-19

上海市科委科研計(jì)劃資助項(xiàng)目（15DZ1100305）

支小莉（1974—），女，副研究員，博士，研究方向?yàn)椴⑿杏?jì)算、軟件定義網(wǎng)絡(luò). E-mail:xlzhi@mail.shu.edu.cn