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

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

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

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