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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

5 劉永紅;Windows多任務管理機制分析[J];成都大學學報(自然科學版);2000年04期

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

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

8 閆效鶯;;μC/OS-Ⅱ?qū)oC驗證支持技術的研究[J];自動化技術與應用;2010年07期

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

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

相關會議論文 前2條

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

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

相關博士學位論文 前1條

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

相關碩士學位論文 前5條

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

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

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

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

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

，

本文編號：2588960