一種多處理式cache技術(shù)

一種多處理式cache技術(shù)

1基于性能分析的基于局部性數(shù)據(jù)重組框架自20世紀70年代以來，計算機處理器的速度基本上符合莫爾定法，每年增加約60%，但存儲速度每年增加不到10%。兩者之間的差距越來越大，這是整個計算機系統(tǒng)的主要瓶頸之一?，F(xiàn)代計算機體系結(jié)構(gòu)中廣泛采用Cache來緩解這個問題,使得Cache已經(jīng)成為整個處理器性能、能耗和價格的決定性因素之一。Cache功能的充分利用很大程度上取決于程序自身的局部性,特別是程序數(shù)據(jù)的局部性。優(yōu)化程序數(shù)據(jù)的布局,改善程序數(shù)據(jù)的局部性,從而提高數(shù)據(jù)Cache的性能,已經(jīng)成為提高程序性能的一種重要方法[3,4,5,6,7,8,9,10,11]。過去在優(yōu)化程序數(shù)據(jù)布局,從而提高數(shù)據(jù)Cache的性能方面的工作主要可以分為兩類:一類是代碼變換(CodeTransformation),如循環(huán)融合(LoopFusion),循環(huán)分塊(LoopTiling)和循環(huán)交換(LoopInterchange)等,這類工作主要通過改變程序指令的執(zhí)行順序,從而優(yōu)化程序訪問數(shù)據(jù)的局部性,包括數(shù)據(jù)的時間局部性(TemporalLocality)和空間局部性(SpatialLocality),其難點是需要分析指令之間的依賴關(guān)系,且變換復(fù)雜,難以保持變換前后的執(zhí)行語義不變;另一類是數(shù)據(jù)重組(DataReorganization)變換,如數(shù)組重組(ArrayRegrouping)、結(jié)構(gòu)拆分(StructureSplitting)等,這類工作只改變數(shù)據(jù)之間的關(guān)系,只優(yōu)化程序數(shù)據(jù)的空間局部性,因此所需的變換也相對較簡單,但是其難點在于分析數(shù)據(jù)之間的Cache行為關(guān)系。近年來,隨著復(fù)用距離(ReuseDistance)成為度量程序Cache行為的標準之一,出現(xiàn)了一些利用變量復(fù)用距離表示局部性,基于其特征來分析變量之間的關(guān)系,從而進行數(shù)據(jù)重組的方法。本文根據(jù)這種思想提出了一個基于局部性的數(shù)據(jù)重組框架,該框架基于變量復(fù)用距離分布特征表現(xiàn)出來的局部性,設(shè)計了一種量化變量之間關(guān)系的變量關(guān)系圖(VRG,VariableRelationGraph),在此基礎(chǔ)上尋找變量之間的優(yōu)化布局,通過數(shù)組重組和結(jié)構(gòu)拆分兩種數(shù)據(jù)重組方法來優(yōu)化程序數(shù)據(jù)的布局,從而提高數(shù)據(jù)Cache性能。針對179.art,183.equake和188.ammp等SPECCPU2000的部分標準測試程序的實驗,獲得了1.5601的平均加速比,這表明我們的數(shù)據(jù)重組框架能夠有效地優(yōu)化數(shù)據(jù)Cache性能,提高整個程序的性能。本文組織如下:第2節(jié)介紹優(yōu)化框架;第3節(jié)介紹基于變量關(guān)系圖的變量關(guān)系分析;第4節(jié)介紹數(shù)組重組和結(jié)構(gòu)拆分兩種數(shù)據(jù)重組方法及變換算法主要過程;第5節(jié)是實驗及結(jié)果分析;最后兩節(jié)分別是相關(guān)工作和結(jié)束語及未來工作。2插樁+c編碼圖1給出了我們實現(xiàn)的基于局部性的數(shù)據(jù)重組框架的整體結(jié)構(gòu),整個框架主要分為兩個模塊。一是變量關(guān)系分析模塊。C源代碼經(jīng)過源代碼級插樁,得到插樁后的C源代碼,經(jīng)過普通的C編譯器編譯后運行。通過插樁加入的代碼得到變量訪問信息的序列,然后對序列分析變量的復(fù)用距離,基于復(fù)用距離分布的特征建立變量關(guān)系圖,在此基礎(chǔ)上尋找變量的優(yōu)化布局,得到變量重組方案。另一是數(shù)據(jù)重組模塊。依據(jù)變量關(guān)系分析得到的數(shù)據(jù)重組方案,在對C源代碼進行源代碼到源代碼的轉(zhuǎn)換過程中進行數(shù)據(jù)重組,目前主要的實現(xiàn)是數(shù)組重組和結(jié)構(gòu)拆分,得到優(yōu)化后的C源代碼。3變量關(guān)系分析3.1訪問變量信息的編碼源代碼級插樁(Source-LevelInstrumentation)主要用來獲取程序訪問數(shù)據(jù)的序列和數(shù)據(jù)與變量的對應(yīng)關(guān)系,以便進行變量之間的關(guān)系分析。源代碼級插樁在對C源代碼進行源代碼到源代碼的轉(zhuǎn)換過程中加入記錄訪問變量信息的代碼,這些代碼在運行時將訪問變量信息直接寫入文件中,供后面進行變量關(guān)系分析。在重組框架的實現(xiàn)中,該源代碼級插樁過程在基于SUIF編譯框架中實現(xiàn)。實際上,訪問變量的信息并不能完全代表程序訪問數(shù)據(jù)的全部信息。這兩者之間存在一些不同之處,主要可以分為兩種:(1)由于寄存器文件的緩存作用,訪問某些標量并不形成訪存;(2)某些變量的一次訪問可能會形成多次訪存(如結(jié)構(gòu)之間賦值)。由于框架中的變量關(guān)系分析的主要目的是分析變量之間的一種相對關(guān)系,尋找經(jīng)常在一起訪問的變量;并且(1)中出現(xiàn)的情況對所有其他變量的影響是相同的,(2)中情況出現(xiàn)的概率比較小,所以這些不同之處可以忽略,我們通過收集程序運行時變量的訪問序列來表示程序訪問數(shù)據(jù)的序列。3.2復(fù)距離分析3.2.1基于cache的訪問機制在20世紀70年代,Mattson等人利用棧來研究虛擬內(nèi)存中頁面之間的復(fù)用關(guān)系,并基于這種方法評估頁面置換算法的效率,提出了棧距離(StackDistance)的概念。為了用體系結(jié)構(gòu)無關(guān)的一些特征來描述程序自身的局部性,Ding等人在棧距離的基礎(chǔ)上提出了復(fù)用距離的概念。下面我們將給出復(fù)用距離的概念。定義1(數(shù)據(jù)元素,DataElement)是指程序運行中被訪問數(shù)據(jù)的標識,可以是內(nèi)存地址,也可以是內(nèi)存區(qū)域。通常用符號a,b,c來表示數(shù)據(jù)元素。定義2(復(fù)用距離,ReuseDistance)指串行程序運行中前后兩次訪問同一數(shù)據(jù)元素之間所訪問的不同數(shù)據(jù)元素的數(shù)目。假設(shè)一個數(shù)據(jù)元素的訪問序列為abcdeaedb,則其相應(yīng)的復(fù)用距離序列為∞∞∞∞∞4124,其中∞表示首次訪問該數(shù)據(jù)元素,不存在復(fù)用關(guān)系。雖然兩次對數(shù)據(jù)元素b訪問之間的數(shù)據(jù)元素個數(shù)為6,但是不同的個數(shù)為4,所以第二次訪問的復(fù)用距離為4。程序的復(fù)用距離通常指該程序所有訪存的復(fù)用距離。由于單次訪問的復(fù)用距離沒有什么意義,所以一般所說的復(fù)用距離是指整個程序的復(fù)用距離。一般而言,數(shù)據(jù)的訪問次數(shù)遠遠多于對指令的訪問次數(shù),通常研究復(fù)用距離只研究數(shù)據(jù)的復(fù)用距離。復(fù)用距離一般用柱狀圖來表示,橫坐標為表示復(fù)用距離大小的區(qū)間,縱坐標為復(fù)用距離在該區(qū)間的訪問次數(shù)。復(fù)用距離能夠用來表示程序的局部性。若局部性較好,則絕大部分訪問的復(fù)用距離的值都較小;反之較大。當數(shù)據(jù)元素為Cache塊所代表的內(nèi)存區(qū)域時,兩次對同一Cache塊訪問之間的復(fù)用距離d就可以用來判斷第二次訪問是否發(fā)生Cache失效(假設(shè)Cache為全關(guān)聯(lián),采用LRU替換策略):如果d<n,其中n為Cache塊數(shù)目,則表示兩次訪問之間所訪問其他Cache塊數(shù)目小于總的Cache塊數(shù)目,此時原來被訪問的Cache塊還沒有替換出去,所以不會出現(xiàn)Cache失效;否則,即d≥n時,則會發(fā)生Cache失效。3.2.2受限的復(fù)用距離分析在分析復(fù)用距離時,我們發(fā)現(xiàn)了兩個重要的特征:(1)除了少數(shù)訪問,絕大部分訪問的復(fù)用距離的值都比較小;(2)利用棧計算復(fù)用距離時,位于棧底的元素極少發(fā)生再次復(fù)用。這樣給我們分析復(fù)用距離很大的啟示:如果只分析復(fù)用距離在一定區(qū)間的訪存,即對每次訪存只搜索一定區(qū)間訪存記錄,判斷這個區(qū)間是否存在復(fù)用關(guān)系,這將在很大程度上加快分析的速度;同時只需保存一定訪存記錄,所需空間也會減少。我們將這種復(fù)用距離分析方法稱為受限的復(fù)用距離分析。在具體的實現(xiàn)中,我們將可能需要的最大Cache大小作為搜索區(qū)間的限制長度,用Cache塊數(shù)目來表示。下面給出我們設(shè)計的受限的復(fù)用距離分析算法。算法1受限的復(fù)用距離分析輸入:訪問數(shù)據(jù)序列χ;輸出:復(fù)用距離序列Dist;對數(shù)據(jù)序列中的每個數(shù)據(jù)χτ(0≤τ<N)重復(fù)下面的過程:(1)查找。在棧上自頂向底搜索最近對χτ的訪問,搜索的最大距離不超過最大Cache大小;(2)計算。計算當前數(shù)據(jù)χτ的復(fù)用距離Distτ,如果在(1)中能夠找到對χτ的訪問記錄,則Distτ為棧中χτ到棧頂?shù)脑貍€數(shù)。否則,Distτ為∞。(3)更新。如果(1)中查找時存在χτ的記錄,則將其紀錄從棧中刪除。將當前的數(shù)據(jù)χτ壓入棧頂,如果棧的大小超出最大Cache大小,刪除棧底元素。受限的復(fù)用距離分析有兩個優(yōu)點:一是確保用于存儲數(shù)據(jù)訪問記錄的棧的大小不超出最大Cache大小;二是查找搜索區(qū)間的最大長度為最大Cache大小。這樣既保證算法需要的空間不至于過大,又能加快查找速度。雖然這種復(fù)用距離分析方法丟失了少量訪問數(shù)據(jù)的復(fù)用距離的精度,但是對總的分析結(jié)果影響很小,幾乎可以忽略。3.3復(fù)用距離分布的描述變量的復(fù)用距離是指對該變量對應(yīng)內(nèi)存區(qū)域的所有訪問的復(fù)用距離,通常能夠用來表示該變量的時間局部性特征。如果程序中兩個變量經(jīng)常在一起訪問,則兩者的復(fù)用距離分布會比較相似;反之,則兩者的復(fù)用距離分布差異可能會較大。這樣,我們可以利用變量之間復(fù)用距離分布的特征來分析變量之間空間局部性,尋找經(jīng)常在一起訪問的變量。我們設(shè)計的變量關(guān)系圖(VariableRelationGraph)就是基于這種思想,下面將以測試程序183.equake中的部分變量為例介紹變量關(guān)系圖。變量的復(fù)用距離通常也用柱狀圖來表示,圖2(a)給出了183.equake之中部分變量的復(fù)用距離分布圖,其中橫坐標為i表示的區(qū)間為[2i-1,2i)(復(fù)用距離為0表示連續(xù)訪問同一變量,不能用來分析變量之間的空間局部性,所以圖中沒有給出;橫坐標為∞表示復(fù)用距離為∞),縱坐標表示該變量的復(fù)用距離的值在該區(qū)間的訪問次數(shù)。從圖中可以看出,變量M23,V23和C23復(fù)用距離分布比較接近,表示經(jīng)常在一起訪問的概率較大。變量C和M除了橫坐標為2的區(qū)間的差異較大外,其他的都非常接近,這表示除了部分訪問外,其他訪問經(jīng)常在一起的概率很大。變量關(guān)系圖中通過一些量化的性質(zhì)來表示兩個變量之間的關(guān)系,下面先給出一些相關(guān)的定義。變量i和變量j的復(fù)用距離分布在橫坐標為k的區(qū)間的相同部分Sk可以通過下面的式(1)計算得到:Sk=Min(Nk(i),Nk(j))(1)其中Nk(i)表示變量i在橫坐標為k的區(qū)間的訪問次數(shù)。變量i和變量j的復(fù)用距離不為0的訪問次數(shù)Ni和Nj分別可以通過下面的式(2)和式(3)計算得到:Νi=∑k∈GΝk(i)(2)Νj=∑k∈GΝk(j)(3)Ni=∑k∈GNk(i)(2)Nj=∑k∈GNk(j)(3)式(2)和式(3)中的G為變量復(fù)用距離分布圖中表示復(fù)用距離大小的區(qū)間的集合。變量i和變量j之間復(fù)用距離分布差異R可以通過式(4)來計算:R=∑k∈GΙk×(Νk(i)-SkΝi+Νk(j)-SkΝj)(4)R=∑k∈GIk×(Nk(i)?SkNi+Nk(j)?SkNj)(4)其中Ik為復(fù)用距離的值對復(fù)用距離分布差異R的影響因子,這里的Ik用復(fù)用距離分布圖中橫坐標的值來表示。需要注意的是:在分布圖中,橫坐標有一個值為∞,此時Ik的值無法決定,由于Ik的意義在于體現(xiàn)復(fù)用距離值較大時的差異對R的值的影響也較大,因此我們將復(fù)用距離為∞時的Ik的值定義為17,大于其他所有的值,即復(fù)用距離為∞時對R的值的影響最大。變量i和變量j之間的訪問次數(shù)比D可以通過式(5)來計算:D={ΝiΝj?Νi≥ΝjΝjΝi?Νi<Νj(5)D=???NiNj?NjNi?Ni≥NjNi<Nj(5)根據(jù)前面對變量復(fù)用距離分布特征的一些量化,我們就可以給出變量關(guān)系圖的定義。定義3(變量關(guān)系圖,VRG,VariableRelationGraph)表示變量之間的關(guān)系,該圖為一個無向加權(quán)圖G=(V,E),其中頂點集合V表示程序中的變量,邊集E中的邊e表示該邊連接的兩個頂點所表示的變量之間的關(guān)系,其權(quán)值由兩個變量之間的復(fù)用距離分布差異R和訪問次數(shù)比D組成的序?qū)Α碦,D〉決定。圖2(b)給出了圖2(a)中對應(yīng)變量的變量關(guān)系圖中的序?qū)Α碦,D〉值?？梢钥闯?變量M23,V23和C23復(fù)用距離分布比較接近,則相互之間對應(yīng)的R值也比較小,D值比較接近于1。3.4變量重組算法根據(jù)變量關(guān)系圖的定義可知,如果兩個變量經(jīng)常在一起訪問,則在變量關(guān)系圖中兩者之間的R值會比較小。我們可以將其分為一組,通過數(shù)組重組或結(jié)構(gòu)拆分充分利用兩者之間的空間局部性來提高Cache性能。在實際的變量分組中,需要確保分在同一組內(nèi)的變量之間存在的訪問次數(shù)比較接近,這樣確保數(shù)據(jù)重組的效果,我們可以充分利用變量之間的D值來確保。在進行數(shù)據(jù)重組時,無論是數(shù)組重組還是結(jié)構(gòu)拆分,都需要得到變量的分組關(guān)系。特別是結(jié)構(gòu)拆分,還需要得到屬于同組的變量的線性序。這樣,我們就需要從變量關(guān)系圖中尋找符合要求的變量的線性序?？梢酝ㄟ^在變量關(guān)系圖上進行一種改進的深度優(yōu)先搜索實現(xiàn)此目的。下面給出該算法的描述:算法2變量重組算法輸入:變量關(guān)系圖G;R值的最大標準R_std;D值的最小標準D_std。1)如果變量關(guān)系圖G中的變量集V(G)=?,則完成算法退出。否則,繼續(xù)執(zhí)行;2)從變量關(guān)系圖G的變量集中取變量s,并將其從變量集中刪除V(G)=V(G)-{s},建立新的變量線性表T,將s加入到T中;3)從變量關(guān)系圖G的變量集中獲取變量g,從變量線性表T的頭部或尾部獲取變量t,使g和t之間的R值最小。如果R值小于R_std,并且D大于D_std,則執(zhí)行4)。否則執(zhí)行5);4)將變量g從變量關(guān)系圖G的變量集中刪除V(G)=V(G)-{g}。如果t位于隊列T頭部,則將g插入T的頭部之前;否則將g追加到隊列T的隊尾之后,執(zhí)行3);5)將變量線性表T中的變量按照線性序作為一組變量分組保存起來,得到需要進行變換的一組變量。執(zhí)行1)。圖3給出了圖2中變量按照我們的重組算法進行分析后得到的重組方案。由于這些變量都是數(shù)組,所以進行的變換是數(shù)組重組,其中C和M;M23,C23和V23分別進行重組。4基于cache的數(shù)據(jù)重組通過前面變量關(guān)系分析得到變量重組方案,就可以對這些變量進行數(shù)據(jù)重組,如數(shù)組重組、結(jié)構(gòu)拆分等。使這些變量在內(nèi)存中的位置臨近,這樣充分利用Cache提高整個程序的性能。我們的數(shù)據(jù)重組框架為基于SUIF編譯框架實現(xiàn)的一個源代碼到源代碼的轉(zhuǎn)換器,目前主要實現(xiàn)了數(shù)組重組和結(jié)構(gòu)拆分兩種數(shù)據(jù)重組方法。下面我們將分別介紹這兩種重組方法和實現(xiàn)重組的變換算法的主要過程。4.1基于兩組重組數(shù)據(jù)的多態(tài)性在C程序中,數(shù)組的各個元素或者結(jié)構(gòu)的各個屬性域都被分配在相鄰的內(nèi)存區(qū)域。數(shù)組重組就是利用這個原理,將經(jīng)常在一起訪問的不同數(shù)組的元素重組為一個結(jié)構(gòu),這樣訪問多個數(shù)組的元素就變成了訪問同一結(jié)構(gòu)多個屬性域,從而提高訪問數(shù)據(jù)空間局部性,提高Cache性能。圖4給出了我們數(shù)據(jù)重組框架中數(shù)組重組的示例,這是針對一種動態(tài)數(shù)組的重組示例。由于普通數(shù)組的重組更加簡單,這里就不再給出相應(yīng)的示例。4.2添加少數(shù)屬性域結(jié)構(gòu)拆分可以看作是數(shù)組重組的一種逆向變換。如果一個由結(jié)構(gòu)組成的數(shù)組中,經(jīng)常在一起訪問的只有結(jié)構(gòu)中少數(shù)屬性域,將這些屬性域分裂出來,重新構(gòu)成一個結(jié)構(gòu),則組成數(shù)組后,能夠較好地提高數(shù)據(jù)的空間局部性,從而提高Cache性能。圖5給出了我們數(shù)據(jù)重組中結(jié)構(gòu)拆分的示例,一個較大的結(jié)構(gòu)根據(jù)屬性域是否經(jīng)常在一起訪問被拆分成多個子結(jié)構(gòu)。4.3動態(tài)個數(shù)重組我們的數(shù)據(jù)重組框架為一個基于SUIF編譯框架的源代碼到源代碼的轉(zhuǎn)換器,在進行源代碼的轉(zhuǎn)換中進行數(shù)據(jù)重組,包括數(shù)組重組和結(jié)構(gòu)拆分。整個變換算法通過在SUIF的中間格式進行變換,其變換過程中主要進行的變換包含下面幾步:(1)變換變量定義。解析SUIF中間格式表示的程序時,如果遇到需要重組的變量定義,如數(shù)組變量或結(jié)構(gòu)變量的定義,需要更改其定義方式。如圖3所示的數(shù)組重組示例中,需要將數(shù)組的變量M23,C23和V23的定義從下面的形式:double**M23,**C23,**V23;變換為另一種的形式:structMCV{doubleM23;doubleC23;doubleV23;};structMCV*pmcv;(2)變換變量初始化。被重組的變量的定義被改變后,這些變量相應(yīng)的初始化過程也應(yīng)該發(fā)生改變。需要注意的是,有些變量的定義和初始化過程是在一起的,需要同時進行兩者的變換。(3)更新變量的訪問形式。變量被重組后,其訪問方式也發(fā)生了改變。如在數(shù)組重組中,對數(shù)組元素的訪問變?yōu)閷Y(jié)構(gòu)屬性域的訪問;在結(jié)構(gòu)拆分中,對拆分前結(jié)構(gòu)屬性域的訪問變?yōu)榱瞬鸱趾笤搶傩杂蛩鶎俳Y(jié)構(gòu)相應(yīng)的屬性域的訪問。在對動態(tài)數(shù)組進行重組時,對重組后結(jié)構(gòu)的訪問變?yōu)榛谥羔樀倪\算,這是其特殊之處。此外,在進行變換的過程中還有一些特殊的情況需要處理,常見的如基于別名分析尋找被變換變量的別名,對這些別名也要進行同樣的變換;嵌套結(jié)構(gòu)被拆分時,如果不是同一結(jié)構(gòu)的循環(huán)嵌套,則只簡單考慮最頂層的結(jié)構(gòu)。由于我們數(shù)據(jù)重組框架只是一個初期的原型系統(tǒng),所以對這些問題的處理都采用較為簡單的方法,這里不再詳敘。5基于cache的數(shù)據(jù)性能分析在我們的數(shù)據(jù)重組框架中,源代碼級插樁和數(shù)據(jù)重組框架都基于SUIF編譯框架實現(xiàn)。實驗測試環(huán)境為RedHatLinux9.0操作系統(tǒng),CPU為IntelCeleron(R)2.0G(Cache塊大小為64byte;L1級數(shù)據(jù)Cache為8k,4路組關(guān)聯(lián);L2級Cache為128k,2路組關(guān)聯(lián))。測試集由SPECCPU2000中的179.art,183.equake和188.ammp組成,輸入集分別為test,train和ref,編譯器為GCC3.2,O3優(yōu)化選項。在數(shù)據(jù)重組框架中,我們利用test輸入集進行變量關(guān)系分析,其他輸入只用于測試數(shù)據(jù)重組前后的性能變化。表1給出了數(shù)組重組、結(jié)構(gòu)拆分和同時進行這兩種優(yōu)化時優(yōu)化結(jié)果,包括3個測試程序優(yōu)化前后的訪問數(shù)據(jù)的次數(shù)(僅給test輸入集的訪問數(shù)據(jù)的次數(shù))及各輸入集時的加速比,其中訪問數(shù)據(jù)的次數(shù)基于程序分析工具Pin收集?？梢钥闯?3個測試程序10組輸入集在3種優(yōu)化下性能都有了一定的提高,平均值分別為1.0374,1.4778和1.5601。另外,除了179.art在結(jié)構(gòu)拆分后訪問數(shù)據(jù)次數(shù)增加外,其他的訪問數(shù)據(jù)次數(shù)都有了一定減少。同時通過實驗,我們發(fā)現(xiàn)在O0級編譯179.art時,優(yōu)化后訪問數(shù)據(jù)次數(shù)減少,但是O3級編譯179.art時,優(yōu)化后訪問數(shù)據(jù)次數(shù)增加,可見這是由于GCC3.2進行的優(yōu)化導致了訪問數(shù)據(jù)次數(shù)的增加。為了驗證我們數(shù)據(jù)重組優(yōu)化框架對數(shù)據(jù)局部性的影響,我們比較了test輸入集時179.art各種優(yōu)化前后的數(shù)據(jù)Cache失效次數(shù)分布變化情況。我們利用程序分析工具Pin對優(yōu)化前后的179.art的可執(zhí)行程序進行插樁,收集程序運行時訪問數(shù)據(jù)的地址序列,然后通過修改SimpleScalar3.0中的Cheetah來分析在4路組關(guān)聯(lián)(由于實驗平臺的CPU的一級為4路組關(guān)聯(lián))下的Cache失效次數(shù)分布情況。圖6給出了179.art優(yōu)化前和3種優(yōu)化后的Cache失效次數(shù)分布變化情況,相應(yīng)的Cache塊大小為64byte,最大Cache大小為4M,最小Cache大小為1k。從圖中我們可以看出:經(jīng)過數(shù)組重組優(yōu)化,其Cache失效次數(shù)有了一定的減少,但減小程度不如結(jié)構(gòu)拆分優(yōu)化和同時進行兩種優(yōu)化,這個優(yōu)化后的程序加速比是對應(yīng)的。6基于性能分析的數(shù)據(jù)重組方法T.Chilimbi等人在文獻中建立了一種Cache敏感的數(shù)據(jù)結(jié)構(gòu)定義方法,利用結(jié)構(gòu)拆分和結(jié)構(gòu)屬性域位置調(diào)整(StructureFieldReordering)兩種數(shù)據(jù)重組方法來提高Cache性能,其數(shù)據(jù)重組利用一個名叫屬性域親密圖(FieldAffinityGraph)模型來度量結(jié)構(gòu)屬性域之間