應用程序在執(zhí)行過程中的行為是不斷變化的，在某些執(zhí)行階段性能可能受內(nèi)存的影響較大，在另外的執(zhí)行階段可能因為大量的分支預測錯誤而被阻塞。程序的這種不斷變化的行為導致程序全局特性的分析困難。然而程序不斷變化的行為并不是無規(guī)律可循。由于應用程序中包含大量的循環(huán)或遞歸結(jié)構(gòu)，程序在執(zhí)行過程中通常包含大量具有周期行為的程序片段。屬于同一周期行為的程序片段行為相似，具有類似的資源需求以及相似的性能指標。因此，對應用程序的周期行為進行分析，通過利用周期行為的相似性可以進行各種體系結(jié)構(gòu)或編譯優(yōu)化，如動態(tài)緩存重配置、緩存預取、基于反饋信息的優(yōu)化、動態(tài)能耗優(yōu)化、模擬器采樣加速和降低軟件調(diào)試檢測開銷[1]等。
為了分析應用程序包含的周期行為，程序在執(zhí)行過程中，動態(tài)指令序列通常被劃分成不重疊的程序片段。通過計算和比較這些程序片段的特征信息，可以分析這些程序片段動態(tài)行為的相似性，從而獲得程序的周期行為。在此基礎上，通過預測程序的周期行為，可以進行各種層次的優(yōu)化。因此，程序周期行為分析已成為體系結(jié)構(gòu)和編譯優(yōu)化領域研究的熱點之一。
本文綜合評述了當前主流的周期行為分析的關鍵因素、周期行為分析和預測的關鍵技術、各種技術的優(yōu)缺點以及當前周期行為分析技術的主要應用領域。并在此基礎上，對周期行為分析技術的發(fā)展方向進行了展望。
1 周期行為分析關鍵因素
由于應用程序中通常包含大量的循環(huán)和遞歸結(jié)構(gòu)，程序在執(zhí)行中通常包含大量重復的執(zhí)行片段。這些片段具有相似動態(tài)行為和體系結(jié)構(gòu)特性。圖1給出SPEC2000中mesa的CPI的特征曲線，橫坐標為mesa最外層循環(huán)的每次迭代，可以看出隨著程序的執(zhí)行，其行為表現(xiàn)出很明顯的周期性。
周期行為分析是一種分析程序行為的方法，它將具有相似性能特征的重復執(zhí)行的程序片段劃分為同一個周期，并利用這種特性進行各種優(yōu)化。周期行為分析主要由以下三個基本步驟組成：
(1)首先，應用程序的執(zhí)行被劃分為不重疊的程序片段。這些程序片段是周期行為分析的基本單位。
(2)其次，收集每個程序段中能夠代表程序片段特性的特征數(shù)據(jù)和緩存缺失率等。
(3)最后，通過計算程序片段間特征數(shù)據(jù)的相似性，進行周期行為分析和預測。具有相似程序特征數(shù)據(jù)的程序片段被劃分為同一個周期。
由于同一個周期行為中的程序片段行為相似，可以通過一些預測方法動態(tài)預測下一個程序片段的周期行為，并根據(jù)已收集的該周期行為的優(yōu)化策略來優(yōu)化性能或降低功耗。因此，周期行為預測的準確性會直接影響到優(yōu)化的效果。
周期行為分析時使用的特征信息、劃分程序執(zhí)行片段的方式以及周期行為的粒度是影響周期行為分析準確性的三個重要因素[2]。
1.1 特征信息
特征信息用來表示不同程序片段的執(zhí)行行為特性，是某一程序片段執(zhí)行過程中統(tǒng)計得到的用以表示該程序片段執(zhí)行特性的某種信息，體現(xiàn)了該段程序的行為特征。目前比較普遍的特征信息有基于程序控制結(jié)構(gòu)的分析方法(如基本塊向量Basic Block Vector- BBV[3-4])和基于程序數(shù)據(jù)訪問方式的分析方法(如內(nèi)存重用距離[5])。其中BBV是當前應用最為廣泛的表征程序執(zhí)行片段的特征指標，下面以BBV為例說明特征信息的構(gòu)造和使用方法。
BBV是一個長度為N的多維向量，每個BBV對應一個程序執(zhí)行片段，表示這個程序執(zhí)行片段所執(zhí)行的不同基本塊（BB）的數(shù)目信息。BBV向量的長度為整個程序所包含BB的種類數(shù)，每個元素代表一種BB，元素值為區(qū)間所執(zhí)行的該BB的數(shù)目乘以BB的權(quán)重，權(quán)重通常為該BB所包含的指令數(shù)。BBV技術的主要應用于判斷兩個程序片斷是否相似，判斷方法是計算兩個程序片段規(guī)范化之后的BBV的曼哈頓距離。若兩者的距離小于設定的閾值，則認為比較的兩個程序片斷具有相似的特性，否則認為兩個程序片斷不相似。相似的區(qū)間具有相似的BB頻率分布。由于兩個程序片斷執(zhí)行了相似的指令流，從而也具有相似的執(zhí)行路徑和相近的體系結(jié)構(gòu)性能指標，如IPC和緩存缺失率等。
1.2 程序片斷劃分方式
程序片斷劃分方式?jīng)Q定如何在程序執(zhí)行過程中對程序執(zhí)行片段進行劃分。主要可以分為定長劃分方法和變長劃分方法。定長劃分方法使用固定數(shù)目的指令作為程序片段劃分的邊界，如10M條指令或100M條指令。變長劃分方法考慮了程序的內(nèi)在結(jié)構(gòu)，通常以程序中函數(shù)調(diào)用或循環(huán)體邊界為界限對程序進行劃分。為了獲取這些程序內(nèi)在結(jié)構(gòu)的邊界信息，變長劃分方法通常需要對程序進行額外的分析以獲取函數(shù)調(diào)用的起始點或循環(huán)體的邊界。因此變長劃分方法相比于定長劃分方法更為復雜，但這種劃分方式由于邊界定位精確，能更準確地反映程序周期行為的變化，從而具有更好的分析準確性。
1.3 周期劃分粒度
周期行為劃分粒度決定了宏觀上從哪個角度觀察程序的周期行為。選擇不同的周期行為粒度會在不同的抽象級別上觀察到程序的周期行為，從而對程序行為的分析產(chǎn)生影響。周期劃分粒度主要分為細粒度劃分和粗粒度劃分兩種。目前并無區(qū)分粗細粒度的嚴格界限。一般來講，細粒度程序段可以是長度相對較小的定長程序段，如100K條指令或10M條指令，也可以是程序的最內(nèi)層循環(huán)或最內(nèi)層遞歸調(diào)用。而粗粒度程序段可以是長度相對較長的定長程序段，如1 000M條指令，也可以是程序的最外層循環(huán)或遞歸調(diào)用。在周期行為分析過程中，除單獨使用這兩種劃分方法外，也有將兩種劃分方法結(jié)合構(gòu)造多層次粒度劃分程序執(zhí)行的方法。
2 周期行為分析和預測技術
在利用周期行為進行動態(tài)優(yōu)化過程中，需要動態(tài)分析程序片段的周期行為，并對后繼片段的周期行為進行預測。根據(jù)預測結(jié)果進行體系結(jié)構(gòu)或編譯的動態(tài)優(yōu)化。
2.1 周期行為分析
周期行為分析的過程需要收集程序執(zhí)行的動態(tài)特性，基于特征信息對當前程序執(zhí)行片段進行周期行為分類。為了高效實現(xiàn)動態(tài)周期行為分析，一方面要求收集的特征信息不能引入過多的空間開銷，從而影響程序正常執(zhí)行的緩存局部性；另一方面需要能高效地根據(jù)特征信息對周期行為進行分類。因此在實現(xiàn)過程中需要在特征的表示方式、存儲信息的格式以及特征信息的處理方式等方面進行折中。
圖2是當前最流行的周期行為分析結(jié)構(gòu)[3]之一。在該結(jié)構(gòu)中，使用BBV作為周期行為的特征信息。在程序執(zhí)行過程中，動態(tài)收集程序的分支和指令數(shù)信息。為了降低BBV的維度，從而降低存儲的信息量，在BBV構(gòu)造過程中，一個BB起始的分支地址信息被隨機哈希到32維向量中。當一個程序片段執(zhí)行結(jié)束，收集到的當前程序片段的BBV信息與存儲在周期行為表中的已有周期行為的BBV進行對比，如果有匹配的BBV，則表示當前程序片段的周期行為已經(jīng)執(zhí)行過，匹配的周期行為編號即當前程序片段的周期號。否則，表示該程序片段的周期行為沒有執(zhí)行過，則將BBV插入到周期行為表中，并對當前周期行為進行編號。
2.2 周期行為預測技術
周期行為預測主要根據(jù)已經(jīng)執(zhí)行的周期行為情況，預測接下來程序執(zhí)行過程中可能出現(xiàn)的周期行為，并根據(jù)預測結(jié)果進行優(yōu)化策略調(diào)整。
細粒度周期行為預測常用的有Last Value預測策略和Markov預測策略。Last Value預測策略的主要出發(fā)點是程序的行為在一段時間內(nèi)是相對穩(wěn)定的，所以這種方法就是簡單地預測下一個程序片段的周期行為就是上一個程序片段的周期行為。這種方法雖然實現(xiàn)簡單，但它只能進行下一周期的預測，且預測準確性不高。Markov預測策略的基本思想是系統(tǒng)將要產(chǎn)生的狀態(tài)是與之前的狀態(tài)集合密切相關的。在周期行為預測過程中，使用一個Markov預測表，將之前若干周期行為的ID作為索引保存在表中，每個索引對應一個預測的周期行為。在進行預測時，根據(jù)索引對預測表進行查找，如果能找到對應的表項則使用該表項的值做為預測結(jié)果。如果不能在預測表找到匹配項，則在預測表中插入一個新的預測項，用于后繼預測。當預測表滿時，使用LRU替換策略進行替換。雖然細粒度周期行為預測策略具有實現(xiàn)簡單的優(yōu)點，但由于預測主要基于程序執(zhí)行的局部信息，因此預測結(jié)果容易受程序波動影響，導致預測準確率較低。
為了克服細粒度周期行為預測準確率低的缺點，準確度更高的多層次周期行為預測策略被提出[1]。多層次周期行為預測策略結(jié)合了粗粒度周期行為的特點對程序行為進行多層次周期行為預測，從而提高預測的準確度。多層次周期行為預測主要利用了粗粒度周期行為的兩方面特征：(1)屬于同一種粗粒度周期行為的不同粗粒度程序片段，它們所包含的細粒度周期行為的組成和分布情況具有較高的相似性和穩(wěn)定性；(2)當一個粗粒度程序段中包含的前若干個細粒度程序段所屬的周期行為已知時，就能比較精確地預測出當前粗粒度程序片段所屬的周期行為。通過利用粗粒度周期行為的這些特性，多層次周期行為預測策略記錄執(zhí)行過的粗粒度周期包含的細粒度周期行為序列。對于新執(zhí)行的粗粒度程序片段開始部分的細粒度行為采用原始的細粒度預測策略并根據(jù)這些初始細粒度周期行為序列確認該程序片段所屬的粗粒度周期行為。當前粗粒度片段所屬的周期行為確定后，則根據(jù)存儲的粗粒度周期行為的細粒度組成序列來預測接下來細粒度周期行為。通過這樣的策略，程序周期行為的預測準確度可以獲得平均20%的提升。
3 周期行為分析的主要應用
由于應用程序在多種特征指標上都表現(xiàn)出周期行為以及周期行為分析技術的有效性，周期行為分析已被廣泛應用于各種體系結(jié)構(gòu)和編譯優(yōu)化領域。其中最主要的應用包括緩存優(yōu)化、模擬器加速和軟件調(diào)試等。
(1)緩存優(yōu)化
隨著片上緩存尺寸的不斷增大，其所占整個處理器晶體管的比例越來越大，能耗比例也越來越高。緩存優(yōu)化通過利用程序運行過程中的周期行為對處理器緩存進行優(yōu)化，如緩存大小重配置和緩存預取等。該優(yōu)化方法是存儲系統(tǒng)優(yōu)化的一個熱點問題。由于不同的應用所需緩存大小不同，在硬件提供支持的情況下，可以根據(jù)應用的需求調(diào)整可用緩存的大小，從而降低使用整個緩存引入的開銷。其基本思想為[6-9]對屬于某個周期的初始程序片段調(diào)整緩存的大小，確定該周期行為所需的最小緩存大小并記錄。當預測后繼程序片段為已執(zhí)行過的某個周期行為時，根據(jù)記錄的該周期所需緩存大小，調(diào)整該程序片段所需的緩存大小。通過這樣的策略，可以實現(xiàn)緩存大小與應用需求的適配，達到低功耗的效果。隨著能耗墻問題的突出，已有越來越多的硬件支持動態(tài)配置實現(xiàn)低功耗。如動態(tài)地調(diào)節(jié)處理器的各種參數(shù)，包括緩存組織形式、發(fā)射寬度、電壓和頻率等。因此，類似的思路還可以用于其他處理器部件的優(yōu)化和調(diào)整，如文獻[10-11]利用性能計數(shù)器分析周期行為對處理器能耗進行優(yōu)化。
(2)模擬器加速
對程序周期行為進行分析在模擬器加速領域也可以得到很好的應用[3，12-13]。一個測試程序如果運行時間較長，則其中通常含有大量的循環(huán)或者遞歸調(diào)用。而循環(huán)的不同迭代或遞歸的不同函數(shù)調(diào)用層次之間都具有比較類似的體系結(jié)構(gòu)指標。因此，在模擬過程中可以選取一次或多次循環(huán)迭代或遞歸函數(shù)的一次或多次調(diào)用作為整個循環(huán)或遞歸函數(shù)的模擬代表元，進行實際模擬。綜合所有代表元的模擬結(jié)果，獲得整個測試程序的最終模擬結(jié)果。周期行為分析模擬器加速技術由于使用局部代表整體，會引入一定的性能指標偏差，但最高可以使體系結(jié)構(gòu)模擬器的運行速度獲得100倍以上的提升。
(3)軟件調(diào)試
針對多線程程序的動態(tài)軟件調(diào)試工具由于其精確性以及對程序員極大的幫助而受到越來越廣泛的應用。然而，動態(tài)調(diào)試工具在調(diào)試過程中較大的開銷一直是阻礙其發(fā)展的一個重要因素。微軟為了提升自己并行程序開發(fā)過程中的調(diào)試效率，開發(fā)了LiteRace系統(tǒng)[14]，該系統(tǒng)設法在軟件調(diào)試過程中，通過周期行為分析和預測技術來降低動態(tài)數(shù)據(jù)競爭檢測的開銷。LiteRace以函數(shù)為粒度劃分程序執(zhí)行片段，根據(jù)周期行為分析技術在調(diào)試過程中僅挑選出執(zhí)行中的一小部分作為代表元進行采樣和分析。結(jié)果顯示，當采用周期行為分析技術后，即使通過很低的頻率（2%）進行采樣也能發(fā)現(xiàn)程序中大部分（70%）不會經(jīng)常出現(xiàn)的數(shù)據(jù)競爭。
4 總結(jié)與展望
周期行為分析技術做為一種通用的手段已廣泛應用于體系結(jié)構(gòu)和編譯優(yōu)化的方方面面。目前，針對串行應用程序的周期行為分析技術，無論從特征信息還是動態(tài)行為預測的準確性方面都能很好地滿足實際環(huán)境的要求。然而，隨著多核硬件的普及，并行應用程序逐漸成為各種平臺運行的主流應用。如何設計特征信息來準確代表并行程序的動態(tài)行為特性以及針對并行程序設計周期行為預測技術，目前還處于剛剛起步階段，也無法滿足并行環(huán)境動態(tài)優(yōu)化的需要。隨著技術的不斷進步，相信未來的周期行為分析技術將會逐漸得到完善。
參考文獻
[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.Auto-matically characterizing large scale program behavior[C].International Conference on Architectural Support for Pro-gramming 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，BUYUKTO-SUNOGLU A，et al.Memory hierarchy reconfiguration for energy and performance in general-purpose processor archi-tectures[C].In：the 33th annual IEEE International Sympo-sium on Microarchitecture，2000：245-257.
[7] LAU J，SCHOENMACKERS S，CALDER B.Structures for phase classification[C].In：IEEE International Symposium onPerformance Analysis of Systems and Software，2004.
[8] Fang Zhenman，Li Jiaxin，Zhang Weihua，et al.Improving dynamic prediction accuracy through multi-level phase anal-ysis[C].Proceedings of the 2012 ACM SIGPLAN/SIGBED Conference on Languages，Compilers，and Tools for EmbeddedSystems.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，F(xiàn)rance，2013.
[13] Chen Chien-Chih，Peng Yin-Chi，Chen Cheng-Fen，et al.DAPs：Dynamic adjustment and partial sampling for mul-tithreaded/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.