基于任務(wù)復(fù)制和插入的分布式任務(wù)調(diào)度算法研究.pdf

1、具有約束關(guān)系任務(wù)的最優(yōu)化調(diào)度在并行和分布式計算領(lǐng)域扮演著重要的角色。它研究如何將具有約束關(guān)系的多個任務(wù)分配到不同的處理機上執(zhí)行，以最小化調(diào)度的長度(即Makespan)。分布式多任務(wù)調(diào)度問題是NP完全的，除非P=NP，否則在多項式時間內(nèi)不能得到精確解。近幾十年來，研究此問題的學(xué)者不斷在探索怎樣以更低的時間復(fù)雜度和更少的資源開銷來近似求解該調(diào)度問題。
　　基于任務(wù)復(fù)制的啟發(fā)構(gòu)造策略普遍被認為是一個好的求解方向，在基于任務(wù)復(fù)制的模式下

2、，同時結(jié)合任務(wù)間有空閑可插入的思想，重點針對異構(gòu)環(huán)境設(shè)計了基于任務(wù)復(fù)制及插入的聚簇和歸并算法（Task-Duplication and Insertion based Clustering and Merging Algorithm(TDICMA)）。算法主要包括初始分簇，任務(wù)復(fù)制，任務(wù)歸并，任務(wù)插入等階段?；谌蝿?wù)復(fù)制的分布式任務(wù)調(diào)度算法存在鏈?zhǔn)椒磻?yīng)現(xiàn)象（chain reaction phenomenon），本輪無效的任務(wù)復(fù)制可能在下

3、一輪就變成是有效的了。傳統(tǒng)的基于任務(wù)復(fù)制的任務(wù)調(diào)度算法因為沒有考慮到鏈?zhǔn)椒磻?yīng)現(xiàn)象，導(dǎo)致算法結(jié)果不夠理想。而TDICMA充分考慮到了連鎖鏈?zhǔn)椒磻?yīng)。
　　最后，實現(xiàn)開發(fā)了分布式任務(wù)調(diào)度算法的綜合比較系統(tǒng)，可以自動隨機生成大量測試用例，通過這個系統(tǒng)詳細分析了有向無環(huán)圖(Directed Acyclic Graph，DAG)中各部分屬性對算法結(jié)果和性能的影響?；诖讼到y(tǒng)可以與國內(nèi)外典型的分布式調(diào)度算法進行比較，實驗重點比較了DCPD，HE