英语原文共 15 页
摘要
工作量复杂性的爆炸式增长和最近摩尔定律的缓慢发展要求采用新的方法来实现高效的计算。---摩尔定律（当价格不变时，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。换言之，每一美元所能买到的电脑性能，将每隔18-24个月翻一倍以上。）研究人员现在开始将机器学习的最新进展用于软件优化，增强或取代传统的启发式方法和数据结构。然而，对计算机硬件体系结构的机器学习空间的探索还很少。在这篇文章中，我们展示了深度学习解决冯·诺依曼记忆性能瓶颈的潜力。我们关注的是学习记忆访问模式的关键问题，目的是构建准确高效的记忆预取器。我们将当代的预取策略与自然语言处理中的n-gram模型联系起来，并展示了递归神经网络如何作为一种临时的替代方法。在一组具有挑战性的基准数据集上，我们发现神经网络在查准率和召回率方面表现出了卓越的性能。这项工作代表了基于神经网络的实用预取的第一步，为计算机体系结构研究中的机器学习开辟了一系列令人兴奋的方向。
1.介绍
在现实世界的应用中，机器学习和最近的深度学习的激增是由于计算能力的指数增长，这主要是由硬件设计的进步所驱动的。为了最大限度地提高给定设计的有效性，计算机体系结构通常涉及到预取和启发式的使用。预取就是一个典型的例子，在这个例子中，指令或数据在其所需的使用之前就被带到了更快存储中。
预取解决了冯·诺依曼计算机中的一个关键瓶颈：计算比访问内存快数量级。这个问题被称为内存墙(Wulf amp; McKee, 1995) ，现代应用程序可能会花费超过50%的计算周期等待从内存到达的数据(Kozyrakis 等.2010;Ferdman等., 2012; Kanev 等., 2015)。为了减少存储器壁，微处理器使用分层存储系统，靠近处理器的内存较小且速度较快，而距离较远的较大但速度较慢的内存较大。预取程序预测何时将哪些数据提取到cache中以减少内存延迟，而有效预取的关键是解决预测内存访问模式这个难题。
预测优化(如预取)是一种猜测。现代微处理器利用多种类型的预测结构发出投机性请求，以提高性能。从历史上看，硬件中的大多数预测因素都是基于表的。也就是说，未来的事件预计将与查找表中记录(以内存数组的形式实现)。这些内存数组的大小基于工作集或应用程序积极使用的信息量。但是，现代数据中心工作负载的工作集要比传统工作负载(如SPEC CPU2006)的工作集大很多，并且还在继续增长。这一趋势带来了巨大的挑战，因为当工作集大于预测表时，预测精度急剧下降。使用快速增长的工作集扩展预测表对于硬件实现来说既困难又昂贵。
神经网络已经成为解决序列预测问题的一种强有力的技术，例如在自然语言处理(NLP)和文本理解中发现的问题。甚至在硬件处理器中部署了简单的感知器来处理分支预测。然而，探索序列学习算法在微结构设计中的有效性仍然是一个开放的研究领域。
本文探讨了基于序列的神经网络在微体系结构系统中的应用。特别地，考虑到记忆墙的挑战，我们将序列学习应用于预取这一难题。
预取基本上是一个回归问题。然而，输出空间很大，而且非常稀疏，这使得它不适合于标准的回归模型。我们从最近关于图像和音频生成的离散空间的工作中得到了启发，即PixelRNN和WaveNET。离散化使预取更类似于神经语言模型，我们利用它作为构建神经预取程序的起点。我们发现，我们可以成功地将输出空间建模到一定的精度，这使得神经预取成为一种非常明显的可能性。在许多基准数据集上，我们发现递归神经网络的性能明显优于传统的硬件预取器。我们还发现我们的结果是可以解释的。在给定内存访问跟踪的情况下，我们证明了RNN能够识别底层应用程序的语义信息。
2.背景
2.1微结构数据预取器
预取器是根据过去的历史预测未来内存访问的硬件结构。它们在很大程度上可以分为两类：步进预取器和相关预取器。步进预取器通常在现代处理器中实现，并锁定到稳定的、可重复的增量(后续内存地址之间的差异)。例如，给定每次向内存添加四个地址的访问模式(0、4、8、12)，步进预取器将学习该增量并尝试在需求流之前进行预取，启动对未来潜在地址目标(16、20、24)的并行访问，直至设定的预取距离。
相关性预取器试图学习可能重复的模式，但不像单个稳定的增量那样一致。它们将过去的内存访问历史存储在大表中，并且比步幅预取器更能预测更多的不规则模式。相关预取器的例子包括Markov预取器、GHB预取器，以及更新的使用较大内存结构的工作。关联预取器需要大型的、昂贵的表，并且通常不能在现代多核处理器中实现
2.2 递归神经网络
深度学习已成为许多序列预测问题的首选模型类。特别是语音识别和自然语言处理。特别是，RNN因其建模长期依赖项的能力而成为首选选择。LSTM已经成为一种流行的RNN变体，它通过额外地传播内部状态而不是乘数传播内部状态，来处理标准RNN中的训练问题。LSTM由隐藏状态h和单元状态c以及输入i、忘记f和输出门o组成，这些门指示存储和传播到下一时间步的信息。在时间步骤N，输入X显示给LSTM，并使用以下过程计算LSTM状态：
- 计算输入门，遗忘门和输出门
- 更新细胞状态
- 计算LSTM的隐含（输出）状态
[]表示将输入和隐含层的前一个状态相连，代表着元素之间的乘法，是sigmoid非线形函数
上述过程形成单个LSTM层，其中为层的权重，为偏置。LSTM层可以进一步堆叠，使得一个LSTM层在时间N时的输出成为另一个LSTM层在时间N的输入。这类似于在前馈神经网络中有多个层，并且允许在相对较少的额外参数的情况下更大的建模灵活性。
3．问题表述
3.1预取作为预测问题
预取是预测未来内存访问但是不在cache中且建立在过去的历史访问的过程，这些存储器地址中的每一个都由存储器指令(加载/存储)生成。内存指令是计算机系统的可寻址内存交互的所有指令的子集。
许多硬件方案使用两个特性来做出这些预取决策：到目前为止已观察到的缓存未命中地址序列和与生成缓存未命中地址的指令相关联的指令地址序列，也称为程序计数器(PC)。
PC是唯一的标记，也就是说，每台PC都是特定指令所独有的，该指令是从特定代码文件中的特定函数编译而来的。PC序列可以通知高级代码控制流中的模式模型，而未命中地址序列可以通知模型下一个要预取的地址。在现代计算机系统中，这两个特性都表示为64位整数。
因此，初始模型可以在给定的时间步N使用两个输入特征，它可以使用在该时间步生成缓存未命中的地址和PC来预测在时间步骤N 1处的未命中地址。
然而，一个问题很快变得明显：应用程序的地址空间非常稀疏。 在我们具有O（100M）高速缓存未命中的训练数据中，在整个264物理地址空间中平均仅出现O（10M）唯一高速缓存块未命中地址。 当我们绘制图1中omnetpp（来自标准SPEC CPU2006基准套件的基准测试）的示例跟踪时，会进一步显示这一点，其中红色数据点是高速缓存未命中地址1。 这个空间的广泛和严重的多模态性质使其成为时间序列回归模型的挑战。 例如，神经网络在归一化输入时效果最好，但是在对这些数据进行归一化时，有限精度浮点表示会导致信息的显着丢失。 这个问题会影响输入和输出级别的建模，我们将描述处理这两个方面的几种方法。
图1 在omnet 数据集上缓存未命中地址，演示多种规模的稀疏访问模式
3.2 预测作为分类
我们选择将地址空间视为一个大的，离散的词汇表，并执行分类，而不是将预取问题视为回归。 这类似于自然语言处理中的下一个单词或字符预测。 空间的极端稀疏性以及某些地址比其他地址更常被访问的事实意味着RNN模型实际上可以管理有效的词汇量大小。 另外，与假设例如高斯似然的单峰回归技术相比，该模型通过能够产生多模态输出而获得灵活性。 将输出预测问题视为分类而不是回归之一的这种想法已经成功地用于图像（Oord等，2016a）和音频生成（Oord等，2016b）。
然而，有264个可能的Softmax类，因此需要一种量化方案。重要的是，要使预取有用，预取必须在高速缓存行中才能完全准确，通常在64个字节内。如果它在一个页面内(通常是4096个字节)，还有第二个好处，但是即使在页面级别上进行预测，也会留下252个可能的目标。在(Oord等人，2016b)中，他们从声音信号中预测16位整数值。为避免必须应用超过216个值的Softmax，他们应用非线性量化方案将空间减少到256个类别。这种形式的量化不适合我们的目的，因为它降低了地址空间的极端分辨率，而在预取时，我们需要在每个使用地址的区域都有较高的分辨率。
幸运的是，程序倾向于以可预测的方式运行，因此只能看到相对较小（但绝对数量仍然很大）和一致地址集。 因此，我们的主要量化方案是在训练期间创建公共地址的词汇表，并在测试期间将其用作目标集。 这会降低覆盖范围，因为在测试时可能会有一些在训练时间内看不到的地址，但是我们将证明，对于合理大小的词汇表，我们捕获了相当大比例的空间。 我们探索的第二种方法是使用地址空间上的聚类来聚类地址。 这类似于非线性量化的自适应形式
由于地址空间布局随机化（ASLR）等动态副作用，同一程序的不同运行将导致不同的原始地址访问（Team，2003）。 但是，给定布局，程序将以一致的方式运行。因此，一种可能的策略是预测增量，，而不是直接地址。 这些将在程序执行期间保持一致，并且带来的好处是，唯一出现的增量的数量通常比唯一出现的地址小几个数量级。 如表1所示，其中显示了一组程序跟踪数据集中的唯一PC，地址和增量的数量。 我们还显示了达到50％覆盖率所需的唯一地址和增量的数量。 在几乎所有情况下，考虑到增量时，这个要小得多。 因此，在我们的模型中，我们使用增量作为输入而不是原始地址。
4.模型
在本节中，我们将介绍两种基于LSTM的预取模型。第一个版本类似于标准语言模型，而第二个版本利用了内存访问空间的结构，以减少词汇表大小和减少模型的内存占用。
4.1长短期记忆网络
假设我们限制输出词汇量大小，以便只模拟最常出现的增量。 根据表1，为了获得最多50％的准确度所需的词汇量通常为O（1000）或更小，完全在标准语言模型的能力范围内。 因此，我们的第一个模型将输出词汇量大小限制为一个大的，但可行的50,000个最常见，唯一的增量。 对于输入词汇表，我们包括所有增量，只要它们在数据集中出现至少10次。 从计算上和统计上来说，扩展词汇量超出这个范围是具有挑战性的。 我们将对等级softmax（Mnih＆Hinton，2009）等方法的探索留给未来的工作。
我们将此模型称为嵌入LSTM，如图2所示。它对输入和输出增量都使用范畴(一热)表示。在时间步骤N，分别嵌入输入PCN和N，然后将嵌入串联并作为两层LSTM的输入馈送。然后，lstm在增量词汇表上执行分类，并选择K个最高概率的增量进行预取。
在实际实现中，预取器可以返回多个预测。 这会产生权衡，其中更多预测会增加在下一个时间步骤中缓存命中的可能性，但可能会从缓存中删除其他有用的项目。 我们选择在每个时间步长预取LSTM的前10个预测。 我们在此未探讨的其他可能性包括使用波束搜索来预测下一个n增量，或者学习在LSTM的一个前向传递中直接预测N到N n步
这种方法有几个局限性。 首先，大量词汇表增加了模型的计算和存储空间。 其次，截断词汇量必然会对模型的准确性设置上限。 最后，处理极少发生的增量是非常重要的，因为在训练期间它们将被看到相对较少的次数。 这在NLP中被称为罕见的单词问题（Luong等，2015）。
图2 嵌入式LSTM模型，f和g代表嵌入函数
4．2簇➕lstm
我们假设，地址之间的许多有趣的交互发生在地址空间中。例如，像结构和数组这样的数据结构往往存储在连续的块中，并且重复访问。在这个模型中，我们利用这一思想设计了一个预取器，该预取器非常仔细地建模了局部上下文，而嵌入的LSTM则同时建模了局部上下文和全局上下文。
通过查看地址空间的较窄区域，我们可以看到确实存在丰富的本地上下文。我们从omnetpp中获取了这组地址，并使用k-means将它们聚为6个不同的区域。我们展示了图3中的两个集群，其余的可以在附录中找到。
为了评估局部地址空间区域建模的相对精度，我们首先使用k-means对原始地址空间进行聚类。然后将数据划分到这些集群中，并在每个集群中计算增量。这方面的一个直观示例如图4a所示。我们发现，这种方法的主要优点之一是，集群中的增量集合明显小于全局词汇表，从而缓解了嵌入LSTM的一些问题。
图3 omnetpp基准数据集中的六个k-means集群中的两个。 内存访问根据生成它们的PC进行着色。
为了减小模型的大小，我们使用多任务LSTM对所有的集群进行建模。换句话说，我们使用LSTM独立地对每个集群进行建模，但是绑定LSTM的权重。但是，我们提供集群ID作为附加功能，这实际上为每个LSTM提供了一组不同的偏差。
将地址空间划分为更窄的区域还意味着每个簇内的地址集将具有大致相同的数量级，这意味着所得的增量可以被有效地归一化并且用作LSTM的实值输入。 这允许我们进一步减小模型的大小，因为我们不需要保持大的嵌入矩阵。 重要的是，我们仍然将下一个增量预测视为一个分类问题，因为我们发现回归仍然太不准确而不实用
此版本的LSTM解决了嵌入LSTM的一些问题。
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
