李愛(ài)玲，王 璐，彭云峰

(安陽(yáng)工學(xué)院計(jì)算機(jī)科學(xué)與信息工程系，河南 安陽(yáng) 455000)

并行軟件被廣泛應(yīng)用于大規(guī)?？茖W(xué)計(jì)算領(lǐng)域，其編程過(guò)程通常非常繁瑣，而且不利于維護(hù)和重用，導(dǎo)致其生產(chǎn)效率不高［1］。并行組件的提出使得并行軟件效率提高有了新途徑。并行組件是用于并行結(jié)構(gòu)的軟件，美國(guó)研究人員專門為并行組件問(wèn)題創(chuàng)辦了通用組件體系結(jié)構(gòu)(CCA)論壇［2］。CCA 定義了科學(xué)接口定義語(yǔ)言［3］。這種語(yǔ)言增強(qiáng)了不同語(yǔ)言編寫(xiě)的組件之間的互操作性。文獻(xiàn)［4］提供了一種自適應(yīng)的組件機(jī)制［4］，這種機(jī)制可以為某些硬件資源選擇合適的組件。文獻(xiàn)［5］中定義了并行組件的概念，并將組件定義分層為抽象層和應(yīng)用層，系統(tǒng)闡述了并行組件組成，并使其組合可預(yù)測(cè)。文獻(xiàn)［6］描述了并行系統(tǒng)的多范例特征［6］，它提高了開(kāi)發(fā)并行應(yīng)用程序的效率，以上研究是現(xiàn)有并行組件技術(shù)的代表。調(diào)度策略方面一般從并行應(yīng)用著手，針對(duì)集群和網(wǎng)格資源的管理，用分析任務(wù)圖的方法生成，用遺傳算法或退火算法分析［7］，但這使并行組件在異構(gòu)平臺(tái)上的應(yīng)用變得復(fù)雜。

以上研究均缺乏對(duì)范例、粒度大規(guī)模并行系統(tǒng)的考慮，這可能會(huì)影響到異構(gòu)平臺(tái)的性能和資源使用。而且現(xiàn)行的計(jì)算模型通常由數(shù)據(jù)并行，任務(wù)并行，串行等構(gòu)成，模型的執(zhí)行驗(yàn)證對(duì)程序的形式化描述和對(duì)預(yù)測(cè)起到了重要的指導(dǎo)作用。根據(jù)以上原則，本文從高性能并行計(jì)算的角度提出多范例、多粒度架構(gòu)，將并行應(yīng)用程序描述為并行組件的組合，并為其編寫(xiě)運(yùn)行范式和編程范式，通過(guò)部署、調(diào)度定義組件的粒度，由資源管理系統(tǒng)負(fù)責(zé)異構(gòu)平臺(tái)的資源管理，用優(yōu)化的窮舉法生成調(diào)度策略。

1 組件體系結(jié)構(gòu)

鑒于CCA 是一個(gè)相對(duì)正規(guī)的標(biāo)準(zhǔn)，組件模型基于CCA 平臺(tái)設(shè)立。組件體系結(jié)構(gòu)由五個(gè)層次組成:組件層、CCA 原型構(gòu)架層、調(diào)度層、資源管理層和異構(gòu)平臺(tái)層。組件層包含一些CCA 并行組件，每個(gè)組件都有其范例和粒度描述;CCA 原型構(gòu)架層［8］，是一個(gè)CCA 的組件的分布式框架，它為組件的連接提供必要的服務(wù);調(diào)度層，負(fù)責(zé)生成并執(zhí)行應(yīng)用程序的調(diào)度策略;資源管理層負(fù)責(zé)監(jiān)控異構(gòu)平臺(tái)的資源使用狀況，每個(gè)資源都模擬一個(gè)C++對(duì)象，此處不使用Java 對(duì)象［2］，是因?yàn)镴ava 虛擬機(jī)影響性能［9］;異構(gòu)平臺(tái)層，負(fù)責(zé)調(diào)控并行組件所需的資源。圖1 以一個(gè)地理圖像過(guò)程應(yīng)用為例給出了它們之間關(guān)系的簡(jiǎn)要描述。

圖1 組件體系結(jié)構(gòu)

1.1 組件層

在這一層，我們?yōu)閼?yīng)用程序定義了標(biāo)準(zhǔn)并行組件。一個(gè)標(biāo)準(zhǔn)的并行組件是在應(yīng)用程序中具有特定功能的CCA 并行組件，且在執(zhí)行過(guò)程中不會(huì)調(diào)用其它組件，它是基于應(yīng)用程序的并行組件中最小組成單位。標(biāo)準(zhǔn)并行組件的運(yùn)行范式如下:如果r 的值是“s”，該組件以串行的方式運(yùn)行。如果是“p”，則并行運(yùn)行。不同的進(jìn)程均以消息傳遞的方式相互聯(lián)系。當(dāng)組件在不同的并行線程運(yùn)行時(shí)，如果r 的值為“ps”，不同線程之間靠共享內(nèi)存信息通信。t 表示標(biāo)準(zhǔn)并行組件的編程范式。如果r 的值是“s”，t 可以是“C”、“Java”、“Fortran77”或其它串行高級(jí)語(yǔ)言。如果r 是“p”，t 可以是“C +MPI”［10］，“F90+MPI”或其它消息傳遞并行編程范例。如果r 是“ps”，t 可以是“HPT”、“C+OpenMP”［11］或其它內(nèi)存共享并行編程范式。例如，標(biāo)準(zhǔn)的CCA 并行組件，r=p，t=C+MPI 是用C 語(yǔ)言編寫(xiě)的一個(gè)組件，組件內(nèi)不同進(jìn)程間的聯(lián)系靠MPI。

我們定義了三個(gè)不同的粒度。粗粒度并行指以上定義的運(yùn)行范例的不同實(shí)例并行運(yùn)行，這意味著兩個(gè)或兩個(gè)以上運(yùn)行范例并行執(zhí)行，這些實(shí)例可以是不同的實(shí)例相同的模式，或不同模式的實(shí)例。例如，在CCA SCMD 組件中，相同組件的不同實(shí)例粗粒度并行執(zhí)行。中粒度并行指在一個(gè)并行運(yùn)行范例內(nèi)部并行運(yùn)行的實(shí)例。例如，在OpenMP 下并行執(zhí)行不同的線程就是中粒度并行。精粒度并行需要特別指出，它是串行執(zhí)行的，不允許并行執(zhí)行。如果一個(gè)組件包括一些粗粒度并行模塊，我們就說(shuō)他是粗粒度并行的。一個(gè)組件包括中粒度并行模塊且無(wú)粗粒度并行模塊稱之為中粒度并行。其它即為精粒度并行。

1.2 CCA 原型架構(gòu)層

本層使標(biāo)準(zhǔn)并行組件組合成復(fù)合并行組件，進(jìn)而所有這些組件組合成一個(gè)應(yīng)用程序。我們將此組合消息存入XML 文件內(nèi)，范例和組件層的描述也存放在這些XML 文件內(nèi)。

圖2 是一個(gè)并行組件實(shí)例。它描述的是圖1 提到的地理圖像處理的應(yīng)用程序過(guò)程。

圖2 并行組件構(gòu)成

1.3 資源管理層和異構(gòu)平臺(tái)層

在調(diào)度層之前先介紹這兩層是由于調(diào)度層需要從這兩層獲取資源信息。異構(gòu)平臺(tái)由四組不同的集群組成，分別如下:

(1)第1 組是SMP(Symmetric Multiprocessing 對(duì)稱多處理)集群。它由37個(gè)SMP 服務(wù)器組成。每個(gè)SMP 服務(wù)器都是一個(gè)雙核Intel Xeon 處理器，屬于對(duì)稱多處理器。

(2)第2 組是多核服務(wù)器群集，包含6個(gè)多核服務(wù)器。其中兩個(gè)為4 ×4 核Intel Xeon E7320 處理器，兩個(gè)4 ×4 核AMD Opteron 8347 HE 處理器，一個(gè)CPU-GPU［12］多核服務(wù)器，一個(gè)AMD 多核服務(wù)器。

(3)第3 組是PS3(PlayStation 3)集群，由16個(gè)PS3 組成，是非常強(qiáng)大的矢量運(yùn)算器。

(4)第4 組是PC 工作站集群，約80個(gè)PC 工作站分布這個(gè)集群內(nèi)。

異構(gòu)平臺(tái)由這4 組集群通過(guò)以太網(wǎng)連接，每個(gè)集群都有其自己的特點(diǎn):SMP 集群針對(duì)MOI 任務(wù)，不同的進(jìn)程可以運(yùn)行在不同的SMP 服務(wù)器上，它們通過(guò)消息庫(kù)傳遞消息。多核服務(wù)器集群處理OpenMP 任務(wù)非常得力，不同的OpenMP 線程在多核服務(wù)器上并行運(yùn)行，通過(guò)共享內(nèi)存進(jìn)行通信。PS3 的群集執(zhí)行矢量運(yùn)算速度遠(yuǎn)遠(yuǎn)超過(guò)其它機(jī)器，偶爾也用顯卡處理矢量運(yùn)算。PC 工作站集群用來(lái)處理時(shí)間限制不是很苛刻的任務(wù)。資源管理層將這些平臺(tái)上的資源看為C++對(duì)象來(lái)模擬，它們屬于繼承層次結(jié)構(gòu)。

1.4 調(diào)度層

調(diào)度層是架構(gòu)的核心層，它從資源管理層獲取資源信息，從XML 文件獲取范例和粒度描述。關(guān)于調(diào)度做以下假設(shè):

(1)粗粒度并行組件在某個(gè)集群上運(yùn)行。

(2)中粒度并行組件在機(jī)器節(jié)點(diǎn)上運(yùn)行。

(3)精粒度并行組件在處理器上運(yùn)行，如果是多核處理器則在其核心處理器上運(yùn)行。

(4)對(duì)于粗粒度并行組件，如果它包含OpenMP任務(wù)，它將會(huì)首先被多核服務(wù)器集群調(diào)度。如果是用Cell BE 編程又涉及大量的矢量運(yùn)算，則由PS3集群調(diào)度，否則被SMP 集群調(diào)度。

(5)對(duì)于中粒度并行組件，如果它包含的OpenMP 任務(wù)，將首先考慮多核服務(wù)器調(diào)度。如果是用Cell BE 編程又涉及大量的矢量運(yùn)算，則某個(gè)PS3 機(jī)調(diào)度，否則被某個(gè)SMP 服務(wù)器調(diào)度。

(6)如果精粒度并行組件用PowerPC 指令編寫(xiě)，則被某個(gè)PS3 機(jī)調(diào)度。否則它將被多核服務(wù)器調(diào)度。

(7)如果組件包含GPU 指令，過(guò)程或線程將被CPU-GPU 多核服務(wù)器調(diào)度執(zhí)行這些指令。

(8)如果組件完成指令有時(shí)間要求且并非Cell BE 語(yǔ)言編寫(xiě)，無(wú)GPU 指令，則優(yōu)先考慮被PC 工作站調(diào)度。

規(guī)則(1)，(2)，(3)和(7)必須嚴(yán)格遵守。規(guī)則(4)－(6)組件首先考慮在多核服務(wù)器上調(diào)度，如多核服務(wù)器忙，則可被SMP 調(diào)度。

根據(jù)以上規(guī)則和范例及粒度描述信息，調(diào)度策略引擎為組件運(yùn)行生成所有可能的調(diào)度信息，這類似于窮舉法。由于上述調(diào)度規(guī)則的規(guī)定，使得調(diào)度方法有窮且可用，從而可在這些有窮的方法內(nèi)選出最優(yōu)策略。所有調(diào)度策略發(fā)送到性能估計(jì)引擎，由性能估計(jì)引擎估算出每個(gè)策略所需的性能成本。我們將標(biāo)準(zhǔn)并行組件的計(jì)算和通信代價(jià)分類，計(jì)算成本可通過(guò)分析模型和微基準(zhǔn)［13］估算。通信成本包括所有不同的進(jìn)程或線程之間的通信，如數(shù)據(jù)的分布，結(jié)果收集等，這種成本可以基于通信模型和平臺(tái)參數(shù)獲得。從而策略引擎可選出最優(yōu)策略。應(yīng)用程序運(yùn)行過(guò)程中，如果某個(gè)資源不再可用，如某個(gè)服務(wù)器關(guān)閉，則資源管理引擎將把組件移植到其它可用資源上。

2 測(cè)試結(jié)果

本小節(jié)給出一個(gè)例子，利用組件體系結(jié)構(gòu)得出測(cè)試結(jié)果。測(cè)試是對(duì)地理圖像處理應(yīng)用的抽象，主要功能是對(duì)地理圖像中值濾波。如表1所示。

表1 組成信息

用C、MPI、OpenMP 分別執(zhí)行本測(cè)試。用SAR圖作為輸入數(shù)據(jù)，數(shù)據(jù)變化范圍100 M至500 M，將測(cè)試組件移植至異構(gòu)平臺(tái)并測(cè)試，調(diào)度層在多核服務(wù)器集群調(diào)度此應(yīng)用程序。為做比較研究，我們?cè)儆迷糃CA 組件工具建立此應(yīng)用程序，隨后隨機(jī)調(diào)度。結(jié)果如圖3所示?？梢?jiàn)，調(diào)度策略改進(jìn)了圖像處理應(yīng)用程序的性能。

圖3 應(yīng)用測(cè)試圖

一周內(nèi)每天應(yīng)用程序總的執(zhí)行時(shí)間，如圖4所示。圖中可見(jiàn)采用策略前后的對(duì)比，異構(gòu)平臺(tái)上一周內(nèi)總的執(zhí)行時(shí)間是之前的83%。這說(shuō)明，在一個(gè)相對(duì)較長(zhǎng)的時(shí)間內(nèi)，調(diào)度策略優(yōu)勢(shì)較為明顯。它可將并行組件應(yīng)用程序分配至合適的資源，也可使一周內(nèi)總的執(zhí)行時(shí)間縮短。

圖4 執(zhí)行總時(shí)間圖

我們也對(duì)異構(gòu)平臺(tái)資源利用率的使用進(jìn)行了記錄。發(fā)現(xiàn)一月內(nèi)機(jī)器的平均資源利用率提升了36%，如圖5所示。

圖5 資源利用率測(cè)試圖

3 結(jié)論

本文以CCA 原型架構(gòu)為中心，在異構(gòu)平臺(tái)的基礎(chǔ)上建立了基于范例和粒度的組件體系結(jié)構(gòu)，組件層描述多范例和多粒度的并行組件特征，資源管理層負(fù)責(zé)生產(chǎn)資源報(bào)告，調(diào)度層執(zhí)行由組成信息和資源信息形成的調(diào)度策略。最優(yōu)策略通過(guò)優(yōu)化的窮舉法確定，實(shí)驗(yàn)結(jié)果表明組件模型和調(diào)度策略改善了并行應(yīng)用程序的執(zhí)行，提高了異構(gòu)平臺(tái)資源的利用率。

［1］Burke B，Monson-Haefel R.Enterprise Java-Beans 3.0.CA，USA:O'Reilly Media，Inc，2006.

［2］David E Bernholdt，Benjamin A Allan，Robert Armstrong，et al.A Component Architecture for Highperformence Scientific Computing［J］.International Journal of High Performance Computing Aplications，2006，20(8):163－202.

［3］Scott R Kohn，Gray Kumfert，Jeffrey F Painter，et al.Divorcing Language Dependencies from a Scientific Software Library［C］//Proceedings of the Tenth SIAM Conference on Parallel Processing for ScientificComputing，2001［CD］.Philadelphia，PA，USA:SIAM Press，2001:10 pages on CD-ROM.

［4］Yves Maheo，F(xiàn)rederic Guidec，Luc Courtrai.Middleware Support for the Deployment of Resource-Aware Parallel Java Components on Heterogeneous Distributed Platforms:Proceedings of the 30th Euromicro Conference2004［C］//Washington，DC，USA:IEEE Compuer Socie-Component-Based Softy，2004:144－151.

［5］Lei Zhao，Stephen A Jarvis.Predictive Performance Modeling of Parallel Component Compositions［J］.Cluster Computing，2007，10(2):155－166.

［6］Hamelin F，Jezequel J M，Priol T.A Multi-Paradigm Object Oriented Parallel Environment Proceeding of English International Parallel Processing Symposium，1994:182－186.

［7］Joanna Jozefowska，Marek Mika，rafat Rozicki，et al.Simulated Annealing for Multi-Mode Resource Constrined Prject Scheduling.

［8］Benjiamin A Allan，Rob Armstrong C.Caffeine Framework:Composing and Debugging Applications Interratively and Running Them Statically［C/OL］:Compframe2005 Workshop，2005.

［9］Oracle Company.Java Virtual Machine［EB/OL］.http://www.java.com/object/gpu_programming_guide.html.

［10］ANL Mathematics and Computer Science.Message passing interface［EB/OL］.http://www.mcs.anl.gov/research/projects/mpi.

［11］M.OpenMP Architecture Review Board［EB/OL］.OpenMp.org.http://openmp.org/wp.

［12］NVIDIA Corporation.NVIDIA GPU Programming Guide-Performance Tuning Advice［EB/OL］.http://developer.nvdia.

［13］Nudd G R，Kerbyson D J，Papaefstathiou E.Pace-a Toolset for the Performance Prediction of Parallel and Distributed Systems［J］.International Jurnal of High Performance Computing Applications，SagePublications，2000，14(3):228－251.