處理器與存儲器的性能差距導(dǎo)致了“存儲墻”問題的出現(xiàn),使得存儲系統(tǒng)成為計(jì)算機(jī)系統(tǒng)的瓶頸。從目前工藝水平和體系結(jié)構(gòu)技術(shù)的發(fā)展趨勢來看,這種差距還會(huì)繼續(xù)增加,因此在未來可預(yù)測的范圍內(nèi),對存儲系統(tǒng)的優(yōu)化將一直是提高計(jì)算機(jī)系統(tǒng)性能的關(guān)鍵技術(shù)之一。 本文著重研究了如何將圖著色理論應(yīng)用于各級存儲層次的優(yōu)化問題,在cache、以流寄存器文件為代表的片上大容量寄存器文件和主存三方面提出了創(chuàng)新的編譯時(shí)優(yōu)化方法。本文取得的主要研究成果如下: (1)提出了一個(gè)基于圖著色的cache優(yōu)化算法—Cache Coloring。該算法根據(jù)訪存行為將程序中的數(shù)據(jù)劃分成若干數(shù)據(jù)對象,然后根據(jù)數(shù)據(jù)對象的大小將cache劃分為一個(gè)帶有別名的偽寄存器文件,每個(gè)偽寄存器由若干cache行組成,可以容納一個(gè)數(shù)據(jù)對象;最后使用一個(gè)經(jīng)過改進(jìn)的圖著色寄存器分配算法來決定這些對象在cache中的位置以及發(fā)生沖突時(shí)的替換關(guān)系。數(shù)據(jù)對象的劃分將cache的管理分為兩個(gè)層次,一個(gè)是編譯時(shí)編譯器對粗粒度的數(shù)據(jù)對象的管理,另一個(gè)是運(yùn)行時(shí)硬件對細(xì)粒度的cache行的管理,這樣編譯器和硬件的優(yōu)勢都得到發(fā)揮。我們構(gòu)造了比傳統(tǒng)的生命周期相干圖蘊(yùn)涵更多相干信息的沖突矩陣,作為處理寄存器分配沖突時(shí)的指導(dǎo)原則。我們基于GCC進(jìn)行了實(shí)現(xiàn),并通過simplescalar構(gòu)造了支持CacheColoring的硬件模擬平臺。實(shí)驗(yàn)結(jié)果表明Cache Coloring能較好的開發(fā)程序的局部性,降低cache失效率。 (2)提出了一個(gè)基于圖著色的流寄存器文件分配算法—SRF Coloring。該算法通過寄存器劃分將流寄存器文件轉(zhuǎn)換為大小和位置固定的傳統(tǒng)寄存器文件,從而將流寄存器文件的分配問題歸結(jié)為一個(gè)可以采用圖著色寄存器分配算法解決的問題。針對流寄存器文件的硬件機(jī)制和程序訪問流寄存器文件的特點(diǎn),我們對已有的圖著色算法進(jìn)行了擴(kuò)充,使之能夠更加有效地進(jìn)行流寄存器文件的分配。為了解決因流太長而導(dǎo)致相干圖不可著色的問題,我們提出了重用優(yōu)先的雙緩沖策略。我們在SF95Compiler編譯框架中實(shí)現(xiàn)了SRF Coloring。SF95Compiler是一個(gè)為FT64及其編程語言SF95開發(fā)的編譯器。實(shí)驗(yàn)結(jié)果表明,SRF Coloring能夠有效地管理流寄存器文件。 (3)提出了一個(gè)基于區(qū)間著色的主存分配算法—MM Coloring。我們以數(shù)組作為分配主存空間的候選,將主存分配問題歸結(jié)為區(qū)間著色問題。由于一般的區(qū)間著色問題是NP完全問題,我們利用程序所具有的一個(gè)性質(zhì),即數(shù)組生命周期的包含性來降低區(qū)間著色的難度,將一般的區(qū)間著色問題簡化為超完美圖的區(qū)間著色問題,并據(jù)此提出了實(shí)現(xiàn)最優(yōu)區(qū)間著色的判定條件以及實(shí)現(xiàn)算法。當(dāng)不滿足最優(yōu)區(qū)間著色的條件時(shí),可以通過分割數(shù)組的生命周期來使之得到滿足。我們提出了兩種分割數(shù)組生命周期的策略。一種是自底向上的積極分割策略,它首先將數(shù)組的生命周期分割到最小,然后在滿足著色條件的前提下逐步合并生命周期;另一種是自頂向下的被動(dòng)分割策略,它在一開始將數(shù)組的生命周期保持為最長,只有在不滿足著色條件時(shí)才選擇某些生命周期進(jìn)行分割。我們基于GCC進(jìn)行了實(shí)現(xiàn)。模擬實(shí)驗(yàn)結(jié)果表明,該算法是一種有效的管理主存的編譯方法。
【學(xué)位單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2007
【中圖分類】：TP333
【部分圖文】：

國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文第一章緒論1.1課題背景1處理器與存儲器的性能差異在過去的十幾年中，處理器速度以每年50%至100%的速度平穩(wěn)增長，而速度卻只以每年7%左右的速度增長[’]。處理器與存儲器之間的速度差距存儲墻”的出現(xiàn)[2]，這使得存儲訪問延遲成為決定程序執(zhí)行時(shí)間的決定性，從圖1一1131和圖1一214]所給出的發(fā)展趨勢來看，處理器與存儲器之間的速越來越大，所以在未來可預(yù)測的范圍內(nèi)，存儲系統(tǒng)仍將是影響整個(gè)計(jì)算能的瓶頸[2][5，6]。尹一處理撰性能nUnUnUnUnU月11.11nU刁..

器的速度卻只以每年7%左右的速度增長[’]。處理器與存儲器之間的速度差距導(dǎo)致了“存儲墻”的出現(xiàn)[2]，這使得存儲訪問延遲成為決定程序執(zhí)行時(shí)間的決定性因素。而且，從圖1一1131和圖1一214]所給出的發(fā)展趨勢來看，處理器與存儲器之間的速度差距會(huì)越來越大，所以在未來可預(yù)測的范圍內(nèi)，存儲系統(tǒng)仍將是影響整個(gè)計(jì)算機(jī)系統(tǒng)性能的瓶頸[2][5，6]。尹一CPU處理撰性能每年提高60%處理器與存儲器性能差趾揀年增加5既 nUnUnUnUnU月11.11nU刁..，性匕匕八以︺目尹尸一山聲M存儲器性能每年提高錢000刊666尸866尸L66甲966尸的66甲啥66門尸66護(hù)入66尸尸66尸066甲686尸8目6護(hù)86L儼公勻6護(hù)的600尸呼口6尸仍06滬6N8甲尸叻6尸0口6尸圖l一 11980年以來處理器和存儲器的性能隨時(shí)間提高的變化曲線圖(以1980年時(shí)的性能為基準(zhǔn))100，000，00010， 000

國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文上集成的。ache容量越來越大。圖1一4給出了Iniel和AMD微處理器片上cache容量隨時(shí)間變化的示意圖。當(dāng)前ItaniumZll“]處理器將三級cache都集成在片上，總?cè)萘砍^gMB。圖1一5顯示了cache訪問時(shí)間(以CPU時(shí)鐘周期計(jì)算)隨cache容量增大和工藝提高的變化曲線11’]�？梢�，隨著容量的增大和工藝的提高，cache與處理器之間的性能差異越來越大。同時(shí)大容量。ache還帶來功耗增大〔’2，”l等負(fù)面影響。50004000300020001000一一泣繼…一一一一萬聲聲{{{{{~Intel萬 萬 萬~~~~~~一 一 一 /////多多二 ///奮 奮多多甲了 了︵國窩︶仲啊。上u。。 19891993199519982001200420052006圖l一4處理器片上cache容量隨時(shí)間變化示意圖訪時(shí)存fal︵時(shí)鐘周期︶ 10100ca比e容凳(拙) 100010000圖1一 5Cache訪問時(shí)間(時(shí)鐘周期)隨。ache容量和工藝變化的曲線圖一些針對十億晶體管結(jié)構(gòu)(Billion一腸ansisto:沁chiteeture)[’4]和高性能計(jì)算而提出的新型體系結(jié)構(gòu)，如Imagine[”，’6]、Merrimac〔‘7]、eell[，81、eyelops64[’”]、clearspeedl20]以及FT6412’]等，采用了大容量軟件管理的片上存儲器來解決存儲墻問題。這些新型體系結(jié)構(gòu)的共同特征是采用了多個(gè)并行執(zhí)行的處理單元
【相似文獻(xiàn)】

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

1 鄧宇;基于圖著色的存儲層次優(yōu)化技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2007年

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

1 陸林海;AVS_M算法優(yōu)化及其在DM642上的實(shí)現(xiàn)[D];五邑大學(xué);2008年

本文編號：2861461