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

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

2、，同時(shí)結(jié)合任務(wù)間有空閑可插入的思想，重點(diǎn)針對(duì)異構(gòu)環(huán)境設(shè)計(jì)了基于任務(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)度算法因?yàn)闆]有考慮到鏈?zhǔn)椒磻?yīng)現(xiàn)象，導(dǎo)致算法結(jié)果不夠理想。而TDICMA充分考慮到了連鎖鏈?zhǔn)椒磻?yīng)。
　　最后，實(shí)現(xiàn)開發(fā)了分布式任務(wù)調(diào)度算法的綜合比較系統(tǒng)，可以自動(dòng)隨機(jī)生成大量測(cè)試用例，通過這個(gè)系統(tǒng)詳細(xì)分析了有向無環(huán)圖(Directed Acyclic Graph，DAG)中各部分屬性對(duì)算法結(jié)果和性能的影響?；诖讼到y(tǒng)可以與國(guó)內(nèi)外典型的分布式調(diào)度算法進(jìn)行比較，實(shí)驗(yàn)重點(diǎn)比較了DCPD，HE