著色Petri網(wǎng)對(duì)高性能集群的建模與性能評(píng)估①

黃偉華,馬 中,戴新發(fā),徐明迪,高 毅

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

著色Petri網(wǎng)對(duì)高性能集群的建模與性能評(píng)估①

黃偉華,馬 中,戴新發(fā),徐明迪,高 毅

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

針對(duì)形式化建模方法導(dǎo)致的狀態(tài)空間爆炸問(wèn)題,提出了一種基于Petri網(wǎng)的高性能集群建模與性能評(píng)估方法.首先分析了高性能集群的系統(tǒng)架構(gòu),構(gòu)建了模型的總體結(jié)構(gòu);然后針對(duì)集群系統(tǒng)建立了相應(yīng)的任務(wù)產(chǎn)生子模型和調(diào)度子模型,并通過(guò)對(duì)Petri網(wǎng)進(jìn)行著色,根據(jù)不同種類(lèi)任務(wù)的執(zhí)行特點(diǎn)設(shè)計(jì)了相應(yīng)的任務(wù)處理模型.仿真結(jié)果表明,利用所建立的模型能夠有效評(píng)估關(guān)鍵參數(shù)對(duì)集群性能的影響.

高性能集群;著色Petri網(wǎng)絡(luò);性能評(píng)估;模型;仿真

隨著高性能計(jì)算技術(shù)的不斷發(fā)展,集群的規(guī)模與結(jié)構(gòu)復(fù)雜度不斷增加[1,2].為了指導(dǎo)高性能集群的系統(tǒng)設(shè)計(jì),有必要在設(shè)計(jì)過(guò)程中對(duì)系統(tǒng)進(jìn)行建模與仿真,以對(duì)其任務(wù)性能指標(biāo)和系統(tǒng)性能指標(biāo)預(yù)先進(jìn)行評(píng)估[3].近年來(lái),基于形式化方法的仿真分析技術(shù)取得了長(zhǎng)足發(fā)展,大多數(shù)研究的焦點(diǎn)集中在利用復(fù)雜方法建立模型進(jìn)而分析建模對(duì)象的性能,如隨機(jī)過(guò)程代數(shù)[4],排隊(duì)網(wǎng)絡(luò)[5],謂詞變換邏輯[6]等.此類(lèi)研究側(cè)重于系統(tǒng)模型的精確建立,但是由于“狀態(tài)空間爆炸問(wèn)題[7]”,上述方法并不適用于高性能集群的建模與性能評(píng)估,將復(fù)雜的集群結(jié)構(gòu)轉(zhuǎn)變化為精確的分析模型有時(shí)非常困難甚至是無(wú)法實(shí)現(xiàn)的[8].

著色Petri網(wǎng)(Colored Petri Net,CPN)[9,10]不僅可以構(gòu)建層次化模型,允許建模者利用多個(gè)彼此聯(lián)系的CPN子模型逐步建立大型復(fù)雜系統(tǒng)的層次模型,且圖形化建模方式和用戶自定義函數(shù)的融合使得在沒(méi)有降低CPN建模能力的前提下,增強(qiáng)了抽象功能,降低了模型復(fù)雜度,從而有效地抑制了“狀態(tài)空間爆炸”的發(fā)生[11].本文按照任務(wù)在集群系統(tǒng)中的處理過(guò)程,為任務(wù)的生成與分發(fā)、調(diào)度和執(zhí)行分別建立相應(yīng)的子模型,從而基于著色Petri網(wǎng)的層次化建模方式實(shí)現(xiàn)了對(duì)高性能集群的建模,以此對(duì)系統(tǒng)性能進(jìn)行評(píng)估.

1 高性能集群系統(tǒng)架構(gòu)

集群系統(tǒng)利用高速互連網(wǎng)絡(luò),將計(jì)算節(jié)點(diǎn)按照一定的結(jié)構(gòu)互連,在集群管理軟件的統(tǒng)一調(diào)度下實(shí)現(xiàn)對(duì)任務(wù)的高效處理.與傳統(tǒng)的單一高性能計(jì)算機(jī)相比,集群系統(tǒng)具有擴(kuò)展能力強(qiáng),可靠性高和性價(jià)比突出等優(yōu)點(diǎn).

根據(jù)現(xiàn)代集群系統(tǒng)的結(jié)構(gòu)[12],可將集群中的節(jié)點(diǎn)分為兩類(lèi):管理節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn).其中,管理節(jié)點(diǎn)主要負(fù)責(zé)任務(wù)的接收,調(diào)度,分發(fā),計(jì)算結(jié)果的反饋等功能;計(jì)算節(jié)點(diǎn)則主要負(fù)責(zé)對(duì)管理節(jié)點(diǎn)分發(fā)的任務(wù)進(jìn)行計(jì)算與處理.

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

圖1 集群系統(tǒng)架構(gòu)

為了對(duì)集群性能進(jìn)行評(píng)估,文中后續(xù)章節(jié)通過(guò)CPN對(duì)上述集群進(jìn)行建模.根據(jù)任務(wù)的處理流程,文中按照任務(wù)在集群系統(tǒng)中的不同生命周期進(jìn)行建模:任務(wù)的到達(dá)與分發(fā),任務(wù)調(diào)度,Single型任務(wù)的執(zhí)行和MPI型任務(wù)的執(zhí)行.為了利用所建立的模型對(duì)系統(tǒng)性能進(jìn)行評(píng)估,建模過(guò)程中對(duì)系統(tǒng)性能有關(guān)鍵影響的參數(shù)均設(shè)定為動(dòng)態(tài)可調(diào).

2 高性能集群的CPN建模

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

在圖形化建模方式中,CPN用圓形表示庫(kù)所,用矩形表示變遷.在本文中,使用庫(kù)所表示集群系統(tǒng)的狀態(tài),利用變遷表示導(dǎo)致系統(tǒng)狀態(tài)發(fā)生變化的操作與事件.

在系統(tǒng)建模時(shí),使用庫(kù)所和變遷模擬了任務(wù)從到達(dá)到執(zhí)行完畢反饋給用戶的整個(gè)過(guò)程,通過(guò)有向弧規(guī)定了任務(wù)在仿真模型中的流動(dòng)方向.CPN允許一個(gè)庫(kù)所中包含多個(gè)托肯[15],每個(gè)托肯代表一個(gè)任務(wù)或任務(wù)隊(duì)列.文中將其著色,以區(qū)分MPI型任務(wù)和Single型任務(wù)這兩種不同類(lèi)型的任務(wù)對(duì)象.圖2是高性能集群的CPN模型總體結(jié)構(gòu).因當(dāng)前的主流CPN建模工具僅支持英文描述,為忠實(shí)于實(shí)際模型,在后文中,CPN模型圖使用默認(rèn)語(yǔ)言進(jìn)行表達(dá).

在所建立的模型中,新任務(wù)的產(chǎn)生與到達(dá)由變遷子網(wǎng)Job Arrival模擬.變遷子網(wǎng)Job Arrival生成MPI型和Single型兩種任務(wù),以模擬高性能集群中對(duì)應(yīng)的并行計(jì)算類(lèi)任務(wù)和非并行計(jì)算類(lèi)任務(wù).模擬生成的任務(wù)隨后被放入任務(wù)池中,由調(diào)度節(jié)點(diǎn)對(duì)任務(wù)進(jìn)行統(tǒng)一分發(fā),此過(guò)程的執(zhí)行實(shí)體對(duì)應(yīng)圖1中的任務(wù)調(diào)度與分發(fā)服務(wù)器.在使用CPN建模時(shí),任務(wù)池由庫(kù)所Job Pool進(jìn)行模擬.模型中,庫(kù)所Job Pool中的任務(wù)經(jīng)過(guò)變遷子網(wǎng)Job Scheduling調(diào)度后分別加入對(duì)應(yīng)的任務(wù)隊(duì)列.模型中分別用庫(kù)所Single Job Queue和MPI Job Queue模擬Single型與MPI型任務(wù)隊(duì)列緩存.

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

在使用模擬軟件CPN Tools對(duì)高性能集群進(jìn)行具體建模時(shí),模型中利用庫(kù)所Job Pool、Single Job Queue、MPI Job Queue、Dropped Single、Dropped MPI、Completed Single、Completed MPI中的托肯代表任務(wù),顏色是復(fù)合型變量Job,由任務(wù)代號(hào)n、任務(wù)類(lèi)型jobtype和時(shí)間標(biāo)記t組成.

圖2 高性能集群CPN模型架構(gòu)

圖3 是子網(wǎng)Job Arrival的結(jié)構(gòu),用以模擬任務(wù)的產(chǎn)生過(guò)程.變遷Single Job Generation到庫(kù)所Single Job的弧函數(shù)[17]n+1@+expTime(Next_Single)指定了下一個(gè)任務(wù)的到達(dá)時(shí)間.為了更加貼近實(shí)際的集群應(yīng)用場(chǎng)景,模型中設(shè)定任務(wù)到達(dá)時(shí)間間隔可調(diào),以模擬不同的任務(wù)負(fù)載;與Single型任務(wù)類(lèi)似,下一個(gè)MPI型任務(wù)的到達(dá)時(shí)間由弧函數(shù)n+1@+expTime(Next_MPI)指定.產(chǎn)生的任務(wù)最終以隊(duì)列的方式進(jìn)行組織并存放進(jìn)任務(wù)池庫(kù)所Job Pool中.

圖4顯示了變遷子網(wǎng)Job Scheduling的結(jié)構(gòu).任務(wù)池庫(kù)所Job Pool中的任務(wù)經(jīng)過(guò)兩種不同的調(diào)度方式Schedule MPI Job和Schedule Single Job進(jìn)行調(diào)度.任務(wù)隨后分流到對(duì)應(yīng)的任務(wù)隊(duì)列緩存MPI Job Queue、Single Job Queue中.為了保證服務(wù)的QoS,當(dāng)隊(duì)列中的任務(wù)數(shù)量達(dá)到上限值時(shí),允許丟棄后續(xù)到達(dá)的任務(wù),模型中對(duì)此種場(chǎng)景進(jìn)行了模擬.以Single型任務(wù)為例,模型中設(shè)定其任務(wù)隊(duì)列的上限值為MaxQueueS,變遷Drop Single通過(guò)守衛(wèi)函數(shù)[18]進(jìn)行條件判斷[QueueLength(S_queue)>MaxQueueS]以決策是否繼續(xù)接收后續(xù)到達(dá)的任務(wù).模型中,為了維持任務(wù)隊(duì)列的實(shí)時(shí)更新,無(wú)論任務(wù)是否會(huì)被接收都需要向Job Queue反饋信息以更新任務(wù)隊(duì)列緩存.

圖3 JobArrival子網(wǎng)結(jié)構(gòu)

圖4 Job Scheduling子網(wǎng)結(jié)構(gòu)

圖5 Single Job Exe子網(wǎng)結(jié)構(gòu)

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

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

圖6 MPI Job Exe子網(wǎng)結(jié)構(gòu)

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 評(píng)價(jià)指標(biāo)與參數(shù)設(shè)置

系統(tǒng)CPN模型建立之后,即可通過(guò)改變模型參數(shù)評(píng)估其對(duì)系統(tǒng)性能的影響.為了通過(guò)上述模型評(píng)估集群系統(tǒng)在不同任務(wù)負(fù)載與系統(tǒng)配置下的若干關(guān)鍵性能指標(biāo),文中利用不同的模型配置參數(shù)進(jìn)行了仿真.

為表述方便,此處對(duì)后文用到的相關(guān)術(shù)語(yǔ)進(jìn)行說(shuō)明:

任務(wù)隊(duì)列長(zhǎng)度:集群模型的任務(wù)隊(duì)列緩存中, Single型任務(wù)和MPI型任務(wù)的緩存長(zhǎng)度;

資源利用率:文中主要針對(duì)集群中的計(jì)算節(jié)點(diǎn)計(jì)算資源利用率,定義為一定時(shí)間段內(nèi)被占用的計(jì)算節(jié)點(diǎn)數(shù)量和模型資源池中計(jì)算節(jié)點(diǎn)總數(shù)量的比值;

任務(wù)響應(yīng)時(shí)間:定義為任務(wù)被提交至集群系統(tǒng)中的時(shí)刻與反饋計(jì)算結(jié)果時(shí)刻之差;

任務(wù)丟失率:定義為被丟棄的任務(wù)數(shù)與總?cè)蝿?wù)數(shù)的比值.

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

表1 仿真參數(shù)配置

3.2 仿真

為了評(píng)估不同任務(wù)負(fù)載時(shí)的系統(tǒng)性能,文中通過(guò)調(diào)整任務(wù)到達(dá)時(shí)間間隔對(duì)不同輕重的任務(wù)負(fù)載進(jìn)行模擬,并通過(guò)仿真對(duì)任務(wù)到達(dá)時(shí)間間隔與系統(tǒng)性能的關(guān)系進(jìn)行研究;考慮到高性能集群的任務(wù)隊(duì)列長(zhǎng)度和計(jì)算節(jié)點(diǎn)數(shù)量對(duì)系統(tǒng)性能有較大影響,仿真過(guò)程中通過(guò)CPN模型對(duì)相關(guān)參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整以評(píng)估其對(duì)系統(tǒng)性能的影響.

基于上述目標(biāo),首先通過(guò)所建立的模型對(duì)不同任務(wù)負(fù)載下的任務(wù)響應(yīng)時(shí)間和資源利用率進(jìn)行了仿真;然后在恒定任務(wù)負(fù)載下通過(guò)對(duì)不同任務(wù)隊(duì)列長(zhǎng)度的仿真以評(píng)估其對(duì)任務(wù)響應(yīng)時(shí)間和丟失率等關(guān)鍵性能指標(biāo)的影響;最后對(duì)集群中包含不同計(jì)算節(jié)點(diǎn)數(shù)量下的系統(tǒng)性能進(jìn)行了仿真,以評(píng)估計(jì)算節(jié)點(diǎn)數(shù)量對(duì)系統(tǒng)性能的影響.

3.2.1 任務(wù)負(fù)載對(duì)系統(tǒng)性能的影響

為了評(píng)估不同任務(wù)負(fù)載對(duì)系統(tǒng)性能的影響,此節(jié)針對(duì)不同的任務(wù)到達(dá)時(shí)間間隔進(jìn)行仿真.通過(guò)改變?nèi)蝿?wù)到達(dá)時(shí)間間隔的長(zhǎng)度,以仿真不同負(fù)載對(duì)任務(wù)響應(yīng)時(shí)間和系統(tǒng)資源利用率的影響.仿真時(shí)設(shè)定任務(wù)到達(dá)的時(shí)間間隔區(qū)間為[10,1000],時(shí)間單位設(shè)定為秒.仿真結(jié)果如圖7所示.

圖7 不同任務(wù)負(fù)載時(shí)的系統(tǒng)性能

由圖7(a)和圖7(b)可知,在任務(wù)到達(dá)時(shí)間間隔較長(zhǎng)時(shí),此時(shí)系統(tǒng)的任務(wù)負(fù)載相對(duì)較低,任務(wù)的響應(yīng)時(shí)間較短,且資源利用率較低,顯示系統(tǒng)此時(shí)具有良好的動(dòng)態(tài)性能;隨著任務(wù)到達(dá)時(shí)間間隔縮短,集群系統(tǒng)的任務(wù)負(fù)載加重,無(wú)論是Single型任務(wù)還是MPI型任務(wù),響應(yīng)時(shí)間均明顯上升,且MPI型任務(wù)響應(yīng)時(shí)間的上升程度遠(yuǎn)高于Single型任務(wù),這是因?yàn)镸PI型任務(wù)在執(zhí)行時(shí)需要消耗更多資源.圖7(b)驗(yàn)證了隨著任務(wù)到達(dá)時(shí)間縮短,MPI型任務(wù)的資源利用率更容易達(dá)到飽和.

3.2.2 任務(wù)隊(duì)列長(zhǎng)度對(duì)系統(tǒng)性能的影響

在高性能集群中,任務(wù)隊(duì)列用以實(shí)現(xiàn)對(duì)任務(wù)調(diào)度節(jié)點(diǎn)分發(fā)的任務(wù)進(jìn)行緩存.隊(duì)列長(zhǎng)度作為高性能集群設(shè)計(jì)時(shí)的關(guān)鍵考慮因素之一,對(duì)系統(tǒng)性能有重要影響.此節(jié)通過(guò)改變CPN模型中任務(wù)隊(duì)列的長(zhǎng)度研究評(píng)估其對(duì)響應(yīng)時(shí)間和任務(wù)丟失率的影響.

在CPN模型中固定任務(wù)到達(dá)時(shí)間為恒定值,分別針對(duì)不同的任務(wù)隊(duì)列長(zhǎng)度進(jìn)行仿真.仿真中設(shè)定任務(wù)隊(duì)列長(zhǎng)度區(qū)間為[5,40],對(duì)此區(qū)間內(nèi)不同任務(wù)隊(duì)列長(zhǎng)度對(duì)系統(tǒng)性能的影響進(jìn)行評(píng)估.仿真結(jié)果如圖8所示.

圖8 不同隊(duì)列長(zhǎng)度對(duì)系統(tǒng)性能的影響

由圖8(a)可以看出,Single型任務(wù)和MPI型任務(wù)的響應(yīng)時(shí)間均隨著任務(wù)隊(duì)列長(zhǎng)度的增加而增長(zhǎng).其中, MPI型任務(wù)的響應(yīng)時(shí)間增長(zhǎng)更為顯著,這是因?yàn)镸PI型任務(wù)的執(zhí)行需要多個(gè)計(jì)算節(jié)點(diǎn)并行進(jìn)行,其響應(yīng)時(shí)間對(duì)由任務(wù)隊(duì)列長(zhǎng)度增加而導(dǎo)致的任務(wù)累積更為敏感.觀察圖8(b)可知,當(dāng)任務(wù)隊(duì)列增加到一定長(zhǎng)度時(shí),集群的任務(wù)丟失率并未進(jìn)一步降低,主要原因在于此時(shí)系統(tǒng)的瓶頸在于計(jì)算資源,資源利用率已經(jīng)接近飽和.文中后續(xù)章節(jié)針對(duì)集群系統(tǒng)中計(jì)算節(jié)點(diǎn)數(shù)量對(duì)任務(wù)丟失率的影響進(jìn)行了仿真研究.

3.2.3 計(jì)算節(jié)點(diǎn)數(shù)對(duì)任務(wù)丟失率的影響

此節(jié)在CPN模型中固定任務(wù)到達(dá)時(shí)間間隔為恒定值,并保持任務(wù)隊(duì)列長(zhǎng)度不變,改變模型中計(jì)算節(jié)點(diǎn)的數(shù)量進(jìn)行仿真.仿真中動(dòng)態(tài)調(diào)整集群所包含的計(jì)算節(jié)點(diǎn)數(shù)量,設(shè)定計(jì)算節(jié)點(diǎn)數(shù)量區(qū)間為[10,70],以評(píng)估不同規(guī)模的計(jì)算節(jié)點(diǎn)對(duì)任務(wù)丟失率的影響.

圖9 計(jì)算節(jié)點(diǎn)數(shù)量對(duì)任務(wù)丟失率的影響

觀察圖9可知,維持系統(tǒng)的任務(wù)負(fù)載不變,并保持相同的隊(duì)列長(zhǎng)度,集群系統(tǒng)的任務(wù)丟失率隨著計(jì)算節(jié)點(diǎn)數(shù)的增加迅速下降.可見(jiàn),在因資源使用飽和而導(dǎo)致任務(wù)丟失率較高的情況下,無(wú)論是Single型任務(wù)還是MPI型任務(wù),增加計(jì)算節(jié)點(diǎn)數(shù)量均能夠有效降低任務(wù)丟失率.

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

仿真過(guò)程表明,使用著色Petri網(wǎng)構(gòu)建的層次化模型能夠?qū)Ω咝阅芗旱男阅苓M(jìn)行有效評(píng)估,與隨機(jī)過(guò)程代數(shù)等復(fù)雜方法相比,基于著色Petri網(wǎng)的建模方法層次明晰,建模過(guò)程也相對(duì)簡(jiǎn)潔高效.

4 結(jié)語(yǔ)

當(dāng)今的高性能集群已變得十分龐大,結(jié)構(gòu)也越來(lái)越復(fù)雜,為系統(tǒng)設(shè)計(jì)帶來(lái)了巨大挑戰(zhàn).文中分析了當(dāng)前高性能集群的典型架構(gòu),并基于著色Petri網(wǎng)建立了集群的仿真與分析模型;通過(guò)不同任務(wù)負(fù)載和系統(tǒng)配置對(duì)高性能集群的性能進(jìn)行仿真,預(yù)測(cè)并評(píng)估了關(guān)鍵參數(shù)對(duì)系統(tǒng)性能的影響,以期望在設(shè)計(jì)階段為系統(tǒng)優(yōu)化提供參考.相對(duì)于形式化方法,文中提出的建模方法有效抑制了狀態(tài)空間爆炸問(wèn)題.建立更為精確的系統(tǒng)模型以及提高模型的自動(dòng)化仿真能力是后續(xù)需要完成的工作.

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伍康文,柴華.微服務(wù)器集群架構(gòu)的綠色云計(jì)算平臺(tái).計(jì)算機(jī)系統(tǒng)應(yīng)用,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屈婉霞,李暾,郭陽(yáng),楊曉東.謂詞抽象技術(shù)研究.計(jì)算機(jī)研究與發(fā)展,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劉偉,尹行,段玉光,杜薇,王偉,曾國(guó)蓀.同構(gòu)DVS集群中基于自適應(yīng)閾值的并行任務(wù)節(jié)能調(diào)度算法.計(jì)算機(jī)學(xué)報(bào), 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劉志強(qiáng),宋君強(qiáng),盧風(fēng)順,趙娟.基于線程的MPI通信加速器技術(shù)研究.計(jì)算機(jī)學(xué)報(bào),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

國(guó)家自然科學(xué)基金(61502438)

2016-08-18;收到修改稿時(shí)間:2016-09-23

10.15888/j.cnki.csa.005735