王寧

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

一種基于集群的通用并行計(jì)算框架設(shè)計(jì)

王寧

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

近年來(lái)各領(lǐng)域應(yīng)用的數(shù)據(jù)量和計(jì)算量需求都大幅增加，傳統(tǒng)單個(gè)計(jì)算設(shè)備往往無(wú)法勝任如此規(guī)模的計(jì)算量，因此越來(lái)越多的領(lǐng)域開(kāi)始嘗試使用并行計(jì)算技術(shù)，分布式并行計(jì)算是進(jìn)行并行計(jì)算的一種主要方式，常見(jiàn)的框架為基于MapReduce的Hadoop。提出一種基于集群的通用并行計(jì)算框架，參考“管道過(guò)濾器”模式，對(duì)三個(gè)模塊“任務(wù)劃分”、“控制器節(jié)點(diǎn)”和“計(jì)算節(jié)點(diǎn)”都進(jìn)行詳細(xì)設(shè)計(jì)描述，相對(duì)于Hadoop，對(duì)有向無(wú)環(huán)圖型任務(wù)由更好支持，并且支持迭代型任務(wù)，另外增加緩存機(jī)制，減少系統(tǒng)耗時(shí)，一定程度支持實(shí)時(shí)性應(yīng)用。

并行計(jì)算；集群；系統(tǒng)框架；有向無(wú)環(huán)圖；緩存

0 引言

并行計(jì)算[1]（Parallel Computing）是指同時(shí)使用多種計(jì)算資源解決計(jì)算問(wèn)題的過(guò)程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。它的基本思想是用多個(gè)處理器來(lái)協(xié)同求解同一問(wèn)題，即將被求解的問(wèn)題分解成若干個(gè)部分，各部分均由一個(gè)獨(dú)立的處理機(jī)來(lái)并行計(jì)算。并行計(jì)算系統(tǒng)既可以是專門設(shè)計(jì)的、含有多個(gè)處理器的超級(jí)計(jì)算機(jī)，也可以是以某種方式互連的若干臺(tái)的獨(dú)立計(jì)算機(jī)構(gòu)成的集群。通過(guò)并行計(jì)算集群完成數(shù)據(jù)的處理。

目前應(yīng)用較為廣泛的并行計(jì)算模型為Jeffrey Dean等提出的MapReduce[2]，MapReduce的基本思想是將所有任務(wù)的執(zhí)行看做兩個(gè)操作，分別是Map（映射）和Reduce（化簡(jiǎn)），首先，Map會(huì)先對(duì)由很多獨(dú)立元素組成的邏輯列表中的每一個(gè)元素進(jìn)行指定的操作，且原始列表不會(huì)被更改，會(huì)創(chuàng)建多個(gè)新的列表來(lái)保存Map的處理結(jié)果。也就意味著，Map操作是高度并行的。當(dāng)Map工作完成之后，系統(tǒng)會(huì)接著對(duì)新生成的多個(gè)列表進(jìn)行清理(Shuffle)和排序，之后，會(huì)這些新創(chuàng)建的列表進(jìn)行Reduce操作，也就是對(duì)一個(gè)列表中的元素根據(jù)Key值進(jìn)行適當(dāng)?shù)暮喜ⅰ?/p>

Hadoop作為最早的基于MapReduce的并行計(jì)算框架之一，目前得到了十分廣泛的使用，其以MapReduce為計(jì)算核心，添加了任務(wù)分配、負(fù)載均衡、網(wǎng)絡(luò)傳輸?shù)饶K。Hadoop的優(yōu)點(diǎn)在于對(duì)大數(shù)據(jù)問(wèn)題的處理很方便，并且系統(tǒng)具有高可擴(kuò)展性，即很容易將新的計(jì)算資源加入已有系統(tǒng)中，Hadoop對(duì)用戶隱藏了底層任務(wù)調(diào)度、負(fù)載均衡、網(wǎng)絡(luò)傳輸?shù)燃?xì)節(jié)，使用戶只需專心于MapReduce模塊的制定。

如果用戶定義了多個(gè)Job，并指定了它們之間的先后關(guān)系，則多個(gè)Job會(huì)依次按照MapReduce的方式進(jìn)行處理，最終用戶需要的結(jié)果就存儲(chǔ)在最后一個(gè)Reduce節(jié)點(diǎn)上，整個(gè)的任務(wù)調(diào)度、網(wǎng)絡(luò)通信、數(shù)據(jù)存儲(chǔ)、負(fù)載平衡等工作都是MapReduce框架底層完成的，不需要用戶關(guān)心。

MapReduce框架的優(yōu)點(diǎn)在于對(duì)大數(shù)據(jù)問(wèn)題處理很方便，并且具有很高的可擴(kuò)展性，即很容易將新的計(jì)算節(jié)點(diǎn)加入到已有的系統(tǒng)中。另外MapReduce和Hadoop也有一些很明顯的缺點(diǎn)：

①所有Reduce任務(wù)必須等前一步的Map任務(wù)全部完成才可以執(zhí)行，這樣會(huì)大大降低可并行度；

②對(duì)DAG（有向無(wú)環(huán)圖）類型的任務(wù)支持不足，Hadoop雖然可以用多個(gè)Job來(lái)模擬出DAG圖，但是Job間的依賴需要開(kāi)發(fā)者分別管理維護(hù)，并且不同層次的任務(wù)不能并行執(zhí)行；

③很難支持迭代類型任務(wù)，迭代類型的任務(wù)通常無(wú)法預(yù)知迭代次數(shù)，所以無(wú)法預(yù)先生成定量的Job；

④MapReduce強(qiáng)制定義了Map和Reduce兩個(gè)階段，但有時(shí)用戶并不需要兩個(gè)階段的處理；

⑤無(wú)法支持實(shí)時(shí)性應(yīng)用，Reduce操作生成的數(shù)據(jù)，會(huì)被HDFS存入硬盤中，由于沒(méi)有相應(yīng)的緩存機(jī)制，所以存儲(chǔ)耗時(shí)導(dǎo)致系統(tǒng)時(shí)延過(guò)高，進(jìn)而無(wú)法支持實(shí)時(shí)性應(yīng)用。

本文提出的基于集群的并行計(jì)算框架在參考了MapReduce模型和Hadoop框架的基礎(chǔ)上，對(duì)于以上5點(diǎn)問(wèn)題均得到了一定程度的解決，下面幾個(gè)小節(jié)將分別對(duì)此框架的整體架構(gòu)和各模塊做相應(yīng)說(shuō)明。

1 整體架構(gòu)描述

系統(tǒng)整體架構(gòu)如圖1所示，整個(gè)框架大體分為TaskSplitter（任務(wù)分割）、Master（主控節(jié)點(diǎn)）和ComputeNode（計(jì)算節(jié)點(diǎn)）三部分。TaskSplitter部分負(fù)責(zé)任務(wù)劃分，本文設(shè)計(jì)了一種腳本語(yǔ)言，用戶使用腳本描述自己的應(yīng)用，TaskSplitter會(huì)根據(jù)腳本自動(dòng)切分任務(wù)，并生成任務(wù)間的依賴關(guān)系，很容易構(gòu)建DAG應(yīng)用，隨后將任務(wù)填充到TaskManager中。Master部分主要負(fù)責(zé)任務(wù)調(diào)度，分別從TaskManager和ComputeNodeManager獲取任務(wù)信息和計(jì)算節(jié)點(diǎn)信息后，再由Schedule負(fù)責(zé)調(diào)度分配，最終Master下發(fā)消息給ComputeNode。ComputeNode部分主要負(fù)責(zé)接收Master發(fā)送過(guò)來(lái)的消息，執(zhí)行具體的計(jì)算任務(wù)，并且對(duì)計(jì)算產(chǎn)生的數(shù)據(jù)進(jìn)行存儲(chǔ)。

整個(gè)架構(gòu)參考了“Pipe-Filter”架構(gòu)模式[4]，”Pipe-Filter”總體思想如圖1所示，將系統(tǒng)看做一系列對(duì)原始數(shù)據(jù)的加工動(dòng)作，首先將原始數(shù)據(jù)經(jīng)過(guò)一次處理（即Filter一次），加工后的數(shù)據(jù)放到管道（Pipe）中，然后等待下一個(gè)Filter繼續(xù)對(duì)數(shù)據(jù)做加工處理，再放到一個(gè)Pipe里，如此持續(xù)進(jìn)行下去直到所有Filter都完成了數(shù)據(jù)加工，那么最終數(shù)據(jù)就保存在最后一個(gè)Pipe里。

對(duì)于并行框架來(lái)說(shuō)，所有的任務(wù)都可以抽象成先從某處取得對(duì)輸入數(shù)據(jù)，做一定的處理后輸出新的數(shù)據(jù)，我們很自然而然的用Filter類來(lái)表示一次計(jì)算，為了充分利用起計(jì)算資源，使用ComputeNode這樣一個(gè)邏輯上的節(jié)點(diǎn)來(lái)管理多個(gè)Filter，每個(gè)ComputeNode本身也是Pipe（這樣設(shè)計(jì)的原因后面再做詳述），Master則做為一個(gè)創(chuàng)建Filter、將Filter和Pipe連接起來(lái)的角色，Master和ComputeNode在邏輯上是一對(duì)多的，在這樣的設(shè)計(jì)下，整個(gè)架構(gòu)流程為：首先TaskSplitter劃分得到任務(wù)（與此同時(shí)各個(gè)ComputeNode節(jié)點(diǎn)會(huì)通過(guò)線程自動(dòng)向Master注冊(cè)信息以填充ComputeNodeManager），然后Master由調(diào)度模塊生成調(diào)度信息（調(diào)度信息包括計(jì)算任務(wù)信息和數(shù)據(jù)Pipe信息），發(fā)送給Com-puteNode，ComputeNode解析這些信息生成相應(yīng)Filter去執(zhí)行計(jì)算任務(wù)，計(jì)算完成后，由Pipe存儲(chǔ)數(shù)據(jù)，然后將任務(wù)完成的消息返回給Master，Master更新相應(yīng)任務(wù)狀態(tài)后繼續(xù)執(zhí)行下一次的任務(wù)調(diào)度，如此往復(fù)直到所有任務(wù)都執(zhí)行完畢。

圖1 系統(tǒng)整體架構(gòu)

圖2 Pipe-Filter

2 TaskSplitter部分

TaskSplitter部分的目的是給用戶提供一種方式（接口、腳本等）用以描述用戶的應(yīng)用需求，根據(jù)用戶的描述進(jìn)行分析，生成任務(wù)為后面的調(diào)度做好準(zhǔn)備。因?yàn)榇瞬糠謺?huì)直接和用戶交互，因此可理解性和可擴(kuò)展性很重要，要盡可能讓用戶方便地去描述多類型的需求，為達(dá)到此目的，本文設(shè)計(jì)了一種簡(jiǎn)便的腳本語(yǔ)言，腳本應(yīng)用舉例如下：

以上所示是一個(gè)對(duì)圖片序列進(jìn)行特征檢測(cè)的應(yīng)用，腳本共包含四部分，INPUT：預(yù)定義一些變量，用以協(xié)助控制任務(wù)流程，支持INT、STR、BOOL、DOUBLE類型；KERNEL：預(yù)聲明計(jì)算處理功能，對(duì)應(yīng)Filter的種類，用來(lái)創(chuàng)建不同F(xiàn)ilter，CPU和MEMORY表示任務(wù)代價(jià)（1 CPU表示5%，1 MEMPRY表示100M）；DATA：預(yù)定義變量，可以是數(shù)組；PROCEDURE：描述應(yīng)用流程，整個(gè)應(yīng)用是從上到下串行處理的，對(duì)于同一層次可并行任務(wù)，使用FOR或WHILE循環(huán)來(lái)描述。根據(jù)此腳本，TaskSplitter會(huì)自動(dòng)生成任務(wù)并設(shè)置好它們之間的依賴關(guān)系。

此腳本解決了2個(gè)問(wèn)題：

①描述DAG任務(wù)很方便，用戶只需按照實(shí)際應(yīng)用思路編寫PROCEDURE，系統(tǒng)會(huì)自動(dòng)生成滿足依賴關(guān)系的任務(wù)列表，并且不同層次的子任務(wù)只要沒(méi)有前置依賴項(xiàng)便可以并行執(zhí)行；

②支持迭代式任務(wù)，用戶使用BOOL類型變量和WHILE循環(huán)便可以描述迭代式任務(wù)，BOOL變量的值可以在用戶自定義的Filter中更改。

在進(jìn)行解析時(shí)，本文使用一個(gè)語(yǔ)句池（Statement-Pool）來(lái)存放解析得到的單條語(yǔ)句，TaskSplitter不斷從語(yǔ)句池中取得語(yǔ)句去生成新的任務(wù)（Task）并更新與其他任務(wù)間的依賴關(guān)系，生成的任務(wù)被不斷填充到任務(wù)管理器中（TaskManager）。使用語(yǔ)句池的目的在于，避免TaskSplitter解析大量循環(huán)時(shí)導(dǎo)致Master阻塞，Master沒(méi)有必要等待全部任務(wù)解析完成，任務(wù)解析和任務(wù)分配可以同時(shí)進(jìn)行。

3 Master部分

Master負(fù)責(zé)任務(wù)管理、任務(wù)調(diào)度、計(jì)算節(jié)點(diǎn)管理等工作。Master的設(shè)計(jì)使用了組合模式，任務(wù)管理功能由TaskManager完成，計(jì)算節(jié)點(diǎn)管理由ComputeNodeManager完成，任務(wù)調(diào)度由Schedule完成，而Master本身只負(fù)責(zé)協(xié)調(diào)各方工作，這樣可以避免Master變得臃腫，并且各組件可以二次開(kāi)發(fā)，提高了系統(tǒng)可擴(kuò)展性，用戶甚至可以自行定制各組件以滿足特殊需求。以下對(duì)消息機(jī)制、計(jì)算節(jié)點(diǎn)管理、任務(wù)調(diào)度和容錯(cuò)機(jī)制做進(jìn)一步的介紹。

3.1 消息機(jī)制

網(wǎng)絡(luò)中所有傳輸?shù)臄?shù)據(jù)都以Packet為基類，由Packet派生得到Message類，作為各種消息的基類，這些消息按照Master To ComputeNode、ComputeNode To Master和ComputeNode To ComputeNode分類如圖3所示：

圖3 消息類型

Master和ComputeNode均使用MessagePool來(lái)做消息緩沖池，收到的消息先壓入消息池，然后每次從中取一條消息進(jìn)行處理，在消息處理方面使用了命令模式，即為每類消息創(chuàng)建一個(gè)Handle類，在處理消息時(shí)，根據(jù)消息類型由工廠模式[5]創(chuàng)建相應(yīng)的MessageHan dle，調(diào)用execute方法執(zhí)行處理，這樣方便對(duì)消息類型進(jìn)行擴(kuò)展。

3.2 計(jì)算節(jié)點(diǎn)管理

要對(duì)計(jì)算節(jié)點(diǎn)（ComputeNode）進(jìn)行管理，首先要獲得計(jì)算節(jié)點(diǎn)的信息，而計(jì)算節(jié)點(diǎn)信息的獲取又分為兩個(gè)階段，第一個(gè)階段是初始化，當(dāng)一個(gè)計(jì)算節(jié)點(diǎn)啟動(dòng)時(shí)，會(huì)自動(dòng)開(kāi)啟一個(gè)線程，向配置文件里配置的Master的IP和PORT發(fā)送注冊(cè)請(qǐng)求，Master收到注冊(cè)請(qǐng)求后便將此節(jié)點(diǎn)信息添加到ComputeNodeManager中，計(jì)算節(jié)點(diǎn)只有當(dāng)收到Master的SimpleMessage::RegisterConfirmed消息后，才會(huì)停止注冊(cè)請(qǐng)求；第二個(gè)階段是更新信息，當(dāng)注冊(cè)成功后，計(jì)算節(jié)點(diǎn)會(huì)開(kāi)啟一個(gè)Keep-Alive線程，每隔固定時(shí)間K便向Master發(fā)送NodeStatusMessage消息更新ComputeNodeManager中相應(yīng)的計(jì)算節(jié)點(diǎn)信息，需注意K設(shè)置的太大會(huì)使任務(wù)調(diào)度時(shí)信息不準(zhǔn)確，K設(shè)置過(guò)小又會(huì)使得此線程開(kāi)銷過(guò)大影響系統(tǒng)效率。

3.3 任務(wù)調(diào)度

任務(wù)調(diào)度有三個(gè)關(guān)鍵問(wèn)題，分別是調(diào)度對(duì)象，調(diào)度時(shí)機(jī)和調(diào)度策略。

對(duì)于本系統(tǒng)，調(diào)度對(duì)象指的是任務(wù)和計(jì)算節(jié)點(diǎn)，根據(jù)前面的描述，我們知道當(dāng)執(zhí)行任務(wù)調(diào)度時(shí)，TaskManger和ComputeNodeManager中已有了用來(lái)調(diào)度的任務(wù)和計(jì)算資源。

調(diào)度時(shí)機(jī)有兩個(gè)，首先當(dāng)有新的計(jì)算節(jié)點(diǎn)注冊(cè)時(shí)，在執(zhí)行完注冊(cè)相關(guān)操作后會(huì)進(jìn)行任務(wù)調(diào)度，其次當(dāng)Master收到TaskStatusMessage后，會(huì)接著進(jìn)行一次任務(wù)調(diào)度，因?yàn)門ask的執(zhí)行狀態(tài)只有兩種，分部是成功和失敗，執(zhí)行成功意味著有計(jì)算資源處于空閑，可以進(jìn)行新的任務(wù)分配，而執(zhí)行失敗表示有空閑的任務(wù)可被調(diào)度。

在進(jìn)行調(diào)度時(shí)，Schedule首先從TaskManager和ComputeNodeManager獲取所有可分配的任務(wù)和計(jì)算資源，先對(duì)可用計(jì)算節(jié)點(diǎn)分別按CPU和內(nèi)存排序，然后對(duì)每一個(gè)任務(wù)，若CPU權(quán)值＞=內(nèi)存權(quán)值，則優(yōu)先選CPU最大的節(jié)點(diǎn)分配此任務(wù)，否則優(yōu)先按內(nèi)存大小尋找節(jié)點(diǎn)，然后此節(jié)點(diǎn)減去消耗值，將此任務(wù)加入此節(jié)點(diǎn)的待分配隊(duì)列，然后對(duì)下一個(gè)任務(wù)繼續(xù)如此分配，直到所有待分配任務(wù)分配完成或所有節(jié)點(diǎn)不滿足任何一個(gè)任務(wù)的分配，最后下發(fā)消息將待分配隊(duì)列的內(nèi)容分別發(fā)送給各個(gè)計(jì)算節(jié)點(diǎn)。

3.4 容錯(cuò)機(jī)制

容錯(cuò)機(jī)制指的是當(dāng)計(jì)算任務(wù)出現(xiàn)問(wèn)題，或者計(jì)算節(jié)點(diǎn)出現(xiàn)問(wèn)題時(shí)整個(gè)系統(tǒng)的應(yīng)對(duì)機(jī)制。首先當(dāng)任務(wù)執(zhí)行錯(cuò)誤時(shí)，會(huì)由ComputeNode主動(dòng)向Master報(bào)告此錯(cuò)誤，然后Master會(huì)回滾此任務(wù)狀態(tài)重新分配執(zhí)行；而當(dāng)計(jì)算節(jié)點(diǎn)因?yàn)閿嚯姟C(jī)械故障等原因無(wú)法和整個(gè)系統(tǒng)通信時(shí)，Master若超過(guò)3個(gè)Keep-Alive線程周期都沒(méi)有收到某ComputeNode的節(jié)點(diǎn)狀態(tài)信息，則認(rèn)為此節(jié)點(diǎn)故障，此時(shí)Master會(huì)先檢查任務(wù)列表，查看此節(jié)點(diǎn)上哪些已完成任務(wù)還有后置任務(wù)（即有其余的尚未完成的任務(wù)依賴于此節(jié)點(diǎn)上已完成的任務(wù)），將這些任務(wù)和上一次分配分配給此節(jié)點(diǎn)的任務(wù)一起重新調(diào)度執(zhí)行，這樣便可使得整個(gè)系統(tǒng)的任務(wù)依賴和數(shù)據(jù)依賴重新修復(fù)，但會(huì)因?yàn)槿蝿?wù)重做造成一定的時(shí)間損耗。

4 ComputeNode部分

ComputeNode部分主要是完成Master分配的計(jì)算任務(wù)，任務(wù)完成或失敗后返回消息給Master，并且通過(guò)Pipe對(duì)計(jì)算得到的數(shù)據(jù)進(jìn)行存儲(chǔ)，接收到其他節(jié)點(diǎn)的數(shù)據(jù)請(qǐng)求時(shí)發(fā)送數(shù)據(jù)給對(duì)方。此部分的消息處理機(jī)制

和Master部分是一樣的。當(dāng)收到Master發(fā)來(lái)的Filter-Message時(shí)，便對(duì)任務(wù)隊(duì)列的每一個(gè)任務(wù)單獨(dú)開(kāi)啟一個(gè)線程，由工廠創(chuàng)建對(duì)應(yīng)的Filter執(zhí)行計(jì)算任務(wù)（如果所需數(shù)據(jù)不在本地，需要進(jìn)行數(shù)據(jù)請(qǐng)求），執(zhí)行完成后，通過(guò)Pipe進(jìn)行數(shù)據(jù)存儲(chǔ)。下面對(duì)數(shù)據(jù)存儲(chǔ)和請(qǐng)求數(shù)據(jù)兩部分做進(jìn)一步說(shuō)明。

4.1 數(shù)據(jù)請(qǐng)求

FilterMessage消息攜帶了每個(gè)任務(wù)所需數(shù)據(jù)存放的節(jié)點(diǎn)IP、名稱等信息，當(dāng)Filter執(zhí)行時(shí)，對(duì)每一個(gè)所需參數(shù)先檢查數(shù)據(jù)IP是否和本地IP一致，若一致則檢查下一個(gè)，若不一致則向此IP發(fā)送數(shù)據(jù)請(qǐng)求消息（RequsetDataMessage），目的ComputeNode接收此消息后，通過(guò)Pipe查找到數(shù)據(jù)，發(fā)送給請(qǐng)求方的PipePool（使用Pool是為了避免多個(gè)數(shù)據(jù)傳輸阻塞），請(qǐng)求方獲取到數(shù)據(jù)后，再對(duì)下一個(gè)參數(shù)做同樣檢查或請(qǐng)求，直到所有參數(shù)都準(zhǔn)備就緒，便開(kāi)始執(zhí)行計(jì)算。

4.2 數(shù)據(jù)存儲(chǔ)

當(dāng)Filter執(zhí)行完計(jì)算任務(wù)后，需要通過(guò)Pipe將數(shù)據(jù)存儲(chǔ)下來(lái)，Pipe本身不執(zhí)行存儲(chǔ)操作，它只負(fù)責(zé)對(duì)數(shù)據(jù)名稱、路徑等信息做記錄，真正的存儲(chǔ)操作交給更底層的Storage處理，本文在設(shè)計(jì)Storage時(shí)使用了緩存技術(shù)，即以一定大小的內(nèi)存來(lái)緩存數(shù)據(jù)對(duì)象，避免寫到硬盤帶來(lái)的序列化和逆序列化時(shí)間消耗，使用的內(nèi)存大小由配置文件進(jìn)行設(shè)置。內(nèi)存緩存策略為：新生成的數(shù)據(jù)會(huì)優(yōu)先存到內(nèi)存中，如果可用內(nèi)存超過(guò)了閾值的話，就將一部分?jǐn)?shù)據(jù)置換到硬盤上，置換算法使用LRU[6]算法，即存儲(chǔ)中的每個(gè)數(shù)據(jù)對(duì)應(yīng)一個(gè)int，剛存入時(shí)置為0，每次存儲(chǔ)新數(shù)據(jù)時(shí)，以前的都加1，被訪問(wèn)的數(shù)據(jù)重新置0，這樣當(dāng)置換時(shí)，優(yōu)先置換int值最大的數(shù)據(jù)。緩存技術(shù)加上底層Infiniband高速網(wǎng)絡(luò)[7-8]使得本文并框架對(duì)實(shí)時(shí)性應(yīng)用也有很好的支持。

5 實(shí)驗(yàn)結(jié)果

本文通過(guò)一個(gè)實(shí)際的應(yīng)用來(lái)驗(yàn)證并行計(jì)算框架的實(shí)用性和有效性，選取的應(yīng)用是“全景圖拼接”[9]，其處理流程如圖4所示，包含多個(gè)步驟，該應(yīng)用是一個(gè)典型的DAG型應(yīng)用，如圖5所示，有的步驟可以切分成多個(gè)子任務(wù)，有的步驟又需要全局的數(shù)據(jù)，各步驟之間的任務(wù)存在較復(fù)雜的依賴關(guān)系，可以全面地檢驗(yàn)本文并行系統(tǒng)的有效性。

5.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)環(huán)境中，每臺(tái)計(jì)算機(jī)配置相同，配置均為：處理器：Intel Xeon CPU E3-1230 v3@3.30GHz四核；內(nèi)存：16.0GB；操作系統(tǒng)：Windows 7(64位)。

5.2 結(jié)果分析

為了證明本文并行計(jì)算框架的有效性，分別對(duì)不同計(jì)算節(jié)點(diǎn)數(shù)量、不同規(guī)模輸入數(shù)據(jù)情況下的計(jì)算耗時(shí)做測(cè)試，各情況下耗時(shí)如表1所示。

可以看出，在數(shù)據(jù)量較小時(shí)，任務(wù)并行計(jì)算帶來(lái)的效率提升被數(shù)據(jù)傳輸?shù)膿p耗所抵消，在2臺(tái)計(jì)算節(jié)點(diǎn)、108張輸入圖片的情況下，多機(jī)并行的執(zhí)行速度已經(jīng)超過(guò)了單機(jī)串行的速度，并且隨著計(jì)算節(jié)點(diǎn)、輸入數(shù)據(jù)規(guī)模的增大，效率提升越來(lái)越明顯。當(dāng)計(jì)算節(jié)點(diǎn)為4個(gè)，輸入圖像數(shù)量為288張時(shí)，并行框架效率比串行時(shí)高了一倍。

圖4 景圖拼接流程

圖5 全景圖拼接子任務(wù)依賴

表1 不同輸入圖像（張）和不同計(jì)算節(jié)點(diǎn)（個(gè)）下運(yùn)算耗時(shí)

通過(guò)此實(shí)驗(yàn)可以驗(yàn)證本文并行框架的有效性，但是效率提升并未達(dá)到1:1（即效率提升倍數(shù)等于同等配置計(jì)算節(jié)點(diǎn)個(gè)數(shù)），分析其原因主要有以下3點(diǎn)：（1）并行框架底層的消息傳輸、數(shù)據(jù)傳輸以及任務(wù)分配算法都會(huì)有一定耗時(shí)；（2）對(duì)于DAG型應(yīng)用，各任務(wù)間有依賴，有時(shí)需要等待任務(wù)同步；（3）全景圖拼接應(yīng)用中有一些“瓶頸”任務(wù)（例如相機(jī)標(biāo)定），這類任務(wù)依賴于上一步的所有數(shù)據(jù)，因此無(wú)法進(jìn)行并行。

6 結(jié)語(yǔ)

本文提出一種基于集群的通用并行計(jì)算框架，參考“管道過(guò)濾器”模型，由TaskSplitter解析自定義的任務(wù)描述腳本，自動(dòng)劃分子任務(wù)和生成依賴關(guān)系，由Master進(jìn)行計(jì)算資源管理和任務(wù)調(diào)度，由ComputeNode完成任務(wù)計(jì)算和數(shù)據(jù)存儲(chǔ)?？蚣苤С秩魏蜠AG型應(yīng)用，并且支持迭代式應(yīng)用和實(shí)時(shí)性應(yīng)用，另外對(duì)于ComputeNode具有一定程度容錯(cuò)備災(zāi)能力。

本文框架目前無(wú)法解決Master節(jié)點(diǎn)單點(diǎn)故障，下一步計(jì)劃采用分布式共享存儲(chǔ)系統(tǒng)[9]重新對(duì)Master信息和計(jì)算數(shù)據(jù)做冗余備災(zāi)。

[1]王磊.并行計(jì)算技術(shù)綜述[J].信息技術(shù),2012,10.

[2]J.Dean,S.Ghemawat.MapReduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM-50th Anniversary Issue:1958-2008.2008.51(1):107-113.

[3]T.White.Hadoop:The Definitive Guide,Third Edtion[M].United States of America.O'Reilly Media,Inc.2012:3-12.

[4]V.Ambriola.G.Tortora.Advances in Software Engineering and Knowledge Engineering[M].Farrer Road,Singapore 9128.World Scientific Publishing Co.Pte.Ltd.1993:95-109.

[5]W.Pree.Design Patterns For Object-Oriented Software Development[M].Wokingham,England.Computing Machines(ACM)and Addison-Wesley Publishing Company，1994

[6]E.J.O'Neil,P.E.O'Neil and G.Weikum.The LRU-K Page Replacement Algorithm for Database Disk Buffering.Proc.of the 1993 ACM SIGMOD International Conference on Management of Data,pp.297-306.

[7][2]Pentakalos O I.An Introduction to the InfiniBand Architecture[M].High Performance Mass Storage and Parallel I/O:Technologies and Applications.Wiley-IEEE Press,2002:616.

[8][4]Vivek D.Deshmukh.InfiniBand:A New Era in Networkint[C].Proceedings of National Conference on Innovative Paradigms in Engineering&Technology.New York,USA:Foundation of Computer Science,2012.

[9][8]Pandey A,Pati U C.Panoramic Image Mosaicing:An Optimized Graph-Cut Approach[M].Proceedings of 3rd International Conference on Advanced Computing,Networking and Informatics.Springer India,2016:299.

[10]K.Shvachko,H.Kuang,S.Radia,R.Chansler.The Hadoop Distributed File System[J].Mass Storage Systems and Technologies (MSST),2010 IEEE 26th Symposium on.IEEE,2010：1-10.

Design of a General Parallel Computing Framework Based on Cluster

WANG Ning

（College of Computer Science,Sichuan University，Chengdu 610065）

In recent years,the amount of data and computation requirements in various fields has increased significantly.Traditional single computing devices are often incapable of performing such computational tasks.More and more fields are beginning to use parallel computing. Distributed computation is one of the main parallel computing methods,Hadoop is a most common framework based on Map-Reduce in distributed computation.Proposes a general parallel computing framework based on cluster.Describes the"task splitter","master node" and"computing node"in details with reference to"pipeline filter"mode.Compared with Hadoop,directed acyclic graph task is better supported,iteration task is supported.In addition,caching mechanism is added to reduce system time-consuming and support real-time application to a certain extent.

Parallel Computing;Cluster;System Framework;DAG;Cache

1007-1423（2016）35-0020-07

10.3969/j.issn.1007-1423.2016.35.004

王寧（1992-），男，陜西咸陽(yáng)人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、并行計(jì)算

2016-10-18

2016-11-30