程序局部性的量化分析

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

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

1 概述

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

2 相關(guān)研究

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

3 局部性測(cè)量方法

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

3.1 時(shí)間局部性測(cè)量

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

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

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

3.2 空間局部性測(cè)量

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

4 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

圖1 gzip程序各段的局部性

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

圖2 訪存比例分布

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

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

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

圖4 art的重用距離分布

圖5 vpr的重用距離分布

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

6 結(jié)束語(yǔ)

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

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

[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ì)算機(jī)應(yīng)用, 2006, 26(3): 531-546.

[5]夏 軍.數(shù)據(jù)局部性及其編譯優(yōu)化技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(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.