【摘要】：本文基于Petri網(wǎng)模型對調(diào)度問題建模、分析，該方法能夠容易地考慮任務調(diào)度環(huán)境的各種實際限制條件，如共享資源的交替使用，緩沖區(qū)的申請與釋放，任務之間的先后順序等；能夠容易地監(jiān)控任務的并發(fā)執(zhí)行的情形；能夠容易地把模型和搜索算法結(jié)合在一起。 本文綜合考慮任務的劃分、通信的協(xié)調(diào)和同步幾個方面的問題。為了獲得低通信延遲和負載平衡的任務調(diào)度方案，我們嘗試把任務圖進行分割，分割的目標是割邊集合的權重最小(通信時間最短)，分割后各子圖的頂點權重和大體相等(負載平衡)。圖形分割問題本身也是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)的合成及合成后一些性質(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)的LRG所代表的狀態(tài)又可以是并發(fā)存在的，所以可以并行生成各個LRG。
【學位授予單位】：山東科技大學
【學位級別】：碩士
【學位授予年份】：2006
【分類號】：TP338.6
【圖文】：

二((M;7*城:)}}(M幾。M幾))根據(jù)各個狀態(tài)M的存在時間區(qū)間和M包含的元素(任務)畫出表示調(diào)度方案的Gantt圖如圖.64所示，圖中的粗線把兩族任務分開，粗線上方和下方各表示同族任務可以在局部環(huán)境內(nèi)使用多臺處理機來處理，在局部環(huán)境中不考慮通信開銷。圖中的數(shù)據(jù)1一9表示被執(zhí)行的任務序號，數(shù)據(jù)10表示任務1向任務3、4、5的通信，

【引證文獻】

相關碩士學位論文 前1條

1 田銀花;網(wǎng)格任務調(diào)度模型及算法的Petri網(wǎng)模型研究[D];山東科技大學;2007年

本文編號：2781857