著色Petri網對高性能集群的建模與性能評估①

黃偉華,馬 中,戴新發,徐明迪,高 毅

(武漢數字工程研究所,武漢 430205)

著色Petri網對高性能集群的建模與性能評估①

黃偉華,馬 中,戴新發,徐明迪,高 毅

(武漢數字工程研究所,武漢 430205)

針對形式化建模方法導致的狀態空間爆炸問題,提出了一種基于Petri網的高性能集群建模與性能評估方法.首先分析了高性能集群的系統架構,構建了模型的總體結構;然后針對集群系統建立了相應的任務產生子模型和調度子模型,并通過對Petri網進行著色,根據不同種類任務的執行特點設計了相應的任務處理模型.仿真結果表明,利用所建立的模型能夠有效評估關鍵參數對集群性能的影響.

高性能集群;著色Petri網絡;性能評估;模型;仿真

隨著高性能計算技術的不斷發展,集群的規模與結構復雜度不斷增加[1,2].為了指導高性能集群的系統設計,有必要在設計過程中對系統進行建模與仿真,以對其任務性能指標和系統性能指標預先進行評估[3].近年來,基于形式化方法的仿真分析技術取得了長足發展,大多數研究的焦點集中在利用復雜方法建立模型進而分析建模對象的性能,如隨機過程代數[4],排隊網絡[5],謂詞變換邏輯[6]等.此類研究側重于系統模型的精確建立,但是由于“狀態空間爆炸問題[7]”,上述方法并不適用于高性能集群的建模與性能評估,將復雜的集群結構轉變化為精確的分析模型有時非常困難甚至是無法實現的[8].

著色Petri網(Colored Petri Net,CPN)[9,10]不僅可以構建層次化模型,允許建模者利用多個彼此聯系的CPN子模型逐步建立大型復雜系統的層次模型,且圖形化建模方式和用戶自定義函數的融合使得在沒有降低CPN建模能力的前提下,增強了抽象功能,降低了模型復雜度,從而有效地抑制了“狀態空間爆炸”的發生[11].本文按照任務在集群系統中的處理過程,為任務的生成與分發、調度和執行分別建立相應的子模型,從而基于著色Petri網的層次化建模方式實現了對高性能集群的建模,以此對系統性能進行評估.

1 高性能集群系統架構

集群系統利用高速互連網絡,將計算節點按照一定的結構互連,在集群管理軟件的統一調度下實現對任務的高效處理.與傳統的單一高性能計算機相比,集群系統具有擴展能力強,可靠性高和性價比突出等優點.

根據現代集群系統的結構[12],可將集群中的節點分為兩類:管理節點和計算節點.其中,管理節點主要負責任務的接收,調度,分發,計算結果的反饋等功能;計算節點則主要負責對管理節點分發的任務進行計算與處理.

基于上述特點,文中將集群抽象為如圖1所示的系統.圖1所示的集群系統抽象模型由若干計算節點和一臺任務調度節點組成.客戶端提交的任務首先進入任務隊列排隊,隨后由調度節點對任務進行分發.因單機任務和并行計算任務在集群上的處理方式存在較大差別[13],調度器分別為單機任務和并行計算任務建立了獨立的任務隊列.為了與建模語言統一,便于理解,后文在建模過程中分別用Single型任務和MPI型(Message Passing Interface)任務指代上述兩種類型的任務.位于隊列中的任務由計算節點依次進行處理.如圖1所示,處理完成的結果首先反饋至調度節點并最終返回給客戶.

圖1 集群系統架構

為了對集群性能進行評估,文中后續章節通過CPN對上述集群進行建模.根據任務的處理流程,文中按照任務在集群系統中的不同生命周期進行建模:任務的到達與分發,任務調度,Single型任務的執行和MPI型任務的執行.為了利用所建立的模型對系統性能進行評估,建模過程中對系統性能有關鍵影響的參數均設定為動態可調.

2 高性能集群的CPN建模

CPN的基本組成包含庫所,變遷和有向弧.庫所表示系統的狀態,變遷表示資源的消耗、使用及系統狀態的變化;變遷的發生受到系統狀態的控制,即變遷發生的前置條件必須滿足.故CPN可用如下的形式化三元組[14]來表示:

在圖形化建模方式中,CPN用圓形表示庫所,用矩形表示變遷.在本文中,使用庫所表示集群系統的狀態,利用變遷表示導致系統狀態發生變化的操作與事件.

在系統建模時,使用庫所和變遷模擬了任務從到達到執行完畢反饋給用戶的整個過程,通過有向弧規定了任務在仿真模型中的流動方向.CPN允許一個庫所中包含多個托肯[15],每個托肯代表一個任務或任務隊列.文中將其著色,以區分MPI型任務和Single型任務這兩種不同類型的任務對象.圖2是高性能集群的CPN模型總體結構.因當前的主流CPN建模工具僅支持英文描述,為忠實于實際模型,在后文中,CPN模型圖使用默認語言進行表達.

在所建立的模型中,新任務的產生與到達由變遷子網Job Arrival模擬.變遷子網Job Arrival生成MPI型和Single型兩種任務,以模擬高性能集群中對應的并行計算類任務和非并行計算類任務.模擬生成的任務隨后被放入任務池中,由調度節點對任務進行統一分發,此過程的執行實體對應圖1中的任務調度與分發服務器.在使用CPN建模時,任務池由庫所Job Pool進行模擬.模型中,庫所Job Pool中的任務經過變遷子網Job Scheduling調度后分別加入對應的任務隊列.模型中分別用庫所Single Job Queue和MPI Job Queue模擬Single型與MPI型任務隊列緩存.

考慮到實際系統僅具有有限的計算能力,為了滿足任務的QoS要求,調度器會監測任務隊列的長度.如果隊列中的任務數已經達到設定的上限值,調度器可以選擇丟棄部分任務以保證QoS,此過程在模型中通過變遷子網Job Scheduling后續的選擇關系[16]進行模擬.被丟棄任務分別被放入庫所Dropped Single、Dropped MPI中.被集群調度器接收的任務將獲得執行機會,具體地,兩種不同任務的執行分別由子網Single Job Exe和MPI Job Exe進行模擬.任務執行過程中需要從資源池中獲取資源,使用CPN建模時,系統資源通過庫所Resource Pool進行模擬.執行完畢的任務最終分別到達庫所Completed Single和Completed MPI中.

在使用模擬軟件CPN Tools對高性能集群進行具體建模時,模型中利用庫所Job Pool、Single Job Queue、MPI Job Queue、Dropped Single、Dropped MPI、Completed Single、Completed MPI中的托肯代表任務,顏色是復合型變量Job,由任務代號n、任務類型jobtype和時間標記t組成.

圖2 高性能集群CPN模型架構

圖3 是子網Job Arrival的結構,用以模擬任務的產生過程.變遷Single Job Generation到庫所Single Job的弧函數[17]n+1@+expTime(Next_Single)指定了下一個任務的到達時間.為了更加貼近實際的集群應用場景,模型中設定任務到達時間間隔可調,以模擬不同的任務負載;與Single型任務類似,下一個MPI型任務的到達時間由弧函數n+1@+expTime(Next_MPI)指定.產生的任務最終以隊列的方式進行組織并存放進任務池庫所Job Pool中.

圖4顯示了變遷子網Job Scheduling的結構.任務池庫所Job Pool中的任務經過兩種不同的調度方式Schedule MPI Job和Schedule Single Job進行調度.任務隨后分流到對應的任務隊列緩存MPI Job Queue、Single Job Queue中.為了保證服務的QoS,當隊列中的任務數量達到上限值時,允許丟棄后續到達的任務,模型中對此種場景進行了模擬.以Single型任務為例,模型中設定其任務隊列的上限值為MaxQueueS,變遷Drop Single通過守衛函數[18]進行條件判斷[QueueLength(S_queue)>MaxQueueS]以決策是否繼續接收后續到達的任務.模型中,為了維持任務隊列的實時更新,無論任務是否會被接收都需要向Job Queue反饋信息以更新任務隊列緩存.

圖3 JobArrival子網結構

圖4 Job Scheduling子網結構

圖5 Single Job Exe子網結構

如圖5所示的變遷子網Single Job Exe描述了Single型任務的數據訪問,任務執行和返回這三個步驟.建模過程中充分利用了CPN的特性,通過賦時變遷Data Access Single的延時函數@+expTime(t_Data)模擬任務訪問存儲設備所耗費的時間,通過賦時變遷Exe Single的延時函數@+expTime(t_ExeS)模擬任務在處理器上的執行時間,Single Return的變遷延時t_ReS則用來模擬任務返回所需時間.

圖6所示的變遷子網MPI Job Exe建立了MPI型任務的執行過程模型.與Single型任務不同的是,MPI型任務在執行時對計算節點數量的需求由任務規模決定[19].針對MPI型任務的資源需求特點,模型中專門為 MPI型任務設計了資源管理函數MPI_Resource_Alloc;根據MPI型任務的執行方式[20],任務以多進程的方式在不同的物理計算節點上并行執行,執行過程中通過消息傳遞進行同步,最后通過匯合操作統一整個執行過程.圖6中的模型模擬了MPI型任務執行的主要步驟,且為了回收MPI型任務在執行過程中占用的系統資源,在任務執行結束之前通過MPI_Resource_Join函數對所占用的資源進行釋放.

圖6 MPI Job Exe子網結構

3 仿真實驗與結果分析

3.1 評價指標與參數設置

系統CPN模型建立之后,即可通過改變模型參數評估其對系統性能的影響.為了通過上述模型評估集群系統在不同任務負載與系統配置下的若干關鍵性能指標,文中利用不同的模型配置參數進行了仿真.

為表述方便,此處對后文用到的相關術語進行說明:

任務隊列長度:集群模型的任務隊列緩存中, Single型任務和MPI型任務的緩存長度;

資源利用率:文中主要針對集群中的計算節點計算資源利用率,定義為一定時間段內被占用的計算節點數量和模型資源池中計算節點總數量的比值;

任務響應時間:定義為任務被提交至集群系統中的時刻與反饋計算結果時刻之差;

任務丟失率:定義為被丟棄的任務數與總任務數的比值.

CPN模型的全局配置參數如表1所示.

表1 仿真參數配置

3.2 仿真

為了評估不同任務負載時的系統性能,文中通過調整任務到達時間間隔對不同輕重的任務負載進行模擬,并通過仿真對任務到達時間間隔與系統性能的關系進行研究;考慮到高性能集群的任務隊列長度和計算節點數量對系統性能有較大影響,仿真過程中通過CPN模型對相關參數進行動態調整以評估其對系統性能的影響.

基于上述目標,首先通過所建立的模型對不同任務負載下的任務響應時間和資源利用率進行了仿真;然后在恒定任務負載下通過對不同任務隊列長度的仿真以評估其對任務響應時間和丟失率等關鍵性能指標的影響;最后對集群中包含不同計算節點數量下的系統性能進行了仿真,以評估計算節點數量對系統性能的影響.

3.2.1 任務負載對系統性能的影響

為了評估不同任務負載對系統性能的影響,此節針對不同的任務到達時間間隔進行仿真.通過改變任務到達時間間隔的長度,以仿真不同負載對任務響應時間和系統資源利用率的影響.仿真時設定任務到達的時間間隔區間為[10,1000],時間單位設定為秒.仿真結果如圖7所示.

圖7 不同任務負載時的系統性能

由圖7(a)和圖7(b)可知,在任務到達時間間隔較長時,此時系統的任務負載相對較低,任務的響應時間較短,且資源利用率較低,顯示系統此時具有良好的動態性能;隨著任務到達時間間隔縮短,集群系統的任務負載加重,無論是Single型任務還是MPI型任務,響應時間均明顯上升,且MPI型任務響應時間的上升程度遠高于Single型任務,這是因為MPI型任務在執行時需要消耗更多資源.圖7(b)驗證了隨著任務到達時間縮短,MPI型任務的資源利用率更容易達到飽和.

3.2.2 任務隊列長度對系統性能的影響

在高性能集群中,任務隊列用以實現對任務調度節點分發的任務進行緩存.隊列長度作為高性能集群設計時的關鍵考慮因素之一,對系統性能有重要影響.此節通過改變CPN模型中任務隊列的長度研究評估其對響應時間和任務丟失率的影響.

在CPN模型中固定任務到達時間為恒定值,分別針對不同的任務隊列長度進行仿真.仿真中設定任務隊列長度區間為[5,40],對此區間內不同任務隊列長度對系統性能的影響進行評估.仿真結果如圖8所示.

圖8 不同隊列長度對系統性能的影響

由圖8(a)可以看出,Single型任務和MPI型任務的響應時間均隨著任務隊列長度的增加而增長.其中, MPI型任務的響應時間增長更為顯著,這是因為MPI型任務的執行需要多個計算節點并行進行,其響應時間對由任務隊列長度增加而導致的任務累積更為敏感.觀察圖8(b)可知,當任務隊列增加到一定長度時,集群的任務丟失率并未進一步降低,主要原因在于此時系統的瓶頸在于計算資源,資源利用率已經接近飽和.文中后續章節針對集群系統中計算節點數量對任務丟失率的影響進行了仿真研究.

3.2.3 計算節點數對任務丟失率的影響

此節在CPN模型中固定任務到達時間間隔為恒定值,并保持任務隊列長度不變,改變模型中計算節點的數量進行仿真.仿真中動態調整集群所包含的計算節點數量,設定計算節點數量區間為[10,70],以評估不同規模的計算節點對任務丟失率的影響.

圖9 計算節點數量對任務丟失率的影響

觀察圖9可知,維持系統的任務負載不變,并保持相同的隊列長度,集群系統的任務丟失率隨著計算節點數的增加迅速下降.可見,在因資源使用飽和而導致任務丟失率較高的情況下,無論是Single型任務還是MPI型任務,增加計算節點數量均能夠有效降低任務丟失率.

基于所建立的模型對高性能集群的仿真,可以得出如下基本結論:ⅰ)任務負載的改變引起集群資源使用率的變化,當高性能集群的資源使用率上升到一定程度時,系統對任務的響應時間顯著增加;MPI型任務因對資源需求敏感,響應時間上升更為明顯;ⅱ)增加任務隊列長度能夠在一定程度上降低任務丟失率,但任務響應時間隨之增加,實質是系統中存在大量任務擁塞;ⅲ)增加集群系統中計算節點的數量能夠降低任務丟失率.提高集群系統的處理能力是降低任務丟失率的最有效方式.

仿真過程表明,使用著色Petri網構建的層次化模型能夠對高性能集群的性能進行有效評估,與隨機過程代數等復雜方法相比,基于著色Petri網的建模方法層次明晰,建模過程也相對簡潔高效.

4 結語

當今的高性能集群已變得十分龐大,結構也越來越復雜,為系統設計帶來了巨大挑戰.文中分析了當前高性能集群的典型架構,并基于著色Petri網建立了集群的仿真與分析模型;通過不同任務負載和系統配置對高性能集群的性能進行仿真,預測并評估了關鍵參數對系統性能的影響,以期望在設計階段為系統優化提供參考.相對于形式化方法,文中提出的建模方法有效抑制了狀態空間爆炸問題.建立更為精確的系統模型以及提高模型的自動化仿真能力是后續需要完成的工作.

1 Niu SC,Zhai JD,Ma XS,Tang X,Chen WG,Zheng WM．Building semi-elastic virtual clusters for cost-effective HPC cloud resource provisionin.IEEE Trans.on Parallel and Distributed Systems,2016,27(7):1915–1928.

2伍康文,柴華.微服務器集群架構的綠色云計算平臺.計算機系統應用,2013,22(2):19–25.

3 David B,Felipe O,Jean A,Felipe F,Alberto A,Patricia E, Paulo M,Edward D.Performance evaluation of hypervisors for HPC applications.IEEE International Conference on System,Man and Cybernetics.2015.846–851.

4 Zhao GS,Wang HP,Wang J.A novel formal analysis method of network survivability based on stochastic process algebra. Tsinghua Science and Technology,2007,12(1):175–179.

5 Tribastone M.A fluid model for layered queuing networks. IEEE Trans.on Software Engineering,2013,39(6):744–756.

6屈婉霞,李暾,郭陽,楊曉東.謂詞抽象技術研究.計算機研究與發展,2008,19(1):27–38.

7 Furkan C,Tolga O.Attacking state space explosion problem in model checking embedded TV software.IEEE Trans.on Consumer Electronics,2015,61(4):572–579.

8 Alexander R.Stabilization of a high performance cluster model.InternationalCongresson UltraModernTelecommunications and Control Systems Workshops.2014. 518–521.

9 Dmitry A.Toward the minimal universal Petri net.IEEE Trans.on Systems,Man,and Cybernetics:Systems,2014, 44(1):47–58.

10 Corneli G,Jose M,Giovanni C.CacheSIM:A web cache simulator tool based on colored Petri nets and Java programming.IEEE Latin America Trans.,2015,13(5): 1511–1519.

11 Juan I,Emilio J,Mercedes P.Simulation-based optimization for the design of discrete event systems modeled by parametric Petrinets.2011 Fifth UKSim European Symposium on Computer Modeling and Simulation.2011. 150–155.

12劉偉,尹行,段玉光,杜薇,王偉,曾國蓀.同構DVS集群中基于自適應閾值的并行任務節能調度算法.計算機學報, 2013,36(2):393–407.

13 Gao YF,He BS,Zhong J.Network performance aware MPI collective communication operations in the cloud.IEEE Trans.on Parallel and Distributed Systems,2015,26(11): 3079–3089.

14 Issam A.Server consolidation using colored Petri nets and CPN tools.IEEE International Conference on Information and Communication Systems.2015.32–37.

15 Peng DG,Qian YL,Zhang H,Xia F.Research on fault diagnosis of turbine generation unit based on improved CPN neural network.IEEE International Symposium on System Integration.2014.672–677.

16 George F,Mehdi M,Giovanni C.A modular colored stochastic Petri net for modeling and analysis of signalized intersections.IEEE Trans.on Intelligent Transportation Systems,2016,17(3):701–713.

17 Clarimundo M,Rita M,Stephane J.Modeling recursive search algorithms by means of hierarchical colored Petri nets.International Conference on Information Technology. 2015.788–791.

18 Ding ZH,Zhou Y,Zhou M.Modeling self-adaptive software systems with learning Petri nets.IEEE Trans.on Systems, Man,and CyberneticsSystems,2016,46(4):483–498.

19 Ashwin M,Lokendra S,Feng J,Karthik M,Milind C,Pavan B,Keith R,James D,Feng W,John M,Ma XS,Rajeev T. MPI-ACC:Accelerator-aware MPI for scientific applications. IEEE Trans.on Parallel and Distributed Systems,2016, 27(5):1401–1414.

20劉志強,宋君強,盧風順,趙娟.基于線程的MPI通信加速器技術研究.計算機學報,2011,34(1):154–164.

Modeling and Performance Evaluation for High Performance Cluster Based on Colored Petri Net

HUANG Wei-Hua,MAZhong,DAI Xin-Fa,XU Ming-Di,GAO Yi

(Wuhan Digital Engineering Institute,Wuhan 430205,China)

To solve the problem of state space explosion caused by formal modeling methods,a simulation model and performance evaluation method for high performance cluster based on Petri net are proposed.Firstly,the system structure of high performance cluster is analyzed and a general model is constructed.Then the sub-models for task generation and scheduling are built respectively for cluster system.Finally,according to the characteristics of different kinds of tasks,the corresponding task processing models of different tasks are designed by coloring the Petri net.The simulation results show that the proposed model could effectively evaluate the effects of key parameters on cluster performance.

high performance cluster;colored Petri net;performance evaluation;model;simulation

國家自然科學基金(61502438)

2016-08-18;收到修改稿時間:2016-09-23

10.15888/j.cnki.csa.005735