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

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

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

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