考慮通信和時間限制的異構多核系統(tǒng)調度理論與方法.pdf

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

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

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

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

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

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

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

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