基于掛靠合成的動態(tài)多DAG調(diào)度.pdf

1、DAG調(diào)度問題是指，在多個任務(wù)節(jié)點(diǎn)情況下，任務(wù)之間有數(shù)據(jù)依賴，進(jìn)而可以構(gòu)成一張有向無環(huán)圖，我們的問題就是給出一種調(diào)度策略，既滿足各個任務(wù)之間的的基本數(shù)據(jù)依賴關(guān)系，又可以盡可能快速的完成任務(wù)。
　　動態(tài)多DAG調(diào)度問題是指多個DAG任務(wù)同時進(jìn)入一個系統(tǒng)時，給出一個算法框架以及優(yōu)先級安排的策略，使得多個DAG的調(diào)度平均時長最短。這類問題屬于NP難解問題，所以一般情況下都會利用近似算法進(jìn)行解決。Planner-guided算法是用來解決

2、多DAG調(diào)度問題的比較流行的方法之一，但是該方法存在一些固有的漏洞，即優(yōu)先級對于單個DAG的不公平性以及單個Node調(diào)度之后對于后續(xù)子節(jié)點(diǎn)調(diào)度會產(chǎn)生影響。本文在Planner-guided算法的框架前提下，提出了新的優(yōu)先級標(biāo)定方法與策略框架流程的優(yōu)化。具體改進(jìn)的算法過程為，當(dāng)一個新的DAG進(jìn)入到系統(tǒng)中時，首先計算每一個DAG任務(wù)組中節(jié)點(diǎn)的各自優(yōu)先級（通過HEFT算法）。第二步通過利用系統(tǒng)中最高EFT與新DAG的EST進(jìn)行計算，將剩余節(jié)點(diǎn)

3、掛靠到新DAG上從而合成一個總DAG。在此之后需要計算每個節(jié)點(diǎn)在總DAG中的優(yōu)先級，并且按照新的優(yōu)先級對所有的Node進(jìn)行從大到小的排序，從而可以選出當(dāng)前準(zhǔn)備就緒并且優(yōu)先級相對較高的節(jié)點(diǎn)集合進(jìn)行調(diào)度。
　　在分配總DAG中的節(jié)點(diǎn)到處理機(jī)上的時候，需要向前看其子節(jié)點(diǎn)的分配情況，即考察當(dāng)前節(jié)點(diǎn)的關(guān)鍵字節(jié)點(diǎn)在其父節(jié)點(diǎn)分配后所受到的延遲情況，并且將其考慮到對于處理記得選擇上。本文也提出了對于Planner-guided算法的框架的改進(jìn)，加