【摘要】：異構(gòu)多核處理器任務(wù)調(diào)度是高性能計算領(lǐng)域的重要問題。針對優(yōu)先級列表調(diào)度算法中存在的優(yōu)先級排序方法失當(dāng)、調(diào)度結(jié)果不理想的問題,提出一種改進(jìn)的優(yōu)先級列表任務(wù)調(diào)度算法。該算法對傳統(tǒng)優(yōu)先級列表任務(wù)調(diào)度中以任務(wù)執(zhí)行時間平均值作為參數(shù)的優(yōu)先級計算方式進(jìn)行優(yōu)化,提出一種基于異構(gòu)核性能差異性、依賴任務(wù)特征加權(quán)優(yōu)先級的排序方式。在此基礎(chǔ)上,以當(dāng)前格局下每個任務(wù)的向后關(guān)鍵路徑執(zhí)行時間為權(quán)值作為任務(wù)分配到處理器內(nèi)核的依據(jù),克服貪心思想在內(nèi)核選擇中帶來的局部最優(yōu)解問題。此外,在任務(wù)分配階段利用任務(wù)復(fù)制和區(qū)間插入技術(shù),縮短任務(wù)最早開始時間,提高處理器利用率。實(shí)例分析和模擬實(shí)驗結(jié)果表明,該算法可有效降低任務(wù)的執(zhí)行時間,能發(fā)揮異構(gòu)多核處理器優(yōu)勢。
[Abstract]:Heterogeneous multicore processor task scheduling is an important problem in the field of high performance computing. In this paper, an improved priority list task scheduling algorithm is proposed to solve the problem that the priority list scheduling algorithm is not suitable and the scheduling results are not satisfactory. This algorithm optimizes the priority calculation method based on the average of task execution time as the parameter in the traditional priority list task scheduling, and proposes a sort method based on the heterogeneous kernel performance difference and depends on the task feature weighted priority. On this basis, taking the execution time of the backward critical path of each task in the current pattern as the weight of the task assigned to the processor kernel, the problem of local optimal solution caused by the greedy idea in the kernel selection is overcome. In addition, the task replication and interval insertion techniques are used in the task assignment phase to shorten the earliest start time of the task and improve the processor utilization. The results of example analysis and simulation show that the proposed algorithm can effectively reduce the execution time of tasks and take advantage of heterogeneous multi-core processors.
【作者單位】： 哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：國家自然科學(xué)基金(61003036) 黑龍江省基金項目(F201124) Fundamental Research Funds for the Central Universities(HEUCF100606)資助
【分類號】：TP332

【參考文獻(xiàn)】

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

1 王小非;方明;;一種基于調(diào)度簇樹的周期性分布實(shí)時任務(wù)調(diào)度算法[J];計算機(jī)科學(xué);2007年03期

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

3 張建軍;宋業(yè)新;曠文;;基于異構(gòu)環(huán)境的Out-Tree任務(wù)圖的調(diào)度算法[J];計算機(jī)科學(xué);2013年04期

4 曹仰杰;錢德沛;伍衛(wèi)國;董小社;;眾核處理器系統(tǒng)核資源動態(tài)分組的自適應(yīng)調(diào)度算法[J];軟件學(xué)報;2012年02期

【共引文獻(xiàn)】

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

1 劉欣媛;鄭日湖;;網(wǎng)格環(huán)境下一種最優(yōu)任務(wù)調(diào)度算法[J];電腦知識與技術(shù);2010年18期

2 林偉偉;齊德昱;;基于概率冗余調(diào)度的可靠P2P計算模型[J];華南理工大學(xué)學(xué)報(自然科學(xué)版);2010年06期

3 夏冰;李金武;裴斐;鄭秋生;;一種分布式安全評估通信與調(diào)度模型[J];計算機(jī)工程與應(yīng)用;2011年12期

4 徐成;趙林祥;楊志邦;;一種基于多處理器任務(wù)復(fù)制的分簇調(diào)度算法[J];計算機(jī)應(yīng)用研究;2012年08期

5 李葉繁;張凱龍;周興社;;基于眾核處理器的多計算模式構(gòu)造技術(shù)研究[J];計算機(jī)測量與控制;2012年11期

6 賈燕成;黎英;;實(shí)時仿真并行調(diào)度算法研究[J];計算機(jī)工程;2013年01期

7 Hamid TABATABAEE;Mohammad Reza AKBARZADEH-T;Naser PARIZ;;Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems[J];Journal of Zhejiang University-Science C(Computers & Electronics);2014年06期

8 黃金貴;李榮珩;;獨(dú)立多處理機(jī)任務(wù)靜態(tài)調(diào)度問題的近似算法[J];軟件學(xué)報;2010年12期

9 王蕾;崔慧敏;陳莉;馮曉兵;;任務(wù)并行編程模型研究與進(jìn)展[J];軟件學(xué)報;2013年01期

10 李靜梅;張大虎;吳艷霞;孫傳恒;;基于蟻群優(yōu)化算法的異構(gòu)多核線程調(diào)度方法[J];計算機(jī)工程與設(shè)計;2014年06期

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

1 潘玉林;多層次并行與分布實(shí)時仿真平臺關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2010年

2 閻朝坤;網(wǎng)格環(huán)境下的科學(xué)工作流優(yōu)化調(diào)度策略研究[D];中南大學(xué);2013年

3 翟文正;基于模型的異構(gòu)多核嵌入式系統(tǒng)開發(fā)研究[D];上海大學(xué);2013年

4 唐小勇;異構(gòu)并行分布式系統(tǒng)可信調(diào)度理論與方法研究[D];湖南大學(xué);2013年

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

1 趙磊;適應(yīng)多核處理器的任務(wù)調(diào)度研究[D];哈爾濱理工大學(xué);2010年

2 郭鑫;網(wǎng)格計算系統(tǒng)中短作業(yè)調(diào)度模塊的設(shè)計與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2010年

3 李靜;基于多核的任務(wù)調(diào)度策略研究[D];哈爾濱工程大學(xué);2011年

4 王霜;基于關(guān)鍵路徑的網(wǎng)格任務(wù)調(diào)度算法研究[D];合肥工業(yè)大學(xué);2009年

5 潘東;多核環(huán)境任務(wù)分配問題復(fù)雜性及求解模型研究[D];大連理工大學(xué);2009年

6 尹楊美;一種改進(jìn)的異構(gòu)多處理器實(shí)時任務(wù)調(diào)度算法研究[D];湖南大學(xué);2010年

7 賈燕成;基于以太網(wǎng)并行系統(tǒng)實(shí)時仿真調(diào)度算法研究[D];云南大學(xué);2012年

8 王軍鋒;基于多核的進(jìn)程調(diào)度算法研究[D];哈爾濱工程大學(xué);2012年

9 趙林祥;基于多核處理器任務(wù)復(fù)制的分簇調(diào)度算法研究[D];湖南大學(xué);2012年

10 李學(xué)輝;異構(gòu)多核系統(tǒng)中面向細(xì)粒度任務(wù)集的調(diào)度算法研究[D];湖南大學(xué);2011年

【二級參考文獻(xiàn)】

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

1 劉振英,方濱興,張毅;TSA-OT:一個調(diào)度Out-Tree任務(wù)圖的算法[J];計算機(jī)學(xué)報;2001年04期

2 石威,鄭緯民;相關(guān)任務(wù)圖的均衡動態(tài)關(guān)鍵路徑調(diào)度算法[J];計算機(jī)學(xué)報;2001年09期

3 周雙娥,袁由光,熊兵周,歐中紅;基于任務(wù)復(fù)制的處理器預(yù)分配算法[J];計算機(jī)學(xué)報;2004年02期

4 龍國平;張軍超;范東睿;;眾核體系結(jié)構(gòu)對Cilk語言的硬件支持及評測研究[J];計算機(jī)學(xué)報;2008年11期

5 劉振英,方濱興,姜 譽(yù),張 毅,趙 宏,張 毅;一個調(diào)度Fork-Join任務(wù)圖的新算法[J];軟件學(xué)報;2002年04期

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

7 何琨;趙勇;陳陽;;分布式環(huán)境下多任務(wù)調(diào)度問題的分析與求解[J];系統(tǒng)工程理論與實(shí)踐;2007年05期

【相似文獻(xiàn)】

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

1 李云濤;崔少輝;;一種基于UUTs模型的并行測試任務(wù)調(diào)度算法[J];電子測量技術(shù);2009年07期

2 周建中;王樹宗;石章松;王成飛;;基于遺傳算法的網(wǎng)格任務(wù)調(diào)度方法研究[J];艦船科學(xué)技術(shù);2009年11期

3 鄧定蘭;于炯;譚亞麗;呂良干;;網(wǎng)格工作流的動態(tài)貪心調(diào)度算法[J];計算機(jī)工程;2010年03期

4 鄧萬濤,彭德純,林子禹,陳天雄;BALANCE-II:一個基于Internet環(huán)境的負(fù)載平衡系統(tǒng)[J];小型微型計算機(jī)系統(tǒng);2000年07期

5 黃鯤;王知衍;翁小雄;;樹形異構(gòu)網(wǎng)格的啟發(fā)任務(wù)調(diào)度算法[J];微電子學(xué)與計算機(jī);2007年10期

6 薛桂香;趙政;史偉;孟和;宋建材;;基于OPNET的局部網(wǎng)格任務(wù)調(diào)度平臺設(shè)計[J];計算機(jī)工程;2008年03期

7 于洋;楊愚魯;楊學(xué)剛;賀銘;;分布式網(wǎng)格系統(tǒng)的任務(wù)調(diào)度算法DE Scheduling[J];計算機(jī)工程;2008年14期

8 馬景奕;隋兵;舒萬能;;基于Min-Min遺傳算法的網(wǎng)格任務(wù)調(diào)度方法[J];計算機(jī)工程與應(yīng)用;2008年23期

9 劉先剛;廖述劍;;網(wǎng)格任務(wù)調(diào)度算法的研究[J];機(jī)械工程與自動化;2011年01期

10 王祖析;;基于QoS Guided Min-min任務(wù)調(diào)度算法局部優(yōu)化[J];電腦編程技巧與維護(hù);2011年10期

相關(guān)會議論文 前5條

1 杜琳;石慧;劉曉平;;一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究[A];全國第20屆計算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

2 陳平;王柏;徐六通;吳斌;王艷輝;;電信社群網(wǎng)絡(luò)中介度的網(wǎng)格并行算法及調(diào)度算法[A];2006年全國通信軟件學(xué)術(shù)會議論文集[C];2006年

3 呂默威;韓世杰;張曉彤;何杰;余美強(qiáng);;一種兼有語音通信功能的實(shí)時定位系統(tǒng)的設(shè)計與實(shí)現(xiàn)[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會議（NCMT2010）、第6屆全國人機(jī)交互學(xué)術(shù)會議（CHCI2010）、第5屆全國普適計算學(xué)術(shù)會議（PCC2010）論文集[C];2010年

4 王益;邢春曉;周立柱;;海量信息系統(tǒng)中服務(wù)器機(jī)群和客戶機(jī)結(jié)合的分布式虛擬現(xiàn)實(shí)計算[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2002年

5 劉懷;黃建新;曹弋;;基于令牌總線的網(wǎng)絡(luò)控制系統(tǒng)中信息的優(yōu)化調(diào)度[A];第二十六屆中國控制會議論文集[C];2007年

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

1 巴巍;實(shí)時系統(tǒng)動態(tài)優(yōu)先級任務(wù)調(diào)度算法的研究[D];大連理工大學(xué);2010年

2 楊志邦;一類異構(gòu)多處理器片上系統(tǒng)任務(wù)調(diào)度算法研究與應(yīng)用[D];湖南大學(xué);2012年

3 馬丹;任務(wù)間相互依賴的并行作業(yè)調(diào)度算法研究[D];華中科技大學(xué);2007年

4 賀小川;單芯片系統(tǒng)（SoC）中的實(shí)時任務(wù)調(diào)度算法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

5 李健;云計算環(huán)境下最小化運(yùn)營開銷的調(diào)度技術(shù)研究[D];北京郵電大學(xué);2013年

6 鐘鋒;基于網(wǎng)格的煤炭企業(yè)信息化關(guān)鍵技術(shù)研究[D];中國礦業(yè)大學(xué)（北京）;2009年

7 張宏巍;現(xiàn)代控制局域網(wǎng)技術(shù)在飛行器控制系統(tǒng)中的研究[D];中國科學(xué)院研究生院（長春光學(xué)精密機(jī)械與物理研究所）;2011年

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

1 李坤;云環(huán)境下的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D];吉林大學(xué);2012年

2 李曉;云計算環(huán)境下基于網(wǎng)絡(luò)博弈的任務(wù)調(diào)度算法[D];山東師范大學(xué);2014年

3 張希翔;云計算環(huán)境下任務(wù)調(diào)度算法的研究[D];廣西大學(xué);2012年

4 封良良;云計算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[D];新疆大學(xué);2013年

5 朱雪慶;基于反饋機(jī)制的實(shí)時彈性任務(wù)調(diào)度算法研究[D];湖南大學(xué);2011年

6 王登科;云計算任務(wù)調(diào)度算法的研究與實(shí)現(xiàn)[D];西北師范大學(xué);2013年

7 高鳴;云計算環(huán)境下基于時間富余度的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D];云南大學(xué);2011年

8 馬寶來;Hadoop平臺任務(wù)調(diào)度算法的研究與改進(jìn)[D];東北大學(xué);2012年

9 鄒偉明;云計算環(huán)境下基于MapReduce模型的任務(wù)調(diào)度算法研究[D];新疆大學(xué);2013年

10 廖福蓉;基于任務(wù)備份的云計算任務(wù)調(diào)度算法研究[D];重慶大學(xué);2013年

，

本文編號：2468354