美文网首页
论文阅读:Learning Memory Access Patt

论文阅读:Learning Memory Access Patt

作者: cccshuang | 来源:发表于2020-06-10 20:25 被阅读0次

    这篇文章如题所示,使用深度学习模型来学习程序的内存存取模式,从而准确有效的进行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建立模型,有两个输入特征:

    1. 目前观察到的cache miss的地址
    2. 指令地址序列,也就是PCs( program counters)。
      PC可以唯一代表一个指令的,因此PC序列反映了程序控制流的模式,产生miss的地址序列则代表了下一个要预取的地址。

    这里还存在一个问题,程序的地址空间达到了2^{64},非常稀疏,当成回归问题来不太适合。为了解决将地址空间视为一个大的、离散的词汇表,并执行分类。另一方面,相同程序不同运行地址会变,因此使用第N次和N+1次访问地址的变化量delta来预测更好。

    模型

    模型很简单,
    第一个模型,Embedding LSTM

    image.png
    模型限制词表为50000个访问最频繁的不同的地址变化量, 在第N步, 输入为和地址变化量∆N ,二者的的词嵌入合并在一起作为LSTM的输入,模型的输出为10个最有可能的∆N 。
    这个模型的限制在于较大的词表增加了模型训练的难度,并且词表的大小的限制也限制了模型的精度。

    第二个模型,Clustering + LSTM

    image.png

    首先使用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替换算法

    相关文章

      网友评论

          本文标题:论文阅读:Learning Memory Access Patt

          本文链接:https://www.haomeiwen.com/subject/kdmptktx.html