【摘要】：隨著多核技術(shù)以及多線程技術(shù)的發(fā)展,多線程在多核處理器上的調(diào)度問題成為研究熱點(diǎn)。由于多核處理器結(jié)構(gòu)的復(fù)雜性,使得資源管理更困難。當(dāng)多線程在多核平臺(tái)上運(yùn)行時(shí),怎樣更好的利用多核資源,讓多線程能夠正確快速的執(zhí)行,決定了系統(tǒng)性能的提高。一個(gè)優(yōu)秀的針對(duì)多核處理器的線程調(diào)度算法可以有效利用資源,提高系統(tǒng)吞吐率,兼顧公平性,降低程序的響應(yīng)時(shí)間和周轉(zhuǎn)時(shí)間。對(duì)于多核多線程的調(diào)度方法的研究,一般都先提出一種多線程的模型,并在這種模型的基礎(chǔ)上針對(duì)不同的多核平臺(tái)提出不同的調(diào)度方法。在多線程模型上,很多人都選擇DAG圖,但是傳統(tǒng)的DAG圖有其自身的缺陷,例如不能對(duì)任務(wù)間的關(guān)系進(jìn)行近一步的刻畫。本文針對(duì)具有臨界區(qū)的線程,提出一種基于Forest的多線程調(diào)度模型,通過該模型維護(hù)線程間的前后依賴、數(shù)據(jù)資源和共享資源關(guān)系。為有效的提高系統(tǒng)性能,減少計(jì)算資源空閑時(shí)間,提出了綜合考慮線程共享資源情況以及前后依賴關(guān)系的調(diào)度方法CSTS算法。該算法以臨界區(qū)作為線程間共享資源的依據(jù),對(duì)具有相同臨界區(qū)線程進(jìn)行同核調(diào)度。并且由于臨界區(qū)不可同時(shí)執(zhí)行的特點(diǎn),臨界區(qū)成為限制系統(tǒng)整體性能的重要因素。為減少由臨界區(qū)而造成的堵塞,算法提出了基于臨界區(qū)的優(yōu)先級(jí)計(jì)算方法,并且兼顧公平性。在多核處理器中,由于各核間計(jì)算能力的不同,異構(gòu)多核處理器較同構(gòu)多核處理器更具有實(shí)用性。因此,本文除針對(duì)一般多核處理器設(shè)計(jì)了多線程模型以及基于該森林模型的調(diào)度方法外,還針對(duì)異構(gòu)多核處理器各核間處理能力的不同,優(yōu)化了加速臨界區(qū)算法。加速臨界區(qū)算法可以有效縮短具有臨界區(qū)的線程的執(zhí)行時(shí)間,但是有可能會(huì)造成無關(guān)臨界區(qū)串行化的問題。本文在加速臨界區(qū)算法基礎(chǔ)上提出改進(jìn)加速臨界區(qū)算法。該算法跟蹤記錄所有包含臨界區(qū)的線程在核上的執(zhí)行情況,對(duì)線程的優(yōu)先級(jí)因子進(jìn)行調(diào)整,通過該優(yōu)先級(jí)因子指導(dǎo)線程在高速核與低速核間的動(dòng)態(tài)遷移。該算法不僅加速了臨界區(qū)的執(zhí)行而且能有效解決加速臨界區(qū)方法所造成的線程在高速核上的堵塞的問題。本文采用模擬實(shí)驗(yàn)的方法對(duì)基于森林線程模型的算法進(jìn)行模擬驗(yàn)證。較同類算法對(duì)于臨界區(qū)密集型任務(wù)具有較高的性能,核利用率也較高。針對(duì)于適應(yīng)于異構(gòu)平臺(tái)改進(jìn)臨界區(qū)遷移算法,本文采用Simics仿真平臺(tái)進(jìn)行異構(gòu)多核系統(tǒng)仿真,輸入為12個(gè)臨界區(qū)密集型負(fù)載,實(shí)驗(yàn)結(jié)果表明,該方法較原始加速臨界區(qū)算法和樸素算法擁有更好的性能。
[Abstract]:With the development of multi-core technology and multi-thread technology, the scheduling problem of multi-thread on multi-core processor has become a hotspot. Because of the complexity of multi-core processor architecture, resource management is more difficult. When multi-thread is running on multi-core platform, how to make better use of multi-core resources, so that multi-thread can execute correctly and quickly, determines the improvement of system performance. An excellent thread scheduling algorithm for multi-core processors can effectively utilize resources, improve system throughput, take fairness into account, and reduce program response time and turnaround time. For the research of multi-core multi-thread scheduling methods, a multi-thread model is proposed firstly, and based on this model, different scheduling methods are proposed for different multi-core platforms. In multithreading model, many people choose DAG diagram, but the traditional DAG graph has its own defects, such as the relationship between tasks can not be further described. In this paper, a multi-thread scheduling model based on Forest is proposed for threads with critical region. The model maintains the relationship among threads, data resources and shared resources. In order to improve the performance of the system and reduce the idle time of computing resources, a scheduling method, CSTS algorithm, is proposed, which considers the resource sharing of threads and the relationship between threads and dependencies. The algorithm uses the critical region as the basis for sharing resources among threads, and schedules the threads with the same critical region with the same core. Because the critical region can not be executed simultaneously, the critical region becomes an important factor that limits the overall performance of the system. In order to reduce the blockage caused by the critical region, the algorithm proposes a priority calculation method based on the critical region and takes fairness into account. In multi-core processors, heterogeneous multi-core processors are more practical than isomorphic multi-core processors because of their different computing power. Therefore, in addition to designing multi-thread model and scheduling method based on the forest model for general multi-core processors, this paper also optimizes the accelerated critical region algorithm for the different processing capabilities of different cores of heterogeneous multi-core processors. The accelerated critical region algorithm can effectively shorten the execution time of threads with critical region, but it may cause serialization of independent critical regions. This paper presents an improved accelerated critical region algorithm based on the accelerated critical region algorithm. The algorithm tracks the execution of all threads with critical region on the kernel, adjusts the priority factor of the thread, and guides the dynamic migration of the thread between the high speed kernel and the low speed kernel. The algorithm not only accelerates the execution of the critical region but also effectively solves the problem of thread blockage on the high speed kernel caused by the accelerated critical region method. In this paper, the algorithm based on forest thread model is simulated and verified by simulation experiment. Compared with similar algorithms, it has higher performance for critical region intensive tasks and higher kernel utilization ratio. In order to adapt to the improved critical region migration algorithm for heterogeneous platforms, this paper uses Simics simulation platform to simulate heterogeneous multi-core systems, and inputs 12 critical zone intensive loads. The experimental results show that, This method has better performance than the original accelerated critical region algorithm and naive algorithm.
【學(xué)位授予單位】：華北電力大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP332

【參考文獻(xiàn)】

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

1 吳琳;;基于共享數(shù)據(jù)關(guān)系的線程調(diào)度策略[J];航空計(jì)算技術(shù);2015年03期

2 黃姝娟;朱怡安;李兵哲;陸偉;;具有依賴關(guān)系的周期任務(wù)實(shí)時(shí)調(diào)度方法[J];計(jì)算機(jī)學(xué)報(bào);2015年05期

3 李靜梅;孫冬微;韓啟龍;;基于異構(gòu)CMP的靜態(tài)任務(wù)調(diào)度研究[J];小型微型計(jì)算機(jī)系統(tǒng);2014年12期

4 湯元斌;;多線程模擬進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度算法研究[J];四川文理學(xué)院學(xué)報(bào);2014年05期

5 楊茂林;雷航;廖勇;;一種共享資源敏感的實(shí)時(shí)任務(wù)分配算法[J];計(jì)算機(jī)學(xué)報(bào);2014年07期

6 李艷華;張悠慧;王為;鄭緯民;;延時(shí)敏感的推測(cè)多線程調(diào)度策略[J];計(jì)算機(jī)工程與科學(xué);2013年11期

7 王磊;劉道福;陳云霽;陳天石;李玲;;片上多核處理器共享資源分配與調(diào)度策略研究綜述[J];計(jì)算機(jī)研究與發(fā)展;2013年10期

8 王桂彬;楊學(xué)軍;徐新海;林一松;李鑫;;異構(gòu)系統(tǒng)功耗感知的并行循環(huán)調(diào)度方法[J];軟件學(xué)報(bào);2011年09期

相關(guān)博士學(xué)位論文 前1條

1 岳虹;嵌入式異構(gòu)多核處理器設(shè)計(jì)與實(shí)現(xiàn)關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2006年

相關(guān)碩士學(xué)位論文 前4條

1 李滋田;基于OpenMP的多核多線程負(fù)載均衡調(diào)度策略研究[D];西安工業(yè)大學(xué);2014年

2 徐元旭;SIMT線程調(diào)度模型分析及優(yōu)化[D];哈爾濱工業(yè)大學(xué);2013年

3 陳文艷;異構(gòu)多核處理器的任務(wù)調(diào)度策略研究[D];湖南大學(xué);2013年

4 黃振寶;面向嵌入式異構(gòu)多核體系的軟硬件協(xié)同任務(wù)調(diào)度方法[D];浙江大學(xué);2007年

，

本文編號(hào)：2278687