一种面向可变粒度内存系统的二进制文件重写方法

摘要

本发明提供一种面向可变粒度内存系统的二进制文件重写方法，包括：在二进制文件的中间表示中找到热循环区域；对于访存行为符合可变粒度访存模式的热循环区域，合并该区域内的访存信息，并且在该区域之前插入头语句；以及，根据修改后的热循环区域生成目标机器代码。本发明能够自动完成在二进制文件上支持可变粒度内存系统的访存操作；通过自动分析应用程序特征以及可变粒度内存系统的核心特征，选择合适的重写方式，兼顾了二进制文件重写过程的效率和二进制文件的执行性能。

说明书

技术领域

本发明涉及编译器优化技术领域，更具体地，涉及一种面向可变粒度 内存系统的二进制文件重写方法。

背景技术

计算机的内存系统是影响计算机体系结构和软件执行效率的重要因 素。传统的内存访问的数据粒度是固定不变的，而且有增大的趋势。但是 在真实程序中，实际每次数据访问的粒度是变化的，对于数据访问是无局 部性且粒度很小的应用，每次访问采用固定的大数据粒度必然会造成浪 费；而一些需要大量连续数据读写的应用，又需要将整个数据访问分割成 多个内存事务进行，从而增加了协议上的开销。可见，固定粒度的访存模 式无法有效利用访存带宽。随着云计算、大数据应用的兴起，程序对数据 的访问带宽和容量要求越来越高，传统内存系统遇到延迟、带宽、效率、 容量、功耗的挑战，从而出现了新型的内存系统，可变粒度内存系统是其 一。可变粒度内存系统是能够支持不同粒度访存请求的内存系统，其合理 地合并访存请求，能够减少访存总开销并提高有效带宽利用率。

对于可变粒度内存系统来说，新的结构特征往往涉及访存方式的一些 变化。例如，需要显式地增加指令来移入/移出数据、合理合并访存请求， 以减少访存次数及开销并提高有效带宽利用率。由于大量的面向传统内存 系统的二进制形式的应用程序代码(下文简称二进制文件)不适用于可变 粒度内存系统，因此如何将该二进制形式的应用程序代码平滑地移植到可 变粒度内存系统上，同时无需应用程序的源码且无需修改编译器源码，是 目前需要解决的问题。

发明内容

针对上述问题，根据本发明的一个实施例，提供一种面向可变粒度内 存系统的二进制文件重写方法，包括：

步骤1)、在二进制文件的中间表示中找到热循环区域，其中，热循环 区域是执行次数超过预定阈值的循环的代码区域；

步骤2)、对于访存行为符合可变粒度访存模式的热循环区域，合并该 区域内的访存信息，并且在该区域之前插入头语句；其中，一个访存信息 指示一条访存指令且包括访存所访问的地址信息，所述头语句用于实现从 可变粒度内存系统读取的功能；

步骤3)、根据修改后的热循环区域生成目标机器代码。

上述方法中，在步骤2)中，合并访存行为符合可变粒度访存模式的 热循环区域内的访存信息包括：

合并该区域内的访存信息，使得合并后的访存信息对应的效益大于构 成该合并的每个访存信息对应的效益之和并且合并后该区域的访存行为 符合可变粒度访存模式；其中，所述效益与资源占用率及性能相关联。

上述方法中，所述效益表示如下：

$f(\mathrm{factor},\mathrm{effcet})=\underset{i=1}{\overset{\mathrm{FACTORS}}{\Sigma }}({\mathrm{factor}}^i*\mathrm{effec}{t}^i*{\beta }^i)$

其中，FACTORS＝3，factorⁱ表示effectⁱ的意愿因子，取值在0到1之 间，并且βⁱ为参数；effect¹＝size(data)/time(data access)， size(data)表示合并的访存信息的数据总长度，time(data access)表示合并的 访存信息对应的可变粒度内存系统的访问次数与一次访问内存的开销之 积；effect²＝size(data)/size(transfer_data)，size(transfer_data)表示合并的 访存信息对应的可变粒度内存系统的访问操作的总数据传输量；effect³＝ size(data)/size(getin_data)，size(getin_data)表示合并的访存信息对应的可 变粒度内存系统访问操作所存入高速缓存的总数据量。

上述方法中，步骤1)之前还包括：选择动态地执行二进制文件重写 或者静态地执行二进制文件重写。其中，人为选择二进制文件重写的动态 或静态执行方式；或者如果不存在人为选择，则对于运行时间大于预定时 间阈值且系统资源满足其资源需求的二进制文件，选择动态地执行二进制 文件重写，否则选择静态地执行二进制文件重写。

上述方法中，步骤1)还包括：

如果静态地执行二进制文件重写，则将所述二进制文件翻译成中间表 示；

如果动态地执行二进制文件重写，则将已执行的并且未翻译过的二进 制文件代码翻译成中间表示。

上述方法中，步骤2)包括对于访存行为符合可变粒度访存模式的热 循环区域执行以下步骤：

步骤21)、提取访存信息，按顺序记录该访存信息；其中，一个访存 信息指示一条访存指令且包括访存所访问的地址信息；

步骤22)、如果动态地执行二进制文件重写，则采用预定的方式合并 该区域内的访存信息；如果静态地执行二进制文件重写，则对该区域内的 访存信息根据地址信息进行聚类，在每个类内采用预定的方式合并访存信 息；

步骤23)、合并后，在该区域之前插入头语句，该头语句用于实现从 可变粒度内存系统读取的功能。

在步骤22)中，采用预定的方式合并区域内的访存信息包括：

从该区域的初始访存信息开始依次尝试合并访存信息，直到遇到一个 访存信息m使得合并后该区域的访存行为不符合可变粒度访存模式或者 合并后的访存信息对应的效益不大于构成该合并的每个访存信息对应的 效益之和，合并初始访存信息到该访存信息m之前的访存信息；将该访存 信息m作为初始访存信息重复以上过程，直到处理完该区域的最后一个访 存信息。

上述方法中，步骤3)还包括：

如果静态地执行二进制文件重写，则根据生成的目标机器代码得到新 的二进制文件并输出；

如果动态地执行二进制文件重写，则将生成的目标机器代码存放到指 定的内存区域并且更新相应前驱基本块的相关跳转指令，如果源二进制文 件未处理完则返回步骤1)。

上述方法中，步骤2)还包括：合并后，在该区域之后插入尾语句， 该尾语句用于实现向可变粒度内存系统写回的功能。

上述方法中，对于采用用户可编程的片上存储器作为片上高速缓存的 可变粒度内存系统，步骤2)还包括：建立内存虚拟地址与对应的片上存 储器虚拟地址的映射关系，并且修改相应指令。

上述方法中，将具有连续访问大块数据的特征或者固定步长地非连续 访问大块数据的特征的热循环区域作为访存行为符合可变粒度访存模式 的热循环区域。

本发明为当前的二进制文件选择适用的重写方式，通过静态或者动态 二进制重写过程，对访存指令自动进行可变粒度内存系统适用性的分析， 自动增加地址空间映射，进行向可变粒度内存系统的访存代码的转换，从 而实现应用程序向可变粒度内存系统的平滑移植。本发明不需要应用程序 的源码并且不需要修改编译器源码，就能够自动完成在二进制文件上支持 可变粒度内存系统的访存操作，适用于很多应用场合；此外，通过合理地 合并访存请求，减少了访存总开销，提高了有效带宽利用率，并且兼顾了 二进制文件重写过程的效率。

附图说明

以下参照附图对本发明实施例作进一步说明，其中：

图1是根据本发明一个实施例的面向可变粒度内存系统的二进制文件 重写方法的流程图；

图2(a)-2(c)是根据本发明一个实施例的访存代码转换前后的示 意图。

具体实施方式

为了使本发明的目的，技术方案及优点更加清楚明白，以下结合附图 通过具体实施例对本发明进一步详细说明。应当理解，此处所描述的具体 实施例仅用以解释本发明，并不用于限定本发明。

根据本发明的一个实施例，提供一种面向可变粒度内存系统的二进制 文件重写方法。

概括而言，该方法包括：在二进制文件的中间表示中找到热循环区域； 对于访存行为符合可变粒度访存模式的热循环区域，合并该区域内的访存 信息，并且在该区域之前插入头语句；以及，根据修改后的热循环区域生 成目标机器代码。

下面结合图1对该面向可变粒度内存系统的二进制文件重写方法的各 个步骤进行详细描述。

第一步：选择合适的重写方式

在本步骤中，对二进制形式的应用程序代码(即二进制文件)选择合 适的重写方式。其中，重写方式包括在线的动态重写方式和离线的静态重 写方式，后文分别简称为动态重写和静态重写。

具体来说，优先满足用户或者管理员的人工决定或干预，如果用户或 者管理员人工输入了对重写方式的选择则遵从该选择；否则，由自动选择 模块(即系统中负责对二进制文件选择合适的重写方式的软件模块)来自 行分析决定。在一个实施例中，自动选择模块根据二进制文件的当前执行 状态和历史记录对重写方式进行选择，规则如下：

如果二进制文件已经运行了足够长的时间(即不宜停止)，并且在之 前的一段时间内系统资源能够满足其资源需求，则对该二进制文件选择动 态重写；否则选择静态重写。其中，如果运行时间大于预定的一个阈值， 则认为该二进制文件已经运行了足够长的时间。这里考虑资源需求的原因 在于：如果相应的应用程序的资源需求太大，则不宜进行需要额外资源的 动态重写。本领域技术人员应理解，上述运行时间和资源需求等数据可通 过现有的编译方法进行估算。

第二步：目标区域圈定

概括而言，本步骤在对二进制文件进行解析生成的中间表示上进行热 循环(例如，FOR循环)区域标注，其中，热循环区域是指执行次数较高 (例如，执行次数超过预定次数)的循环的代码区域；以及，判断热循环 区域是否是要转换的目标区域。

在一个实施例中，目标区域圈定过程包括如下子步骤：

1.将二进制文件转换成该二进制文件的中间表示。

本领域技术人员应理解，中间表示是指二进制翻译软件采用的某种中 间表示，中间表示需要尽可能地保持源程序里每条指令的语义，并且支持 多种指令集的不同特性，方便二进制翻译的设计与实现。

其中，对于静态重写，一般先装载源二进制文件、再反汇编，并且将 其翻译成中间表示；而对于动态重写，则将已执行过且之前未翻译过的二 进制文件代码进行翻译，生成中间表示。

2.在中间表示上找到热循环区域。

3.对热循环区域的代码做分析，判断其访存行为是否符合可变粒度访 存模式，如果符合，则认为是要转换的目标区域并对其进行标注，从而得 到目标区域R₁,R₂,…,R_k(k为正整数)。对于每个目标区域R_j(1<＝j<＝k) 提取访存信息，得到<m_j0,m_j1,…,m_jn>(n为整数)，其中m_ji称为一个访存 信息结点(简称结点)，其表示应用程序的一条访存指令，包含访存所访 问的地址信息，m_j0,m_j1,…,m_jn的顺序即对应的访存信息在目标区域中的顺 序。

在一个实施例中，判断热循环区域内的访存行为是否符合可变粒度访 存模式包括：考虑是否具有连续访问大块数据的特征，或者固定步长地非 连续访问大块数据(从而导致带宽利用率低)的特征，如果具有该特征， 则将该热循环区域视为目标区域。

根据以上步骤，具体地，对于动态重写，对被执行的且未翻译的二进 制文件代码生成中间表示，然后分析程序的动态执行踪迹(即动态执行的 指令流，trace)得到热循环区域，分析热循环区域的访存行为是否符合可 变粒度访存模式，如果符合，则将该热循环区域视为目标区域进行圈定。

对于静态重写，生成中间表示，借助编译器技术的控制流分析识别出 热循环区域，分析其访存行为是否符合可变粒度访存模式，如果符合，则 在中间表示上将该循环区域视为目标区域进行圈定。

第三步：一体化访存分析

在目标区域R_j(1<＝j<＝k)内对访存信息结点进行合并分析，在本文 中，采用参数化的效益模型来计算连续、非连续访存操作合并的收益，根 据收益来指导合并哪些访存信息结点，并在后续步骤替换成对可变粒度内 存系统的访问。其中，效益模型考虑以下两方面因素：

1)用户意愿；

2)可变粒度内存的核心特征。

其中，用户意愿作为模型中的系数而存在；可变粒度内存的核心特征 涉及性能、资源、功耗等因素，例如，访存数据长度、访存延迟、有效带 宽占用率、有效OCM(片上存储器)占用率等等。

在一个实施例中，效益模型的构建过程如下：

1)考虑用户意愿因子：每个因子取值在0～1之间，以FACTORS表 示因子的总数，其中：

factor¹＝以单位时间数据量衡量的性能的用户意愿因子；

factor²＝有效带宽占有率的用户意愿因子；

factor³＝有效OCM占有率的用户意愿因子；

$\underset{i=1}{\overset{\mathrm{FACTORS}}{\Sigma }}{\mathrm{factor}}^i=1;$

其中，FACTORS＝3。

2)考虑核心特征，包括：

(a)时间效益，以单位时间的数据量来计算，如下式所示：

effect¹＝size(data)/time(data access)

其中，以考虑合并的若干结点表示的数据总长度为size(data)，而其 对应的可变粒度内存的访问次数乘以一次访问内存的开销为time(data  access)。

(b)资源效益，以有效带宽占用率effect²和有效OCM占用率effect³来计算。

其中，有效带宽占用率表示如下：

effect²＝size(data)/size(transfer_data)；

其中，以考虑合并的若干结点表示的数据总长度为size(data)，而其 对应的可变粒度内存的访问操作的总数据传输量为size(transfer_data)，包 括这些结点表示的数据、这些内存访问操作访问的无用数据，以及访问操 作相关的信息数据。

有效OCM占用率表示如下：

effect³＝size(data)/size(getin_data)；

以考虑合并的若干结点表示的数据总长度为size(data),而其对应的 可变粒度内存访问操作所存入高速缓存的总数据量为size(getin_data)，包 括这些结点表示的数据、这些内存访问操作访问的无用数据。其中，一次 内存访问操作可能在访问需要的数据同时也访问到部分无用数据，这是由 于内存系统提供的访问操作模式与用户应用中出现的各种数据访问模式 之间可能存在差异，导致访问到部分无用数据。

3)得到效益模型。

首先进行归一化，为每部分(即单位时间的数据量、有效带宽占用率 和有效OCM占用率)分别设置一个参数β¹,β²,…,β^FACTORS,使每部分效益 具有可比性，接着得到如下的效益模型：

$f(\mathrm{factor},\mathrm{effcet})=\underset{i=1}{\overset{\mathrm{FACTORS}}{\Sigma }}({\mathrm{factor}}^i*\mathrm{effec}{t}^i*{\beta }^i)$

根据效益模型可计算合并后的收益，如下式所示：

benefit＝f^after-f^before

其中，f^after表示合并后的结点对应的效益，f^before表示合并前每个参与 该合并的节点分别对应的效益之和。

根据上述效益模型，对于符合可变粒度访存模式的所有可能的合并方 式，收益大于零的情况被认为值得合并。优选地，在所有可能的合并方式 中，选择收益最大的方式在第四步进行合并。在一个实施例中，可以将读 操作与写操作分开合并，也可以放在一起进行合并。

在进一步的实施例中，对于动态重写，考虑效率而采用快速合并法。 其中，从R_j区域内的起始结点开始顺序尝试合并，直到遇到某个结点m_ji(i为正整数)而停止；其中m_ji不能与前面已尝试合并的结点合并成可变 粒度内存访问操作(即不符合可变粒度访存模式)，或者经由效益模型计 算认为不值得合并成可变粒度内存访问操作；因此，从m_j0到m_ji-1确定了 一个可合并的、有收益的范围。接着，以结点m_ji为起始结点重复上述过 程直到对R_j区域内的访存信息结点都进行了分析。在该过程中，收益大于 零的情况都认为值得合并。

在进一步的实施例中，对于静态重写，采取聚类分析再合并的方法。 首先，对R_j区域内的访存信息结点按照地址信息作聚类分析，地址相近的 划分在同一类，地址相距较远的划分在不同类。分类后，对每一类的结点 再采取快速合并法，其中结合效益模型考虑该类内哪些结点适合合并，直 到对Rj区域内的访存信息结点都进行了分析。

第四步：一体化合并

根据第三步分析得到的合并方案，进行合并。将需要合并的一个或多 个访存信息结点合并为一个结点并更新其数据长度信息，而未发生合并的 结点不作更新依然记入目标区域R_j的访存信息。自此更新目标区域R_j的 访存信息为<m’_j0,m’_j1,…,m’_jp>(p<＝n)，其中m’_ji是一体化合并后的访存信 息结点，每个m’_ji对应一个可变粒度内存访问操作。

第五步：地址映射

本步骤适用于采用了用户可编程的OCM(on-chip-memory)作为片上 高速缓存的可变粒度内存系统，这样的OCM需要由用户或者编译器来管 理其地址空间，包括分配、回收以及实用时的映射，通常需要插入显式的 Map指令以建立内存虚拟地址与对应的OCM虚拟地址的映射关系。若不 是采用OCM作为片上高速缓存的可变粒度内存系统，则本步骤不是必须 的。并且，根据目标区域R_j的访存信息<m’_j0,m’_j1,…m’_jp>，找到结点对应 的中间表示上的各条指令，将其中的虚拟地址替换成相应的OCM虚拟地 址。

参见图2(a)-图2(b)，其中在图2(b)中插入了Map指令来进行地 址映射，并且对相应的指令也作出修改。

第六步：内存操作头、尾语句的注入

在每个R_i区域前增加新基本块以插入内存操作的头语句，从而完成访 存操作m’_ji的从可变粒度内存系统的某个地址读入指定长度数据的功能。 此外，还可以在R_i区域后新增加基本块以插入内存操作的尾语句，完成访 存操作m’_ji的向可变粒度内存系统的某个地址写入指定长度数据的功能， 但如果R_i中没有写回动作则不插入该尾语句。相应地，更新相关基本块的 控制流信息。

参见图2(c)，插入头、尾语句可完成从可变粒度内存的读取和向可变 粒度内存的写回。

第七步：生成目标代码。

首先，由经过第五、第六步处理的中间表示生成目标机器代码。

接着，对于动态重写，将生成的目标机器代码存放到专门的内存区域， 并且相应地，更新前驱基本块的相关跳转指令；如果源二进制文件未处理 完，则返回第二步继续处理。对于静态重写方式，将生成的目标机器代码 重新进行链接(原因在于：根据修改后的中间表示，可能生成多个目标机 器代码)从而生成新的二进制文件，并且输出该二进制文件。

根据本发明提供的面向可变粒度内存系统的二进制文件重写方法，发 明人还对以下目标区域进行了实验，其中数组a为整数类型：

For(i＝0；i<1000；i++)

  For(j＝0；j<1000；j++)

  {

  关于a[i][j]的计算；

  }

对于普通的DRAM内存系统，按照cache line大小(64Byte)取数， 则需要从内存取4*1000*1000/64＝62500次，由于每次从CPU片外取数， 延迟较大，需要几十到上百个拍(即时钟周期)。

而对于可变粒度内存系统，其中以OCM作为片上高速缓存(相当于 cache)，数据从内存先取入OCM(采用可变粒度的特殊访存指令，如果是 消息式内存即为一条消息指令)，实际计算时数据从OCM经过普通的load 指令取入而进行计算。假定从可变粒度内存到OCM取数每次最多1KB， 则从内存到OCM取4*1000*1000/1024＝3906次。这里，用普通load指令 从OCM取数，一般只需要几拍。这里极大地减少了片外取数的开销，从 而通过减少用户应用的运行时间开销获得性能提升。

应当理解，虽然本说明书是按照各个实施例描述的，但并非每个实施 例仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起 见，本领域技术人员应当将说明书作为一个整体，各实施例中的技术方案 也可以经适当组合，形成本领域技术人员可以理解的其他实施方式。

以上所述仅为本发明示意性的具体实施方式，并非用以限定本发明的 范围。任何本领域的技术人员，在不脱离本发明的构思和原则的前提下所 作的等同变化、修改与结合，均应属于本发明保护的范围。