程序局部性的量化分析

劉 揚，安 虹，鄧博斌，毛夢捷，劉 玉

(中國科學技術大學計算機科學與技術學院，合肥 230027)

1 概述

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

2 相關研究

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

3 局部性測量方法

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

3.1 時間局部性測量

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

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

其中，N為區間數目。

3.2 空間局部性測量

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

4 實驗環境

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

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

表1 基準測試程序

由于本文的目的是分析程序的局部性，程序的局部性是程序固有的性質，與所運行的環境無關，因此模擬器中并沒如入任何優化選項，沒有預取沒有分支預測，也沒有亂序執行多線程多核等優化技術。

5 測試結果及分析

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

圖1 gzip程序各段的局部性

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

圖2 訪存比例分布

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

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

圖4和圖5分別是art和vpr的重用距離分布圖。圖中橫坐標是重用距離，縱坐標代表該訪存個數統計，由于數字值之間相差太大，圖中為實際值的對數。

圖4 art的重用距離分布

圖5 vpr的重用距離分布

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

6 結束語

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

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

[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]王 芳, 高玲刑 鄭明春.基于局部性的分布式哈希表資源定位技術[J].計算機應用, 2006, 26(3): 531-546.

[5]夏 軍.數據局部性及其編譯優化技術研究[D].長沙:國防科學技術大學, 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.