劉 揚(yáng)，安 虹，鄧博斌，毛夢捷，劉 玉

(中國科學(xué)技術(shù)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230027)

1 概述

在現(xiàn)代計算機(jī)系統(tǒng)結(jié)構(gòu)中，存儲墻問題是限制計算機(jī)性能的一個主要因素，成為計算機(jī)領(lǐng)域研究的重要問題之一[1]。存儲系統(tǒng)的層次化結(jié)構(gòu)設(shè)計，是解決這一問題的經(jīng)典方法，即引入緩存(cache)。在過去的幾十年里，關(guān)于cache的研究和優(yōu)化一直在進(jìn)行，從單一 cache到指令和數(shù)據(jù)分離的 cache，從簡單的堆棧結(jié)構(gòu)到多種替換策略，從只能處理一個請求的cache到并發(fā)處理多個請求的cache[2]，從被動訪問到主動預(yù)取，甚至在分離式結(jié)構(gòu)[3]設(shè)計中，發(fā)展成訪存處理器(access processor)與執(zhí)行處理器(execute processor)并行。然而，這些都離不開局部性這個前提。理解程序的局部性原理，即有助于應(yīng)用軟件程序員優(yōu)化程序代碼[4]，有利于系統(tǒng)程序員寫出更有效率工具[5]，又能給系統(tǒng)結(jié)構(gòu)設(shè)計師帶來靈感，設(shè)計出更高性能的硬件[6]。因此，本文分析基準(zhǔn)測試程序SPEC2000，量化其局部性，便于比較程序間局部性的高低。通過對局部性的分類分析討論，理解程序局部性。

2 相關(guān)研究

很多學(xué)者研究程序的訪存模式分析程序訪存行為。文獻(xiàn)[7]提出通過多叉樹結(jié)構(gòu)記錄訪存的地址，作為回溯查找窗口。雖然準(zhǔn)確性很高，但這種方法的空間/時間復(fù)雜度比較大。本文用cache作為回溯查找窗口。也有學(xué)者用取樣統(tǒng)計的方法測量分析程序的空間局部性[8]。取樣的方法準(zhǔn)確性相對較低，本文采用全程序分析，統(tǒng)計計算每次訪存地址。還有學(xué)者分析HPC的 benchmark，用cache line數(shù)目為 N的cache統(tǒng)計重用距離不大于N的訪存數(shù)目[9]。該方法的缺點是做多次實驗才能組合得到完整的重用距離分布數(shù)據(jù)。用cache的命中率來分析技術(shù)時間空間局部性也是一種方法[10]。這種方法計算出來的時間局部性和空間局部性必然有交叉，而且與運(yùn)行平臺有關(guān)，并不完全是程序所固有的特性。上述研究分析程序的全局?jǐn)?shù)據(jù)局部性，本文進(jìn)一步劃分分別測量分析程序的代碼段、數(shù)據(jù)段和堆、棧的局部性。

3 局部性測量方法

本文希望用簡單、易于實現(xiàn)且與平臺無關(guān)的方法，測量程序的局部性。從局部性的定義入手，根據(jù)前人的經(jīng)驗，做出適當(dāng)?shù)恼壑?。實驗中跟蹤每條指令的執(zhí)行，記錄訪存指令，并對訪存地址進(jìn)行統(tǒng)計。對量化統(tǒng)計的結(jié)果進(jìn)行化簡，化簡成0～1之間的數(shù)，以方便比較2個程序的局部性。程序的邏輯分段被映射到硬件的4個段：靜態(tài)數(shù)據(jù)到數(shù)據(jù)段，用戶管理的數(shù)據(jù)到堆段，系統(tǒng)管理的數(shù)據(jù)到棧段，指令到代碼段。進(jìn)一步，分別測量各段的時間、空間局部性。

3.1 時間局部性測量

時間局部性是指某數(shù)據(jù)被訪問，那么很快被再次訪問。通過分析重用距離，能量化出同一數(shù)據(jù)究竟有多快被再次訪問。本文中定義對同一數(shù)據(jù)2次訪問期間的訪存數(shù)目為重用距離。為了測量重用距離，用訪問計數(shù)器記錄數(shù)據(jù)上次被訪問時間(每次訪存時間遞增一次)，當(dāng)數(shù)據(jù)再次被訪問時，當(dāng)前時間減去計數(shù)器記錄的時間，就得到了重用距離。為每個數(shù)據(jù)配置一個計數(shù)器代價太高，因此，把cache配置成cache line大小為一個數(shù)據(jù)項的cache，并在cache line里增加一個數(shù)據(jù)項，作為訪問計數(shù)器。值得注意的是，這樣的測量精度有所下降，但只要把cache性能配置高些，即命中率 90%以上，則本文方法的準(zhǔn)確率也在 90%以上。

根據(jù)重用距離的值，按照(0,32], (32,64],…,(16×2N?1,16×2N]區(qū)間，分別統(tǒng)計每個區(qū)間內(nèi)的訪存總數(shù)。最后根據(jù)式(1)計算時間局部性的得分，分值的值域為[0,1]，分值越高代表時間局部性越好。

其中，N為區(qū)間數(shù)目。

3.2 空間局部性測量

空間局部性是指某數(shù)據(jù)被訪問，那么地址相近的數(shù)據(jù)很快被訪問。類似地，用步長來量化被訪問數(shù)據(jù)之間的相對地址距離。對同一個地址的2次訪問，即具有重用距離為1的時間局部性，也具有步長為0的空間局部性，因此步長的下限為0。為了測量步長，設(shè)長度為 N的查找窗口，用來記錄之前 N個被訪問的數(shù)據(jù)。當(dāng)訪問一個數(shù)據(jù)時，遍歷查找窗口，相對步長最短的值為當(dāng)前數(shù)據(jù)空間局部性的步長。這里N的值即要設(shè)的足夠大，保證捕捉到大部分空間局部性，又要設(shè)的足夠小，保證程序的性能。這里設(shè)N的值為32。類似地，根據(jù)步長的值，按照區(qū)間分別統(tǒng)計各個區(qū)間的訪存數(shù)目。同樣利用式(1)計算出空間局部性的量化得分，分值的值域為[0,1]，分值越高代表空間局部性越好。

4 實驗環(huán)境

本文涉及到的實驗方法基于 CPU模擬器SimpleScalar和基準(zhǔn)測試程序SPEC2000。在原有模擬器代碼上，實現(xiàn)了上述測量局部性的算法。該模擬器是的指令是64位，根據(jù)上節(jié)討論，cache line大小為8 Byte。一級指令Cache大小配置為1 MB，16路組相連，LRU替換算法。一級數(shù)據(jù)Cache大小4 MB，32路組相連，LRU替換算法。

到目前為止，SPEC2000是最為廣泛研究的處理器基準(zhǔn)測試程序，它代表了絕大多數(shù)應(yīng)用程序的典型程序行為。編譯程序(176.gcc)、壓縮程序(164.gzip和256.bzip2)、系統(tǒng)管理程序(253.perlbmk)有多種輸入集。面向科學(xué)研究和工程計算的程序(175.vpr、181.mcf和 255.vortex)與現(xiàn)實世界的應(yīng)用程序有很大的相似性。純粹面向科學(xué)計算的浮點型程序(177.mesa、179.art和188.ammp)，因其輸入集和程序本身復(fù)雜度的不同，很好地體現(xiàn)了現(xiàn)實世界的科學(xué)計算應(yīng)用。盡管SPEC2000為計算專門設(shè)計的而非訪存，這恰恰是選擇它來測量訪存局部性的原因——它的代表性強(qiáng)；為訪存專門設(shè)計的程序，如 Random Access，過分夸大了存儲器的重要性，與現(xiàn)實世界的程序行為相差太大，不具有廣泛的代表性。所使用的程序說明如表1所示。

表1 基準(zhǔn)測試程序

由于本文的目的是分析程序的局部性，程序的局部性是程序固有的性質(zhì)，與所運(yùn)行的環(huán)境無關(guān)，因此模擬器中并沒如入任何優(yōu)化選項，沒有預(yù)取沒有分支預(yù)測，也沒有亂序執(zhí)行多線程多核等優(yōu)化技術(shù)。

5 測試結(jié)果及分析

同一個程序的各個分段的局部性不盡相同，如圖1所示。圖中d-cache的柱狀圖代表程序的數(shù)據(jù)局部性，包括數(shù)據(jù)段和堆棧段。text代表程序的代碼段，也是程序的數(shù)據(jù)的指令并行性。data、heap和 stack分別代表程序的數(shù)據(jù)段、棧和堆段。程序中棧的局部性最好，空間局部性和時間局部性得分最高。這與棧的結(jié)構(gòu)設(shè)計有關(guān)。棧只有入棧和出棧2個操作，訪問上要么是相對棧頂增加要么是相對地址減少，因此空間局部性大于0.99。局部性最低的是堆段。堆段的地址空間很大，訪問次數(shù)最少，空間局部性最低。對這種情況，采用軟件預(yù)取測量是有效的優(yōu)化措施，因為軟件預(yù)取準(zhǔn)確性高，且代碼膨脹不會很大。由于跳轉(zhuǎn)分支等程序行為，代碼段的空間局部性不是很好，循環(huán)使得代碼的時間局部性很好。針對這個特點，分支預(yù)測技術(shù)和指令預(yù)取技術(shù)能有效提高代碼的空間局部性。

圖1 gzip程序各段的局部性

根據(jù)程序的訪存指令所占的比例不同，可將程序分為計算受限型和訪存受限型。在圖2中，絕大多數(shù)的訪存比例為30%，為計算受限型程序。也有相當(dāng)數(shù)目的程序訪存比例超過40%，vortex的訪存比例高達(dá) 53%。對于這種訪存受限高通量型的程序，除了增加帶寬保證數(shù)據(jù)供應(yīng)外，還有必要采取增加局部性的技術(shù)，否則，由于空間局部性較差(vortex的時間局部性僅有 0.4，見圖 3)，因此程序的性能不高。

圖2 訪存比例分布

圖3 各程序的二維局部性分布

圖3為各個程序的二維局部性，其中，橫坐標(biāo)為空間局部性，縱坐標(biāo)為時間局部性。在程序中，bzip、gzip、parser和mesa的空間局部性很高，而art、ammp的時間局部性好，vpr的時間局部性差。

圖4和圖5分別是art和vpr的重用距離分布圖。圖中橫坐標(biāo)是重用距離，縱坐標(biāo)代表該訪存?zhèn)€數(shù)統(tǒng)計，由于數(shù)字值之間相差太大，圖中為實際值的對數(shù)。

圖4 art的重用距離分布

圖5 vpr的重用距離分布

在圖4中，數(shù)據(jù)局部性與heap段的局部性相似，這是由于heap段的訪存量占總數(shù)據(jù)訪問量的92%。由于重用距離小的訪存量非常高，重用距離不大于256的訪存數(shù)量占總訪存量的 93%，很容易被 cache捕獲，因此實際局部性非常高。相比較而言，圖5中重用距離不大于256的訪存比僅為72%，時間局部性差。實驗中對 cache配置較高，缺失率 1%以下，因此重用距離測量的偏差在1%以內(nèi)。

6 結(jié)束語

本文介紹了如何設(shè)計并實現(xiàn)對程序局部性的測量和量化分析。實驗測量并量化了時間局部性和空間局部性。通過數(shù)據(jù)分析表明，大多數(shù)程序都具有良好的時間局部性或空間局部性，因此，cache結(jié)構(gòu)對程序性能的提升明顯。對于程序本身，堆段的訪問比例最高，其局部性決定程序的數(shù)據(jù)局部性；堆段的地址空間最大，時間局部性和空間局部性最低，程序員通過編程或編譯優(yōu)化，可以提高局部性。對系統(tǒng)而言，可以通過優(yōu)化cache結(jié)構(gòu)、預(yù)取、分支預(yù)測等技術(shù)手段提高cache對局部性的利用能力。

然而，對于訪存密集型的程序，僅使用上面的技術(shù)是不夠的；由于存儲墻的存在，增加訪存帶寬、提高存儲部件的并行能力也許是行之有效的方法。但是，對程序局部性與具體平臺上的執(zhí)行效率之間的關(guān)系，以及各種優(yōu)化機(jī)制對局部性的效果，還沒有量化的結(jié)論。因此，下一步工作將探討各種訪存優(yōu)化技術(shù)，對各種局部性的程序有怎樣的可量化的性能提升效果。

[1]McKee S A.Reflections on the Memory Wall[C]//Proc.of the 1st Conference on Computing Frontiers.Ischia, Italy:ACM Press, 2004.

[2]Tuck J, Ceze L, Torrellas J.Scalable Cache Miss Handling for High Memory-level Parallelism[C]//Proc.of the 39th Annual IEEE/ACM International Symposium on Microarchitecture.Washington D.C., USA: IEEE Computer Society, 2006.

[3]Crago N C, Patel S J, OUTRIDER: Efficient Memory Latency Tolerance with Decoupled Strands[C]//Proc.of the 38th Annual International Symposium on Computer Architecture.San Jose, USA: ACM Press, 2011.

[4]王 芳, 高玲刑 鄭明春.基于局部性的分布式哈希表資源定位技術(shù)[J].計算機(jī)應(yīng)用, 2006, 26(3): 531-546.

[5]夏 軍.數(shù)據(jù)局部性及其編譯優(yōu)化技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué), 2004.

[6]Sung M, Krashinsky R, Asanovi K.Multithreading Decoupled Architectures for Complexity-effective General Purpose Computing[J].ACM SIGARCH Computer Architecture News, 2001, 29(5): 56-61.

[7]Zhong Yutao, Shen Xipeng, Ding Chen.Program Locality Analysis Using Reuse Distance[J].ACM Transactions on Programming Languages and Systems, 2009, 31(6): 1-39.

[8]Gu Xiaoming, Christopher I, Bai T, et al.A Component Model of Spatial Locality[C]//Proc.of International Symposium on Memory Management.Dublin, Ireland:ACM Press, 2009.

[9]Weinberg J, McCracken M O, Strohmaier E, et al.Quantifying Locality in the Memory Access Patterns of HPC Applications[C]//Proc.of ACM/IEEE Conference on Supercomputing.Washington D.C., USA: IEEE Computer Society, 2005.

[10]Murphy R C, Kogge P M.On the Memory Access Patterns of Supercomputer Applications: Benchmark Selection and Its Implications[J].IEEE Transactions on Computers, 2007,56(7): 937-945.