【摘要】：為解決單處理器系統(tǒng)的功耗和散熱等問(wèn)題,采用以多處理器為代表的先進(jìn)體系結(jié)構(gòu)逐漸成為未來(lái)處理器性能提升的主要技術(shù)途徑,并受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。超大規(guī)模集成電路和制造工藝技術(shù)的不斷發(fā)展,使得單芯片上集成的處理器數(shù)目越來(lái)越多。當(dāng)芯片上集成的處理器數(shù)量達(dá)到數(shù)十個(gè)或數(shù)百個(gè),甚至上千時(shí),芯片內(nèi)部采用什么通信結(jié)構(gòu)就變得越來(lái)越重要。處理器之間的信息交換能否正確、可靠地完成完全取決于片上處理器之間的通信互連技術(shù),尤其是在超亞微米技術(shù)條件下,處理器的運(yùn)算速度已經(jīng)不再是制約整個(gè)系統(tǒng)快速發(fā)展的瓶頸,相反,處理器之間的互連方式卻成為了多處理器系統(tǒng)向更大規(guī)模和更復(fù)雜化發(fā)展所亟待解決的問(wèn)題,因此,片上多處理器系統(tǒng)通信結(jié)構(gòu)的設(shè)計(jì)往往成為影響整個(gè)系統(tǒng)性能的瓶頸。而且,芯片上集成的處理器越多,通信結(jié)構(gòu)越龐大,占用芯片的面積越多,通信功耗隨著片上處理器的增加成超線性的增長(zhǎng),所以,如何設(shè)計(jì)一個(gè)快速、緊湊和低功耗的通信體系結(jié)構(gòu),已經(jīng)成為當(dāng)前研究的熱點(diǎn)和難點(diǎn)。 多任務(wù)調(diào)度問(wèn)題一直是并行系統(tǒng)的長(zhǎng)久研究領(lǐng)域,而且此類(lèi)問(wèn)題大多數(shù)情況下是NP完全問(wèn)題,因此對(duì)該類(lèi)問(wèn)題的研究大多數(shù)側(cè)重于利用啟發(fā)式算法獲取近似最優(yōu)解。即使是其近似算法的求解也非常困難,求解過(guò)程中需要考慮的因素非常多。這類(lèi)問(wèn)題是調(diào)度理論中的經(jīng)典問(wèn)題,也是并行計(jì)算中的核心問(wèn)題,得到了廣泛和深入的研究。隨著半導(dǎo)體技術(shù)的發(fā)展促使更多的處理器集成到單個(gè)芯片上,如何充分利用片上多處理器系統(tǒng)提供的強(qiáng)大計(jì)算資源,成為了并行系統(tǒng)中研究的熱點(diǎn)和難點(diǎn)問(wèn)題。雖然已經(jīng)存在大量的多任務(wù)調(diào)度的啟發(fā)式算法,但是傳統(tǒng)的多任務(wù)調(diào)度方案沒(méi)有考慮片上系統(tǒng)獨(dú)有的特點(diǎn)和性能要求,因此迫切需要設(shè)計(jì)適應(yīng)片上多處理器系統(tǒng)的多任務(wù)調(diào)度算法。各國(guó)學(xué)者針對(duì)片上多處理器系統(tǒng)的任務(wù)調(diào)度技術(shù)已經(jīng)開(kāi)展了一些相關(guān)研究,但仍然存在許多問(wèn)題有待解決。如有些算法沒(méi)有考慮系統(tǒng)可靠性等因素會(huì)導(dǎo)致運(yùn)行過(guò)程中計(jì)算資源的可變性問(wèn)題,有些算法沒(méi)有考慮到通信功耗的影響等,因此,多任務(wù)調(diào)度問(wèn)題是當(dāng)前片上多處理器系統(tǒng)研究的關(guān)鍵問(wèn)題之一。 本文主要圍繞片上多處理器系統(tǒng)的通信體系結(jié)構(gòu)和多任務(wù)調(diào)度問(wèn)題,開(kāi)展了以下研究工作： 1.針對(duì)環(huán)狀通信體系結(jié)構(gòu)的任務(wù)遷移敏感和可容錯(cuò)的多任務(wù)調(diào)度算法 傳統(tǒng)的靜態(tài)調(diào)度算法主要通過(guò)冗余和備份兩種方式實(shí)現(xiàn)容錯(cuò)。為適應(yīng)片上多處理器系統(tǒng)的特點(diǎn)和解決傳統(tǒng)靜態(tài)容錯(cuò)算法的開(kāi)銷(xiāo),提出了片上環(huán)狀通信體系結(jié)構(gòu),并在此結(jié)構(gòu)基礎(chǔ)上,設(shè)計(jì)了任務(wù)遷移敏感和可容錯(cuò)的靜態(tài)多任務(wù)調(diào)度算法。在環(huán)狀的通信體系結(jié)構(gòu)中,當(dāng)有處理器失效時(shí),可通過(guò)把失效處理器上的任務(wù)遷移到其鄰居處理器去完成。但過(guò)量的任務(wù)遷移不僅提高了通信功耗,還會(huì)增加訪存操作等,而這些因素反過(guò)來(lái)又會(huì)影響任務(wù)的調(diào)度長(zhǎng)度,甚至引起任務(wù)時(shí)序錯(cuò)誤。為減少處理器之間任務(wù)遷移造成的通信開(kāi)銷(xiāo)和對(duì)系統(tǒng)性能的影響,提出了基于two-line的任務(wù)遷移方法。為減少因負(fù)載過(guò)重可能會(huì)導(dǎo)致的處理器過(guò)熱失效問(wèn)題,以及進(jìn)一步減少處理器失效時(shí)任務(wù)遷移的數(shù)目,在基于two-line任務(wù)遷移方法基礎(chǔ)上,設(shè)計(jì)了一種同時(shí)考慮任務(wù)遷移數(shù)目和負(fù)載平衡的多任務(wù)調(diào)度方法,即任務(wù)遷移敏感和可容錯(cuò)的多任務(wù)調(diào)度算法MNTM。MNTM算法通過(guò)實(shí)現(xiàn)負(fù)載平衡不僅能減少處理器失效時(shí)任務(wù)遷移的數(shù)目,實(shí)現(xiàn)高度有規(guī)則的任務(wù)遷移,而且可充分利用片上的計(jì)算資源。仿真實(shí)驗(yàn)結(jié)果表明了所提出的算法能夠有效減少處理器失效時(shí)任務(wù)遷移的數(shù)目,而且以合理的調(diào)度長(zhǎng)度代價(jià),取得了處理器失效時(shí)高度有規(guī)則的和可預(yù)測(cè)的任務(wù)遷移和快速重構(gòu)。 2.針對(duì)基于分段總線通信體系結(jié)構(gòu)的優(yōu)化通信功耗的多任務(wù)調(diào)度算法 隨著半導(dǎo)體技術(shù)向著超亞微米不斷擴(kuò)展,通信功耗占整個(gè)系統(tǒng)功耗的比例越來(lái)越大,如何設(shè)計(jì)低功耗高性能的通信體系結(jié)構(gòu)是當(dāng)今研究的熱點(diǎn)和難點(diǎn)。為解決當(dāng)片上處理器數(shù)目增多時(shí),共享總線結(jié)構(gòu)性能急劇下降而通信功耗卻增長(zhǎng)的問(wèn)題,提出了低功耗高性能的基于分段總線的線性通信體系結(jié)構(gòu)。該結(jié)構(gòu)利用交換開(kāi)關(guān),隔離不在數(shù)據(jù)傳輸路徑上的分段總線,從而減少通信總線的長(zhǎng)度,進(jìn)而降低通信功耗。同時(shí),多個(gè)分段總線可實(shí)現(xiàn)無(wú)重疊路徑的多個(gè)數(shù)據(jù)傳輸,提高了總線帶寬,進(jìn)而提高系統(tǒng)的性能。在此通信結(jié)構(gòu)基礎(chǔ)上,設(shè)計(jì)了優(yōu)化通信功耗的多任務(wù)調(diào)度算法。算法通過(guò)建立任務(wù)的通信結(jié)構(gòu)圖,分析虛擬處理器之間的通信頻率,利用遺傳算法搜索虛擬處理器到物理處理器的最優(yōu)映射,從而在基于分段總線的通信結(jié)構(gòu)基礎(chǔ)上,進(jìn)一步減少了通信功耗。模擬實(shí)驗(yàn)結(jié)果表明所提出的遺傳算法在不影響任務(wù)調(diào)度長(zhǎng)度的前提下,有效的減少了通信功耗。 3.針對(duì)類(lèi)似于片上網(wǎng)絡(luò)的類(lèi)二維網(wǎng)格通信體系結(jié)構(gòu)的綜合貪心策略和遺傳思想的混合調(diào)度算法 隨著片上處理器數(shù)目的增多,通信體系結(jié)構(gòu)對(duì)系統(tǒng)的影響將越來(lái)越大,特別是對(duì)芯片面積、性能和功耗等方面的影響。對(duì)于片上擁有眾多處理器系統(tǒng)的互連方式,借鑒并行領(lǐng)域計(jì)算機(jī)網(wǎng)絡(luò)的研究成果,片上網(wǎng)絡(luò)NoC的理念應(yīng)運(yùn)而生。由于片上網(wǎng)絡(luò)技術(shù)還很不成熟,有很多需要進(jìn)一步解決的問(wèn)題,因此目前主要處在理論研究和實(shí)驗(yàn)階段。為解決擁有眾多處理器的片上系統(tǒng)對(duì)通信結(jié)構(gòu)低功耗和高性能的要求,提出了類(lèi)似于片上網(wǎng)絡(luò)的基于分段總線的類(lèi)二維網(wǎng)格通信體系結(jié)構(gòu)。通過(guò)對(duì)稱(chēng)地設(shè)置交換開(kāi)關(guān),該通信結(jié)構(gòu)可綜合利用片上網(wǎng)絡(luò)有規(guī)則性的連接方式和總線資源豐富等優(yōu)點(diǎn)。在系統(tǒng)運(yùn)行過(guò)程中通過(guò)動(dòng)態(tài)設(shè)置交換開(kāi)關(guān)狀態(tài),可實(shí)現(xiàn)廣播或是路徑不重疊的數(shù)據(jù)同時(shí)傳播。針對(duì)此結(jié)構(gòu),提出了兩種不同的基于列表調(diào)度的擴(kuò)展算法,即基于遺傳思想的混合貪心算法和基于貪心策略的混合遺傳算法。在不影響基礎(chǔ)算法調(diào)度長(zhǎng)度的前提下,算法通過(guò)調(diào)整任務(wù)簇到處理器的映射關(guān)系,進(jìn)一步減少了因處理器之間信息交換而引起的通信功耗。實(shí)驗(yàn)結(jié)果表明兩種混合算法都能有效減少通信功耗,且通信功耗的降低隨著片上處理器數(shù)目的增多而提高。
【圖文】：

w_?Ce)和w,,_(r)分別表示測(cè)試任務(wù)圖DAG的平均11信7B肖和平均計(jì)算7T閾位STDvalue的值可通過(guò)選擇不同的￠7值進(jìn)行微調(diào)。設(shè)桻cr=0. 5和Nutifrhresho時(shí)得到的比較結(jié)果如圖3-15、圖3-16和圖3-17所示。閾值取其他同值時(shí)對(duì)性能響將在這一節(jié)后面詳細(xì)討論。
【學(xué)位授予單位】：武漢大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2011
【分類(lèi)號(hào)】：TP332

【相似文獻(xiàn)】

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

1 張晶;祝連慶;王君;郭陽(yáng)寬;;一種全自動(dòng)酶免分析儀多任務(wù)調(diào)度方法[J];計(jì)算機(jī)仿真;2014年06期

2 楊亮,阮曉星,魏晉鵬,黃俊杰;Windows多任務(wù)調(diào)度機(jī)制中的核心技術(shù)分析[J];微計(jì)算機(jī)應(yīng)用;1998年02期

3 劉衛(wèi)東,高立娥,徐德民,沈猛;水下航行器控制系統(tǒng)實(shí)時(shí)多任務(wù)調(diào)度[J];探測(cè)與控制學(xué)報(bào);2002年03期

4 楊官平,胡志光,胡滿銀,高香林,武曉莉;電除塵器仿真培訓(xùn)軟件的實(shí)時(shí)多任務(wù)調(diào)度系統(tǒng)[J];計(jì)算機(jī)工程與設(shè)計(jì);2002年02期

5 劉永紅;Windows多任務(wù)管理機(jī)制分析[J];成都大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年04期

6 栗波;廖啟征;郭磊;;基于μC/OS-II的多任務(wù)調(diào)度設(shè)計(jì)及實(shí)時(shí)性分析[J];儀表技術(shù);2007年09期

7 孫彪;劉凱;許明恒;;μC/OS Ⅱ在TMS320F2812平臺(tái)上的移植[J];微處理機(jī);2009年06期

8 閆效鶯;;μC/OS-Ⅱ?qū)oC驗(yàn)證支持技術(shù)的研究[J];自動(dòng)化技術(shù)與應(yīng)用;2010年07期

9 金彪;微機(jī)控制系統(tǒng)的實(shí)時(shí)多任務(wù)調(diào)度[J];計(jì)算機(jī)應(yīng)用研究;1994年04期

10 沈金榮;劉翔;;μC/OS-II內(nèi)核結(jié)構(gòu)分析及多任務(wù)調(diào)度實(shí)現(xiàn)[J];計(jì)算機(jī)工程;2006年23期

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

1 馮yN;王景中;;μC/OS-Ⅱ在車(chē)輛自動(dòng)轉(zhuǎn)向系統(tǒng)中的應(yīng)用研究[A];2007通信理論與技術(shù)新發(fā)展——第十二屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2007年

2 李楠;;基于Linux嵌入式GUI的研究與設(shè)計(jì)[A];第二十六屆中國(guó)（天津）2012IT、網(wǎng)絡(luò)、信息技術(shù)、電子、儀器儀表創(chuàng)新學(xué)術(shù)會(huì)議論文集[C];2012年

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

1 何琨;多任務(wù)調(diào)度問(wèn)題的研究與實(shí)現(xiàn)[D];華中科技大學(xué);2006年

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

1 歐國(guó)建;多嵌入式系統(tǒng)的多任務(wù)調(diào)度研究[D];重慶大學(xué);2007年

2 王罡;可重構(gòu)加速平臺(tái)下基于面積性能比的多任務(wù)調(diào)度優(yōu)化策略研究[D];浙江大學(xué);2010年

3 張宏;機(jī)組排班中多任務(wù)調(diào)度技術(shù)研究[D];南京航空航天大學(xué);2010年

4 談敏;深海集礦機(jī)多任務(wù)調(diào)度及算法研究[D];中南大學(xué);2007年

5 朱自民;船舶網(wǎng)絡(luò)信息監(jiān)視系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工程大學(xué);2005年

，

本文編號(hào)：2588960