傳統(tǒng)任務(wù)分配問題是以最小化計(jì)算代價和處理器間通信代價之和為研究目標(biāo)的。然而,隨著計(jì)算機(jī)硬件獲得巨大的性能提升,多核處理器成為主流,傳統(tǒng)任務(wù)分配理論面臨前所未有的巨大挑戰(zhàn)。在由多核處理器構(gòu)建的集群環(huán)境中,不僅需要考慮計(jì)算節(jié)點(diǎn)間通信,還需要考慮計(jì)算節(jié)點(diǎn)內(nèi)通信(處理器間通信和核間通信)。研究表明,NAS基準(zhǔn)測試平臺中超過50%的消息是通過計(jì)算節(jié)點(diǎn)內(nèi)通信完成的。在此背景下,本文提出了多核環(huán)境任務(wù)分配問題,目標(biāo)是最小化計(jì)算代價,計(jì)算節(jié)點(diǎn)間通信代價和計(jì)算節(jié)點(diǎn)內(nèi)通信代價(包括處理器間通信代價和核間通信代價)。 多核環(huán)境任務(wù)分配問題的研究面臨兩方面的重大挑戰(zhàn)。挑戰(zhàn)之一,傳統(tǒng)任務(wù)分配問題是NP-hard問題,多核任務(wù)分配問題與之相比更為復(fù)雜,但是該新問題一定也是NP-hard問題嗎?在多核集群環(huán)境下,隨著核數(shù)越來越多,節(jié)點(diǎn)內(nèi)通信代價也越來越大,通信代價的量變會不會導(dǎo)致質(zhì)變?也就是說通信代價的變化會不會導(dǎo)致問題復(fù)雜性發(fā)生本質(zhì)的變化,即使得NP-hard問題變?yōu)镻問題?這些問題是算法復(fù)雜性研究的難點(diǎn),具有重要的理論意義和實(shí)際意義。挑戰(zhàn)之二,在傳統(tǒng)任務(wù)分配問題的精確求解模型研究中,最好的結(jié)果是通過數(shù)學(xué)規(guī)劃方法得到的。在多核任務(wù)分配問題研究中,如何使用數(shù)學(xué)規(guī)劃方法建立高效的精確求解模型? 本文研究正是圍繞這兩個挑戰(zhàn)性問題展開的,在以下三個方面做出了重要貢獻(xiàn)。首先,本文研究了多核環(huán)境任務(wù)分配問題的復(fù)雜性。首次證明了多核環(huán)境下新的任務(wù)分配問題是NP-hard問題,即使在任務(wù)通信圖是二部圖并且是平面圖時,該結(jié)論依然成立。其次,本文使用最小費(fèi)用流理論定量分析了通信代價的變化對問題復(fù)雜性的影響。得出的結(jié)論是,多核環(huán)境任務(wù)分配問題的復(fù)雜性是由通信代價決定的,并且隨著節(jié)點(diǎn)內(nèi)通信代價持續(xù)增大到一定程度,會使原來的NP-hard問題變?yōu)镻問題。最后,本文建立了多核環(huán)境任務(wù)分配問題的0-1整數(shù)二次規(guī)劃模型,并提出了兩種線性松弛策略,為進(jìn)一步設(shè)計(jì)高效的模型求解算法打下了堅(jiān)實(shí)的基礎(chǔ)。
【學(xué)位單位】：大連理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2009
【中圖分類】：TP332
【部分圖文】：

學(xué)研究、工程計(jì)算以及商業(yè)計(jì)算等領(lǐng)域得到了越來越多的應(yīng)用。并行分具發(fā)展前景，但同時也提出了大量富于挑戰(zhàn)性的課題，任務(wù)調(diào)度就是其的問題。度問題是研究如何將一組計(jì)算任務(wù)合理地或最優(yōu)化地分配到分布式系統(tǒng)。如果這個問題得不到解決，則有可能導(dǎo)致分布式計(jì)算效率低下，更有甚并行計(jì)算效率不如單機(jī)計(jì)算，乃至計(jì)算失敗。度具有廣泛的應(yīng)用基礎(chǔ)，除并行計(jì)算領(lǐng)域外，任務(wù)調(diào)度問題還是其他諸注的問題。例如，網(wǎng)格，云計(jì)算，PZP，普適計(jì)算，流媒體，交通領(lǐng)域，工程等。因此，從應(yīng)用角度來說，任務(wù)調(diào)度問題作為諸多領(lǐng)域共同面對具有重要的研究意義。以不受優(yōu)先關(guān)系的約束而相互作用或進(jìn)行通信，這類任務(wù)的調(diào)度問題稱是屬于略微簡化了一點(diǎn)的調(diào)度問題。任務(wù)分配問題不需要強(qiáng)調(diào)任務(wù)在分行次序，在一個或多個處理機(jī)組成的分布式系統(tǒng)中，相互作用的任務(wù)應(yīng)個處理機(jī)上，以充分利用系統(tǒng)資源。

【相似文獻(xiàn)】

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

1 劉淑華;張崳;付帥;吳洪巖;;基于粒子群蟻群算法的多機(jī)器人任務(wù)分配方法[J];東北師大學(xué)報(bào)(自然科學(xué)版);2009年04期

2 陳慶枝;;無線傳感器網(wǎng)絡(luò)任務(wù)分配的粒子群優(yōu)化算法[J];廣西工學(xué)院學(xué)報(bào);2009年03期

3 陳慶枝;;無線傳感器網(wǎng)絡(luò)任務(wù)分配的粒子群優(yōu)化算法[J];蘇州科技學(xué)院學(xué)報(bào)(工程技術(shù)版);2009年03期

4 汪毅;郭立峰;;基于遺傳算法的雷達(dá)網(wǎng)任務(wù)分配[J];微計(jì)算機(jī)信息;2006年22期

5 韓泉葉;李王君;;一種MAS任務(wù)分配及資源競買算法的探討[J];甘肅科學(xué)學(xué)報(bào);2006年03期

6 倪謠;周德云;馬云紅;賀寶財(cái);;基于MILP模型的多無人機(jī)對地攻擊任務(wù)分配[J];火力與指揮控制;2008年11期

7 嚴(yán)建峰;李偉華;劉明;;多Agent系統(tǒng)任務(wù)分配的研究[J];計(jì)算機(jī)工程;2009年11期

8 楊克巍;李興兵;李孟軍;岑凱輝;;基于集合覆蓋理論的Agent協(xié)作問題研究[J];系統(tǒng)工程學(xué)報(bào);2009年06期

9 葉菁;陳國龍;吳運(yùn)兵;朱丹紅;;無線傳感器網(wǎng)絡(luò)任務(wù)分配的遺傳優(yōu)化算法[J];計(jì)算機(jī)工程與應(yīng)用;2010年35期

10 石剛;井元偉;鄒德旋;;主從式免疫克隆選擇算法求解任務(wù)分配問題[J];信息與控制;2011年03期

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

1 鄢超波;趙千川;;任務(wù)分配問題的研究進(jìn)展與算法比較[A];第二十七屆中國控制會議論文集[C];2008年

2 郭建軍;戴葵;王志英;;一種多核處理器存儲層次性能評估模型[A];第八屆全國信息隱藏與多媒體安全學(xué)術(shù)大會湖南省計(jì)算機(jī)學(xué)會第十一屆學(xué)術(shù)年會論文集[C];2009年

3 柳林;鄭志強(qiáng);;多機(jī)器人任務(wù)分配技術(shù)及其在機(jī)器人足球中應(yīng)用[A];2004中國機(jī)器人足球比賽暨學(xué)術(shù)研討會論文集[C];2004年

4 蔣漢平;李臘元;;基于多核處理器的NAT-PT的軟件架構(gòu)的研究[A];中國通信學(xué)會第五屆學(xué)術(shù)年會論文集[C];2008年

5 張煒;馮權(quán)友;曾超;竇文華;;一種基于光互連技術(shù)的存儲墻問題解決方案[A];中國電子學(xué)會第十六屆信息論學(xué)術(shù)年會論文集[C];2009年

6 趙宏偉;許錦洲;;一種基于在線仿真的多無人機(jī)任務(wù)調(diào)度方法研究[A];2009年中國高校通信類院系學(xué)術(shù)研討會論文集[C];2009年

7 潘送軍;胡瑜;李曉維;;多核處理器瞬態(tài)故障敏感性分析[A];第五屆中國測試學(xué)術(shù)會議論文集[C];2008年

8 盧宇彤;楊學(xué)軍;所光;;一種面向多核系統(tǒng)的并行計(jì)算任務(wù)分配方法[A];第八屆全國信息隱藏與多媒體安全學(xué)術(shù)大會湖南省計(jì)算機(jī)學(xué)會第十一屆學(xué)術(shù)年會論文集[C];2009年

9 葉媛媛;閔春平;沈林成;朱華勇;;基于混合遺傳算法的多UCAV協(xié)同任務(wù)分配方法[A];2005年全國自動化新技術(shù)學(xué)術(shù)交流會論文集[C];2005年

10 葉媛媛;閔春平;沈林成;朱華勇;;基于混合遺傳算法的多UCAV協(xié)同任務(wù)分配方法[A];2005全國自動化新技術(shù)學(xué)術(shù)交流會論文集（二）[C];2005年

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

1 李暉;高性能計(jì)算機(jī)若干關(guān)鍵問題研究[D];中國科學(xué)技術(shù)大學(xué);2009年

2 祖麗楠;多機(jī)器人系統(tǒng)自主協(xié)作控制與強(qiáng)化學(xué)習(xí)研究[D];吉林大學(xué);2006年

3 馬巧云;基于多Agent系統(tǒng)的動態(tài)任務(wù)分配研究[D];華中科技大學(xué);2006年

4 楊永明;群體機(jī)器人系統(tǒng)協(xié)同行為研究[D];吉林大學(xué);2009年

5 姜健;多移動機(jī)器人協(xié)作方法研究[D];哈爾濱工業(yè)大學(xué);2008年

6 孫國璽;多變異擬子—基因共同進(jìn)化算法的理論及應(yīng)用研究[D];華南理工大學(xué);2006年

7 董煬斌;多機(jī)器人系統(tǒng)的協(xié)作研究[D];浙江大學(xué);2006年

8 朱敬華;無線傳感器網(wǎng)絡(luò)QoS保障技術(shù)的研究[D];哈爾濱工業(yè)大學(xué);2009年

9 鐘一文;智能優(yōu)化方法及其應(yīng)用研究[D];浙江大學(xué);2005年

10 柳林;多機(jī)器人系統(tǒng)任務(wù)分配及編隊(duì)控制研究[D];國防科學(xué)技術(shù)大學(xué);2006年

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

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

2 熊s

本文編號：2811808