并行應用程序調度策略研究*

李愛玲，王 璐，彭云峰

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

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

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

1 組件體系結構

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

圖1 組件體系結構

1.1 組件層

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

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

1.2 CCA 原型架構層

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

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

圖2 并行組件構成

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

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

(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 工作站分布這個集群內。

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

1.4 調度層

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

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

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

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

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

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

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

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

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

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

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

2 測試結果

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

表1 組成信息

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

圖3 應用測試圖

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

圖4 執行總時間圖

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

圖5 資源利用率測試圖

3 結論

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

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