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

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

【相似文獻(xiàn)】

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

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

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

3 陳慶枝;;無(wú)線傳感器網(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ìng)買(mǎi)算法的探討[J];甘肅科學(xué)學(xué)報(bào);2006年03期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 熊s

本文編號(hào)：2811808