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

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

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

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