并行應用程序調(diào)度策略研究*

李愛玲，王 璐，彭云峰

(安陽工學院計算機科學與信息工程系，河南 安陽 455000)

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

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

1 組件體系結構

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

圖1 組件體系結構

1.1 組件層

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

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

1.2 CCA 原型架構層

本層使標準并行組件組合成復合并行組件，進而所有這些組件組合成一個應用程序。我們將此組合消息存入XML 文件內(nèi)，范例和組件層的描述也存放在這些XML 文件內(nèi)。

圖2 是一個并行組件實例。它描述的是圖1 提到的地理圖像處理的應用程序過程。

圖2 并行組件構成

1.3 資源管理層和異構平臺層

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

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

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

(3)第3 組是PS3(PlayStation 3)集群，由16個PS3 組成，是非常強大的矢量運算器。

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

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

1.4 調(diào)度層

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

(1)粗粒度并行組件在某個集群上運行。

(2)中粒度并行組件在機器節(jié)點上運行。

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

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

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

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

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

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

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

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

2 測試結果

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

表1 組成信息

用C、MPI、OpenMP 分別執(zhí)行本測試。用SAR圖作為輸入數(shù)據(jù)，數(shù)據(jù)變化范圍100 M至500 M，將測試組件移植至異構平臺并測試，調(diào)度層在多核服務器集群調(diào)度此應用程序。為做比較研究，我們再用原始CCA 組件工具建立此應用程序，隨后隨機調(diào)度。結果如圖3所示?？梢?，調(diào)度策略改進了圖像處理應用程序的性能。

圖3 應用測試圖

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

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

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

圖5 資源利用率測試圖

3 結論

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

［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.