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

圖2-2:受限的復(fù)用距離分析示例問(wèn)一個(gè)數(shù)據(jù)元素時(shí)，從棧頂開(kāi)始檢索該數(shù)據(jù)元素在棧中的位置.如果在棧中檢索到該數(shù)據(jù)元素，則其復(fù)用距離為棧頂?shù)疆?dāng)前元素的距離，然后將該元素從當(dāng)前位置移走，并且在棧頂壓入該元素;否則其復(fù)用距離為co，然后將該元素壓入棧頂。圖2-l(c)給出了利用基于棧的方法計(jì)算訪問(wèn)序號(hào)為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ù)這樣的過(guò)程。在利用基于棧的方法計(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 張夢(mèng)龍;盤陣列中基于分組的緩存優(yōu)化技術(shù)研究與實(shí)現(xiàn)[D];華中科技大學(xué);2011年

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

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

本文編號(hào)：2778076