李 凌

（淮北職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)系，安徽 淮北 235000）

日益復(fù)雜的科學(xué)計(jì)算、多媒體、虛擬化等應(yīng)用領(lǐng)域要求強(qiáng)大的計(jì)算能力，并行計(jì)算可以快速解決復(fù)雜的計(jì)算問題，同時(shí)使用多種資源，克服單個(gè)計(jì)算機(jī)上存在的存儲(chǔ)器限制，降低問題的求解時(shí)間，增加問題求解規(guī)模，提高問題求解精度、吞吐率和可用性［1］。并行計(jì)算主要有任務(wù)并行和數(shù)據(jù)并行兩種，任務(wù)并行依據(jù)求解過程，把任務(wù)切片分解成若干子任務(wù)，［2］旨在提高CPU的利用率。隨著CPU核心數(shù)的不斷增加，計(jì)算機(jī)的計(jì)算能力得到極大提高，從云計(jì)算到網(wǎng)格計(jì)算，再到桌面計(jì)算機(jī)系統(tǒng)中各種線程池技術(shù)，軟件開發(fā)需要大步提高以適應(yīng)計(jì)算機(jī)系統(tǒng)的發(fā)展，并行任務(wù)軟件設(shè)計(jì)已經(jīng)成為一個(gè)熱點(diǎn)。

一、相關(guān)概念

（一）并行任務(wù)

一個(gè)并行任務(wù)可以抽象為一個(gè)有向無環(huán)圖，用四元組表示［3］，記為 DAG＝（V，E，W，D），其中：V＝｛v1，v2…vn｝表示子任務(wù)的集合，vi∈V；E＝｛e1，e2…em｝，E∈V×V，表示有向邊的集合，ek＝（vm，vn）∈E，表示子任務(wù)vm和vn依賴關(guān)系，只有當(dāng)vm執(zhí)行完成后，vn才能執(zhí)行；W＝｛w1，w2…wn｝，任務(wù)負(fù)載向量集合；D＝（dij）m×n，其中dij表示子任務(wù)vi和vj的數(shù)據(jù)通信量。并行任務(wù)的DAG圖如圖1所示。圖1是包含10個(gè)節(jié)點(diǎn)的并行計(jì)算任務(wù)圖，圓圈內(nèi)的vi表示節(jié)點(diǎn)的編號(hào)，圓圈旁邊的數(shù)字是任務(wù)節(jié)點(diǎn)的計(jì)算機(jī)量，有向邊旁的數(shù)字是任務(wù)間的數(shù)據(jù)通信量。

圖1 并行任務(wù)DAG圖

（二）任務(wù)間的依賴關(guān)系

程序的各個(gè)部分之間總是存在一定的依賴關(guān)系［4］，在不破壞依賴關(guān)系的前提下，把程序分解成多個(gè)任務(wù)并行執(zhí)行，進(jìn)而縮短整個(gè)程序的運(yùn)行時(shí)間，這就是并行處理。任務(wù)之間的依賴關(guān)系主要有數(shù)據(jù)依賴和控制依賴［5］。

1.數(shù)據(jù)依賴關(guān)系

運(yùn)行的多個(gè)任務(wù)同時(shí)訪問相同的數(shù)據(jù)，即為數(shù)據(jù)依賴，數(shù)據(jù)依賴的形式化定義如下：

已知任務(wù)S和T，若存在數(shù)據(jù)X滿足如下條件之一，則稱任務(wù)T數(shù)據(jù)依賴任務(wù)S，記為SδT，否則任務(wù)S和T不存在依賴關(guān)系。

（1）任務(wù)T使用由S計(jì)算出的X，且同時(shí)x∈OUT（s）∧x∈IN（T），則稱T依賴S，記作：SδfT（WAR）

（2）S使用的X先于T對(duì)X的定值，且x∈IN（s）∧x∈OUT（T），則稱 T反依賴于S，記為：SδaT（WAR）

（3）S對(duì)X的定值先于 T對(duì)X的定值，且x∈OUT（s）∧x∈OUT（T），則稱 T輸出依賴于S，記為：Sδ0T（WAR）

2.控制依賴關(guān)系

依賴關(guān)系是由程序流程引起的，若一個(gè)任務(wù)是否執(zhí)行取決于其他任務(wù)執(zhí)行的結(jié)果，稱這種任務(wù)之間的依賴關(guān)系為控制依賴。對(duì)于有控制依賴的任務(wù)，在實(shí)際使用中應(yīng)提供預(yù)測(cè)方法，一旦預(yù)測(cè)失誤，則必須實(shí)現(xiàn)任務(wù)回滾機(jī)制?？刂埔蕾嚨男问交x如下：

已知任務(wù)S和T，T控制依賴S，當(dāng)且僅當(dāng)：

（1）S和T之間存在一條路徑；

（2）存在一條路徑S到程序結(jié)束但是不經(jīng)過T。

數(shù)據(jù)依賴由讀、寫同一數(shù)據(jù)引起，控制依賴導(dǎo)致程序流程的變化，數(shù)據(jù)依賴是影響程序并行化的主要因素［4］，本文所說的依賴關(guān)系是指數(shù)據(jù)依賴關(guān)系。如何能夠在確保依賴關(guān)系穩(wěn)定的情況下最快地計(jì)算出最終結(jié)果，是現(xiàn)代計(jì)算機(jī)軟件技術(shù)發(fā)展的重要趨勢(shì)。本文設(shè)計(jì)了一種并行框架，可以并行化處理任務(wù)，充分利用計(jì)算機(jī)硬件資源，實(shí)驗(yàn)表明可以有效提高并行任務(wù)的并行度，提高軟件的性能。

二、軟件框架

軟件框架通常采用分層設(shè)計(jì)，每一層實(shí)現(xiàn)不同的功能，下層為上層提供健壯穩(wěn)定的服務(wù)。在支持依賴關(guān)系的并行任務(wù)軟件框架中，需要解決如下問題：

1）完成任務(wù)的執(zhí)行；2）確保依賴關(guān)系中后續(xù)任務(wù)必須在前置任務(wù)之后執(zhí)行；3）充分利用計(jì)算機(jī)系統(tǒng)資源，在最短時(shí)間內(nèi)完成運(yùn)算，提高軟件性能的可伸縮性。

假定有相互依賴關(guān)系的任務(wù)需要運(yùn)算的對(duì)象為一大塊（chunk）可切分的數(shù)據(jù)，本軟件框架將解決如何在最短的時(shí)間內(nèi)完成整個(gè)運(yùn)算。整個(gè)軟件框架分為任務(wù)分發(fā)和線程執(zhí)行兩層，如圖2所示，線程執(zhí)行層為任務(wù)分發(fā)層提供任務(wù)執(zhí)行的服務(wù)，借鑒操作系統(tǒng)中的多線程庫(kù)（.NET task庫(kù)）提供線程能力。

圖2 軟件框架圖

（一）任務(wù)分發(fā)層（Dispatching Layer）

相互依賴的任務(wù)在任務(wù)分發(fā)層基于數(shù)據(jù)驅(qū)動(dòng)被切分為相互無關(guān)的任務(wù)，每個(gè)運(yùn)行于此數(shù)據(jù)段上的任務(wù)定義為子任務(wù)，基于任務(wù)之間的相互依賴關(guān)系，按照順序生成子任務(wù)，把他們分發(fā)到線程執(zhí)行層，執(zhí)行子任務(wù)，每個(gè)子任務(wù)在生成時(shí)都是可運(yùn)行的。公共大塊數(shù)據(jù)被切分為若干個(gè)數(shù)據(jù)段（Segment），如圖3所示，當(dāng)前置任務(wù)完成處理一個(gè)數(shù)據(jù)段之后，相應(yīng)的后續(xù)任務(wù)才可以處理該數(shù)據(jù)段。

圖3 塊數(shù)據(jù)切分圖

1.模塊劃分

任務(wù)分發(fā)層主要有依賴關(guān)系圖（Topology）、段切分（Partition）和分發(fā)器（Task Dispatcher）三個(gè)模塊構(gòu)成，如圖4所示：

圖4 任務(wù)分發(fā)模塊圖

（1）依賴關(guān)系圖模塊。依賴關(guān)系圖模塊維護(hù)任務(wù)之間的相互關(guān)系，并在整個(gè)運(yùn)算過程中維護(hù)并更新無前置任務(wù)或前置任務(wù)已經(jīng)完成的任務(wù)列表。依賴關(guān)系圖模塊提供擴(kuò)展接口，當(dāng)任務(wù)之間的關(guān)系同時(shí)依賴于任務(wù)運(yùn)算的部分結(jié)果時(shí)，通過擴(kuò)展接口，依賴關(guān)系圖模塊可以維護(hù)運(yùn)算過程中動(dòng)態(tài)改變的任務(wù)關(guān)系。當(dāng)一個(gè)任務(wù)的依賴關(guān)系被改變時(shí)，該任務(wù)所有的后置任務(wù)在相同的數(shù)據(jù)段上也應(yīng)當(dāng)重新配置依賴關(guān)系。這種改變是通過數(shù)據(jù)驅(qū)動(dòng)的異步通知進(jìn)行的。只有當(dāng)后置模塊運(yùn)算到前置任務(wù)關(guān)系改變的數(shù)據(jù)段時(shí)，才會(huì)得到該異步通知。

（2）段切分模塊。段切分模塊基于具體任務(wù)的依賴關(guān)系，首先計(jì)算出該任務(wù)可以運(yùn)行的所有數(shù)據(jù)段區(qū)間，然后根據(jù)不同的算法為該任務(wù)動(dòng)態(tài)生成可運(yùn)行的子任務(wù)。為了提高運(yùn)算性能，算法中可以為輕量級(jí)任務(wù)生成大數(shù)據(jù)段，為重量級(jí)任務(wù)生成小數(shù)據(jù)段，以達(dá)到負(fù)載平衡的目的，或者為重量級(jí)任務(wù)生成多個(gè)子任務(wù)，提高并行度。

在段切分模塊中，為了提高性能，采用一種依賴控制算法來計(jì)算一個(gè)任務(wù)的所有可運(yùn)行數(shù)據(jù)段區(qū)間。假設(shè)依賴關(guān)系如圖5所示：

圖5 依賴關(guān)系圖

任務(wù)T1已經(jīng)完成數(shù)據(jù)段［1，4］［6，9］上的運(yùn)算，任務(wù)T2已經(jīng)完成數(shù)據(jù)段［2，4］和［5，8］上的運(yùn)算。該依賴控制算法首先為來自于任務(wù)T1和T2的每個(gè)數(shù)據(jù)段的開始位置定義權(quán)值1，為每個(gè)數(shù)據(jù)段的結(jié)束位置定義權(quán)值－1。并對(duì)所有的開始和結(jié)束位置統(tǒng)一進(jìn)行排序。然后從所有數(shù)據(jù)運(yùn)算的開始位置向結(jié)束位置累積權(quán)值，最終得到權(quán)值如表1所示：

表1 權(quán)值表

在累積權(quán)值中，若某個(gè)數(shù)值等于該任務(wù)T3的所有依賴任務(wù)個(gè)數(shù)，那么相對(duì)應(yīng)的位置即為可運(yùn)行數(shù)據(jù)段的開始位置。從表中可以看到，任務(wù)T3的可運(yùn)行數(shù)據(jù)段有［2，4］和［6，8］。

該依賴控制算法的前置條件是：同一個(gè)任務(wù)的所有數(shù)據(jù)段不允許有相互重疊的部分。因此，如果在切分模塊中使用了重試策略，即如果一個(gè)數(shù)據(jù)段運(yùn)算失敗，那么該數(shù)據(jù)庫(kù)會(huì)重新嘗試第二次運(yùn)行時(shí)，在應(yīng)用依賴控制算法之前，需要對(duì)數(shù)據(jù)段記錄進(jìn)行預(yù)處理，去除重疊的部分。段切分模塊同樣支持算法擴(kuò)展，如：控制所有子任務(wù)在固定時(shí)間內(nèi)完成，以實(shí)現(xiàn)負(fù)載均衡；或者為重量級(jí)任務(wù)生成多個(gè)子任務(wù)實(shí)例以提高并發(fā)度。

（3）分發(fā)器模塊。分發(fā)器模塊負(fù)責(zé)分發(fā)子任務(wù)。首先，它從依賴關(guān)系圖模塊中獲取無依賴關(guān)系的任務(wù)，委派段切分模塊生成子任務(wù)，然后把子任務(wù)分發(fā)執(zhí)行，并監(jiān)聽執(zhí)行的結(jié)果；在子任務(wù)完成后對(duì)相關(guān)的任務(wù)更新狀態(tài)，分發(fā)對(duì)應(yīng)的后續(xù)任務(wù)，直至最終所有的任務(wù)結(jié)束。該模塊實(shí)現(xiàn)進(jìn)度的管理，并可根據(jù)需要，按照優(yōu)先級(jí)分發(fā)不同的任務(wù)。表2列出了在分發(fā)器中可能的算法實(shí)現(xiàn)，針對(duì)不同的需求，在分發(fā)器中可以采用不同的分發(fā)算法。

表2 分發(fā)器算法比較

2.工作流程

分發(fā)器從依賴關(guān)系圖模塊中獲取無依賴關(guān)系的任務(wù)，段切分模塊為這些可執(zhí)行的任務(wù)生成子任務(wù)；分發(fā)器把這些子任務(wù)依據(jù)優(yōu)先級(jí)分發(fā)到線程執(zhí)行層，并監(jiān)聽子任務(wù)結(jié)束事件；當(dāng)子任務(wù)完成后，分發(fā)器收到通知；分發(fā)器把子任務(wù)的運(yùn)行結(jié)果通知給相應(yīng)的任務(wù)以及該任務(wù)的后續(xù)任務(wù)。

圖6給出了在任務(wù)分發(fā)層中任務(wù)分發(fā)的簡(jiǎn)要流程：

圖6 任務(wù)分發(fā)流程圖

在運(yùn)算過程中，對(duì)數(shù)據(jù)段的讀寫涉及大量的I／O操作，為了提高性能，在框架中運(yùn)用了任務(wù)優(yōu)化的方式。一個(gè)任務(wù)通常由讀取數(shù)據(jù)段、數(shù)據(jù)運(yùn)算和寫數(shù)據(jù)段三個(gè)步驟組成。優(yōu)化后把每個(gè)步驟作為一個(gè)任務(wù)，一個(gè)常規(guī)任務(wù)被優(yōu)化為有依賴關(guān)系的三個(gè)任務(wù)，并在讀取數(shù)據(jù)段和寫數(shù)據(jù)段任務(wù)中采用異步I／O算法提高任務(wù)的并行度。

（二）線程執(zhí)行層

線程執(zhí)行層實(shí)現(xiàn)了計(jì)算機(jī)系統(tǒng)線程池的接口管理。作為任務(wù)分發(fā)層和系統(tǒng)線程池之間的中介，該層抽象了子任務(wù)的執(zhí)行接口，因此在總體框架實(shí)現(xiàn)之后能夠很容易的替換具體的線程池技術(shù)，當(dāng)新技術(shù)出現(xiàn)時(shí)，采用更合適的新技術(shù)替換現(xiàn)有軟件中的技術(shù)債務(wù)，獲取新技術(shù)帶來的好處。

三、原型測(cè)試

基于以上并行框架，本文實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的原型。該原型使用配置文件來自定義任務(wù)的類型及具體算法，在段切分模塊中未使用任何優(yōu)化算法，在分發(fā)器中采用前置任務(wù)優(yōu)先的分發(fā)算法。在原型測(cè)試中，本文使用了Visual Studio中的分析工具，分析運(yùn)算消耗的時(shí)間和CPU的使用率。任務(wù)的相互依賴關(guān)系如圖7所示：

圖7 任務(wù)的相互依賴關(guān)系圖

（一）理想狀態(tài)下的負(fù)載測(cè)試

在理想狀態(tài)下，任務(wù)中沒有I／O操作且任務(wù)之間負(fù)載均衡，在一臺(tái)虛擬8核的計(jì)算機(jī)上，所有核都在滿負(fù)荷運(yùn)算，任務(wù)的并行度被調(diào)度到了最高。

（二）數(shù)據(jù)量測(cè)試

本文測(cè)試了在運(yùn)算不同數(shù)據(jù)量時(shí)，并行框架所消耗時(shí)間與順序執(zhí)行所有任務(wù)時(shí)所消耗時(shí)間的對(duì)比。測(cè)試分兩次進(jìn)行，第一次依賴關(guān)系圖中的所有任務(wù)負(fù)載均衡，所有任務(wù)與計(jì)算單獨(dú)一個(gè)數(shù)據(jù)時(shí)消耗的時(shí)間相似，并行運(yùn)算所消耗的時(shí)間隨數(shù)據(jù)量的增加線性增加，增長(zhǎng)的速度遠(yuǎn)遠(yuǎn)小于順序運(yùn)算時(shí)消耗時(shí)間增長(zhǎng)的速度，在虛擬8核計(jì)算機(jī)中，RATIO數(shù)值（順序運(yùn)算時(shí)間／并行運(yùn)算時(shí)間）在5到5.5之間。測(cè)試結(jié)果如圖8所示：

圖8 并行框架所消耗時(shí)間與順序執(zhí)行所有任務(wù)時(shí)所消耗時(shí)間的對(duì)比

第二次在任務(wù)相互依賴關(guān)系圖中，設(shè)置三個(gè)菱形的三個(gè)最高頂點(diǎn)任務(wù)為重量級(jí)任務(wù)，任務(wù)在計(jì)算一個(gè)數(shù)據(jù)時(shí)所消耗的時(shí)間是其他任務(wù)的20倍左右。測(cè)試結(jié)果如圖9所示：

圖9 并行框架所消耗時(shí)間與順序執(zhí)行所有任務(wù)時(shí)所消耗時(shí)間的對(duì)比

從測(cè)試結(jié)果中可以看到，如果在依賴關(guān)系中出現(xiàn)了負(fù)載不平衡，RATIO數(shù)值下降到4.5左右，CPU的運(yùn)算資源沒有能夠得到最大利用。

（三）段總數(shù)測(cè)試

在固定數(shù)據(jù)量情況下，段切分模塊采用不同的固定段大小，切分?jǐn)?shù)據(jù)時(shí)，測(cè)試了運(yùn)算所消耗的時(shí)間。當(dāng)段的數(shù)量多于計(jì)算機(jī)中邏輯核數(shù)（8）時(shí)，總運(yùn)算所消耗的時(shí)間穩(wěn)定在一個(gè)常數(shù)附近。當(dāng)段的數(shù)量非常多時(shí)，子任務(wù)的個(gè)數(shù)也會(huì)增多，運(yùn)算過程中對(duì)于系統(tǒng)內(nèi)存等資源的消耗也會(huì)增多。在實(shí)際運(yùn)用中段的數(shù)量應(yīng)當(dāng)保持在區(qū)間［計(jì)算機(jī)CPU邏輯核數(shù)，16＊計(jì)算機(jī)CPU邏輯核數(shù)］內(nèi)。

測(cè)試結(jié)果如圖10所示：

圖10 數(shù)據(jù)段的數(shù)量與子任務(wù)的個(gè)數(shù)關(guān)系

（四）異步IO測(cè)試

本文測(cè)試了在非SSD硬盤上，采用同步I／O和異步I／O時(shí)運(yùn)算所消耗的時(shí)間及RATIO值。與其他測(cè)試時(shí)后續(xù)任務(wù)直接從內(nèi)存中讀取前置任務(wù)的輸出數(shù)據(jù)不同，該測(cè)試中每個(gè)任務(wù)都從磁盤中讀取輸入數(shù)據(jù)，并在每段數(shù)據(jù)計(jì)算結(jié)束時(shí)把結(jié)果存儲(chǔ)在磁盤上。

同步I／O時(shí)采用操作系統(tǒng)默認(rèn)的緩存機(jī)制。異步I／O時(shí)直接使用系統(tǒng)的Complete I／O模型實(shí)現(xiàn)。測(cè)試如圖11所示：

圖11 同步I／O和異步I／O時(shí)運(yùn)算所消耗的時(shí)間的對(duì)比

四、結(jié) 論

本文闡述了并行任務(wù)框架設(shè)計(jì)中，如何從設(shè)計(jì)以及算法的角度提高相互依賴的并行任務(wù)框架的并行程度，以提高框架的性能。設(shè)計(jì)了一種并行框架，實(shí)現(xiàn)了原型。實(shí)驗(yàn)結(jié)果表明，該框架可有效提高并行任務(wù)的并行程度，具有良好的可靠性、穩(wěn)定性以及可擴(kuò)展性。

［1］ 魏長(zhǎng)虎.多核并行計(jì)算在流媒體服務(wù)系統(tǒng)中的研究與應(yīng)用［D］.濟(jì)南：山東大學(xué)，2009：1－2.

［2］ 汪前進(jìn)，高勇，李存華.基于多核處理器的多任務(wù)并行處理技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2012：29（7）：141－142.

［3］ 郝水俠，許金超.云計(jì)算中相似驅(qū)動(dòng)的并行任務(wù)劃分方法［J］.計(jì)算機(jī)科學(xué)與探索，2012：6（8）：41－43.

［4］ 閆邵，劉磊.基于數(shù)據(jù)依賴關(guān)系的程序自動(dòng)并行化方法［J］.吉林大學(xué)學(xué)報(bào)，2010：48（1）：94－95.

［5］ 郭龍，陳閎中，葉青.構(gòu)造串行程序?qū)?yīng)的并行任務(wù)（DAG）圖［J］.計(jì)算機(jī)工程與應(yīng)用，2007：43（1）：41－42.