面向異構系統(tǒng)的可靠性任務調度算法研究.pdf

1、任務調度算法的好壞直接影響到異構計算系統(tǒng)整體的性能，隨著異構計算系統(tǒng)規(guī)模的增大，系統(tǒng)處理器數(shù)目的增加，系統(tǒng)可靠性降低，在其上運行的任務調度算法的可靠性也隨之降低，勢必影響到任務調度算法的效率。傳統(tǒng)的任務調度算法是把任務調度的總長度作為衡量任務調度算法效率的指標，然而可靠性是保證任務調度算法效率的前提。因此，設計基于異構計算系統(tǒng)的任務調度算法時，如何盡可能地提高任務調度算法的可靠性也成為了任務調度算法研究的重點問題之一。
　　提高系

2、統(tǒng)可靠性通常采用軟件冗余和硬件冗余的方法，由于硬件冗余方法需要額外的設備開銷，軟件冗余方法是經常被選用的方法。軟件冗余是通過任務的復制來提高系統(tǒng)可靠性，動態(tài)多副本的復制技術是解決該問題的有效方法。本文研究基于動態(tài)多副本的復制技術，尋找處理器之間傳遞數(shù)據(jù)時的最大可靠性傳輸鏈路，從而實現(xiàn)任務調度算法可靠性最大化；采用處理器之間的并行化特性以降低調度執(zhí)行時間。本文主要工作如下：
　　首先，提出了一種基于副本的最大化可靠性任務調度算法 R

3、MSR（Replication-based Scheduling for Maximizing System Reliability）。該算法通過復制任務形成多個任務副本，任務副本的數(shù)量根據(jù)任務可靠性閾值來確定，保證所提出的算法中的每一個任務的最終可靠性都高于該任務可靠性閾值；同時，該算法考慮了異構計算系統(tǒng)處理器之間的通信可靠性，選擇具有最大可靠性的鏈路進行處理器之間傳遞數(shù)據(jù)傳輸。
　　然后，本文對RMSR算法的模擬實驗是基于兩種

4、不同類型的DAG圖的。一種是隨機生成的DAG圖。在這一類DAG圖中，本文從任務數(shù)量、處理器數(shù)量、并行因子和CCR值四種參數(shù)分別變化的情況下，驗證了RMSR算法的系統(tǒng)可靠性要高于其他兩個已知的算法RASD和HEFT。另一種是實際應用問題的DAG圖。通過實驗結果可以發(fā)現(xiàn)，對于這一類 DAG圖，RMSR算法的系統(tǒng)可靠性最多被輸入任務數(shù)量的大小這一個參數(shù)所影響。實驗證明了本文所提出算法的有效性。
　　最后，本文提出一個基于RMSR算法的并