用深度学习解决冯-诺依曼结构内存性能瓶颈

论文导读

摘要： 如何将机器学习应用于计算机硬件结构领域，目前依然鲜有研究。这篇论文展示了深度学习在解决冯·诺依曼架构计算机内存性能瓶颈问题中的应用。论文关注的是学习内存访问模式这一关键问题，意在构建一种准确高效的内存预期器。研究提出将预期策略视为NLP中的n-gram模型，并使用RNN模型完全替代基于表的传统预取。在基准测试集上的实验表明，基于神经网络的模型在预测内存访问模式上可稳定地给出更优的准确率和召回率。该论文是将神经网络应用于计算机结构设计中的一篇开创性工作。

作者： Milad Hashem等

正文：

在计算机结构的设计中，很多问题涉及使用预测和启发式规则，内存预取就是其中的一个经典问题。内存预取将指令和数据在被微处理器实际使用前，预先置于存取速度更快的内存中。因为在冯·诺伊曼结构计算机中，微处理器的运算速度要比内存访问速度高出数个数量级，因此内存预取是一个关键的瓶颈问题，也被称为“内存墙”（Memory Wall）。有统计表明，计算机中50%的计算周期是在等待数据加载到内存中。为解决内存墙的问题，微处理器使用了层次结构的内存，即在结构上采用多级缓存设计，让规模更小但是访问速度更快的缓存更接近于处理器。为降低内存读取的延迟，需要预测何时以及哪些数据应预取到缓存中。因此，提高性能的一个关键问题，是如何给出有效的内存访问模式预测。

在现代处理器中，使用了一些预测方法。很多预测器是基于记录表实现的。记录表是一种内存数组结构，记录了未来事件与以往历史信息的关联性。但是相比起传统的单机工作负载，现代数据中心的工作负载规模呈现指数级的增长，这对内存访问模式预测提出了严峻挑战。预测的准确性会随预测表规模的增大而显著下降。简单地扩展预测表的规模，需在硬件实现上付出很大的代价。

神经网络技术已在NLP和文本理解取得了很好的效果，它为解决序列预测问题提供了一种强大的技术。例如，在SPARC T4处理器中，已经部署了一种简单的感知机，实现对分支处理指令的预测。但是，对于微处理器架构设计而言，如何有效地引入序列学习算法依然是一个开放的问题。

本文的研究考虑在微处理架构中引入基于序列的神经网络模型，意在解决内存墙所提出挑战，将序列学习应用到内存预取这一难题上。内存预取问题，在本质上可以看成是一种回归问题。但是该问题的输出空间很大，并且非常稀疏，使用标准的回归模型难以给出好的效果。本文作者们考虑使用一些图像和语言生成上的最新研究成果，例如PixelRNN和Wavenet。这些研究成果对搜索空间做离散化，使得内存预取模型更近似于神经语言模型，并依此作为构建神经网络内存预取器的出发点。本文研究所提出的神经网络模型，可以成功地建模问题的输出空间，实现一种神经网络内存预取，并给出了显著优于现有传统硬件预取器的性能。此外，论文中使用的RNN可以根据应用的内存访问轨迹辨别应用的底层语义信息，给出的结果更具可解释性。

背景知识

内存预取器（Prefetcher）

内存预取器是一种计算机硬件结构，它使用历史内存访问记录预测将来的内存访问模式。现有的内存预取器大体上可分为两类。一类称为“步长预取器”（stride prefetcher），另一类称为“关联预取器”（correlation prefetcher）。现代处理器中通常使用的是步长预取器，序列中固定采用稳定的、可重复的地址差值（即序列中相邻两个内存地址间的差值）。例如，给定一个内存访问模式（0，4，8，12），每次访问的地址差值为4，那么预取器可以由此预测此后的地址访问模式为（16，20，24）。

关联预取器可预测地址差值不固定的重复模式。它使用了一个大的记录表，保持过往的内存访问历史信息。相比于步长预取器，关联预取器可以更好地预测非规则变化的模式。典型的管理预取器包括Markov预取器、GHB预取器，以及一些使用大规模内存中结构的最新研究预取器。关联预取器需要具备一张大规模的记录表，该表的实现代价大，因此通常并未实现在多核处理器中。

递归神经网络（RNN）

深度学习适用于很多的序列预测问题，例如语言识别和自然语言处理。其中，RNN可对长距离依赖建模。LSTM作为一种广为使用的RNN变体，通过以加法方式而非乘法方式传播内部状态，解决了标准RNN的训练问题。LSTM由隐含状态$h$、元胞状态$c$、输入门$i$、输出门$o$和记忆门$f$组成，分别表示了需要存储的信息，以及在下一个时间步（timestep）中传播的信息。给定时间步$N$和输入$x_N$，LSTN的状态可以使用如下过程计算：

1 计算输入门、输出门和记忆门

$i_N=\sigma(W_i[x_n,h_{N-1}+b_i])$
$f_N=\sigma(W_f[x_N,h_{N-1}]+b_f)$
$o_N=sigma(W_o[x_N,h_{N-1}]+b_f)$

2 更新胞元状态

$c_N=f_N \odot c_{N-1}+i_N\odot tanh(W_c[x_N,h_{N-1}]+b_c)$

3 计算LSTM隐含状态（输出）

$h_N=o_N \odot tanh(c_N)$

其中，$[x_n,h_{N-1}]$表示当前的输入和前一个隐含状态的级联（concatenation），$\odot$表示点乘操作（element-wise multiplication），$\sigma(u)=\frac{1}{1+exp(-u)}$是Sigmoid非线性函数。上面给出的过程表示了单个LSTM层的处理形式，$W_{\{i,f,o,c\}}$是该层的权重，$b_{\{i,f,o,c\}}$是偏差。LSTM层可以进行堆叠，在时间步N的LSTM层的输出，可以作为另一个LSTM层的输入，这类似于前向回馈神经网络中的多层结构。这使得模型在使用相对较少额外参数的情况下，增大了灵活性。

问题定义

将预取作为预测问题

预取可以看成是对未来内存访问模式的预测过程。如果数据并不在缓存中（即缓存未命中），预期器需要根据历史访问情况，到主存中去获取数据。每条内存地址由内存操作指令（load/store）生成。内存操作指令是计算机指令集中的一个子集，实现对计算机系统中具有地址内存的操作。

很多硬件厂商建议在做出预期决策时使用两个特征。一个是截至目前缓存未命中的地址序列，另一个是指令地址序列，也称为程序计数器（Program counter，PC），即关联到生成每条缓存未命中地址的指令。

每条PC可以唯一标识一条指令，指令是对给定代码文件中的特定函数编译生成的。PC序列可告知模型应用代码的控制流模式，而缓存未命中地址序列可告知模型需要下一步预期的地址情况。在现代计算机系统中，上述特性均使用64位整数表示。

初始模型可以在每个时间步$N$使用两个输入特征，即在$N$步生成的缓存未命中地址，以及由PC预测的N+1步缓存未命中情况。但是其中存在一个问题，应用的地址空间是非常稀疏的。对于此问题的训练数据而言，缓存未命中的空间复杂度为$O(100M)$量级，其中只有$O(10M)$的缓存未命中地址出现在$2^{64}$的物理地址空间中。图1显示了使用标准SPEC CPU2006基准测试集omnetpp时的缓存情况，红色点表示了缓存未命中地址。这一空间范围宽泛，具有重度多模态本质，这对传统的时序回归模型提出了挑战。例如，虽然神经网络非常适用于正则化输入，但是对这样的数据做正则化时，有限精度的浮点数表示将导致显著的信息丢失。该问题影响了对输入层和输出层的建模。在本文中，作者对此给出了解决方法。

图1 数据集omnetpp上的缓存未命中情况。图中多尺度地展示了稀疏访问模式。

将预取作为分类问题

在本文作者提出的解决方法中，考虑将整个地址空间视为一个离散的大规模词汇表，并对词汇表执行分类操作。这类似于NLP中对随后出现的字符或单词的预测问题。但是，该空间是极度稀疏的，并且其中部分地址比其它地址更频繁地访问。对于RNN模型，是可以管理这样规模的有效词汇表的。此外，相比于单模态回归技术，通过生成多模态输出，模型处理可以变得更加灵活。在图像处理和语音生成领域中，已有一些研究成功地将输出输出作为预测问题而非回归问题。

但是，预期问题存在着$2^{64}$种可能的softmax目标，因此需要给出一种量化（quantization）模式。更重要的是，预取必须完全准确才能发挥作用。对于通常的64个字节情况应该如此，对于通常是4096个字节的页面也应如此。在页面层级上的预测，将会给出$2^{52}$中可能的目标。为避免对超过$2^{16}$个值应用softmax，一些研究提出应用非线性量化模式将空间降维到256类。但是这些解决方法这并不适用于本文中的问题。因为这些方法降低了地址的分辨率，使得预取无法获得所需的高精度。

由于动态边界效应，例如地址空间布局随机化（ASLR）问题，同一程序的多轮运行可能会访问不同的原始地址。但是，同一程序对于一个给定的布局将给出一致的行为。由此，一种可行的策略是预测地址差值$\Delta_N=Addr_{N+1}-Addr_{N}$，而非直接预测地址本身。如表1所示，地址差值$\Delta_N$的可能出现情况，要比地址的可能出现情况呈空间指数级别降低。

表1 程序追踪数据集统计情况，“M”表示“百万”

模型描述

论文给出了两种基于LSTM的预取模型。第一种模型称为“嵌入LSTM”模型，它类似于标准的语言模型。第二种模型利用内存访问空间的结构去降低词汇表的规模，降低了模型占用的内存量。

嵌入LSTM模型

该模型限制输出词汇表的规模，仅建模最频繁出现的地址间隔。根据表1，要获得最优50%的准确性，所需的词汇表规模仅为$O(1000)$量级乃至更小。这样规模的词汇表完全处于标准语言模型可解决的能力范围内。基于此，论文提出的第一种模型对输出词汇表规模做了限制，选用了其中50000个最频繁出现的唯一地址差值。对于输入词汇表，模型考虑在词汇表中出现了至少10次的所有地址差值。要进一步扩展词汇表，无论在统计学还是计数上都是有挑战的。这些挑战可以采用层次softmax类方法解决，有待进一步研究。

嵌入LSTM的结构如图2所示。模型将输入和输出地址差值以分类表示（即独热编码）。在时间步$N$，分别嵌入输入$PC_{N}$和$\Delta_{N}$，并将嵌入词汇级联起来，构成两层LSTM的输入。进而，LSTM对地址差值词汇做分类，并且选取$K$个最高概率地址差值，用于预取。分类方法可直接给出预测概率，这对传统硬件是另一个优点。

图2 嵌入LSTM模型结构。其中$f$和$g$分别表示嵌入函数

实际实现中，预取器会返回多个预测值，因此需要从中做出权衡。虽然更多的预测值增加了缓存命中下一个时间步的可能性，但是有可能会从缓存中移除其它一些有用的项。论文选取在每个时间步预取LSTM的头部10个预测值。这里还有其它一些可能的做法，例如使用使用beam-search预测之后$n$个时间步，或是通过直接学习先于LSTM的一次前向操作给出对$N$到$N+n$时间步的预测。

嵌入LSTM模型存在一些局限性。首先，大型的词汇表增加了模型的计算复杂度和存储量。其次，截取部分词汇表无疑为模型准确性设置了一个上限。最后，不易处理一下罕见发生的地址差值，因为这些差值很少在训练集中出现。该问题在NLP领域称为“罕见词汇问题”。

聚类与LSTM的组合模型

假定大多数地址间感兴趣操作发生在本地地址空间中。例如，结构体和数组的数据结构通常使用持续的数据块存储，并会被指令重复访问。论文在模型设计中引入了上述理念，对本地上下文做细致建模。与之不同的是，在嵌入LSTM模型中不仅考虑了本地上下文，而且引入了全局上下文。

通过查看更窄区域的地址空间，可以发现其中的确存在着丰富的本地上下文。为此，论文从omnetpp中取出了部分地址集，并使用K-Means聚类为6个不同的区域。图3中展示了其中的两个聚类。

图3 展示了基准测试数据集omnetpp的六个K-Means聚类中的两个聚类。内存访问按照生成访问的PC分别标记颜色。

为达到对本地地址空间区域建模的相对准确性，论文对原始地址空间进行K-Means聚类，将数据分区为多个聚类，并对计算每个聚类内的地址差值。图4a是对上例的可视化。该方法具有一个显著的优点，就是聚类内的地址差值集要显著地小于全局词汇表中的差值，这缓解了嵌入LSTM模型中存在的一些问题。

为进一步降低模型的规模，论文使用了多任务LSTM对所有距离建模，即对每个聚类独立使用一个LSTM建模。聚类ID也添加为模型的特性，这为每个LSTM提供了一组不同的偏差。

将地址空间分区为更小的区域，意味着每个聚类内地址组使用的幅度量级大体上相同。因此，所生成的地址差值可以有效地正则化为适用于LSTM的真实输入值，不再需要维护一个大型的嵌入矩阵，进而进一步降低了模型的规模。更重要的是，下一个地址差值预测的问题可作为一个分类问题，而回归模型在现实中通常不够精确。

该模型解决了一些嵌入LSTM中存在的问题。预处理步骤（即对地址空间的聚类）是模型中需要权衡考虑的一个因素。此外，该模型只对本地上下文建模，也可以对程序访问的不同地址空间区域进行动态建模。

图4 组合聚类和LSTM模型的结构，以及数据处理

实验

一个有效的内存预取器，应该具备对缓存未命中情况的准确预测能力。因此，论文的实验主要针对如何测定预取器的有效性。

实验数据的收集

实验中所使用的数据主要是程序的动态追踪数据，其中包含程序计算的一个内存地址序列。追踪数据使用动态工具Pin捕获。该工具附着在进程上，并以文件形式给出被测量应用访问内存的“PC，虚地址”元组。原始访问追踪数据主要包含了堆栈访问等命中内存的方法。对于研究中关注的预测缓存未命中情况，实验中使用了一个模拟Intel Broadwell微处理器的模拟器，获取缓存未命中情况。

实验程序使用的是对内存做密集访问的SPEC CPU2006应用。该基准测试集用于算机系统的性能做完全评估。但是，与现代数据中心工作负载相比，SPEC CPU2006依然是一个小规模的工作集。因此在论文的实验中，还添加了Google的Web搜索工作负载。

实验中将内存访问数据集分为训练集和测试集，其中70%用于训练，30%用于测试。在每个数据集上独立训练每个LSTM。嵌入LSTM使用ADAM训练，聚类LSTM使用Adagrad训练。使用的超参数参见原文附录。

实验测试的度量包括准确率和召回率。在实验中，对每个模型做出10次预测。如果在头部10次预测中给出了完全正确的地址差值，就认为生成了一次准确预测。

模型对比情况

实验将基于LSTM的预取器与两种硬件预取器进行了对比。第一种是标准流预取器。为保持机器学习预取器与传统预取器的一致性，实验中模拟了支持多至10个并发流的硬件结构。第二种是GHB PC/DC预期器。这是一种关联预取器，它使用了两个表。一个表用于存储PC，并将所存储的PC作为执行第二个表的指针。第二个表存储了地址差值的历史信息。在每次访问时，GHB预取器跳转到第二个表，预取历史记录的地址差值。关联预取器对于复杂内存访问模式表现很好，具有比流预取器更低的召回率。

图5给出了不同预取器在各种基准测试数据集上的对比情况。尽管流预取器由于其动态词汇表特性可以获得最高的召回率，但是LSTM模型整体表现更好，尤其是准确率。

图5 传统预取器和LSTM预取器的准确率和召回率对比图。其中，“Geomean”表示几何平均值

通过对比嵌入LSTM模型和聚类与LSTM的组合模型，可以看到两种模型间的准确率不相上下。后者趋向于给出更好的召回率。当然，组合更多的模型将会给出更好的结果，这有待未来的工作去探索。

$\Delta s$对比PC的预测情况

该实验从嵌入LSTM模型的输入中分别移除$\Delta s$或PC。实验设计意在确定在不同输入模组中所包含的相对信息内容。

实验结果如图6所示。从图中可以看出，PC和地址差值中包含有大量预测信息。地址差值序列中的预测信息可以提高准确率，而PC序列有助于提高召回率。

图6 不同输入模组的嵌入LSTM模型，准确率和召回率的对比图

解释程序的语义

相比于基于查找表的预期器，模式学习模型的一个主要优点是可以通过审视模型获取数据的内涵。图7展示了$(\Delta,PC)$级联串在mcf上嵌入情况的t-SNE可视化。

图7 $(\Delta,PC)$级联串在mcf上嵌入情况的t-SNE可视化，图中按指令展示为不同的颜色

图中的一个聚类是由一组具有统一代码的重复指令组成，这是由于编译器对循环体展开所导致。还有一个聚类仅由指针解除引用（pointer dereference）组成，这是由于程序遍历链接列表所导致的。在omnetpp中，对数据结构的插入和移除操作映射为同一个聚类，而数据比较操作则映射在不同聚类中。例子所使用的代码参见原文附录。

结论及进一步工作

对应用程序行为的学习和预测，可在解决计算机架构中的控制和数据并发问题中发挥重要作用。传统方法是使用基于表的预测器，但是当扩展到数据密集不规则工作负载时，实现此类方法的代价过大。

本文介绍了两者基于神经网络的预取模型，它们给出了比基于表的传统方法显著高的准确率和召回率。在实验中，论文对模型做离线训练并在线测试，使用准确率和召回率评估了模型。实验表明，论文提出的预取器模型可以改进缓存未命中的分布。当然，还有其它一些在不增加预取器的计算和内存负担条件下改进预期器的方法。在进一步的研究中，可以考虑基于内存命中和未命中数据训练模型，但是这将显著改变数据集的分布和规模。

时效性也是研究预期其中一个考虑的重要因素。对于RNN预取器而言，预期过早会导致处理器未使用缓存数据，预取过迟会则对性能影响甚微，因为延迟访问内存的代价已经付出。一个简单的启发式规则是采用类似于流预期器的行为，预先对多个时间步做出预测，而非仅是下一个时间步。

最后一点，对应用性能的影响可以评估RNN预取器的有效性。在理想情况下，RNN将会直接优化应用性能。一个考虑是，使用强化学习技术作为动态环境中RNN的训练方法。

当然，内存预取并非计算机系统中唯一需要给出预测执行的领域。只要涉及分支行为，就需要做出预测。分支算法用于重定向控制流的地址，高速缓存替换算法在需要做出替换决定时预测从高速缓存的最佳替换处。如果采用机器学习系统代替传统微体系结构中的启发式规则，可以通过对此类系统审视，更好地理解系统的行为。论文中的t-SNE实验仅给出了一些表面上的观察，展示了内存访问模式是程序行为的一种表示。这表明，利用最新研究的RNN系统，为计算机系统结构研究提供了大量的机会。

查看论文原文： Learning Memory Access Patterns