王寧

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

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

王寧

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

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

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

0 引言

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

目前應(yīng)用較為廣泛的并行計(jì)算模型為Jeffrey Dean等提出的MapReduce[2]，MapReduce的基本思想是將所有任務(wù)的執(zhí)行看做兩個操作，分別是Map（映射）和Reduce（化簡），首先，Map會先對由很多獨(dú)立元素組成的邏輯列表中的每一個元素進(jìn)行指定的操作，且原始列表不會被更改，會創(chuàng)建多個新的列表來保存Map的處理結(jié)果。也就意味著，Map操作是高度并行的。當(dāng)Map工作完成之后，系統(tǒng)會接著對新生成的多個列表進(jìn)行清理(Shuffle)和排序，之后，會這些新創(chuàng)建的列表進(jìn)行Reduce操作，也就是對一個列表中的元素根據(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)在于對大數(shù)據(jù)問題的處理很方便，并且系統(tǒng)具有高可擴(kuò)展性，即很容易將新的計(jì)算資源加入已有系統(tǒng)中，Hadoop對用戶隱藏了底層任務(wù)調(diào)度、負(fù)載均衡、網(wǎng)絡(luò)傳輸?shù)燃?xì)節(jié)，使用戶只需專心于MapReduce模塊的制定。

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

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

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

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

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

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

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

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

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

系統(tǒng)整體架構(gòu)如圖1所示，整個框架大體分為TaskSplitter（任務(wù)分割）、Master（主控節(jié)點(diǎn)）和ComputeNode（計(jì)算節(jié)點(diǎn)）三部分。TaskSplitter部分負(fù)責(zé)任務(wù)劃分，本文設(shè)計(jì)了一種腳本語言，用戶使用腳本描述自己的應(yīng)用，TaskSplitter會根據(jù)腳本自動切分任務(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ā)送過來的消息，執(zhí)行具體的計(jì)算任務(wù)，并且對計(jì)算產(chǎn)生的數(shù)據(jù)進(jìn)行存儲。

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

對于并行框架來說，所有的任務(wù)都可以抽象成先從某處取得對輸入數(shù)據(jù)，做一定的處理后輸出新的數(shù)據(jù)，我們很自然而然的用Filter類來表示一次計(jì)算，為了充分利用起計(jì)算資源，使用ComputeNode這樣一個邏輯上的節(jié)點(diǎn)來管理多個Filter，每個ComputeNode本身也是Pipe（這樣設(shè)計(jì)的原因后面再做詳述），Master則做為一個創(chuàng)建Filter、將Filter和Pipe連接起來的角色，Master和ComputeNode在邏輯上是一對多的，在這樣的設(shè)計(jì)下，整個架構(gòu)流程為：首先TaskSplitter劃分得到任務(wù)（與此同時各個ComputeNode節(jié)點(diǎn)會通過線程自動向Master注冊信息以填充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存儲數(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)榇瞬糠謺苯雍陀脩艚换ィ虼丝衫斫庑院涂蓴U(kuò)展性很重要，要盡可能讓用戶方便地去描述多類型的需求，為達(dá)到此目的，本文設(shè)計(jì)了一種簡便的腳本語言，腳本應(yīng)用舉例如下：

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

此腳本解決了2個問題：

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

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

在進(jìn)行解析時，本文使用一個語句池（Statement-Pool）來存放解析得到的單條語句，TaskSplitter不斷從語句池中取得語句去生成新的任務(wù)（Task）并更新與其他任務(wù)間的依賴關(guān)系，生成的任務(wù)被不斷填充到任務(wù)管理器中（TaskManager）。使用語句池的目的在于，避免TaskSplitter解析大量循環(huán)時導(dǎo)致Master阻塞，Master沒有必要等待全部任務(wù)解析完成，任務(wù)解析和任務(wù)分配可以同時進(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變得臃腫，并且各組件可以二次開發(fā)，提高了系統(tǒng)可擴(kuò)展性，用戶甚至可以自行定制各組件以滿足特殊需求。以下對消息機(jī)制、計(jì)算節(jié)點(diǎn)管理、任務(wù)調(diào)度和容錯機(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來做消息緩沖池，收到的消息先壓入消息池，然后每次從中取一條消息進(jìn)行處理，在消息處理方面使用了命令模式，即為每類消息創(chuàng)建一個Handle類，在處理消息時，根據(jù)消息類型由工廠模式[5]創(chuàng)建相應(yīng)的MessageHan dle，調(diào)用execute方法執(zhí)行處理，這樣方便對消息類型進(jìn)行擴(kuò)展。

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

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

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

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

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

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

在進(jìn)行調(diào)度時，Schedule首先從TaskManager和ComputeNodeManager獲取所有可分配的任務(wù)和計(jì)算資源，先對可用計(jì)算節(jié)點(diǎn)分別按CPU和內(nèi)存排序，然后對每一個任務(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ì)列，然后對下一個任務(wù)繼續(xù)如此分配，直到所有待分配任務(wù)分配完成或所有節(jié)點(diǎn)不滿足任何一個任務(wù)的分配，最后下發(fā)消息將待分配隊(duì)列的內(nèi)容分別發(fā)送給各個計(jì)算節(jié)點(diǎn)。

3.4 容錯機(jī)制

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

4 ComputeNode部分

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

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

4.1 數(shù)據(jù)請求

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

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

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

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

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

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

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

5.2 結(jié)果分析

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

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

圖4 景圖拼接流程

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

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

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

6 結(jié)語

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

本文框架目前無法解決Master節(jié)點(diǎn)單點(diǎn)故障，下一步計(jì)劃采用分布式共享存儲系統(tǒng)[9]重新對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àn)橛?jì)算機(jī)圖形學(xué)、并行計(jì)算

2016-10-18

2016-11-30