【摘要】： 由于處理器性能和存儲器性能的巨大差異,導致了“存儲墻”問題的出現(xiàn),使得存儲系統(tǒng)成為系統(tǒng)的瓶頸。傳統(tǒng)計算機體系結構均采用硬件管理的cache來解決存儲墻問題。然而,隨著應用和工藝的發(fā)展,Cache逐漸暴露出一些問題。相比之下,軟件管理的片上存儲器以其面積、功耗和訪問時間等方面的優(yōu)勢,被認為是解決存儲墻問題的一個有效途徑。目前,軟件管理的片上存儲器已被普遍運用于嵌入式系統(tǒng)、流處理器和圖形處理器中,并被逐漸運用到新型高性能計算機體系結構中。與硬件管理的cache不同,軟件管理的片上存儲器需要由軟件通過數(shù)據(jù)傳輸語句顯式地管理所有片上與片外存儲器之間的數(shù)據(jù)傳輸,決定數(shù)據(jù)進入存儲器的時機和位置。軟件管理的片上存儲器給編譯提出了重要的挑戰(zhàn)。如何在保證程序正確性的基礎上,盡可能提高有限的片上存儲器空間的利用率,盡量避免存儲器碎片;充分捕獲數(shù)據(jù)復用,優(yōu)化存儲層次間的通信,從而最小化存儲器帶寬需求;開發(fā)計算與訪存并行,有效隱藏存儲器訪問延遲,是提高基于軟件管理片上存儲器的系統(tǒng)上程序性能的關鍵。本文重點研究了面向軟件管理片上存儲器的編譯優(yōu)化問題。本文的主要工作和創(chuàng)新概述如下: (1)提出了基于置換圖著色的便箋存儲器分配算法。現(xiàn)代嵌入式系統(tǒng)中,廣泛地將片上存儲器組織為軟件管理的便箋存儲器(Scratchpad Memory, SPM)。本文深入研究了面向嵌入式應用的SPM分配問題,首次發(fā)現(xiàn)了大部分嵌入式應用的相干圖(Interference Graph)為置換圖(Permutation Graph),從而能在線性時間內獲得最優(yōu)的SPM分配。本文首次提出了一個基于置換圖著色的SPM分配算法。理論分析和實驗表明,基于置換圖著色的SPM分配算法與國際上最新的基于超完美圖(Superperfect Graph)的SPM分配算法相比,流程更簡潔,復雜度更低,性能更優(yōu)。 (2)提出了基于存儲器著色的流寄存器文件分配框架。流體系結構是一種新興的面向流應用的高性能計算機體系結構。流體系結構采用軟件管理的片上存儲器,稱為流寄存器文件(Stream Register File, SRF),作為數(shù)據(jù)的核心存儲部件。SRF是不可旁路的存儲層次,軟件必須保證計算需要的輸入流提前加載到SRF中,并為輸出流分配足夠的SRF空間。優(yōu)良的SRF分配方案還應能在避免引入額外的片外存儲器傳輸?shù)那疤嵯?有效地捕獲流應用中廣泛存在的生產(chǎn)者消費者局部性,并盡可能地開發(fā)計算與訪存并行。本文提出了一套基于存儲器著色(即存儲器劃分加上圖著色寄存器分配)技術的SRF分配框架。本文研究的新穎之處在于將開發(fā)重用和并行巧妙地整合到傳統(tǒng)的圖著色寄存器分配框架中。此外,針對應用的特點,本文對傳統(tǒng)的圖著色寄存器分配技術做出了一些改進,如提出了漸增的聯(lián)合技術,寄存器排序技術。實驗表明基于存儲器著色的SRF分配框架能夠在不引入溢出的前提下,有效地開發(fā)復用和并行。 (3)提出了基于最佳有向路徑尋找的流寄存器文件分配算法�；诖鎯ζ髦腟RF分配框架能夠有效地開發(fā)復用和并行。但是,存儲器著色技術在劃分SRF以及對相干圖進行著色時有一定的缺陷,容易引入SRF空間浪費。本文的另一個研究重點是在相干圖確定的情況下(即操作流相干圖開發(fā)復用和并行后),如何最小化需要的SRF空間,避免引入存儲碎片。本文首次發(fā)現(xiàn)了大部分的流應用的相干圖為可比圖(Comparability Graph),或可以降解為多個可比子圖,從而能夠獲得多項式時間的最優(yōu)SRF分配。本文首次將SRF分配問題建模為最佳有向路徑尋找問題,提出了一個新穎的SRF分配算法。嚴格的理論分析和大量的實驗表明,我們的算法能獲得最優(yōu)或近似最優(yōu)的SRF分配。相對目前普遍采用的基于First-Fit的啟發(fā)式算法,我們的算法具有更好的性能。 (4)提出了基于層次圖著色的軟件管理多級存儲層次分配算法�，F(xiàn)代的高性能計算機體系結構中,為了更有效地實現(xiàn)計算與訪存的平衡,優(yōu)化訪存帶寬和延遲,越來越多地采用軟件管理的多級存儲層次來替代硬件管理的多級cache存儲層次。傳統(tǒng)的編譯優(yōu)化研究大都面向單一存儲層次,缺乏對存儲層次全局的綜合考慮,對存儲層次間通信等的優(yōu)化不足。而最小化存儲層次間的通信,能大大減少存儲器帶寬需求,是影響性能的一個重要因素。本文擴展了圖著色寄存器分配算法,首次將其運用到多級存儲層次分配上。通過將存儲層次建模為一個帶權圖,我們的方法可以運用到任何多級軟件管理存儲層次組織上。我們對傳統(tǒng)數(shù)據(jù)相干圖進行擴展,提出路徑合并和路徑消解技術,有效地減少存儲層次間通信。通過數(shù)據(jù)生存期擴展技術,還能有效地進行計算與訪存并行的開發(fā),從而隱藏存儲訪問延遲。以上的優(yōu)化都跟擴展后的圖著色寄存器分配框架巧妙地整合在一起。實驗表明,我們的算法有良好的性能。
【學位授予單位】：國防科學技術大學
【學位級別】：博士
【學位授予年份】：2009
【分類號】：TP333

【相似文獻】

相關期刊論文 前10條

1 鄭明光;;調度自動化軟件可靠性測試及管理研究[J];機電信息;2011年18期

2 王志軍;;利用金山裝機精靈清理軟件[J];電腦迷;2011年16期

3 吳桂玲;;論過程方法和系統(tǒng)方法應用于軍用軟件質量管理[J];標準科學;2010年11期

4 王海;;從軟件管理談信息網(wǎng)絡安全[J];水電廠自動化;2011年02期

5 ;軟件咨詢[J];電腦迷;2011年14期

6 ;給你“五星級”的操作體驗 QQ電腦管家打造一鍵式管理[J];電腦愛好者;2010年23期

7 ;QQ電腦管家推出手機管理功能,搶占安卓用戶[J];網(wǎng)絡與信息;2011年08期

8 朱利東;尹新江;張紹圍;;電務維護工作中的軟件管理[J];鐵道通信信號;2011年07期

9 ;Wind River加強基于OpenSAF的高可用性系統(tǒng)開發(fā)[J];中國電子商情(基礎電子);2011年08期

10 ;巴馬縣率先啟用工資管理信息系統(tǒng)[J];人事天地;2011年06期

相關會議論文 前10條

1 王秋芳;;淺談如何提高車輛軟件可靠性[A];中國汽車工程學會汽車電子技術分會第七屆（2006）年會暨學術研討會論文集[C];2006年

2 王鈞;;PMBOK與CMM相關性分析[A];2001年中國管理科學學術會議論文集[C];2001年

3 邵百群;;規(guī)范化接種門診的實施與評估[A];新世紀預防醫(yī)學面臨的挑戰(zhàn)——中華預防醫(yī)學會首屆學術年會論文摘要集[C];2002年

4 朱巨軍;;防治BO黑客軟件對策的探討[A];第14屆全國計算機安全學術交流會論文集[C];1999年

5 ;財政部:“政府采購法”部分配套法規(guī)年底有望出臺[A];中國物流與采購聯(lián)合會會員通訊總第33期-52期（2003年2月-12月）[C];2003年

6 劉增艷;;CGG地震資料處理系統(tǒng)管理方法研究[A];中國地球物理學會第22屆年會論文集[C];2006年

7 賀啟明;;淺談工程項目管理信息化[A];第九屆建筑業(yè)企業(yè)信息化應用發(fā)展研討會論文集[C];2005年

8 于曉東;曲靜濤;;淺談醫(yī)院網(wǎng)絡管理工作[A];第一屆航天醫(yī)院管理論壇論文匯編[C];2007年

9 陸國強;;企業(yè)醫(yī)院深化改革的構想[A];中華醫(yī)院管理學會職工醫(yī)院管理分會第三屆學術年會論文集[C];1998年

10 蘇春康;蘇振文;;從科學的角度出發(fā)對基層醫(yī)院實驗室進行合理設計——福建省永定縣醫(yī)院檢驗科新搬遷的規(guī)劃[A];第五次全國中青年檢驗醫(yī)學學術會議論文匯編[C];2006年

相關重要報紙文章 前10條

1 王新軍;天方藥業(yè)：強化全員培訓和軟件管理[N];中國醫(yī)藥報;2011年

2 安文利;北京豐臺：研發(fā)軟件管理10萬件涉案物品[N];人民公安報;2011年

3 湖北 renhen007;軟件管理專家FlashSoft[N];電腦報;2001年

4 士心;軟件管理的硬度[N];中國醫(yī)藥報;2006年

5 王新平;合作一中軟件管理和硬件建設成效突出[N];甘南日報(漢文版);2007年

6 商報記者 羅添;1/3軟件管理企業(yè)兩年內將遭淘汰[N];北京商報;2009年

7 張雪琳;軟件管理：運營商的另一張牌[N];通信產(chǎn)業(yè)報;2004年

8 本報記者 劉方遠;卡丁車“熄火” 網(wǎng)游冬意漸增[N];21世紀經(jīng)濟報道;2008年

9 本報記者 張東風;新藥品GMP評定標準重點加強軟件管理[N];中國中醫(yī)藥報;2007年

10 孫志永 肖曙光;軟件管理把握過程[N];中國計算機報;2002年

相關博士學位論文 前9條

1 汪黎;面向軟件管理片上存儲器的編譯優(yōu)化技術研究[D];國防科學技術大學;2009年

2 陳虔;大型應用軟件協(xié)同開發(fā)的版本控制和管理—面向組件增量的版本控制方法[D];中國科學院研究生院（高能物理研究所）;1997年

3 孟建熠;超標量嵌入式處理器關鍵技術設計研究[D];浙江大學;2009年

4 劉彩霞;基三片上多核系統(tǒng)TriBA存儲體系關鍵技術研究[D];北京理工大學;2010年

5 張小強;基于事務的軟件投機并行機制研究[D];國防科學技術大學;2009年

6 張雷;嵌入式系統(tǒng)性能優(yōu)化若干問題研究[D];電子科技大學;2010年

7 薛國偉;醫(yī)用CT圖像解析類重建方程的投影幀驅動重建技術研究[D];哈爾濱工業(yè)大學;2011年

8 陳彬;分布環(huán)境下虛擬機按需部署關鍵技術研究[D];國防科學技術大學;2010年

9 張海濤;自律計算系統(tǒng)的自律可信性評估研究[D];哈爾濱工程大學;2010年

相關碩士學位論文 前10條

1 陳利劍;基于USDP的成本/進度量化管理研究[D];重慶大學;2003年

2 姜靜靜;基于WCDMA軟件管理的研究與實現(xiàn)[D];華東師范大學;2009年

3 王偉科;3G移動網(wǎng)管軟件管理的設計與實現(xiàn)[D];西北工業(yè)大學;2006年

4 李強;基于TMN的網(wǎng)元軟件管理[D];東南大學;2005年

5 李瀟瀟;數(shù)據(jù)并行協(xié)處理器存儲系統(tǒng)的研究與實現(xiàn)[D];國防科學技術大學;2005年

6 許道利;基于模型的軟件成本估算技術研究及工具原型的實現(xiàn)[D];國防科學技術大學;2007年

7 石金鋒;基于SPM的寄存器拋出能耗優(yōu)化研究[D];中南大學;2009年

8 吳康;嵌入式多核編譯器研究與開發(fā)[D];南京理工大學;2008年

9 秦銀濤;基于CMMI的軟件管理與改進評價指標體系的層次分析研究[D];南京理工大學;2010年

10 劉基軍;基于ScratchPad Memory的實時性研究[D];中南大學;2010年

本文編號：2747271