【摘要】：傳統(tǒng)的單核處理器主要借助提升主頻或增加指令級(jí)并行度來(lái)提高處理器性能,但主頻提升帶來(lái)了功耗急劇增加及電流泄露等問(wèn)題,而指令級(jí)并行度又受到指令間數(shù)據(jù)相關(guān)、控制相關(guān)以及結(jié)構(gòu)相關(guān)的限制,很難進(jìn)一步提高單核處理器性能。多核處理器以其高主頻、低功耗和高并行性等優(yōu)點(diǎn)迅速成為當(dāng)前處理器發(fā)展主流,備受廣大用戶和研究者青睞。由于處理器有多個(gè)內(nèi)核,要提高多核處理器整體性能就必需充分發(fā)揮每一個(gè)內(nèi)核的作用,單核處理器的任務(wù)調(diào)度算法并不適合多核處理器,而多核處理器任務(wù)調(diào)度已經(jīng)被證明為NP完全問(wèn)題,因此如何利用高效的任務(wù)調(diào)度算法使多核處理器充分發(fā)揮其性能成為當(dāng)前研究熱點(diǎn)之一。由于動(dòng)態(tài)任務(wù)調(diào)度比靜態(tài)任務(wù)調(diào)度具有較高性價(jià)比,所以本文圍繞異構(gòu)多核處理器對(duì)動(dòng)態(tài)任務(wù)調(diào)度算法進(jìn)行研究。通過(guò)分析現(xiàn)有動(dòng)態(tài)調(diào)度算法的基本原理和執(zhí)行過(guò)程,結(jié)合負(fù)載均衡策略,提出一種DSMDQ動(dòng)態(tài)調(diào)度器模型。DSMDQ采用集中式調(diào)度模式,便于控制內(nèi)核的任務(wù)調(diào)度情況,根據(jù)異構(gòu)多核處理器內(nèi)核處理性能差異設(shè)置內(nèi)核負(fù)載上下限,控制各個(gè)內(nèi)核負(fù)載保持在同一活躍水平,實(shí)現(xiàn)負(fù)載均衡;使用全局調(diào)度隊(duì)列和局部調(diào)度隊(duì)列結(jié)合的方式,在克服集中式調(diào)度模式性能瓶頸的同時(shí)降低調(diào)度頻率,從而減少調(diào)度消耗時(shí)間。在DSMDQ基礎(chǔ)上設(shè)計(jì)了一種基于異構(gòu)多核處理器的STDS動(dòng)態(tài)任務(wù)調(diào)度算法,算法采用基于優(yōu)先級(jí)列表的啟發(fā)式調(diào)度思想,依據(jù)等待時(shí)間長(zhǎng)短、任務(wù)間通信大小和內(nèi)核負(fù)載輕重三種因素計(jì)算任務(wù)優(yōu)先級(jí),調(diào)度時(shí)優(yōu)先分配優(yōu)先級(jí)最高的任務(wù);STDS算法為調(diào)節(jié)這三種因素對(duì)優(yōu)先級(jí)的影響比重,引入了實(shí)時(shí)因子、負(fù)載因子等參數(shù),可以滿足不同的應(yīng)用需求。本文最后對(duì)SDTS算法進(jìn)行實(shí)驗(yàn)驗(yàn)證,選擇調(diào)度時(shí)間、負(fù)載均衡和任務(wù)等待時(shí)間作為評(píng)價(jià)指標(biāo),使用TGFF工具生成不同特性的隨機(jī)任務(wù)圖作為測(cè)試用例,并在Simics模擬器上觀察算法執(zhí)行結(jié)果。對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)分析表明,STDS算法在內(nèi)核數(shù)目較多系統(tǒng)中具有較好的優(yōu)勢(shì),在保證速度性能的同時(shí)有較理想的內(nèi)核負(fù)載均衡效果。
[Abstract]:The traditional single-core processor mainly improves the performance of the processor by raising the main frequency or increasing the parallelism of instruction level. However, the main frequency upgrade brings problems such as sharp increase in power consumption and leakage of current, and the parallelism of instruction level is dependent on the data between instructions. It is difficult to further improve the performance of single-core processors due to the constraints of control and architecture. Because of its advantages of high main frequency, low power consumption and high parallelism, multicore processor has become the mainstream of processor development, and has been favored by users and researchers. Because the processor has multiple cores, to improve the overall performance of the multi-core processor, it is necessary to give full play to the role of each kernel. The task scheduling algorithm of the single-core processor is not suitable for the multi-core processor. The task scheduling of multi-core processors has been proved to be a complete problem of NP, so how to make use of efficient task scheduling algorithm to give full play to the performance of multi-core processors has become one of the current research hotspots. Because dynamic task scheduling has higher performance-price ratio than static task scheduling, this paper studies dynamic task scheduling algorithm around heterogeneous multi-core processors. By analyzing the basic principle and execution process of the existing dynamic scheduling algorithm and combining the load balancing strategy, a DSMDQ dynamic scheduler model is proposed. The centralized scheduling mode is adopted by DSMDQ to facilitate the task scheduling in the kernel. The upper and lower limits of kernel load are set according to the performance difference of heterogeneous multi-core processor kernel, and each kernel load is kept at the same active level to realize load balancing. Using the combination of global scheduling queue and local scheduling queue, the performance bottleneck of centralized scheduling mode is overcome and the scheduling frequency is reduced, thus reducing the scheduling time. Based on DSMDQ, a dynamic task scheduling algorithm for STDS based on heterogeneous multi-core processor is designed. The algorithm adopts the heuristic scheduling idea based on priority list, according to the waiting time. The task priority is calculated by three factors: the communication size between tasks and the kernel load, and the task with the highest priority is assigned first in scheduling. In order to adjust the influence of these three factors on priority, the STDS algorithm introduces parameters such as real time factor and load factor, which can meet different application requirements. Finally, the SDTS algorithm is verified by experiments. Scheduling time, load balancing and task waiting time are selected as evaluation indexes, and random task diagrams with different characteristics are generated by using TGFF tools as test cases. The algorithm execution results are observed on the Simics simulator. The statistical analysis of the experimental results shows that the STDS algorithm has a good advantage in the system with a large number of kernels, and has an ideal kernel load balancing effect while ensuring the speed performance.
【學(xué)位授予單位】：哈爾濱工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP301.6;TP332

【相似文獻(xiàn)】

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

1 張松慧;熊錦江;;一種針對(duì)非平穩(wěn)網(wǎng)絡(luò)任務(wù)調(diào)度防沖突算法研究[J];科技通報(bào);2013年10期

2 孟憲福;基于優(yōu)先級(jí)的任務(wù)調(diào)度與負(fù)載均衡模型研究[J];小型微型計(jì)算機(jī)系統(tǒng);2005年09期

3 廖曉文;廖京盛;;時(shí)間觸發(fā)模式的任務(wù)調(diào)度與分解策略[J];單片機(jī)與嵌入式系統(tǒng)應(yīng)用;2006年07期

4 樊曉香;;任務(wù)調(diào)度問(wèn)題機(jī)制設(shè)計(jì)[J];計(jì)算機(jī)技術(shù)與發(fā)展;2008年07期

5 黃漾;;分布式環(huán)境下任務(wù)調(diào)度探討[J];電腦知識(shí)與技術(shù);2011年19期

6 陳軍;謝立;孫鐘秀;;分布式任務(wù)調(diào)度研究的新趨向[J];計(jì)算機(jī)研究與發(fā)展;1990年04期

7 陳艇;;基于混沌最優(yōu)博弈的網(wǎng)絡(luò)任務(wù)調(diào)度算法仿真[J];計(jì)算機(jī)仿真;2013年11期

8 李陶深;李明麗;張希翔;;云計(jì)算環(huán)境下任務(wù)調(diào)度技術(shù)的研究進(jìn)展[J];玉林師范學(xué)院學(xué)報(bào);2014年02期

9 劉雄文,陸鑫達(dá);元計(jì)算環(huán)境中任務(wù)調(diào)度的深入分析[J];計(jì)算機(jī)工程與應(yīng)用;2002年17期

10 羅紅,慕德俊,鄧智群,王曉東;網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2005年05期

相關(guān)會(huì)議論文 前10條

1 劉培培;李連;叢海鵬;謝勇;;基于多代理協(xié)商機(jī)制的任務(wù)調(diào)度系統(tǒng)研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集（下）[C];2006年

2 張磊;馬軍;;描述短時(shí)資源混雜占用型任務(wù)調(diào)度的數(shù)學(xué)模型與算法[A];2005年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

3 王軍;巢玉強(qiáng);彭釗軼;;基于任務(wù)調(diào)度的電能量計(jì)量采集系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[A];2006電力系統(tǒng)自動(dòng)化學(xué)術(shù)交流研討大會(huì)論文集[C];2006年

4 張志強(qiáng);王萬(wàn)玉;王建平;李凡;袁剛;;多站多星任務(wù)調(diào)度優(yōu)化模型研究[A];第二十三屆全國(guó)空間探測(cè)學(xué)術(shù)交流會(huì)論文摘要集[C];2010年

5 韓云;于炯;張偉;王命全;;基于負(fù)載均衡的任務(wù)調(diào)度改進(jìn)算法[A];2010年全國(guó)開(kāi)放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集[C];2010年

6 王全民;王靚;許智宏;;網(wǎng)格環(huán)境中基于蟻群算法的批量任務(wù)調(diào)度的研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集（上）[C];2006年

7 張曉云;岳繼光;楊麟祥;;零星任務(wù)調(diào)度在多控制任務(wù)系統(tǒng)中的應(yīng)用[A];第16屆中國(guó)過(guò)程控制學(xué)術(shù)年會(huì)暨第4屆全國(guó)故障診斷與安全性學(xué)術(shù)會(huì)議論文集[C];2005年

8 劉宇;劉玉榮;周冰;;基于WCF的環(huán)境減災(zāi)星座運(yùn)控任務(wù)調(diào)度系統(tǒng)[A];第二十五屆全國(guó)空間探測(cè)學(xué)術(shù)研討會(huì)摘要集[C];2012年

9 黃文澤;邵峰晶;孫仁誠(chéng);;基于雙總線安全結(jié)構(gòu)的操作系統(tǒng)任務(wù)調(diào)度[A];2009全國(guó)計(jì)算機(jī)網(wǎng)絡(luò)與通信學(xué)術(shù)會(huì)議論文集[C];2009年

10 楊艦;黃道平;李小亞;;GDCS任務(wù)調(diào)度的SPN模型研究[A];第二十六屆中國(guó)控制會(huì)議論文集[C];2007年

相關(guān)重要報(bào)紙文章 前7條

1 王波;Linux與服務(wù)器集群技術(shù)[N];中國(guó)計(jì)算機(jī)報(bào);2002年

2 記者 曹繼軍 顏維琦;我國(guó)多核處理器研究實(shí)現(xiàn)新突破[N];光明日?qǐng)?bào);2012年

3 慶廣;多核處理器助力無(wú)線多媒體業(yè)務(wù)拓展[N];中國(guó)電子報(bào);2009年

4 北京大學(xué)計(jì)算語(yǔ)言所副所長(zhǎng) 詹衛(wèi)東;多核服務(wù)器：計(jì)算優(yōu)勢(shì)更上層樓[N];計(jì)算機(jī)世界;2005年

5 北京大學(xué)計(jì)算語(yǔ)言所副所長(zhǎng) 詹衛(wèi)東;雙/多核服務(wù)器 計(jì)算優(yōu)勢(shì)更上層樓[N];網(wǎng)絡(luò)世界;2005年

6 江南計(jì)算技術(shù)研究所 何正未;軟件滯后制約多核應(yīng)用[N];計(jì)算機(jī)世界;2006年

7 李梅　編譯;多核處理器新年井噴[N];計(jì)算機(jī)世界;2007年

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

1 趙凡宇;航天器多目標(biāo)觀測(cè)任務(wù)調(diào)度與規(guī)劃方法研究[D];北京理工大學(xué);2015年

2 孫明明;云計(jì)算平臺(tái)上任務(wù)調(diào)度算法的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

3 張旭;面向網(wǎng)絡(luò)服務(wù)的傳輸協(xié)議設(shè)計(jì)與任務(wù)調(diào)度優(yōu)化[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

4 汪昌健;面向MapReduce計(jì)算模型的調(diào)度技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2015年

5 何華;云計(jì)算的調(diào)度策略研究與性能分析[D];天津大學(xué);2017年

6 陸平;云計(jì)算應(yīng)用中的任務(wù)調(diào)度與資源分配的協(xié)同優(yōu)化[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

7 郭力爭(zhēng);云計(jì)算環(huán)境下資源部署與任務(wù)調(diào)度研究[D];東華大學(xué);2015年

8 黃萬(wàn)偉;基于服務(wù)屬性區(qū)分的可重構(gòu)任務(wù)調(diào)度研究[D];解放軍信息工程大學(xué);2009年

9 瞿進(jìn);可重構(gòu)系統(tǒng)軟硬功能劃分及任務(wù)調(diào)度技術(shù)研究[D];解放軍信息工程大學(xué);2011年

10 周雙娥;實(shí)時(shí)分布容錯(cuò)系統(tǒng)的任務(wù)調(diào)度技術(shù)研究[D];哈爾濱工程大學(xué);2003年

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

1 周智;基于動(dòng)態(tài)任務(wù)調(diào)度的STDS算法設(shè)計(jì)研究[D];哈爾濱工程大學(xué);2015年

2 尤曉非;基于異構(gòu)多核的偽動(dòng)態(tài)任務(wù)調(diào)度研究[D];哈爾濱工程大學(xué);2014年

3 羅棟梁;基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度研究[D];哈爾濱工程大學(xué);2016年

4 張巧龍;云計(jì)算環(huán)境下任務(wù)調(diào)度問(wèn)題的研究[D];江南大學(xué);2015年

5 徐彬;云環(huán)境下基于動(dòng)態(tài)融合遺傳蟻群算法的DAG任務(wù)調(diào)度研究[D];南京信息工程大學(xué);2015年

6 鐘瀟柔;基于動(dòng)態(tài)遺傳算法的云計(jì)算任務(wù)節(jié)能調(diào)度策略研究[D];哈爾濱工業(yè)大學(xué);2015年

7 李婷;分布式爬蟲(chóng)任務(wù)調(diào)度與AJAX頁(yè)面抓取研究[D];電子科技大學(xué);2015年

8 趙彬;基于任務(wù)調(diào)度和動(dòng)態(tài)資源調(diào)整的云計(jì)算節(jié)能機(jī)制及能效分析[D];廣西大學(xué);2015年

9 楊鏡;基于人工免疫系統(tǒng)的云平臺(tái)動(dòng)態(tài)任務(wù)調(diào)度[D];電子科技大學(xué);2014年

10 王一冰;基于ASP.NET的任務(wù)調(diào)度管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2013年

，

本文編號(hào)：2404272