程序周期行为技术分析*

隋 然，张 铮，张为华

(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。