【摘要】： 在近40年來，處理器運(yùn)行速度的增長和存儲器訪問速度的增長之間存在著巨大的差距，這使得兩者之間的速度差距越來越大，導(dǎo)致的“Memory Wall”問題變得越來越嚴(yán)重，已經(jīng)成為整個(gè)系統(tǒng)性能最主要的瓶頸之一�，F(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)中廣泛采用Cache來緩解這兩者之間的速度差距，使得Cache已經(jīng)成為影響處理器性能、能耗、價(jià)值的重要因素之一。Cache的充分利用很大程度上取決于程序自身的局部性，特別是訪問數(shù)據(jù)的局部性，包括時(shí)間局部性和空間局部性。優(yōu)化程序的數(shù)據(jù)局部性成為提高Cache性能的重要方法之一。 由于無需硬件的支持，具有良好的跨平臺性．利用程序分析和優(yōu)化來改善程序的局部性，提高Cache性能成為當(dāng)前研究的熱點(diǎn)。過去在這方面的工作有兩個(gè)重要的思路：一是針對程序運(yùn)行時(shí)的訪問數(shù)據(jù)，利用相關(guān)的Cache行為模型，建立一些程序分析工具，從源代碼級給出程序Cache性能的瓶頸，指導(dǎo)程序員通過程序變換來優(yōu)化程序的局部性，從而提高Cache性能；二是在編譯器上開發(fā)編譯優(yōu)化過程，或者開發(fā)專門的程序優(yōu)化工具，通過對程序進(jìn)行分析，在此基礎(chǔ)上自動進(jìn)行程序變換，包括代碼變換和數(shù)據(jù)變換兩種，優(yōu)化程序的局部性，從而提高Cache性能。 本文根據(jù)上面的思路進(jìn)行了下面的一些工作： (1)程序Cache行為模型的研究 雖然復(fù)用距離已經(jīng)成為程序Cache行為的一種重要度量標(biāo)準(zhǔn)，但是高復(fù)雜度和可能存在的內(nèi)存溢出問題使得其難以被應(yīng)用。在通過引入最大Cache大小，限制復(fù)用距離分析范圍的基礎(chǔ)上，本文提出了一種受限的復(fù)用距離模型。受限的復(fù)用距離舍棄少量訪問的復(fù)用距離分析精度，有效地避免了進(jìn)行復(fù)用距離分析時(shí)可能導(dǎo)致的內(nèi)存溢出問題，同時(shí)使得復(fù)用距離的分析達(dá)到訪問數(shù)據(jù)次數(shù)的線性時(shí)間復(fù)雜度。文章還通過實(shí)驗(yàn)說明了基于受限的復(fù)用距離進(jìn)行Cache失效率分析的可行性和正確性。 (2)程序Cache行為分析工具的設(shè)計(jì)與實(shí)現(xiàn) 程序Cache行為的分析和理解能夠幫助程序員尋找程序中Cache性能的瓶頸，指導(dǎo)程序員通過程序變換改善程序局部性，提高程序Cache性能。本文介紹一種基于復(fù)用距離的程序Cache行為分析工具的設(shè)計(jì)與實(shí)現(xiàn)，該工具利用一種基于中間信息棧的源代碼級插樁收集程序的訪存信息，然后基于受限的復(fù)用距離模型分析程序的Cache行為。同時(shí)還通過示例表明該分析工具不但能在源代碼中給出Cache性能瓶頸的位置，指導(dǎo)進(jìn)行代碼變換；而且還能分析變量的Cache行為關(guān)系，指導(dǎo)進(jìn)行數(shù)據(jù)變換。 (3)基于復(fù)用距離分布的數(shù)據(jù)布局優(yōu)化 在利用程序Cache行為分析工具進(jìn)行分析時(shí)，總結(jié)出程序中經(jīng)常在一起訪問的變量的復(fù)用距離在分布上具有一定的相似性。如果將這些變量進(jìn)行重組，改變其布局，則能提高Cache性能。根據(jù)這個(gè)原理，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)數(shù)據(jù)布局優(yōu)化框架，在框架中采用了一種基于復(fù)用距離分布的變量關(guān)系模型，用于尋找程序中經(jīng)常在一起訪問的變量。目前在框架中實(shí)現(xiàn)了一種動態(tài)數(shù)組的重組方法，用來重組利用變量關(guān)系模型發(fā)現(xiàn)的動態(tài)數(shù)組，以此來提高程序的數(shù)據(jù)局部性。針對SPEC CPU2000中部分測試程序的實(shí)驗(yàn)表明了該優(yōu)化框架在優(yōu)化數(shù)據(jù)局部性和提高數(shù)據(jù)Cache性能上具有一定的可行性和有效性。 (4)利用結(jié)構(gòu)拆分提高Cache性能 結(jié)構(gòu)拆分作為一種常用的通過數(shù)據(jù)變換提高Cache性能的方法，由于只需要分析結(jié)構(gòu)屬性域之間的相對關(guān)系，具有一定的特殊性。為了克服復(fù)用距離分析的復(fù)雜性，本文在引入一種較復(fù)用距離更為簡單的距離的基礎(chǔ)上，提出了一種屬性域關(guān)系模型來度量結(jié)構(gòu)中屬性域之間的關(guān)系，然后尋找程序中的結(jié)構(gòu)的優(yōu)化布局，通過結(jié)構(gòu)拆分來優(yōu)化數(shù)據(jù)布局，從而提高數(shù)據(jù)Cache性能。相關(guān)的實(shí)驗(yàn)表明了這種基于屬性域關(guān)系模型的結(jié)構(gòu)拆分在提高Cache性能上有一定的有效性。
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2007
【分類號】：TP332.3
【圖文】：

圖2-2:受限的復(fù)用距離分析示例問一個(gè)數(shù)據(jù)元素時(shí)，從棧頂開始檢索該數(shù)據(jù)元素在棧中的位置.如果在棧中檢索到該數(shù)據(jù)元素，則其復(fù)用距離為棧頂?shù)疆?dāng)前元素的距離，然后將該元素從當(dāng)前位置移走，并且在棧頂壓入該元素;否則其復(fù)用距離為co，然后將該元素壓入棧頂。圖2-l(c)給出了利用基于棧的方法計(jì)算訪問序號為12的數(shù)據(jù)元素e的復(fù)用距離的示例:搜索棧時(shí)，在棧中發(fā)現(xiàn)該元素到棧頂?shù)木嚯x為4(此時(shí)棧中到棧頂含有h，f，a，g四個(gè)數(shù)據(jù)元素)，則記數(shù)據(jù)元素e的復(fù)用距離為4。得到相應(yīng)的復(fù)用距離后，需要重新調(diào)整棧的結(jié)構(gòu)(按圖中虛線所示的方法)，原有的數(shù)據(jù)元素e將被從棧中刪除，并且新的數(shù)據(jù)元素e被壓入到此時(shí)的棧頂，這樣此次復(fù)用距離計(jì)算完畢.后面數(shù)據(jù)元素的復(fù)用距離的計(jì)算同樣依據(jù)這樣的過程。在利用基于棧的方法計(jì)算復(fù)用距離的同時(shí)，出現(xiàn)了一些基于和棧比較接近的數(shù)據(jù)結(jié)構(gòu)的復(fù)用距離分析方法，如隊(duì)列’159}、向量!6，10]等，這些

復(fù)用距離分布圖

圖冬5:基于復(fù)用距離的C創(chuàng)上e失效率分布圖31

【引證文獻(xiàn)】

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

1 王煒;基于ASIP的實(shí)時(shí)GPS軟件接收機(jī)的實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2010年

2 張夢龍;盤陣列中基于分組的緩存優(yōu)化技術(shù)研究與實(shí)現(xiàn)[D];華中科技大學(xué);2011年

3 楊明;基于存儲訪問的SIMD優(yōu)化技術(shù)研究[D];解放軍信息工程大學(xué);2011年

4 張穎;在達(dá)芬奇DSP上對AVS視頻編碼器的結(jié)構(gòu)優(yōu)化[D];華中科技大學(xué);2008年

本文編號：2778076