迭代计算特征识别的方法研究

　　【摘要】

为了应对网络空间信息服务面临的海量空间数据发布和大规模用户并发访问的挑战，现如今的大数据应用对内存容量和性能提出了更高的要求，完成高性能计算系统功能优化的研究显得尤为重要。而高性能计算应用往往具有迭代计算的特征，应用的计算和访存特征一般都与正在执行的指令密切相关，因此识别一次迭代中不同的执行代码区域，以及识别出程序迭代发生过程会有助于更准确地分析和预测应用执行特征。不同的代码区域对应着不同的执行阶段，HPC应用的迭代中一般具有多个不同的执行阶段。以常见的卷积神经网络训练为例，一次训练迭代中包含卷积层、池化层、全连接层等多个执行阶段。不同的执行阶段具有截然不同的计算和访存特征，所以识别出一次迭代中不同的执行阶段，并对各个阶段的计算和访存特征进行刻画是至关重要的。

为了从性能上优化这些具有普遍迭代计算特征的高性能计算系统，本文将通过程序阶段识别技术，利用Scarphase程序阶段分类方法实现分析和识别典型应用程序中的迭代计算过程和阶段信息，并在此基础上成功识别出计算机应用程序在执行中发生迭代计算过程的时间片段，并使用Intel Pin动态二进制插桩框架,同时为了减少开销时间对其Pintools中算法进行优化，采集其中迭代计算过程中的访存地址特征，以达到以更好地通过资源调度分配或者数据预取等手段提高系统性能的目的。

　　【关键词】高性能应用；程序阶段分类；迭代计算；内存访存特征；基本块向量

　　1引言

　　1.1研究背景与意义

在大数据时代和高性能应用广泛的今天，高性能应用如人工智能，机器学习，深度学习等应用往往存在明显的迭代计算特征，即周期性地执行特定的代码指令。举一个高性能应用中比较经典的例子：机器学习。机器学习的广泛应用离不开迭代计算的执行过程。在机器学习实践的应用中，机器学习系统的一般流程包括了数据源获取、预处理数据、验证、最终投入运用预估等内容，在这之中模型训练的过程中存在普遍的迭代计算特征，为了达到所预期的机器学习模型，并且提升机器学习模型的识别率和准确性，通常需要大量数据集对模型进行训练，训练数据，再根据训练结果调整选择的模型所暴露的一些参数，然后再次回到训练过程，根据训练结果调整模型参数，不断重复，最终经过海量的迭代训练得到最终模型，这个过程具有明显迭代计算特征，而这整个训练模型的迭代阶段几乎是整个应用系统中最耗费时间和性能的过程。因此，识别迭代计算过程的方法研究也会为高性能应用的性能提升优化指出新的方向。

从识别迭代运算的方法展开研究，对迭代计算典例合理分析和识别，针对下一次的迭代运算、访存特性展开描述。通过前几轮迭代的信息来预测下一轮迭代的计算和访存数据区域，据此充分利用预取、复用、局部性等优化方法，提升HPC应用访存性能，相邻迭代中往往具有相同的执行阶段，相同执行阶段具有类似的计算和访存特征。从硬件层面上，利用前几轮迭代的信息来预测下一轮迭代的计算和访存密度关系，依此提前对硬件资源进行合理的调度，提高硬件资源利用率，迭代计算阶段识别与访存特征对于实现计算机设备硬件方面可以提供有效的技术数据参考，根据这些特征理论上设计专门面向高性能计算的存储器设备和应用，对内存的性能，硬件开销，功耗等设计进行优化。从软件层面上，通过获取迭代计算阶段识别和访存特征，可以对程序进行迭代计算分析和优化，利用迭代计算的规律，在进行一个迭代程序阶段时，根据上一次迭代循环的访存特征去预测下一次迭代过程的访存情况，减少缓存命中时间，降低缓存的失效率，从而提升访存平均时间，维持相较低的运行开销。除此之外，在涉及迭代计算的多个高性能应用领域中，识别程序执行过程中的迭代计算过程，获取到的迭代计算特征与访存特征将为进一步提升高性能应用系统的性能和内存预测方法提供重要数据依据和支撑。

　　1.2国内外研究现状

在国内外目前的研究方向中，提升高性能应用的运算速度以及性能的方法主要分为大体着重于硬件或软件实现。从硬件方面上实现对高性能应用的计算速度提升的方法一般有优化硬件中的结构设计或者专门设计面向适配高性能计算特征计算过程的计算机硬件组件，随着大数据和高性能应用的持续普及化，针对更高性能存储器的要求也愈发急切，例如近几年比较新的存储器技术的提出：D C Gilmer等人[1]研发的NRAM技术，是一个新型高性能存储器技术，具备众多优点同时继承了FRAM（ferroelectric Random Access Memory）的高速写入、高读写耐久性，又具备与相当的大容量，并实现很低的功耗。着重使用软件实现的技术一般会对程序适当分析和识别，整体提升程序数据、指令存在的局限性，让内存缓存失效率有所降低，划分主要有软件预取、循环变换等方式，运用程序分析方式，能够获取下一步程序具体的访问数据或是指令，由此能够在信息之上代入现代处理器所支持的一些非阻塞指令。对比所谓的硬件预取，软件预取能够更轻易的按照软件自身的特性合理拟定。早些时候，软件预取技术集中焦点在密集性内存操作程序，对此应用程序分析技术[4-5]，就能够获悉之后程序执行时可能应用到的相关数据信息，由此预取数据。比如Wu, Youfeng[6]通过分析程序的步幅模式（Stride Pattern）来实现数据预取，Beyls K和Cong J等人[7-8]分析程序对数据访问的复用距离（Reuse Distance）对程序执行过程进行分析来实现数据预取。Chilimbi T M等人[9]研发了一项动态软件预取框架对软件之中存在的热数据流加以分析，转而完成指针之上的数据结构数据预取作业。Cong，Json等人[10]利用循环变换针对迭代空间变换、调度等操作完成数据访问局部性的提升。应用循环变换技术，既能够让指令局部性特点有所提升，也可以让指令转变执行顺序而让数据的局部性获得提升。而本文使用的方法可以归类为上述软件实现方法，通过识别出迭代计算的过程以及识别迭代计算过程中的内存访问模式，对下一次迭代计算进行预测，并研究如何提高识别的准确性和维持系统较低的开销，进而可以提高运算效率。

　　1.3本文的研究内容

本课题的目的是设计一种有能力识别例如机器学习模型等的典型高性能应用在运行过程中的迭代计算过程的识别技术方法，并学习采集其在进行迭代计算任务的访存地址数据和性能指标，对之后下一次迭代计算提供所需数据和访存特征提供参考，以达到提高系统预测准确率与减少系统开销的目的。本课题的主要工作内容展示如图1-1所示，针对于目前少有能直接识别程序执行中迭代计算过程的框架和应用，因此为了实现识别程序迭代计算过程的目的，需要先使用程序阶段分类技术，对程序执行过程中相同阶段内出现的特征值进行收集，分类出程序阶段信息，然后设计迭代识别算法对程序阶段信息进行识别，确定应用程序迭代计算阶段的执行具体分布，本文提出了一种基于Scarphase程序阶段分类方法的识别迭代解决方案，并且借助基于动态二进制插桩技术的程序分析工具Intel Pin采集由上一步中识别出来的程序迭代计算过程中的访存地址和性能指标，总结出高性能迭代计算的访存特征。本课题工作具体可以划分为两部分：识别计算应用程序迭代过程以及采集其中迭代计算任务的访存地址和性能指标。

第一部分详细地阐述了我们提出的Scarphase方法识别迭代解决方案的具体步骤和原理，以及每一步骤的实现方法和算法优化，实现对计算机应用程序执行过程中的迭代计算过程识别。第二部分描述了我们如何根据第一部分程序中识别出来的迭代计算阶段的时段分布，利用我们优化改进过的程序分析工具，采集此阶段的内存访存数据和性能指标，并最终总结出迭代计算的访存特征。

图1-1 本文主要工作内容展示

　　1.4本文的组织结构

本文一共划分为五个章节，本文的第一章主要介绍了高性能应用计算优化的具体发展实况，对高性能应用迭代计算全过程予以识别，了解其对于计算优化相关的研究背景、研究意义，让高性能应用的功能、计算速度等提升的研究现状加以介绍，对本文研究内容也有简单介绍。第二章侧重于对本文工作背景相关技术，程序阶段分类模型，程序分析工具以及内存预测技术等相关背景技术展开介绍。第三章我们将具体阐述本文提出的Scarphase识别迭代过程解决方案的具体实现步骤细节以及原理，该方案借助程序阶段分类技术，识别程序迭代过程算法等技术实现了对程序中迭代计算过程的识别，并得出迭代过程在整个程序执行中的执行分布以及性能信息。第四章介绍本文的实验环境与配置，并展示我们的实验结果，并分析总结迭代过程中的访存与性能特征。第五章总结全文并探讨了未来可能的研究方向。

　　2程序阶段检测分类技术与动态二进制插桩

　　2.1基于动态二进制插桩的pin程序分析技术

Pin是Intel公司在2012年推出的一种动态二进制检测框架，主要应用的是IA-32、x86-64 和 MIC 指令集架构，能够构建起一种动态程序分析工具，对包括Linux， macOS 和 Windows等在内的操作系统以及可执行程序予以支持。Pin为之提供相对丰富的API，能够将底层指令集特征抽象出来，准许进程寄存器数据等信息能够当做是参数所传递出的代码。Pin是一种寄存器，能够在代码覆盖上自动存储、重置，由此能够恢复程序以便继续运行，针对符号、调试信息等能够有一定的访问权限。

2.1.1动态二进制插桩技术的优势

程序插桩技术顾名思义就是确保被测试的程序保证原本的逻辑完整性，基于此能够在程序里插进部分探针，也就是一种探测仪。究其本质就是对信息进行采集的一种代码段，能够为赋值语句或是采集覆盖信息相对的函数调用，从探针执行、抛出程序运行等特性数据操作中，对相关数据展开分析，由此能够获得程序的管控流、数据流等数据，对于程序运行的动态上下信息都有所收集，转而达成测试最终目的的一种方式。

根据插桩对象的区别，能够划分为两种，一种是源代码插桩，一种是二进制插桩。

1)源代码插桩（Source Code Instrumentation，SCI)：将额外代码添加到程序源代码里。意思是，源代码插桩就是源文件实现完整词法和语法的分析，基于此展开运行。如此就能够确保源文件插桩可以达成较高的精度和针对性。不过源代码插桩可以和源代码接触，让工作量有所加大，因为编码语言、版本区别等需要适当改动，源插桩对于软件应用程序的源代码掌握有所要求，不然就不能操作插桩。

2)二进制插桩（Binary Instrumentation，BI）区别于源代码插桩技术，二进制插桩对于被分析的应用程序源代码没有获取需求，反而是针对额外插桩分析代码适当添加到二进制可执行文件里，对于二进制插桩，理论上可以与任何软件应用程序一起使用。

基于二进制插桩，它能够划分为两类状况：其一是对于没有执行的目标代码进行插桩，也就是静态插桩，由始至终将测试代码插入，而后执行程序。此等模式适合应用到需要完成完整系统或是仿真的时候的代码覆盖操作测试；其二是对于运行中的程序进行测试代码插入操作，从而对程序在特殊时间的运行状态信息加以检测。向正在运行的程序插人测试代码，即动态二进制插桩（dynamic binary instrumentation ,DBI）技术，由于其易用性和灵活性使其在编程语言、软件测试和安全研究中得到了广泛的应用。两者主要区别有：

1)静态插桩：该项技术主要是程序执行之前将额外的代码、数据插入，由此成为一个永久变化的可执行文件，涵盖的有简单手动插桩，基于编译器/汇编器的插桩，以及链接时或链接后的可执行文件编辑。

2)动态二进制插桩（dynamic binary instrumentation ,DBI）进行程序运行的时候动态的将额外代码、数据一一插入，自此可执行文件毫无永久变动。动态插桩技术的实现往往比静态的更复杂，但可以跟踪动态链接的库和间接分支，而这些是静态插桩难以处理的。

图2-2 插桩技术分类

所谓动态二进制插桩技术，能够保证不影响程序动态执行结果之下，严格遵照用户的需求分析，进行程序执行的时候将特定的分析代码插入，完成对于程序动态执行全过程的分析和监控。大部分动态二进制插桩框架都存在着三式执行形式，分别是解释模式、探测模式和JIT模式。现阶段，动态二进制分析平台应用十分广泛，涵盖的内容有Pin，DynamoRIO和Frida，此外诸如动态二进制插桩以及别的框架等。

2.1.2Intel Pin – 动态二进制插桩框架

Pin是一项动态二进制插桩检测框架，整个检测过程就是在运行的时候针对编译二进制文件合理执行。所以，它不能对源代码重新编译，同时能够对动态生成代码的检测程序予以支持。Pin能够从别的Pintools应用在程序执行时候动态的插入代码到可执行文件中，同时也能够在正在执行的进程里有所运行。此外，作为一个闭源框架，Pin是它的本体和工具所组成。在其内部存在API，用户用此编写插件，利用Pin调用动态链接库模式，也就是Pintool。具体的Pin大致框架和组成详见下图。

图2-2 Pin 的基本架构和原理

（1）Pin的基本架构与原理

从上图就能够了解到，Pin主要是进程级虚拟机、代码缓存、给用户的插桩检测API等构成。对于其虚拟机则是涵盖了JIT编译器、模拟执行单元、代码调度内容，在这之中重点就是JIT编译器。一旦Pin对待插桩程序进行加载谋求控制权后，协调好调度器之后，编译器对二进制文件指令负责插桩，完成动态编译之后的代码涵盖的内容有用户定义下的插桩代码。等到编译之后的代码需要保存在代码缓存里，从调度完成交付。在程序运行的时候，Pin就会对于可执行代码的首段指令有所拦截，自此在后续的指令序列支持下生成新代码，生成的新代码也就是遵照用户定义的具体插桩规则基于原始指令之上添加到用户代码，从种种代码能够让运行的信息被抛出。而后让控制权给到新生成的指令序列中，进而在虚拟机之中合理运行。一旦程序转到新分支的时候，Pin能够重新抓到控制权，由此在新分支指令序列之上诞生新代码。

理解Pin就是一种JIT编译器，不过其中的输入并非字节码，属于一种可执行文件。Pin能够将可执行文件中的第一条指令拦截住，而后对于该项指令起始到后续的指令序列做好新的代码重新编译，自此控制权限也就发展到新生代码上。它会和原始代码相一致，不过Pin能够确保分支退出以后的代码序列能够再次获得控制权限。把控到控制权之后，Pin能够根据分支生成较多的代码，保持运行。Pin让全部生成的代码都能够存储在内存里，如此就能够重用代码。此等JIT模式下，执行的是一种生成的代码，仅仅以原始代码作为一种参考。一旦代码生成，Pin就会给到用户自身执行的代码机会。Pin针对具体执行的代码完成插桩，不需要管代码究竟是在哪个区域里。

（2）Pintool的介绍与使用

Pin在操作系统上工作的时候，能够将用户级别指令捕捉到。对于插桩程序运行，需要同时完成3个程序运行，分别是应用程序自身、Pin、Pintool。Pin属于一种引擎，能够对应用程序完成插桩，Pintool之中蕴含了插桩指令，能够视为是Pin的一个库。三者能够共享一个地址空间，不能够共享库，需要规避可能的冲突。要通过插桩完成对目标程序的分析，需要了解插桩的位置以及插入的代码，也就是插桩部分和分析代码部分。这两部分在Pin中被集成到了一类可执行程序中，也就是Pintool。

因此使用Pintool时，我们需要关注

1)插桩机制（instrumentation code）：具体在何位置将代码插入。

2)分析代码（analysis code）针对插桩点完成代码执行。

Pintool的插桩机制主要有四种模式（即四种插桩粒度）：

1)instruction instrumentation指令粒度：令INS表示的是一种指令对应的数据结构，它是最小的一种粒度。INS代码插桩就是对指令执行前后添加的一些附加代码，Pintool能够在可执行文件的各个指令支持下完成插桩，此等模式能够让开发者对trace中的迭代循环指令不会过多投入关注，包含循环的指令可能产生多次。会导致程序执行缓慢

2)trace instrumentation踪迹粒度： TRACE代表的是单入口、多出口的一种指令序列数据结构。Pin能够将TRACE划分为一些基本块，其中BLL就是单入口、单出口的一种指令序列。对于TRACE就是需要在指令出现跳转的时候插入，深入展开基础块分析，多是应用在记录程序执行序列

3)routine instrumentation 例程粒度： RTN能够代表过程程序语言编译器生成的函数或是过程。其中Pin运用符号表对例程进行查找，也就是对应的插入位置，应当将内置的初始化表函数调用。

4)image instrumentation镜像粒度： IMG代表的是全部被加载到内存的二进制可执行模块类别数据结构。对于每一次的被插桩进程能够在执行中载入了镜像类型文件，如此就能够认定是IMG类型处置

Pintool给出了较为丰富的API，能够将底层指令集特性抽象出来，准许进程寄存器数据等信息能够当做是参数所传递出的代码。Pin是一种寄存器，能够在代码覆盖上自动存储、重置，由此能够恢复程序以便继续运行，针对符号、调试信息等能够有一定的访问权限。最开始Pin是一种创建起的计算机体系结构恩熙工具，不过其API的灵活性特点能够构建起较之安全、仿真、并行等程序多项分析的一种多样化工具。对于Pin内置较多的样例插桩工具源代码，涵盖的内容有基础块分析等，严格遵照自身需求便于完成自定义开发。

　　2.2本章小结

本章介绍了程序阶段检测分类的工作原理并重点解释了介绍了Intel公司的动态二进制插桩分析框架pin的基本架构和原理，为下文我们使用其中Pintools并对其算法进行优化，收集程序中迭代计算过程的访存地址数据集并总结出迭代过程的访存特征做铺垫。到此，我们初步介绍了本文中的相关模型与技术背景。

　　【参考文献】

[1]D C Gilmer,T Rueckes,L Cleveland. NRAM: a disruptive carbon-nanotube resistance-change memory[J]. Nanotechnology,2018,29(13).

[2]付雄. 利用程序分析和优化提高Cache性能[D].中国科学技术大学,2007.

[3]Xiaoxia Wu,Jian Li,Lixin Zhang,Evan Speight,Ram Rajamony,Yuan Xie. Design exploration of hybrid caches with disparate memory technologies[J]. ACM Transactions on Architecture and Code Optimization (TACO),2010,7(3).