網絡并行計算環(huán)境中基于多處理機任務的調度研究.pdf

1、該文就NPC系統(tǒng)的任務調度策略與調度算法進行了較為深入的研究.首先介紹了NPC系統(tǒng)中的基于多處理機任務的調度模型,并在已有工作的基礎上進行了探索和創(chuàng)新,并取得了一定的成果.具體內容體現(xiàn)在如下幾個方面:(1)在全局調度上把NPC系統(tǒng)當成一個異構的多處理機系統(tǒng)來考慮.根據處理機本身的處理能力、處理機之間的通信能力及任務對處理機的不同需求,定義具有多模式的多處理機任務,從而建立NPC系統(tǒng)中的多處理機任務調度模型P<,m>|set|C<,max

2、>.并從理論上探討了該調度模型的近似優(yōu)化問題的難度,在強NP-難的基礎上證明了不存在一個多項式時間的常數(shù)近似比的調度算法.同時,通過對多處理機任務之間的并行關系的分析,得到了一般最優(yōu)調度的下界.(2)研究了3-處理機系統(tǒng)中的規(guī)則調度(Normal schedule),通過比較6個規(guī)則任務之間的時間長度關系,構造了一個最簡單的調度算法,使得其調度時間跨度不超過最優(yōu)調度的5/4倍,并通過一個實例說明該算法得到的是最優(yōu)規(guī)則調度.然后在規(guī)則調度

3、的基礎上進行改進,利用拆分(Partition)和半規(guī)則調度(Semi-normalschedule)方法,將3-處理機系統(tǒng)中由Goemans'保持了數(shù)年之久的世界最好結果7/6改進到了9/8.(3)研究了4-處理機系統(tǒng)中的規(guī)則調度.在組調度(GroupSchedule)的基礎上,改善各處理機的間隙搭配方式,并引入部分調度(Partial schedule)以便充分利用間隙,構造了一系列線性算法.(4)研究了多處理機(≥5)的NPC系統(tǒng)