【摘要】： 隨著計(jì)算機(jī)技術(shù)的發(fā)展,計(jì)算機(jī)應(yīng)用范圍不斷擴(kuò)大,異構(gòu)計(jì)算系統(tǒng)在并行處理中得到了廣泛運(yùn)用。任務(wù)調(diào)度是并行處理中的關(guān)鍵問題,異構(gòu)計(jì)算環(huán)境下的調(diào)度問題則更加復(fù)雜,是研究中亟待解決的一個(gè)難題。 調(diào)度的目標(biāo)是在滿足一定性能指標(biāo)和有限約束關(guān)系的前提下減少總的執(zhí)行時(shí)間。絕大部分情況下的任務(wù)調(diào)度問題已經(jīng)被證明為NP完全問題,這使得啟發(fā)式方法在調(diào)度中得到了普遍運(yùn)用。本文針對異構(gòu)計(jì)算系統(tǒng)的任務(wù)調(diào)度展開研究,在經(jīng)典的任務(wù)模型上提出了兩個(gè)新的算法： 針對基于優(yōu)先驅(qū)動(dòng)的表調(diào)度算法常出現(xiàn)優(yōu)先級相同的問題,提出了一種綜合性啟發(fā)式算法(Heterogeneous Critical Path First Synthetic, HCPFS)。該算法在任務(wù)選擇階段按照是否關(guān)鍵路徑節(jié)點(diǎn)、ranku值遞減、后繼數(shù)遞減的優(yōu)先級順序選擇任務(wù),在任務(wù)分配階段根據(jù)任務(wù)的最早完成時(shí)間進(jìn)行處理器選擇,并采用了任務(wù)復(fù)制和插入策略,以達(dá)到充分利用處理器資源,減少任務(wù)通信開銷的目的。 在采用復(fù)制方法的調(diào)度算法中,是以當(dāng)前任務(wù)的開始時(shí)間、完成時(shí)間和執(zhí)行時(shí)間等作為任務(wù)分配的依據(jù),往往會(huì)產(chǎn)生不必要的任務(wù)復(fù)制。本文提出了一種基于后繼任務(wù)最早完成的調(diào)度方法(Heterogeneous Successor Finish Earliest, HSFE),根據(jù)下一調(diào)度任務(wù)與當(dāng)前調(diào)度任務(wù)的關(guān)系來進(jìn)行任務(wù)分配,在當(dāng)前調(diào)度任務(wù)與下一調(diào)度任務(wù)存在前驅(qū)后繼關(guān)系時(shí),以下一任務(wù)的最早完成作為當(dāng)前處理器分配的依據(jù),從而有效抑制了任務(wù)的不必要復(fù)制,增加了任務(wù)調(diào)度空間,提高了調(diào)度效率。 本文從多個(gè)角度對算法進(jìn)行了測試,通過對調(diào)度長度下界比、加速比的比較可知,本文提出的多優(yōu)先級策略和基于后繼就緒任務(wù)調(diào)度的方法有效地縮短了調(diào)度長度,通過對任務(wù)平均復(fù)制比和平均執(zhí)行時(shí)間下界比的比較可知,.算法根據(jù)后繼調(diào)度任務(wù)選擇處理器分配,有效地抑制了任務(wù)的多余復(fù)制,節(jié)約了處理器資源,復(fù)制方法體現(xiàn)了更好的靈活性。
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2010
【分類號】：TP338.6

【相似文獻(xiàn)】

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

1 袁志祥;王小平;;基于廣義隨機(jī)Petri網(wǎng)的網(wǎng)格調(diào)度模型[J];計(jì)算機(jī)工程;2010年02期

2 黃海于;何大可;;一種基于負(fù)載均衡性的網(wǎng)格任務(wù)調(diào)度算法[J];計(jì)算機(jī)工程;2010年02期

3 蔣瀚洋;王櫻;;網(wǎng)格計(jì)算中Min-Min算法及改進(jìn)算法的研究[J];計(jì)算機(jī)時(shí)代;2010年01期

4 蘇翊;;網(wǎng)格任務(wù)調(diào)度算法Min-min的GridSim模擬實(shí)現(xiàn)[J];電腦知識與技術(shù);2010年05期

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

6 易侃;王汝傳;;一種基于SOA的網(wǎng)格任務(wù)調(diào)度框架[J];計(jì)算機(jī)技術(shù)與發(fā)展;2010年04期

7 張建生;;基于人工魚群算法的網(wǎng)格任務(wù)調(diào)度策略[J];電腦編程技巧與維護(hù);2010年10期

8 孟憲福;劉偉偉;;基于選擇性復(fù)制前驅(qū)任務(wù)的DAG調(diào)度算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2010年06期

9 譚亞麗;于炯;鄧定蘭;呂良干;田國忠;;基于多維QoS約束的網(wǎng)格任務(wù)調(diào)度算法[J];計(jì)算機(jī)工程;2010年12期

10 葉春曉;陸杰;;基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度研究[J];計(jì)算機(jī)科學(xué);2010年07期

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

1 李英楠;余華山;;一種基于任務(wù)復(fù)雜度評估的網(wǎng)格任務(wù)調(diào)度算法[A];2010國際信息技術(shù)與應(yīng)用論壇論文集[C];2010年

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

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

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

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

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

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

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

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

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

1 王向慧;網(wǎng)格計(jì)算中任務(wù)調(diào)度算法的改進(jìn)[D];大連交通大學(xué);2010年

2 許玉杰;基于信任模型的數(shù)據(jù)網(wǎng)格任務(wù)調(diào)度算法研究[D];大連海事大學(xué);2010年

3 秦濤;基于最早完成時(shí)間的網(wǎng)格任務(wù)調(diào)度算法[D];大連海事大學(xué);2010年

4 任鵬;嵌入式多任務(wù)調(diào)度算法及CAN總線通信技術(shù)研究[D];西安電子科技大學(xué);2010年

5 肖曉鋒;基于多QoS約束的網(wǎng)格計(jì)算任務(wù)調(diào)度算法研究[D];西南交通大學(xué);2010年

6 劉定一;基于SOA的海量遙感數(shù)據(jù)并行處理的研究與應(yīng)用[D];河南大學(xué);2010年

7 羅飛;片上多處理器芯片上的SPX性能優(yōu)化研究[D];上海交通大學(xué);2010年

8 鐘英姿;QoS約束下的網(wǎng)格任務(wù)調(diào)度算法研究[D];中南大學(xué);2010年

9 王曉宇;實(shí)時(shí)任務(wù)在集群計(jì)算中的自適應(yīng)容錯(cuò)調(diào)度研究[D];復(fù)旦大學(xué);2010年

10 范國昌;網(wǎng)格計(jì)算的Online-Min-Min任務(wù)調(diào)度算法研究[D];北京郵電大學(xué);2010年

，

本文編號：2696040