基于Petri網(wǎng)的并行分布計算中的調(diào)度問題的研究.pdf

1、本文基于Petri網(wǎng)模型對調(diào)度問題建模、分析，該方法能夠容易地考慮任務調(diào)度環(huán)境的各種實際限制條件，如共享資源的交替使用，緩沖區(qū)的申請與釋放，任務之間的先后順序等；能夠容易地監(jiān)控任務的并發(fā)執(zhí)行的情形；能夠容易地把模型和搜索算法結(jié)合在一起。
　　本文綜合考慮任務的劃分、通信的協(xié)調(diào)和同步幾個方面的問題。為了獲得低通信延遲和負載平衡的任務調(diào)度方案，我們嘗試把任務圖進行分割，分割的目標是割邊集合的權重最?。ㄍㄐ艜r間最短），分割后各子圖的頂點

2、權重和大體相等（負載平衡）。圖形分割問題本身也是NP問題，我們采用目前已有的啟發(fā)式的分割方法，以獲得次優(yōu)解。
　　其具體步驟是用圖形分割算法分割任務圖，把任務聚族，使得不同族之間任務通訊量最小。根據(jù)任務族的劃分結(jié)果，把同一族任務分配到同一局部環(huán)境（同一節(jié)點，或高速局域網(wǎng)），并借此建立Petri網(wǎng)模型。對同一族內(nèi)任務建立Petri網(wǎng)模型，求解不考慮任務間通訊的局部最優(yōu)的任務調(diào)度方案。對各任務族Petri網(wǎng)同步合成，通過網(wǎng)的合成及合成

3、后一些性質(zhì)尋找全局較優(yōu)的任務調(diào)度解。為了緩解狀態(tài)空間的爆炸問題我們構(gòu)造同步可達圖SRG。同步可達圖SRG只是描述Petri網(wǎng)模塊間同步變遷發(fā)生時的狀態(tài)的變化，而對于模塊內(nèi)局部變遷的發(fā)生引起的狀態(tài)變化則用局部可達樹LRG來描述，由于模塊間的交互相對較少，而同一階段模塊內(nèi)的狀態(tài)變化又相對獨立，無須把它們進行組合，而是分開考慮，這樣降低了問題的組合程度。這種方法對于規(guī)模較大的任務圖Petri網(wǎng)系統(tǒng)可以分塊研究，而任意兩個模塊Petri網(wǎng)的LR