程序周期行為技術分析*

隋 然，張 錚，張為華

(1.全軍后勤信息中心，北京100084；2.解放軍信息工程大學 數學工程與先進計算國家重點實驗室，河南 鄭州450001；3.復旦大學 并行處理研究所，上海201203)

程序周期行為技術分析*

隋 然1，張 錚2，張為華3

(1.全軍后勤信息中心，北京100084；2.解放軍信息工程大學 數學工程與先進計算國家重點實驗室，河南 鄭州450001；3.復旦大學 并行處理研究所，上海201203)

由于程序中存在大量循環和遞歸，程序執行過程中通常體現大量周期行為。這些周期行為的不同實例行為相似，具有類似體系結構特性，如類似的緩存訪問特性和CPI等。這種程序行為執行的相似性也為各種體系結構和編譯優化提供了可能。探討了周期行為分析的關鍵因素、當前主流技術以及主要應用領域。在對現有周期行為分析技術的不足進行討論的基礎上，展望了程序周期行為分析技術的發展趨勢。

周期行為；動態優化；模擬采樣

0 引言

應用程序在執行過程中的行為是不斷變化的，在某些執行階段性能可能受內存的影響較大，在另外的執行階段可能因為大量的分支預測錯誤而被阻塞。程序的這種不斷變化的行為導致程序全局特性的分析困難。然而程序不斷變化的行為并不是無規律可循。由于應用程序中包含大量的循環或遞歸結構，程序在執行過程中通常包含大量具有周期行為的程序片段。屬于同一周期行為的程序片段行為相似，具有類似的資源需求以及相似的性能指標。因此，對應用程序的周期行為進行分析，通過利用周期行為的相似性可以進行各種體系結構或編譯優化，如動態緩存重配置、緩存預取、基于反饋信息的優化、動態能耗優化、模擬器采樣加速和降低軟件調試檢測開銷[1]等。

為了分析應用程序包含的周期行為，程序在執行過程中，動態指令序列通常被劃分成不重疊的程序片段。通過計算和比較這些程序片段的特征信息，可以分析這些程序片段動態行為的相似性，從而獲得程序的周期行為。在此基礎上，通過預測程序的周期行為，可以進行各種層次的優化。因此，程序周期行為分析已成為體系結構和編譯優化領域研究的熱點之一。

本文綜合評述了當前主流的周期行為分析的關鍵因素、周期行為分析和預測的關鍵技術、各種技術的優缺點以及當前周期行為分析技術的主要應用領域。并在此基礎上，對周期行為分析技術的發展方向進行了展望。

1 周期行為分析關鍵因素

由于應用程序中通常包含大量的循環和遞歸結構，程序在執行中通常包含大量重復的執行片段。這些片段具有相似動態行為和體系結構特性。圖1給出SPEC2000中mesa的CPI的特征曲線，橫坐標為 mesa最外層循環的每次迭代，可以看出隨著程序的執行，其行為表現出很明顯的周期性。

圖1 SPEC2000中mesa行為特征曲線

周期行為分析是一種分析程序行為的方法，它將具有相似性能特征的重復執行的程序片段劃分為同一個周期，并利用這種特性進行各種優化。周期行為分析主要由以下三個基本步驟組成：

(1)首先，應用程序的執行被劃分為不重疊的程序片段。這些程序片段是周期行為分析的基本單位。

(2)其次，收集每個程序段中能夠代表程序片段特性的特征數據和緩存缺失率等。

(3)最后，通過計算程序片段間特征數據的相似性，進行周期行為分析和預測。具有相似程序特征數據的程序片段被劃分為同一個周期。

由于同一個周期行為中的程序片段行為相似，可以通過一些預測方法動態預測下一個程序片段的周期行為，并根據已收集的該周期行為的優化策略來優化性能或降低功耗。因此，周期行為預測的準確性會直接影響到優化的效果。

周期行為分析時使用的特征信息、劃分程序執行片段的方式以及周期行為的粒度是影響周期行為分析準確性的三個重要因素[2]。

1.1 特征信息

特征信息用來表示不同程序片段的執行行為特性，是某一程序片段執行過程中統計得到的用以表示該程序片段執行特性的某種信息，體現了該段程序的行為特征。目前比較普遍的特征信息有基于程序控制結構的分析方法(如基本塊向量 Basic Block Vector-BBV[3-4])和基于程序數據訪問方式的分析方法(如內存重用距離[5])。其中BBV是當前應用最為廣泛的表征程序執行片段的特征指標，下面以BBV為例說明特征信息的構造和使用方法。

BBV是一個長度為N的多維向量，每個BBV對應一個程序執行片段，表示這個程序執行片段所執行的不同基本塊（BB）的數目信息。BBV向量的長度為整個程序所包含BB的種類數，每個元素代表一種BB，元素值為區間所執行的該BB的數目乘以BB的權重，權重通常為該BB所包含的指令數。BBV技術的主要應用于判斷兩個程序片斷是否相似，判斷方法是計算兩個程序片段規范化之后的BBV的曼哈頓距離。若兩者的距離小于設定的閾值，則認為比較的兩個程序片斷具有相似的特性，否則認為兩個程序片斷不相似。相似的區間具有相似的BB頻率分布。由于兩個程序片斷執行了相似的指令流，從而也具有相似的執行路徑和相近的體系結構性能指標，如IPC和緩存缺失率等。

1.2 程序片斷劃分方式

程序片斷劃分方式決定如何在程序執行過程中對程序執行片段進行劃分。主要可以分為定長劃分方法和變長劃分方法。定長劃分方法使用固定數目的指令作為程序片段劃分的邊界，如10M條指令或100M條指令。變長劃分方法考慮了程序的內在結構，通常以程序中函數調用或循環體邊界為界限對程序進行劃分。為了獲取這些程序內在結構的邊界信息，變長劃分方法通常需要對程序進行額外的分析以獲取函數調用的起始點或循環體的邊界。因此變長劃分方法相比于定長劃分方法更為復雜，但這種劃分方式由于邊界定位精確，能更準確地反映程序周期行為的變化，從而具有更好的分析準確性。

1.3 周期劃分粒度

周期行為劃分粒度決定了宏觀上從哪個角度觀察程序的周期行為。選擇不同的周期行為粒度會在不同的抽象級別上觀察到程序的周期行為，從而對程序行為的分析產生影響。周期劃分粒度主要分為細粒度劃分和粗粒度劃分兩種。目前并無區分粗細粒度的嚴格界限。一般來講，細粒度程序段可以是長度相對較小的定長程序段，如 100K條指令或 10M條指令，也可以是程序的最內層循環或最內層遞歸調用。而粗粒度程序段可以是長度相對較長的定長程序段，如 1 000M條指令，也可以是程序的最外層循環或遞歸調用。在周期行為分析過程中，除單獨使用這兩種劃分方法外，也有將兩種劃分方法結合構造多層次粒度劃分程序執行的方法。

2 周期行為分析和預測技術

在利用周期行為進行動態優化過程中，需要動態分析程序片段的周期行為，并對后繼片段的周期行為進行預測。根據預測結果進行體系結構或編譯的動態優化。

2.1 周期行為分析

周期行為分析的過程需要收集程序執行的動態特性，基于特征信息對當前程序執行片段進行周期行為分類。為了高效實現動態周期行為分析，一方面要求收集的特征信息不能引入過多的空間開銷，從而影響程序正常執行的緩存局部性；另一方面需要能高效地根據特征信息對周期行為進行分類。因此在實現過程中需要在特征的表示方式、存儲信息的格式以及特征信息的處理方式等方面進行折中。

圖2是當前最流行的周期行為分析結構[3]之一。在該結構中，使用BBV作為周期行為的特征信息。在程序執行過程中，動態收集程序的分支和指令數信息。為了降低BBV的維度，從而降低存儲的信息量，在BBV構造過程中，一個BB起始的分支地址信息被隨機哈希到32維向量中。當一個程序片段執行結束，收集到的當前程序片段的BBV信息與存儲在周期行為表中的已有周期行為的BBV進行對比，如果有匹配的BBV，則表示當前程序片段的周期行為已經執行過，匹配的周期行為編號即當前程序片段的周期號。否則，表示該程序片段的周期行為沒有執行過，則將BBV插入到周期行為表中，并對當前周期行為進行編號。

圖2 周期分析結構

2.2 周期行為預測技術

周期行為預測主要根據已經執行的周期行為情況，預測接下來程序執行過程中可能出現的周期行為，并根據預測結果進行優化策略調整。

細粒度周期行為預測常用的有 Last Value預測策略和Markov預測策略。Last Value預測策略的主要出發點是程序的行為在一段時間內是相對穩定的，所以這種方法就是簡單地預測下一個程序片段的周期行為就是上一個程序片段的周期行為。這種方法雖然實現簡單，但它只能進行下一周期的預測，且預測準確性不高。Markov預測策略的基本思想是系統將要產生的狀態是與之前的狀態集合密切相關的。在周期行為預測過程中，使用一個Markov預測表，將之前若干周期行為的 ID作為索引保存在表中，每個索引對應一個預測的周期行為。在進行預測時，根據索引對預測表進行查找，如果能找到對應的表項則使用該表項的值做為預測結果。如果不能在預測表找到匹配項，則在預測表中插入一個新的預測項，用于后繼預測。當預測表滿時，使用LRU替換策略進行替換。雖然細粒度周期行為預測策略具有實現簡單的優點，但由于預測主要基于程序執行的局部信息，因此預測結果容易受程序波動影響，導致預測準確率較低。

為了克服細粒度周期行為預測準確率低的缺點，準確度更高的多層次周期行為預測策略被提出[1]。多層次周期行為預測策略結合了粗粒度周期行為的特點對程序行為進行多層次周期行為預測，從而提高預測的準確度。多層次周期行為預測主要利用了粗粒度周期行為的兩方面特征：(1)屬于同一種粗粒度周期行為的不同粗粒度程序片段，它們所包含的細粒度周期行為的組成和分布情況具有較高的相似性和穩定性；(2)當一個粗粒度程序段中包含的前若干個細粒度程序段所屬的周期行為已知時，就能比較精確地預測出當前粗粒度程序片段所屬的周期行為。通過利用粗粒度周期行為的這些特性，多層次周期行為預測策略記錄執行過的粗粒度周期包含的細粒度周期行為序列。對于新執行的粗粒度程序片段開始部分的細粒度行為采用原始的細粒度預測策略并根據這些初始細粒度周期行為序列確認該程序片段所屬的粗粒度周期行為。當前粗粒度片段所屬的周期行為確定后，則根據存儲的粗粒度周期行為的細粒度組成序列來預測接下來細粒度周期行為。通過這樣的策略，程序周期行為的預測準確度可以獲得平均20%的提升。

3 周期行為分析的主要應用

由于應用程序在多種特征指標上都表現出周期行為以及周期行為分析技術的有效性，周期行為分析已被廣泛應用于各種體系結構和編譯優化領域。其中最主要的應用包括緩存優化、模擬器加速和軟件調試等。

(1)緩存優化

隨著片上緩存尺寸的不斷增大，其所占整個處理器晶體管的比例越來越大，能耗比例也越來越高。緩存優化通過利用程序運行過程中的周期行為對處理器緩存進行優化，如緩存大小重配置和緩存預取等。該優化方法是存儲系統優化的一個熱點問題。由于不同的應用所需緩存大小不同，在硬件提供支持的情況下，可以根據應用的需求調整可用緩存的大小，從而降低使用整個緩存引入的開銷。其基本思想為[6-9]對屬于某個周期的初始程序片段調整緩存的大小，確定該周期行為所需的最小緩存大小并記錄。當預測后繼程序片段為已執行過的某個周期行為時，根據記錄的該周期所需緩存大小，調整該程序片段所需的緩存大小。通過這樣的策略，可以實現緩存大小與應用需求的適配，達到低功耗的效果。隨著能耗墻問題的突出，已有越來越多的硬件支持動態配置實現低功耗。如動態地調節處理器的各種參數，包括緩存組織形式、發射寬度、電壓和頻率等。因此，類似的思路還可以用于其他處理器部件的優化和調整，如文獻[10-11]利用性能計數器分析周期行為對處理器能耗進行優化。

(2)模擬器加速

對程序周期行為進行分析在模擬器加速領域也可以得到很好的應用[3，12-13]。一個測試程序如果運行時間較長，則其中通常含有大量的循環或者遞歸調用。而循環的不同迭代或遞歸的不同函數調用層次之間都具有比較類似的體系結構指標。因此，在模擬過程中可以選取一次或多次循環迭代或遞歸函數的一次或多次調用作為整個循環或遞歸函數的模擬代表元，進行實際模擬。綜合所有代表元的模擬結果，獲得整個測試程序的最終模擬結果。周期行為分析模擬器加速技術由于使用局部代表整體，會引入一定的性能指標偏差，但最高可以使體系結構模擬器的運行速度獲得100倍以上的提升。

(3)軟件調試

針對多線程程序的動態軟件調試工具由于其精確性以及對程序員極大的幫助而受到越來越廣泛的應用。然而，動態調試工具在調試過程中較大的開銷一直是阻礙其發展的一個重要因素。微軟為了提升自己并行程序開發過程中的調試效率，開發了 LiteRace系統[14]，該系統設法在軟件調試過程中，通過周期行為分析和預測技術來降低動態數據競爭檢測的開銷。LiteRace以函數為粒度劃分程序執行片段，根據周期行為分析技術在調試過程中僅挑選出執行中的一小部分作為代表元進行采樣和分析。結果顯示，當采用周期行為分析技術后，即使通過很低的頻率（2%）進行采樣也能發現程序中大部分（70%）不會經常出現的數據競爭。

4 總結與展望

周期行為分析技術做為一種通用的手段已廣泛應用于體系結構和編譯優化的方方面面。目前，針對串行應用程序的周期行為分析技術，無論從特征信息還是動態行為預測的準確性方面都能很好地滿足實際環境的要求。然而，隨著多核硬件的普及，并行應用程序逐漸成為各種平臺運行的主流應用。如何設計特征信息來準確代表并行程序的動態行為特性以及針對并行程序設計周期行為預測技術，目前還處于剛剛起步階段，也無法滿足并行環境動態優化的需要。隨著技術的不斷進步，相信未來的周期行為分析技術將會逐漸得到完善。

[1]Zhang Weihua，Li Jiaxin，Li Yi，et al.Multi-level phase analysis[C].ACM transaction on embedded Computing Systems(TECS)，2014，2.

[2]HIND M J，RAJAN V T，SWEENEY P F.Phase shift detection：A problem classification[R].Technical report，IBM，2003.

[3]SHERWOOD T，PERELMAN E，HAMERLY G，et al.Automatically characterizing large scale program behavior[C]. International Conference on Architectural Support for Programming Languages and Operating Systems，New York，NY，USA，2002：ACM，2002：45-57.

[4]SHERWOOD T，SAIR S，CALDER B.Phase tracking and prediction[C].The 30th Annual International Symposium on Computer Architecture，2003：336-349.

[5]SHEN X，ZHONG Y，DING C.Locality phase prediction[C]. The 11th International Conference on Architectural Support for Programming Languages and Operating Systems，2004：165-176.

[6]BALASUBRAMONIAN R，ALBONESI D H，BUYUKTOSUNOGLU A，et al.Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures[C].In：the 33th annual IEEE International Symposium on Microarchitecture，2000：245-257.

[7]LAU J，SCHOENMACKERS S，CALDER B.Structures for phase classification[C].In：IEEE International Symposium on Performance Analysis of Systems and Software，2004.

[8]Fang Zhenman，Li Jiaxin，Zhang Weihua，et al.Improving dynamic prediction accuracy through multi-level phase analysis[C].Proceedings of the 2012 ACM SIGPLAN/SIGBED Conference on Languages，Compilers，and Tools for Embedded Systems.Beijing，China，June，2012.

[9]CHOI I，YEUNG D.Symbiotic cache resizing for cmps with shared llc[R].In University of Maryland Technical Report UMIACS-TR-2013-02，2013.

[10]ISCI C，MARTONOSI M.Runtime power monitoring in high-end processors：Methodology and empirical data[C]. In Proc.MICRO，2003.

[11]ISCI C，MARTONOSI M.Phase characterization for power: evaluating control-flow-based and event-counter based techniques[C].In Proc.HPCA，2006：133-144.

[12]Li Jiaxin，Zhang Weihua，Chen Haibo.Multi-level phase analysis for sampling simulation[C].Design，Automation& Test in Europe Conference&Exhibition(DATE 2013). Grenoble，France，2013.

[13]Chen Chien-Chih，Peng Yin-Chi，Chen Cheng-Fen，et al. DAPs：Dynamic adjustment and partial sampling for multithreaded/multicore simulation[C].The 51st Design Automation Conference(DAC 2014).San Francisco，USA，2014.

[14]MARINO D，MUSUVATHI M，NARAYANASAMY S.Literace：effective sampling for lightweight data-race detection[C]. In Proc.PLDI，2009：134-143.

Development of phase-analysis techniques

Sui Ran1，Zhang Zheng2，Zhang Weihua3
(1.PLA Logistics Information Center，Beijing 100084，China；2.State Key Laboratory of Mathematical Engineering and Advanced Computing，The PLA Information Engineering University，Zhengzhou 450001，China；3.Parallel Processing Institute，Fudan University，Shanghai 201203，China)

There are many loops and recursions in applications,which leads to a lot of phase behavior.Different instances of a phase have the similar architectural behaviors,such as cache characteristics and CPI.These similarities also provide the opportunities for various optimizations.This paper discusses the key issues,mainstream techniques and applications for phase analysis techniques.Then the trend of phase analysis techniques is analyzed.

phase；dynamic optimization；sampling simulation

TP3

：A

：0258-7998(2015)03-0154-04

10.16157/j.issn.0258-7998.2015.03.041

2015-01-20）

隋然（1974-），男，博士，講師，主要研究方向：體系結構、編譯優化。

上海市科委科技攻關項目（13DZ1108800）；國家高技術研究發展計劃(863)（2012AA010901）；國家自然科學基金(61370081)

張錚（1977-），男，博士，副教授，主要研究方向：體系結構、網絡安全與模式識別。

張為華（1974-），通信作者，男，博士，副教授，主要研究方向：體系結構與編譯優化，Email：zhangweihua@fudan.edu.cn。