面向異構(gòu)系統(tǒng)的可靠性任務(wù)調(diào)度算法研究.pdf

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

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

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

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