考慮通信和時(shí)間限制的異構(gòu)多核系統(tǒng)調(diào)度理論與方法.pdf

1、異構(gòu)多核處理器具有高性能和靈活性以及低成本和低功耗等特點(diǎn)，使其在工業(yè)、國防、醫(yī)療和通信等諸多領(lǐng)域得到了越來越廣泛的應(yīng)用，它被普遍地認(rèn)為是未來的多核處理器的主要發(fā)展趨勢。對于大而復(fù)雜的應(yīng)用，為了提高計(jì)算系統(tǒng)的性能和滿足應(yīng)用的要求，常常需要將應(yīng)用按照某種規(guī)則劃分成多個各式各樣的任務(wù)。不同的任務(wù)在同一種處理核上執(zhí)行的消耗不同，同一任務(wù)在不同種類的處理核上執(zhí)行的消耗也不相同。鑒于這個原因，要充分地發(fā)揮異構(gòu)多核處理器的優(yōu)勢，還必須對任務(wù)進(jìn)行合理的

2、分配和調(diào)度。任務(wù)分配是指把任務(wù)分配給合適的處理核。任務(wù)調(diào)度除了需要對任務(wù)進(jìn)行分配外，還需要確定任務(wù)在處理核上的執(zhí)行順序。隨著“綠色計(jì)算”需求的提出，如何減少各種計(jì)算系統(tǒng)在執(zhí)行應(yīng)用時(shí)所消耗的資源、能量和預(yù)算等成本問題已經(jīng)成為當(dāng)前工業(yè)界和學(xué)術(shù)界共同關(guān)注和研究的熱點(diǎn)。高效的任務(wù)分配和任務(wù)調(diào)度策略不僅可以減少計(jì)算系統(tǒng)所消耗的能量和成本，還可以降低溫度和提高計(jì)算系統(tǒng)的可靠性。
　　目前為止，關(guān)于任務(wù)分配和任務(wù)調(diào)度問題的研究，大多數(shù)工作面向同

3、構(gòu)計(jì)算系統(tǒng)，只有少數(shù)工作面向異構(gòu)計(jì)算系統(tǒng)。由于同構(gòu)計(jì)算系統(tǒng)和異構(gòu)計(jì)算系統(tǒng)之間存在著差異，基于同構(gòu)計(jì)算系統(tǒng)的任務(wù)分配和調(diào)度技術(shù)不能有效地解決基于異構(gòu)多核系統(tǒng)的任務(wù)分配和調(diào)度問題。對于少數(shù)面向異構(gòu)計(jì)算系統(tǒng)的工作，有些考慮周期性實(shí)時(shí)任務(wù)，有些考慮同構(gòu)的通信鏈接，有些不考慮通信，有些不考慮時(shí)間限制。實(shí)際生活中，很多應(yīng)用對時(shí)間有著嚴(yán)格的要求，如嵌入式實(shí)時(shí)設(shè)備、移動通信設(shè)備、工業(yè)控制、數(shù)字多媒體、航空航天、國防等。對于某些應(yīng)用，如果不能滿足時(shí)間要求

4、，就會造成嚴(yán)重的后果。此外，通信普遍存在于很多計(jì)算系統(tǒng)中且是不可忽視的。因此，有必要研究異構(gòu)多核計(jì)算系統(tǒng)中考慮通信和時(shí)間限制的任務(wù)分配和任務(wù)調(diào)度問題。
　　本文圍繞異構(gòu)多核系統(tǒng)中的任務(wù)分配和任務(wù)調(diào)度兩個方面展開了研究，目標(biāo)均是最小化系統(tǒng)的成本。成本指的是任務(wù)分配和調(diào)度問題中提到的諸如能耗和金錢等開銷的抽象表示。假設(shè)在任務(wù)分配的研究中有足構(gòu)多的處理核，而在任務(wù)調(diào)度的研究中只有有限個處理核。一般的任務(wù)分配和調(diào)度問題是NP完全問題。將給

5、定的應(yīng)用建模成一個有向無環(huán)的數(shù)據(jù)流圖，探索了不同情況下的任務(wù)分配和任務(wù)調(diào)度方法。
　　首先，研究了異構(gòu)多核系統(tǒng)中在時(shí)間限制下考慮通信的任務(wù)分配問題(TCTAC)。針對TCTAC問題實(shí)例的數(shù)據(jù)流圖是路徑和樹的特殊情況，采用動態(tài)規(guī)劃方法設(shè)計(jì)了兩種最優(yōu)的任務(wù)分配算法，路徑分配算法和樹分配算法。路徑分配算法用于求解路徑型數(shù)據(jù)流圖的應(yīng)用，樹分配算法用于求解樹型數(shù)據(jù)流圖的應(yīng)用。
　　接著，針對TCTAC問題實(shí)例的數(shù)據(jù)流圖是通用的有向無環(huán)

6、圖的情況，建立了整數(shù)線性規(guī)劃(ILP)模型，并提出了擴(kuò)展樹分配算法。ILP模型用于求解問題的最優(yōu)解，但其計(jì)算復(fù)雜度隨著有向無環(huán)圖規(guī)模的增大呈指數(shù)級增長。當(dāng)有向無環(huán)圖的規(guī)模比較大時(shí)，ILP不能在可接受的計(jì)算時(shí)間內(nèi)求出最優(yōu)解。擴(kuò)展樹分配算法是一種啟發(fā)式算法，它克服了ILP模型的不足，可以為大規(guī)模的問題實(shí)例提供次優(yōu)解。
　　然后，研究了異構(gòu)多核系統(tǒng)中在時(shí)間限制下考慮通信的任務(wù)調(diào)度問題(TSCT)。針對TSCT問題實(shí)例的數(shù)據(jù)流圖是有向無環(huán)

7、圖的情況，提出了一種啟發(fā)式任務(wù)調(diào)度算法，比率局部時(shí)間限制(RLD)算法。RLD算法首先計(jì)算每個任務(wù)的優(yōu)先級，確定任務(wù)的調(diào)度順序。其次，依據(jù)給定的全局截止時(shí)間為每個任務(wù)分配一個局部截止時(shí)間。然后，按照調(diào)度順序在每個任務(wù)的局部截止時(shí)間內(nèi)調(diào)度該任務(wù)，并用一個成本/時(shí)間比例來確定每個任務(wù)的分配。最后，調(diào)整相關(guān)參數(shù)的值以獲取更多成功的調(diào)度方案，并從所有滿足全局截止時(shí)間的調(diào)度方案中選取具有最小成本的調(diào)度方案作為所有任務(wù)的最終調(diào)度方案。
　　最

8、后，針對TSCT問題實(shí)例的數(shù)據(jù)流圖是有向無環(huán)圖的情況，提出了改進(jìn)的安全圖聚集(ISGG)算法和比率局部時(shí)間限制分組(RLDG)算法。ISGG算法服務(wù)于RLDG算法，它將給定的數(shù)據(jù)流圖中的所有任務(wù)分成若干個組，保證分組均衡并且使得分組后新形成的數(shù)據(jù)流圖仍然是一個有向無環(huán)圖，目的是減少任務(wù)調(diào)度時(shí)產(chǎn)生的通信開銷和增加調(diào)度的靈活性。RLDG算法是一種啟發(fā)式任務(wù)調(diào)度算法，其主要思想與RLD算法類似，不同之處在于它以組為單位進(jìn)行任務(wù)調(diào)度。RLDG算