基于第二類Petri網(wǎng)對多處理機的任務(wù)并行性與負(fù)載均衡解

1、基于第二類Petri網(wǎng)對多處理機的任務(wù)并行性與負(fù)載均衡解決方案的建模摘要：當(dāng)一次計算服務(wù)由多個彼此之間存在依賴關(guān)系的運行時任務(wù)組成時，可以用第二類Petri網(wǎng)的結(jié)構(gòu)描述運行時任務(wù)及其之間的依賴關(guān)系和所依賴的數(shù)據(jù)量，并以此作為并行性發(fā)掘的模型。通過計算服務(wù)確定化、構(gòu)建Petri網(wǎng)、求解任務(wù)的等待時間優(yōu)先級，可以得出任務(wù)和處理機的分配關(guān)系，以達到提高并行度、均衡負(fù)載、減少數(shù)據(jù)通信的目標(biāo)。文章將討論該方案的特點，以及其適用環(huán)境。關(guān)鍵詞：并行計算；Petri網(wǎng)；負(fù)載均衡A Model of the Solution of the Task Parallelism and Load Balance un

2、der the Parallelism of Multiprocessors Based on the Class 2 of Petri NetAbstract: If a computing service is composed by several runtime tasks among which dependence relationships exist, the structure of the class 2 of Petri Net can be used to describe the dependence relationships and how much data i

3、s depended among runtime tasks, and it can be regarded as a model for concurrency minding. Via determining computing service, constructing Petri Net, solving the waiting time priority for each task, the distribution mapping can be resolve to achieve the objective of improving the parallelism, balanc

4、ing the load, reducing data communication. The essay will investigate the features of the solution and under which circumstance it is appropriate.Keyword: parallelism computer; Petri Net; load balance0 引言將一次計算服務(wù)中的多個運行時任務(wù)分配到多臺處理機上，進行并行計算是提高運算能力的一種重要的手段，同時也是將計算機的計算能力虛擬化的有效方法。運行時任務(wù)是一次計算服務(wù)中粒度相對較小、功能相對獨立

5、的組件。它與具體的業(yè)務(wù)需求無關(guān)，只是計算機一次處理過程的體現(xiàn)，且具有相對較高的重用性，可以根據(jù)具體的業(yè)務(wù)需求將不同的運行時任務(wù)組裝成為一次具有內(nèi)部邏輯的計算服務(wù)。運行時任務(wù)之間的關(guān)系比較松散，它們之間的主要通過數(shù)據(jù)的輸入輸出相關(guān)聯(lián)，即某個運行時任務(wù)的輸出數(shù)據(jù)被另一個任務(wù)當(dāng)作的輸入數(shù)據(jù)。因此，多個運行時任務(wù)可以被部署到不同的處理機上執(zhí)行。文章將對多任務(wù)、多處理機情況下的并行性發(fā)掘和負(fù)載均衡的解決方案進行建模與討論。1 建模準(zhǔn)備為了使描述求解問題的模型可以的得到適當(dāng)?shù)暮喕?，文章將進行如下合理的假設(shè)：a. 假設(shè)每一個處理機的運算能力相同，且所有的處理機都有能力順利執(zhí)行分配在其上的任務(wù)。b. 假設(shè)每臺

6、處理機擁有足夠容量的外存空間。c. 假設(shè)數(shù)據(jù)拷貝和網(wǎng)絡(luò)傳輸?shù)臅r間消耗只有與數(shù)據(jù)本身的大小有關(guān)。d. 假設(shè)被分配在同一臺處理機上的運行時任務(wù)之間的數(shù)據(jù)傳遞的時間可以忽略不計e. 假設(shè)執(zhí)行每個運行時任務(wù)的時間消耗只與該任務(wù)輸入的數(shù)據(jù)量總和的大小有關(guān)。f. 假設(shè)每個運行時任務(wù)的輸出數(shù)據(jù)的數(shù)目、流向是在構(gòu)造計算服務(wù)時就已經(jīng)確定的。g. 假設(shè)每個運行時任務(wù)每一個條輸出數(shù)據(jù)的數(shù)據(jù)量的大小只取決于該任務(wù)輸入數(shù)據(jù)量總和的大小。文章采用第二類Petri網(wǎng)建立運行時任務(wù)的并行處理模型1。文章中所使用的網(wǎng)可以定義為：元組為一個網(wǎng) (1)文章中所使用的Petri網(wǎng)由四部分組成：a 庫所的集合。b 變遷的集合。c 有向

7、弧的集合；有向弧是上的一個二元關(guān)系，代表令牌的流向。d 令牌的集合；令牌是Petri網(wǎng)中的動態(tài)對象，在庫所和變遷之間沿著有向弧移動，在變遷發(fā)生后令牌的屬性和數(shù)目可能發(fā)生改變。文章采用第二類Petri網(wǎng)建模問題模型。整個計算服務(wù)將被構(gòu)造成為一個Petri網(wǎng)，每個變遷代表一個運行時任務(wù)，令牌代表輸入輸出的數(shù)據(jù)，每個庫所代表其所連接的變遷的數(shù)據(jù)傳遞，數(shù)據(jù)傳遞的方向沿著有向弧的方向進行，傳遞數(shù)據(jù)量的大小以令牌的值來代表。2 建模過程2.1 計算服務(wù)的確定化在組成計算服務(wù)的運行時任務(wù)中，有一些任務(wù)可能會反復(fù)的迭代執(zhí)行，有些任務(wù)可能會在選擇分支中出現(xiàn)。在運行之前，無法確定迭代的次數(shù)，也無法確定所要選擇的分

8、支，所以在建模之前需要消除這些不確定因素，這就需要對計算服務(wù)進行重構(gòu)，或者這一過程可被稱為計算服務(wù)的確定化。不包含迭代和選擇的計算服務(wù)被稱作確定的計算服務(wù)。計算服務(wù)的確定化的方法如流程一所示。流程一 Determine_Computer_Service2.2 構(gòu)造Petri網(wǎng)計算服務(wù)確定化后，所有的控制流程都被隱藏在了運行時任務(wù)的內(nèi)部，每一個運行時任務(wù)就必然會被執(zhí)行一次且只執(zhí)行一次，而且每一個運行時任務(wù)的輸入輸出的數(shù)據(jù)量也是可以確定的。同時Petri網(wǎng)支持層次化的模型描述2，可以將高層次的Petri網(wǎng)中的一個變遷細(xì)化成為下一層次的一張Petri網(wǎng)（如圖一），以此遞推可以將變遷的過程逐步細(xì)化。利

9、用Petri網(wǎng)的這一特性，可以對運行時任務(wù)中的包含的計算服務(wù)進行建模。圖一 Petri的層次結(jié)構(gòu)基于確定的計算服務(wù)構(gòu)造的Petri網(wǎng)的方法如流程二：流程二 Construct_Petri_Net依照上面的算法就構(gòu)造出了可以用于并行性發(fā)掘的第二類Petri網(wǎng)。3 模型特點通過流程Determine_Computer_Service和流程Construct_Petri_Net所構(gòu)造出的Petri網(wǎng)不是任意的。為了說明其特點文章定義了如下概念：假設(shè)=(,;)為一個網(wǎng)，對于變遷，inflow()(,)|(,) 叫做的輸入流，即指向的有向??；outflow()(,)|(,) 叫做的輸出流，即從出發(fā)的有向

10、??；() = | (,)(,)inflow()| 叫做的數(shù)據(jù)入度，對應(yīng)數(shù)據(jù)輸入的個數(shù)，() = |outflow()| 叫做的數(shù)據(jù)出度，對應(yīng)數(shù)據(jù)輸出的個數(shù)。環(huán)的定義如下：假設(shè)=(,;)為一個網(wǎng)，對于一個以一組有向弧串聯(lián)的序列,，其中(i =1, 2 n)，(i =1, 2 n-1)。如果=，則稱上述序列為一個環(huán)。直接先驅(qū)變遷和直接后繼變遷的定義如下：假設(shè)=(,;)為一個網(wǎng)，對于變遷,，使得(,) (,)變遷為變遷的直接先驅(qū)變遷；變遷為位置的直接后繼變遷。所構(gòu)造出的Petri網(wǎng)有兩個主要的特點：1. 每個變遷的輸入流只有一個；2. 網(wǎng)中不包含環(huán)，可以被看作一個無環(huán)的有向圖(ADG)。這些特點是計

11、算服務(wù)確定化的必然結(jié)果。下面對所構(gòu)造Petri網(wǎng)中的兩大特性進行證明：證明1 所構(gòu)造的Petri網(wǎng)中所有變遷的輸入流只有一個根據(jù)流程Construct_Petri_Net，所有向輸入數(shù)據(jù)的變遷，都通過有向弧指向同一個庫所，并且該庫所通過一條有向弧指向，此時|inflow()| = 1，即，輸入流只有一個。證明2 所構(gòu)造的Petri網(wǎng)中沒有環(huán)：假設(shè)Petri網(wǎng)中存在環(huán),，其中(i =1, 2 n)，(i =1, 2 n)，由于經(jīng)過確定化后形成的Petri網(wǎng)中的所有變遷執(zhí)行且只執(zhí)行一次。對于環(huán)上的所有變遷而言，如果可以達成第一次執(zhí)行的條件，則將會是環(huán)上的變遷按照環(huán)上的順序依次循環(huán)執(zhí)行下去。而這與P

12、etri網(wǎng)中的所有變遷執(zhí)行且只執(zhí)行一次矛盾。所以Petri網(wǎng)中的所有變遷執(zhí)行且只執(zhí)行一次。根據(jù)Petri網(wǎng)的遷被允許的規(guī)則，對于變遷，|(,) inflow()都含有令牌時可以被允許，執(zhí)行完成|(,) outflow()含有標(biāo)記時。由于Petri網(wǎng)中所有變遷的入流的個數(shù)都為一，所以必然避免了多個變遷爭奪令牌的情況，使得變遷的執(zhí)行情況唯一確定，同時Petri網(wǎng)中沒有環(huán)的出現(xiàn)就避免了算法陷入死循環(huán)的情況出現(xiàn)3。4 負(fù)載均衡解決方案將Petri網(wǎng)上的變遷分派的不同的處理機上的算法的目的是使處理機的負(fù)載相對平衡，充分利用處理機的運算能力，減少網(wǎng)絡(luò)的數(shù)據(jù)傳輸量。并在此基礎(chǔ)上達到提高運算速度的目的。首先需

13、要對Petri網(wǎng)中的變遷花費的時間和數(shù)據(jù)傳輸花費的時間進行靜態(tài)預(yù)測4。設(shè)映射向量用于存儲Petri網(wǎng)中所有變遷以及部分向弧的消耗時間。變遷所消耗的令牌數(shù)值的總和代表計算的處理時間，記作 = 。沿變遷的輸出流傳遞的令牌的值代表沿數(shù)據(jù)傳輸所消耗的時間，記作 = 。如果把所有變遷和庫所的看成是節(jié)點，把所有在沒有出現(xiàn)的弧和節(jié)點的時間消耗置為0，由于所構(gòu)造的Petri網(wǎng)是一個ADG，則可以通過關(guān)鍵路徑算法求出每個變遷的最早開始時間和最晚開始時間，分別使用映射向量、表示。代表變遷的最早開始時間，代表變遷的最晚開始時間。為變遷的等待時間比，即至少要等待的時間比上實際的執(zhí)行時間。為變遷的等待時間優(yōu)先級，它大致

14、可以表示每個變遷被執(zhí)行的批次。假設(shè)現(xiàn)在有臺處理機同于執(zhí)行運行時任務(wù)，這就意味著我們要進行對原有的網(wǎng)，進行分解成個子網(wǎng)，允許某個子網(wǎng)為空，即處理機可能不執(zhí)行任何任務(wù)。負(fù)責(zé)均衡的實現(xiàn)步驟如流程三。流程三 Load_Banlance對于Petri網(wǎng)中可以細(xì)化成下一層次Petri網(wǎng)的變遷，文章在Determine_Computer_Service流程中將其對應(yīng)的運行時任務(wù)的耗時設(shè)為零，由于對于該類變遷的實際處理并不是在其被分配的處理機上進行，所以在建立本層次Petri網(wǎng)模型時這種假設(shè)是合理的。而當(dāng)執(zhí)行到下一層次的Petri網(wǎng)所對應(yīng)的計算服務(wù)時，則對下一層次的Petri網(wǎng)應(yīng)用流程Load_Banlanc

15、e進行分配，以此方法就可以實現(xiàn)對所建立的層次化的Petri網(wǎng)的模型實現(xiàn)負(fù)載的分配。5 對模型的評價文章所討論的基于第二類Petri網(wǎng)的模型和負(fù)載均衡的解決方案實現(xiàn)了將Petri網(wǎng)中所有變遷分配到各自的處理機上并行地處理的方法。將Petri網(wǎng)中等待時間優(yōu)先級相同或相近的變遷看作是同一時刻可以并行執(zhí)行的單元。同時，本著減少網(wǎng)絡(luò)通信的目標(biāo)，將有數(shù)據(jù)依賴關(guān)系的變遷盡量部署在通信代價較小的處理機上5。該模型與基于有向圖的子圖分割的算法相比，實現(xiàn)相對簡單，與關(guān)鍵路徑算法相比而言，本模型可以利用Petri網(wǎng)的層次結(jié)構(gòu)實現(xiàn)選擇塊和迭代塊的任務(wù)的分配；另外，時間等待優(yōu)先級的應(yīng)用可以使等待了較長時間的任務(wù)可以得到

16、優(yōu)先執(zhí)行，也使該模型可以不必依賴于關(guān)鍵路徑算法具體時間值，而將計算任務(wù)的內(nèi)在并行特性表現(xiàn)為執(zhí)行的批次。對模型的性能進行量化的評價：假設(shè)該計算服務(wù)的所有運行時任務(wù)的串行執(zhí)行，其耗時為。若這些任務(wù)都在同一臺處理機上完成，則不考慮網(wǎng)絡(luò)的時延，近似地， ，即任務(wù)的時間的總和。假設(shè)多處理機并行處理的情況下所用時間為，設(shè)時間提升比用表示。在最壞的情況下，的值將為略小于零的負(fù)數(shù)。這種最壞的情況為所有的運行時任務(wù)必須串執(zhí)行，其每一個任務(wù)的執(zhí)行時間略大于在他前面執(zhí)行的所有任務(wù)實行時間的總和。在最好的情況下，該算法在很大層度上減少運算時間。設(shè)有個處理機，個運行時任務(wù)，遠大于，每個任務(wù)的耗時相同，且彼此之間沒有數(shù)據(jù)

17、，依賴相互獨立。此時，當(dāng)和都很大是，運算速度的提升是十分明顯的。在一般情況下，當(dāng)計算服務(wù)可以分成幾個明顯的階段，階段之間串行執(zhí)行，階段內(nèi)部有較多可以并行的模塊時，該模型中每個變遷的時間等待優(yōu)先級可以與其對應(yīng)任務(wù)的所處的階段相吻合，能夠?qū)⒂嬎惴?wù)的執(zhí)行效率得到提升。6 致謝文章的撰寫和修改受到鄭智捷教授的耐心指導(dǎo)。鄭教授在指導(dǎo)本課題組成員在文章立意和寫作的同時，還以他一絲不茍的科研態(tài)度深深地影響著我們。另外，李浩副教授在文章寫作前對本項目組成員的鼓勵和支持也為文章的完成起到了很大的推動作用。在此謹(jǐn)向鄭智捷教授和李浩副教授表示衷心的感謝并致以崇高的敬意。參考文獻1李彤. 軟件演化過程建模M. 清華大學(xué)出版社，1998. 2Hsu Pm, Chang Y, Chen Y. STRPN: a Petri-Net