PMEvo：通过演化优化推断端口映射

1. 背景介绍

1.1 现代处理器设计

现代处理器会乱序执行指令。通常情况下，乱序执行会伴随着指令分解，就是把指令分解为更简单的微架构特定操作，叫做μops。CPU设计的简化视图如下，端口后有具体的执行单元，具体的执行流程如下：

1. 指令从L1 Cache中取指和译码，译码产生μops，μops会被放在μop Cache中，为将来的重复使用做准备。
2. 寄存器管理通过把每个操作的操作寄存器映射到一个更大的寄存器号的物理寄存器上，来解决依赖（写后读、写后写）
3. 调度器根据操作依赖和具体的可利用资源决定具体执行μop的端口
4. 端口后的具体执行单元，流水线的执行μop。

图1 现代CPU架构简略图

1.2 目的

为了能够提高处理器的性能，需要利用CPU的指令级并行的特性，因此需要知道每个端口后面具体有什么执行单元，也就是端口映射，但是处理器厂商不提供微架构的端口映射。

1.3 现有方法的缺点

目前存在通过实验推断端口映射的方法。但是有这些不足：但是依赖于具体的硬件性能计数器，因此不适用于所有平台。

1. 一些需要相当数量的手动尝试【7，12】
2. 局限于验证现有的端口映射【19】
3. 使用到Intel平台提供的性能计数器，适用性小【1，12，13】
4. 使用神经网络训练，但是不能够定位具体的性能瓶颈【20】

1.4 本文的工作

PMEvo是什么？使用演化算法寻找端口映射的框架，并且能够很好的解释自动产生的指令序列的吞吐测量结果

A framework that uses an evolutionary algorithm to find a port mapping that excels in explaining measured throughputs for automatically generated instruction sequences

本文的贡献如下：

1. 一个不依赖特定微架构特性，能够从特定设计的实验和测量的吞吐结果推断端口映射的演化算法。
2. 一个瓶颈模拟算法，能够根据给定的实验，有效的评估端口映射关系的适用性。

2. Throughput模型

目标是从吞吐测量值，推断具体的端口映射。因此提出了处理器在给定端口映射的情况下，执行指令的具体模型。

2.1 吞吐的定义

定义：throughput t*(e)，指执行一个指令序列的平均周期数

The throughput ???(??) of an instruction sequence (or experiment) ?? on a given processor is the average number of processor cycles required to execute ?? in a steady state.

2.2 两层模型

2.2.1模型介绍

问题：对于一次执行在一个端口映射上的experiment，throughput是固定的，如何最小化？或者说这些指令不需要执行，猜测一个端口映射，计算对应的throughput，然后到一直找到throughput最小的端口映射。

两层模型先暂时不考虑指令的分解。

定义：两层模型，由指令到对应端口的双向图。

具体模型如下

图2 一个示例的端口映射模型

定义：experiment e，指令集合I到自然数N的映射，表示每个指令在此次实验中的执行次数

experiment ?? : I → N

优化目标

表达式的含义：

• A：e(i)指的是在实验中，指令i的执行次数；x_ik表示指令i在端口k上的执行次数。表达式A的含义为：对任意指令i而言，在所有端口上执行的次数之和，是指令i在实验e中的执行次数。
• B：在每一个端口上执行完（分配给端口的）所有的指令所用的周期数，小于t。
• C：如果i可以在端口k上执行，那么在实验中，该指令在此端口上的执行次数不小于0。
• D：如果i不可以在端口k上执行，那么在实验中，该指令在此端口上的执行总次数为0。

2.2.2 示例

对于实验?? := {add ?→ 2, mul ?→ 1, store ?→ 1} ，按照图2所示的端口映射模型。执行结果如下（Throughput为执行实验的平均周期数）。

图3 Throughput模型示例

2.2.3 假设

Throughput模型基于以下假设

1. 处理器能够最优化调度指令
2. 操作单元能够完全流水化执行，每个指令只是占用端口的一个周期
3. 取指和译码阶段没有瓶颈
4. 实验中的指令没有数据相关（写后读）

1和2取决于处理器，现在的处理器通常容易满足，除了一些复杂指令（比如除法通常会阻塞一个端口的多个周期）。对于3，只选择足够短，不会触发瓶颈的experiment。

2.3 三层模型

2.3.1 定义

三层模型考虑了指令的分解，一个指令会被分解为更简单的μop操作。具体定义如下：

三层模型示例

对应的优化方程

只需要将experiment e修改为从μop到对应执行次数的映射e'，即可以将其简化为二层模型。

3. PMEvo框架

PMEvo框架的整体概览如下图。主要包含五个阶段，产生相关experiment，在给定机器上测量throughput，预处理步骤确定等价的指令，和演化优化。

3.1 Experiment生成

PMEvo第一阶段的输入是指令集的描述，这种描述是指令形式，但是每一个操作符都是一个占位符，这种占位符确定了操作类型（比如，内存操作或向量寄存器。

如何构建experiment?

如果i_A和i_B需要同样的资源，（2）会是两个throughput之和，如果相互独立，第(3)会是n·t^*(i_B)。太过复杂的experiment很难解释，而且发现效果并不会好。演化算法的任务是找到一个端口映射解释这些测量得到的throughput。

3.2 测量throughput

根据前面的假设，测量throughput，需要保证，1、尽可能少的数据依赖。2、fetch和decode不会有瓶颈

具体做法：1.使用寄存器分配器。2.循环展开。3.保证指令长度。

使用寄存器分配器：使用尽可能多的寄存器。写操作时，尽量使用最近读取过的寄存器；读操作时，使用最近最久使用的写寄存器。怎么减少依赖的？？？

To avoid harmful dependencies, written operands are instantiated with most recently read registers and read operands with least recently written registers

experiment中的指令都避免数据依赖，得到的指令序列会在一个loop中执行，以保证能够达到一个稳定状态。

对循环迭代进行展开，好处：

1. 分配更多的寄存器，增大了依赖距离
2. 避免了循环带来的依赖
3. 减少了循环代码对时间测量的影响

发现长度为50的指令序列最好，原因如下：

1. 循环体都能在μop cache中（如果存在的话）
2. 避免了取指和译码阶段导致的性能瓶颈。

throughput的计算公式：

3.3 等价指令的筛选

进行等价指令的筛是为了降低演化算法的搜索空间。把指令分成同的等价类，一个类内的指令，在experiment中的表现一致。等价指令在执行时需要相同的计算资源。

如何判断两个指令是否是一类呢？一、throughput相同。二、与其他指令结合后的throughput相同。

考虑到实际的测量结果会存在误差，因此的相对误差要小于常数。

对于同一类的指令，执行时只需要选择其中一个即可。

3.4 端口映射演化

演化算法如下，采用的是进行μop分解的模型。

3.4.1 初始化

对于指令i产生的μop，随机设置到每个端口的映射。这些指令i的μop出现次数，设置在区间[1, ????(??) · |??|?]内。这个上限的意思是，一个有??? · |??|? 个实例的μop u的指令，不能实现小于t的throughput。

3.4.2 演化操作

演化算法中，最常用的操作时变异和重组。本文使用了重组操作，将两个双亲端口映射混合，以产生两个新的端口映射。对于每个指令i，复制产生的μop，被随机分配到两个孩子中。对每一个个体执行此操作。

设计演化算法时，考虑了变异，但验证发现，变异几乎不起作用。因此放弃了变异。

3.4.3 适应性函数

优化目标是最小化两个特性：一、平均相对误差（决定测量精度）；二、μop的总数（决定

将这两个特性结合起来

其中Λ₁ 和 Λ₂是仿射变换，以保证在每个迭代中归一化两个目标，使得范围在[0, 1000]之间。

将这两个特性结合在一起的原因：

throughput并不能唯一决定一个特定的端口映射，对特定值的throughput，端口映射的变化范围很大。而且对于处理器而言，设计时一般会考虑到相对compact的端口映射，这些能够捕捉到从外界观察到的性能特征。

3.4.5 有效的性能模拟算法

相比于直接的求解线性方程，本文选择了一种瓶颈模拟算法来计算线性方程的最优解。

其中Ports(m, i) := {k | (i, k)∈ M}，表示在端口映射m下，能够执行指令i的端口集合。这个特性基于以下观察，throughput取决于一个非空的瓶颈端口集合Q^*。在Q^*中的每一个端口，执行指令总数为t^*_m(e)。一个理想的调度器会将可以不再瓶颈端口执行上的指令，分配给其他使用较少的端口。因此对于每一个Q（应该是端口集合的一个子集）而言，上述公式对应的最大值，其实是throughput的下界。

对图三中的指令执行情况分析：

为了利用这一特性，本文枚举了端口集合的所有子集，然后评估上面公式对应的值。虽然算法的复杂度为2^|P|(|P|为端口数目)，但由于端口数目不多，实际执行起来相比线性规划反而更快一些。

4. 评估

4.1准备工作

要评估的CPU信息如下：

对于SKL，有一个长期运行的独立的流水线，标记为DIV，需要被标记为额外的端口（问题：为什么）。A72中的一个端口被专门用来进行分支预测，在本文的模型中，不考虑控制流的改变，也就是不考虑分支，因此这个端口会被忽略。需要重点关注的是A72和Zen，因为它们并没有提供每个端口的性能计数器，SKL上的结果可以用来做比较。

忽略的指令类型如下：

1. 分支和跳转
2. 有隐式读操作数的指令（ Instructions with implicitly read operands），因为这些造成的依赖不能通过重新分配寄存器来解决。
3. X86 SSE指令（SIMD指令，单指令多数据），因为这些指令在转变为AVX指令时会有性能损失（通用的为AVX)
4. 操作在subregister上的指令。

4.2 处理器模型和测量

将论文【1】中的结果作为ground truth，比较测量的throuthput结果（只针对Intel平台）。

Fig 6. Mean absolute percentage error (MAPE) of simulation with the port mapping from Abel and Reineke [1] and with IACA [17] with respect to our measurements for experiments of varying length

综上，错误足够小，能够判断测量机制和throughput模型的正确性。

4.3 模型预测

因为对于大多数处理器，缺少实际端口映射的ground truth，所以很难直接评估推断的端口映射的。论文中通过评估它们预测对于已知端口映射的experiment的throughput的准确性，来评估推断得到的端口映射。

We therefore assess the inferred port mappings by their ability to accurately predict the measured throughput of port-mapping bound experiments.

PMEvo的主要用途是给性能评估工具提供端口映射。因此我们对比了PMEvo与其他现有方法预测的准确度。因此，使用了相同的benchmark评估IACA [17] (version 3.0)，llvm-mca [7] (from LLVM version 8.0.14),，Ithemal [20]，uops.info给出的端口映射。

只有μops的方法是与PMEvo相当的，它们只能预测无数据依赖的指令序列，而其他方法更加通用些。

下面表格展示了PMevo在不同平台上的特性，可以看到，等价指令的筛选是很有用的。μop的数量展示了所推断端口映射的compact程度。

为了能够比较预测的准确性，使用下面三个参数：

1. MAPE：平均绝对误差

   The Mean Absolute Percentage Error (MAPE) is a measure of the relative error of the simulation over measurements.

   

   Ft是预测值，At是真实值

2. PCC：皮尔逊相关系数

   The Pearson Correlation Coefficient (PCC) describes how closely the relation between simulation and measurements can be described by a linear equation.

   

3. SCC：斯皮尔曼等级相关系数

   The Spearman Correlation Coefficient (SCC) is a measure of rank correlation. A high rank correlation indicates that if the measurement for one experiment is smaller than for another experiment, its simulated
   value is likely to be smaller as well.

   

   

4.3.1 SKL

使用热力图来表示测量结果，横轴表示测量的周期数，纵轴表示预测的周期数，热度表示落在该区间的experiment个数。理想的情况是数据分布在对角线附近。

不同方法在SKL上的throughput预测结果如下。

详细结果如下。

IACA和μops.info和llvm-mca预测误差均小于10%。在对角线下方有一些数据点，这是因为bit test指令，测量的throuhput和从端口中推断的结果不一致，这个结论在论文一中被证实。

PMEvo平均绝对误差略大，但是皮尔森相关系数和斯皮尔曼等级相关洗漱与其他方法接近。这是因为，对于bit test指令，它的多个μops被映射到多个端口执行，这与实际的端口映射结果不符，但是个错误刚好能让观察到的throughput更符合。

对于Ithemal方法，因为训练的时候被用到的指令序列都是包含数据依赖的，因此对于实验中的不包含数据依赖的结果预测的不好。

4.3.2 ZEN和A72

其他的方法只适用于Intel架构的CPU，对于AMD和ARM的微架构，PMEvo只能和llvm-mca比较结果。总体结果如下表所示。对于ZEN，容易看到PMEvo推断的正确率接近SKL架构的结果，但是对于A72的结果，准确率会明显的下降，而且相关系数也会更低。

在详细的结果中，可以看到运行时间越长，PMEvo就会低估throughput，这是因为A72的并不能做到很好的乱序执行【2，4，6】，所以实际运行的会比预测的throughput更高一些。但是llvm-mca相对会有更大的误差，而且预测的throughput会比实际的更高。一个可能的解释是，llvm-mca运行的不准确。

4.4 模拟算法的性能

这部分讨论一下瓶颈模拟算法和线性规划方法的性能表现，线性规划使用Gurobi求解器的C++API实现。有两个参数需要考虑：一是微架构的端口数目，二是experiment的长度。对于每个配置（端口数目、experiment长度），有128个随机设置的experiment，每个experiment被重复超过1000次，来计算平均用时。

Fig 8a. 每个experiment的用时随端口数目的变化情况

Fig 8b. 每个experiment的用时随实验长度的变化

从图8a中可以看到，小于十个端口时，瓶颈算法会比线性规划算法小两个数量级，但是从12个端口开始，瓶颈算法快速增长，直到18个端口，线性规划算法性能优于瓶颈模拟算法。对于线性规划算法，每个experiment的用时只是随着端口数目的增加缓慢增长。

在实际求解端口映射的遗传算法中，experiment的长度比较短，目的是能够保证在真实处理器上的可靠执行。图8b中，固定端口数目为10，能够看到，随着长度的增加，两种算法的用时均有所增加，但是瓶颈模拟算法，始终比线性规划算法低两个数量级。