本文選題：異構(gòu)多核　切入點(diǎn)：分層　出處：《湖南大學(xué)》2013年碩士論文

【摘要】：多核處理器的起跳主頻比單核處理器低，性能更好，多核處理器已經(jīng)成為當(dāng)今的主流處理器。多核處理器根據(jù)系統(tǒng)的內(nèi)核結(jié)構(gòu)是否存在差異，可以分為同構(gòu)多核處理器和異構(gòu)多核處理器。異構(gòu)多核處理器能更好地處理異構(gòu)的應(yīng)用程序，比如，快速復(fù)雜的核可以執(zhí)行串行代碼部分，而較簡單的核則能并行處理數(shù)字，這樣不僅能提高處理器系統(tǒng)的性能，而且能節(jié)省能耗。研究人員普遍相信異構(gòu)多核處理器將是未來多核處理器發(fā)展的趨勢，同時(shí)，異構(gòu)多核處理器的發(fā)展也為任務(wù)調(diào)度與負(fù)載均衡的研究提供了廣闊的發(fā)展空間。 本文對現(xiàn)有的任務(wù)調(diào)度算法和任務(wù)調(diào)度模型進(jìn)行改進(jìn)，提出了一種負(fù)載均衡的異構(gòu)多核處理器的任務(wù)調(diào)度算法，并對提出的算法進(jìn)一步優(yōu)化，充分考慮核間的負(fù)載均衡問題，本文主要工作包括以下幾個(gè)方面： (1)對現(xiàn)有的調(diào)度模型和方法進(jìn)行分析，提出了一種負(fù)載均衡的啟發(fā)式任務(wù)調(diào)度算法，該算法考慮了多核處理器系統(tǒng)的異構(gòu)性和任務(wù)間的依賴關(guān)系，將任務(wù)間的依賴關(guān)系用DAG(Directed Acyclic Graph)模型來刻畫。首先，該算法將DAG圖中表示的任務(wù)根據(jù)任務(wù)的入度值對任務(wù)集進(jìn)行分層，經(jīng)過分層處理的DAG圖消除了任務(wù)間的數(shù)據(jù)依賴和控制依賴，，能確保同層的任務(wù)盡可能的并行執(zhí)行；然后，將每層內(nèi)的任務(wù)調(diào)度到相應(yīng)的處理器核上，在將任務(wù)調(diào)度到處理器核上時(shí)，充分考慮核的異構(gòu)性，根據(jù)核的計(jì)算能力給不同的核分配不同的負(fù)載。模擬實(shí)驗(yàn)結(jié)果表明，提出的任務(wù)調(diào)度策略在調(diào)度長度和負(fù)載均衡方面要優(yōu)于其他的任務(wù)調(diào)度算法，優(yōu)化了異構(gòu)多核處理器系統(tǒng)的性能。 (2)通過分析任務(wù)間負(fù)載均衡的影響因素，發(fā)現(xiàn)提出的調(diào)度算法雖然避免了誤差的累積現(xiàn)象，但是存在單個(gè)核誤差并沒有減少的問題，這在一定程度上影響了核間的負(fù)載均衡，針對此問題，考慮負(fù)載均衡影響因素，改進(jìn)提出的任務(wù)調(diào)度算法，即在任務(wù)組調(diào)度階段，在找到使核總耗時(shí)剛好小于等于核參考值的最后一個(gè)任務(wù)時(shí)，還可以繼續(xù)從最小的任務(wù)開始增加任務(wù)，盡可能的減少單個(gè)核的誤差。為了進(jìn)一步提高計(jì)算精度，設(shè)計(jì)了一種誤差下降調(diào)度方案，該方案將誤差大的核上的任務(wù)集進(jìn)行合并，再將合并的任務(wù)集重新調(diào)度到相應(yīng)的核上，保證單個(gè)核的誤差降到最低。
[Abstract]:The take-off frequency of multi-core processors is lower than that of single-core processors, and the performance of multi-core processors is better than that of single-core processors. It can be divided into isomorphic multicore processors and heterogeneous multicore processors. Heterogeneous multicore processors can better handle heterogeneous applications. For example, fast and complex cores can execute serial code parts, while simpler cores can process numbers in parallel. This will not only improve the performance of processor systems, but also save energy. Researchers generally believe that heterogeneous multicore processors will be the trend of future multi-core processors, at the same time, The development of heterogeneous multi-core processors also provides a broad development space for task scheduling and load balancing. In this paper, the existing task scheduling algorithms and task scheduling models are improved, and a load-balanced task scheduling algorithm for heterogeneous multi-core processors is proposed. The proposed algorithm is further optimized to take full account of the load balancing problem between cores. The main work of this paper includes the following aspects:. 1) based on the analysis of the existing scheduling models and methods, a load balancing heuristic task scheduling algorithm is proposed, which takes into account the heterogeneity of multi-core processor systems and the dependencies between tasks. The dependencies between tasks are described by DAG(Directed Acyclic Graph.Firstly, the tasks represented in the DAG graph are stratified according to the degree of the task, and the hierarchical DAG graph eliminates the data dependency and control dependency between the tasks. It can ensure that the tasks in the same layer are executed in parallel as much as possible; then, the tasks in each layer are scheduled to the corresponding processor core, and the heterogeneity of the core is taken into account when scheduling the task to the processor core. The simulation results show that the proposed task scheduling strategy is superior to other task scheduling algorithms in terms of scheduling length and load balancing. The performance of heterogeneous multi-core processor system is optimized. 2) by analyzing the influencing factors of load balancing between tasks, it is found that the proposed scheduling algorithm avoids the accumulation of errors, but there is a problem that the single kernel error has not been reduced, which to some extent affects the load balance between cores. In order to solve this problem, considering the influence factors of load balancing, the proposed task scheduling algorithm is improved, that is, in the task group scheduling stage, when the last task with the total kernel time is just less than or equal to the kernel reference value, In order to further improve the calculation accuracy, an error descent scheduling scheme is designed, in which the task sets on the kernel with large errors are merged. Then the merged task set is rescheduled to the corresponding kernel to ensure that the error of the single core is minimized.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2013
【分類號】：TP332

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 鐘求喜,謝濤,陳火旺;基于遺傳算法的任務(wù)分配與調(diào)度[J];計(jì)算機(jī)研究與發(fā)展;2000年10期

2 李慶華,韓建軍,Abbas A.Essa;同構(gòu)計(jì)算環(huán)境中一種快速有效的靜態(tài)任務(wù)調(diào)度算法[J];計(jì)算機(jī)研究與發(fā)展;2005年01期

3 袁道華;;分布式系統(tǒng)負(fù)載分布研究綜述[J];計(jì)算機(jī)科學(xué);1994年01期

4 周笑波;汲化;謝立;;一個(gè)基于PVM的異構(gòu)型智能分布式任務(wù)調(diào)度系統(tǒng)[J];計(jì)算機(jī)科學(xué);1996年06期

5 何琨;趙勇;黃文奇;;基于任務(wù)復(fù)制的分簇與調(diào)度算法[J];計(jì)算機(jī)學(xué)報(bào);2008年05期

6 林成江，李三立;一種可適應(yīng)的分布式動態(tài)負(fù)載平衡策略及其仿真[J];計(jì)算機(jī)學(xué)報(bào);1995年10期

7 彭蔓蔓;徐立超;王穎;;異構(gòu)多核處理器的任務(wù)分配及能耗的研究[J];計(jì)算機(jī)應(yīng)用研究;2010年05期

8 張建軍;李慶華;瞿勇;;基于任務(wù)復(fù)制的調(diào)度算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2009年08期

9 阮幼林 ,劉干 ,朱光喜 ,盧小峰;一個(gè)基于復(fù)制的相關(guān)任務(wù)調(diào)度算法[J];小型微型計(jì)算機(jī)系統(tǒng);2005年03期

10 林劍檸;吳慧中;;一種基于任務(wù)復(fù)制調(diào)度算法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2006年07期

本文編號：1693021