| 标题 | 一种安卓应用典型特征片段的提取方法 |
| 范文 | 陈耀 摘要：面向移动终端的处理器性能评估需要具有代表性的测试程序，本文通过分析安卓应用阶段性的微架构无关特征，选取能够代表整个应用的程序片段，为最终生成代表性测试程序提供可靠依据。本文所提出的微架构无关特征包括指令混合比、关键路径长度、寄存器传输、指令/数据的空间局部性/时间局部性、分支行为、串行指令分布7大类，总计227个微架构无关特征维度。同时在Gem5中加入了特征参数的统计代码，通过基于固定Cycle数的切割方法，对安卓应用进行切片，并提取了所有特征片段中的微架构无关参数以及相应的微架构相关参数。随后通过降维、聚类的方法从众多的特征片段中挑选出典型特征片段来代表整个安卓应用执行时的负载特征。 关键词：安卓应用；微架构无关特征；降维；聚类；典型特征片段 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）14-0214-03 当前，对移动智能设备硬件性能的评估已成为业界以及用户所关注的重点。为了得到有意义、可量化比较的性能评估结果，首先必须确定量化的标准，即需要选择合适的测试程序对硬件性能进行评估。当前学界对传统桌面应用程序的研究已经较为完善，但针对移动智能终端交互式应用的研究较为不足。传统的面向通用处理性能的测试集，如针对计算机系统的SPEC测试集以及针对嵌入式系统的MiBench[1]、MediaBench[2]测试集等，在程序的功能以及规模等方面都与移动智能设备应用存在着较大的不同[3]。面向安卓应用还没有像SPEC一样权威的测试集。因此，所在课题组提出了如图1所示的构造测试集的过程： 即首先通过对安卓应用进行负载特征分析，提取典型特征片段，然后进行合成，最终构造面向安卓应用的测试集。本文的主要工作在于负载特征分析以及典型特征片段提取。 安卓应用的执行行为主要由2方面的特征可以描述，其一是与具体运行的处理器微架构相关的特征，比如cache缺失率、分支预测错误率、TLB缺失率等；其二是与处理器微架构无关的特征，比如指令混合比、寄存器传输、指令/数据局部性、分支行为以及程序内在的指令级并行度等。使用微架构相关负载特性来比较程序极有可能产生误导，因为在特定微架构上得到的负载特性并不一定等同于在其他微架构上得到的负载特性。微架构无关特征是程序的内在特征，与具体的处理器实现之间没有必然联系。因此，本文基于微架构无关负载特征对安卓应用进行典型特征片段的提取。 1 微架构无关负载特征 当前所提出的微架构无关负载特征几乎覆盖了安卓应用的所有程序行为特征，主要包括指令混合比、关键路径长度、寄存器传输、指令的空间局部性/时间局部性、数据的空间局部性/时间局部性、分支行为、串行指令分布7大类，总计227个微架构无关特征维度。各特征维度的具体含义如下： 1.1指令混合比 指令混合比表示特定类型的动态执行指令占全部动态执行指令的比例，基于ARM指令集架构特点，本文考虑了六类指令包括寄存器载入指令、寄存器存储指令、分支指令、整数指令、浮点指令以及串行指令。 1.2关键路径长度 关键路径是指指令窗口中最长的依赖关系链，也就是指令窗口中动态指令流的源寄存器和目的寄存器之间的依赖关系。 1.3寄存器传输 本文使用三类参数反映寄存器传输相关特性，包括平均寄存器读取数、平均寄存器赋值数、寄存器依赖距离分布，其中依赖距离定义为寄存器赋值操作与读取该寄存器操作之间的指令数。 1.4指令的空间局部性及时间局部性 指令的空间局部性定义为上一条指令地址与当前指令地址的差值，指令的时间局部性定义为两次获取相同指令地址之间的指令数。 1.5数据的空间局部性及时间局部性 数据的空间局部性分为全局数据跨度和局部数据跨度。全局数据跨度是指相邻的两次访存操作中，访存地址的距离；局部数据跨度是指由同一条指令发起的两次访存操作中访存地址的距离。由于ARM指令中的访存指令分为Load、Store两大类，因此空间局部性又分为Load指令、Store指令这两类来进行统计。 数据的时间局部性定义为两次访问相同存储地址之间的访存指令数。类似与数据的空间局部性，数据的时间局部性同样分为全局数据跨度和局部数据跨度。同时，存储器操作分为存储器读操作和存储器写操作，因此同样需要分为Load指令和Store指令来统计数据的时间局部性。 1.6 分支行为 本文使用基本块大小、分支跳转方向、分支跳转比例、分支跳转地址跨度、以及分支跳转变化率来描述分支行为的负载特征。基本块大小指的是动态指令流中连续两次条件分支指令之间的指令数。分支跳转方向有两种，分为前向分支跳转和后向分支跳转。分支跳转比例指的是程序动态指令流中分支发生跳转的概率。分支跳转地址跨度是指相邻两次分支指令之间的跳转地址的差值。分支跳转变化率是指指令从跳转变为不跳转，或从不跳转变为跳转的频率。 1.7 串行指令分布 串行指令分布是指动态指令流中连续两条串行指令之间的指令数。 2 特征获取 2.1 仿真工具 安卓应用的微架构无关负载特征即安卓应用程序的动态指令流信息。因此，首先需要以翻译的方式执行安卓应用程序，获取安卓应用程序的动态指令流，继而进行相应的微架构无关負载特征分析。对于ARM指令集，当前主要有Gem5以及SimpleScalar两种指令集模拟器能够以翻译的方式执行安卓应用程序的二进制代码。当前，Gem5的支持更为完善并且得到了广泛的应用。因此，本论文将基于Gem5，在原有特征参数统计的基础上，增加相应的微架构无关负载特征的统计模块，获取本文所需的安卓应用微架构无关负载特征。 2.2 典型特征片段提取步骤 典型特征片段是指那些能够代表众多特征片段的片段。其选取的流程如图2所示，具体的选取步骤如下： 1）在加入了微架构无关负载特征统计代码的Gem5上以固定Cycle数运行Moby测试集（该测试集是中科院提出的一个用于硬件体系架构研究的移动智能终端基准测试程序集），从应用执行过程中的动态指令流中获取应用每个片段的微架构无关负载特征。 2）由于不同的微架构无关特征参数具有不同的量纲，因此需要对每个片段的数据做标准化，以免影响到后续数据分析的结果。 3）提取到的原始特征片段是个高维数据，很多传统的聚类算法在对高维数据做聚类处理时，往往会出现维度灾难[4]。同时，原始数据中不同的微架构无关特征参数之间存在着一定的相关性，因此需要对原始特征参数进行降维处理。 4）基于微架构无关特征参数，通过聚类算法将所有的特征片段分成若干类，每一类中选取离聚类中心最近的特征片段作为典型特征片段。 3 数据的获取与分析 3.1 特征获取与预处理 本文以固定Cycle数（1 千万个 cycle）作为切割的粒度，将所选取的安卓应用程序切分成不同的片段，该操作可以利用Gem5 自带的命令行选项就可以实现。然后在Gem5的o3_config.ini配置文件中添加本文所需的特征参数名称，并通过修改Gem5原生提供的m5stats2streamline.py数据提取工具，对 Gem5 仿真获得的 stats.txt 文件做第一步数据提取工作，获取本文所需的微架构无关特征参数以及微架构相关特征参数。 不同的微架构无关特征参数具有不同的量纲，比如关键路径长度和空间局部性这两类微架构无关特征所对应的量纲是不一样的。为了消除微架构无关特征参数间的量纲影响，需要对数据进行标准化处理。原始数据经过标准化处理后，使得各数据指标处在同一数量级，适合后续一系列的降维以及聚类处理。标准化的方法如式（1）所示，其中[X]为原始数据中某一个微架构无关特征参数，[μ]表示[X]的平均值，[σ]表示[X]的标准差，[X*]是标准化之后的数据。 3.2 特征降维 由于本文总共选取了227个微架构无关特征维度，属于高维数据，而这些高维数据通常包含许多冗余[5]， 其本质维度往往比原始的数据维度要小得多。针对高维数据，通常可以采用相关的降维方法来减少若干并不相关的数据，从而降低高维数据的维度。本文所采用的降维方法为主成分分析，该方法是一种经典的数据统计分析方法，有两个主要功能：①将维度相关的数据集转换为维度互不相关的数据集；②降低数据集的维度，而不会损失太多信息。主成分分析的主要思想是对变量进行计算，得到互不相关的主成分（每个主成分是原始变量的线性组合），即将p个变量转化为p个主成分，保留p个主成分中的前q个，在q[<<]p的情况下可以大大降低数据集的维度。一般来说，主成分分析所得到的主成分与原始数据间有如下关系： 1） 每个主成分都是个原始特征维度的线性组合。 2） 主成分的数目远远小于原始特征维度的数目。 3） 主成分保留了原始特征维度中绝大多数的信息量。 4） 各主成分间互不线性相关。 3.3 特征聚类 对微架构无关负载特征数据集进行降维处理以后，本文采用K-means聚类算法对微架构无关参数进行聚类分析，并将聚类后每一类中离聚类中心最近的片段作为最终所选取的典型特征片段。K-means[6]是同类文献中使用最频繁的聚类算法，由于K-means算法的执行效率较高，因此在对规模较大的数据集进行聚类时被广泛使用。K-means聚类算法以 k 为参数，把所有数据对象分成 k 个类，使得类内数据的相似度较高，而类间数据的相似度较低。该算法是一个迭代过程，其处理过程如下：首先，随机的选取 k个数据对象，每个数据对象初始的代表了一个类的平均值，对于剩下的每个数据对象，计算该对象与各类中心的距离，并将其赋给与之最近的类，然后重新计算每个类的平均值，该过程不断重复，直到收敛，即每一个类中的数据对象不再改变或者达到最大迭代次数[7]。可以看出，K-means聚类算法产生的是球形聚类，数据点分布在聚类中心的周围。聚类分析得到的聚类有着相似的负载行为特征。对于特定聚类来说，最接近聚类中心的数据点可以代表该聚类，作为相似特征片段的代表性样例。 4 典型特征片段代表性验证 基于PCA处理后的微架构无关负载特征，利用K-means算法将Moby中的每一个应用的片段聚成了100类，并选取每一类中离聚类中心最近的片段作为该类的典型特征片段。为了验证所选典型特征片段的代表性，本文计算了特征片段与应用整体的IPC 误差、L1 I-Cache miss 误差、L1 D-Cache miss 误差以及Branch miss 误差。以IPC误差为例，其误差计算公式如（2）所示。 其中[IPCseli]为聚类后第i类所选典型特征片段的[IPC]值，[ai]为聚类后第i类中的片段数，即对应所选典型特征片段的权重值，A为应用切割后的总片段数，[IPCtotal]为应用整体的[IPC]值。每个应用所选典型特征片段与应用整体的各相关特征的误差如表1所示。 由表1可知，将每个应用的片段均聚成100类后，所选典型特征片段与多个安卓应用整体的IPC平均误差为1.29%，L1 I-Cache miss 平均误差为3.84%，L1 D-Cache miss 平均误差为3.73%，Branch miss 平均误差为7.85%，所选典型特征片段与应用整体的多个相关特征的平均误差均在10%以内。因此，最终所选取的典型特征片段能较好地代表整个安卓应用执行时的负载特征。 5 结语 本文基于微架构无关负载特征参数提取了安卓应用的典型特征片段，且最终所选取的典型特征片段能较好地代表整个安卓应用执行时的负载特征，但仍有很多地方值得完善。第一，在微架構无关负载特征的参数选择上，还可以根据新的应用场景添加新的参数，使得微架构无关负载特征更加完善，更能准确地量化软件负载特征。第二，本文仅针对Moby测试集中的安卓应用进行了分析与研究，而没有涉及到其他交互式应用，后续对安卓应用场景的选择需要进一步完善。第三，在研究应用的阶段行为时，对不同的切割方法需要进一步研究，使得切割所得的特征片段更能反映程序阶段性的软件负载特征。 参考文献： [1] Guthaus M R， Ringenberg J S， Ernst D， et al. MiBench： A free， commercially representative embedded benchmark suite [C].Proceedings of the Workload Characterization， 2001 WWC-4 2001 IEEE International Workshop on， IEEE， 2001： 3-14. [2] Lee C， Potkonjak M， Mangione-Smith W H. MediaBench： a tool for evaluating and synthesizing multimedia and communicatons systems [C].Proceedings of the Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture， IEEE Computer Society， 1997： 330-5. [3] Gutierrez A， Dreslinski R G， Wenisch T F， et al. Full-system analysis and characterization of interactive smartphone applications [C].Proceedings of the Workload Characterization （IISWC）， 2011 IEEE International Symposium on， IEEE， 2011： 81-90. [4] 李郁林. 高維数据分析中的降维研究[J]. 计算机软件与应用，2012，17（3）： 2-5. [5] 谭维. 数据挖掘中聚类集成与半监督聚类研究 [D].西南交通大学， 2010. [6] 冯超. K-means聚类算法的研究 [D].大连理工大学， 2007. [7] 付峰.聚类分析（三）K 中心点算法（k-mediods）[D].西南交通大学， 2009. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。