这篇文章如题所示,使用深度学习模型来学习程序的内存存取模式,从而准确有效的进行memory prefetching。
背景
先来看一下为什么需要memory prefetching。现代计算机冯诺依曼架构中存在的memory wall这个问题,即计算比访问内存快几个数量级,因此内存访问就会成为程序的瓶颈。为了解决这个问题,现代计算机多采用一种金字塔型的存储结构,即越上层存取速度越快,但也越小,越下层越大但也越慢。这时候把频繁访问的数据放在越上层有利于提高程序性能。但有可能数据访问上层的cache时,数据并不在cache中,这时会产生cache miss,此时就需要访问下一层的内存,而memory prefetching就是提前把程序需要的数据提前预取到cache中,从而避免程序访问时产生cache miss造成的性能损耗。
过去,硬件中大多数预测器都是基于表实现。也就是未来的事件应该与在表(实现为内存数组)中跟踪的程序内存访问历史相关联。可分为两类 stride prefetchers 和correlation prefetchers 。stride prefetcher在现代多核处理器中比较普遍,一般用来预测访问连续数组时,步长访问具有规律性,根据步长的规律性进行预取,如前面按照步长 (0, 4, 8, 12)访问,那么可以预测后面可能要访问(16, 20, 24) 。correlation prefetchers将内存访问的过去历史存储在表中,如Markov prefetchers (Joseph & Grunwald, 1997), GHB prefetchers (Nesbit & Smith, 2004), 可以比跨步预取器更擅长预测更多的不规则模式。因为存储历史数据需要较大的表存储开销,因此未在现代多核处理器中实现。
prefetching可以看作一个根据历史内存访问信息来预测未来内存访问的问题,因此论文中使用LSTM建立模型,有两个输入特征:
- 目前观察到的cache miss的地址
- 指令地址序列,也就是PCs( program counters)。
PC可以唯一代表一个指令的,因此PC序列反映了程序控制流的模式,产生miss的地址序列则代表了下一个要预取的地址。
这里还存在一个问题,程序的地址空间达到了,非常稀疏,当成回归问题来不太适合。为了解决将地址空间视为一个大的、离散的词汇表,并执行分类。另一方面,相同程序不同运行地址会变,因此使用第N次和N+1次访问地址的变化量delta来预测更好。
模型
模型很简单,
第一个模型,Embedding LSTM:
模型限制词表为50000个访问最频繁的不同的地址变化量, 在第N步, 输入为和地址变化量∆N ,二者的的词嵌入合并在一起作为LSTM的输入,模型的输出为10个最有可能的∆N 。
这个模型的限制在于较大的词表增加了模型训练的难度,并且词表的大小的限制也限制了模型的精度。
第二个模型,Clustering + LSTM:
首先使用kmeans划分区域,然后在每个区域内计算地址变化量,每个区域内的地址变化量的值数量级差不多,有利于更好的规范化。图中,每个区域的PC和∆N分别喂给一个LSTM,并且这多个LSTM共享参数。
衡量指标:
Precision:如果真正的delta在前10个预测所给出的delta集合内,则模型预测被认为是正确的。
Recall:测试时所有预测值对测试时看到的所有实际值的比值。
在只使用PC作为特征和只使用delta作为特征和使用两者作为特征的对比实验中,发现delta有利于Precision,而PC序列有助于提高召回。
此外,本文使用的是一个a train-offline test-online 模型,在使用过程中可能预取器的使用会改变改变了cache miss的分布,从而降低在之前没有使用预取器的数据上训练的模型的有效性,虽然可以考虑online training缓解这个问题,但online的计算和内存使用成本较大。
启示
本质上memory trace也是一种 程序的行为,所以我们可以使用神经网络建模程序行为,使用数据的分布来学习特定的模型,而不是部署通用的数据结构或者使用启发式算法。神经网络压缩了学习到的分布的表示,将问题转换为一个计算问题,考虑到最近ML加速器的发展,将其用硬件实现很有希望。
可以使用NN代替启发式算法的一些地方:
- 预取
- 分支预测
- cache替换算法
网友评论