bingo

Bingo Spatial Data Prefetcher

概要

在本文中,我们做出以下贡献:•我们表明,依靠单个事件发出预取请求是最先进的空间数据预取的主要效率来源。

•我们提出了一个tage-like预测器,以准确和最大提取空间相关的数据访问模式。

•我们建议将多个历史表合并到单个统一元数据表中的方案,从而大大降低了存储要求。

•将所有内容放在一起,我们提出了一个名为Bingo的空间数据预取器,并对各种大数据应用程序进行了精心评估。我们表明,我们的提案平均将系统性能提高了60%,而没有预取器的基线高达285%。同时,它的表现胜过最好的先前的空间数据预取器平均11%,高达67%

背景

Spatial data prefetching:

  • 仅需要存储offset或者delta,不需要存储完整地址
  • 访问顺序不重要,不需要记录访问顺序
  • 消除强制cache miss,(cache的3C)

之前的空间预取器分为两类:

  1. PPH:记录每个页面的访问历史方法
  2. SHH:记录全局访问方法(SPP)

微结构设计

bingo在访问新页面时去将模式移动到历史表,他使用PC+addr和pc+offset模式,PC+addr预测的为长历史事件(相同的指令和相同的地址应该同时发生),

1739535735601

但是实际两个表是多于的

1739536173909

也就是短事件和长事件有很多预测一致的表项

对于Bingo的情况,在“PC+Address”中携带“PC+Offset”的信息;因此,通过知道‘PC+地址’,我们也知道‘PC+偏移’是什么。为了利用这种现象,我们建议只具有一个历史表,该历史表仅存储长事件的历史,但是用长事件和短事件来查找。对于宾果的情况,历史表存储在每个“PC+地址”事件之后观察到的足迹,但是利用触发器访问的“PC+地址”和“PC+偏移”两者来查找足迹,以便提供高准确性,同时不丢失预取机会。

为了达到这样,我们使用短事件去hash,但长事件作为tag保存,并且替换算法为LRU

每次访问时,先使用pc+addr匹配,如果没匹配到,就使用pc+offset匹配

1739537107193

Bingo历史表的组成

Bingo的空间数据预取器采用了一个存储高效的单历史表设计,这个表是实现预取功能的核心组件。历史表的每个条目包含了以下几个关键组成部分:

  • 触发访问事件 :这是预取器在记录访问模式时所依据的事件,通常包括程序计数器(PC)、地址(Address)和偏移量(Offset)等信息。例如,长事件为 PC+Address,短事件为 PC+Offset
  • 页面足迹(Footprint) :这是一个位向量,表示页面中哪些块被访问过。每个位对应页面中的一个缓存块,1表示该块被访问过,0表示未被访问。
  • 踏频信息(Recency) :用于记录条目的最近使用情况,帮助预取器选择替换策略,如最久未使用(LRU)。
  • 标签(Tag) :用于标识条目,确保正确的事件匹配。

Bingo历史表的工作原理

Bingo历史表的工作过程可以分为以下几个步骤:

  1. 触发访问 :当处理器访问一个新的页面时,触发访问发生,预取器开始记录该页面的访问模式。
  2. 记录足迹 :在页面的驻留期间,预取器会记录所有访问到的缓存块,生成页面的足迹(Footprint)。
  3. 存储足迹 :当页面的驻留结束时,预取器将足迹以及触发访问的事件(如 PC+Address)存储到历史表中。存储时,使用短事件的哈希值来索引表的位置,并将长事件作为标签存储。
  4. 预取决策 :当后续的访问触发预取时,预取器首先使用长事件(如 PC+Address)查找历史表。如果找到匹配项,就使用对应的足迹进行预取。如果未找到匹配项,则使用短事件(如 PC+Offset)再次查找历史表。如果找到匹配项,就使用对应的足迹进行预取。如果仍未找到匹配项,则不进行预取。

通过这种设计,Bingo能够在保持高准确性的同时,不丢失预测机会,从而提高系统性能。

其中足迹的获取是第一次访问这个页面就记录,然后结束后把足迹送入,类似于SMS生成方式

总结

该论文创新点在于结合了PC+addr和PC+offset,并且将二者存在一个表内,pc+offset索引,pc+addr作为tag