網(wǎng)絡(luò)并行計算環(huán)境中基于多處理機(jī)任務(wù)的調(diào)度研究.pdf

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

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

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