Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling(MICRO2018)

[meton-robean]

Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling

[meton-robean]

演讲PPT

[meton-robean]

传统图算法的图表示

[meton-robean]

传统图算法瓶颈: 随机访问多，局部性差

以常用的一种遍历调度算法为例：Vertex-ordered (VO) schedule

[meton-robean]

创新一: 新的调度算法：BDFS: Bounded Depth-First Scheduling

作者认为 利用带遍历深度限制的DFS搜索有更好的局部性。虽然在邻居数组那边的空间局部性变差了一些， 但是在节点数据数组这边获得了高时间局部性。

疑问点：为什么节点数据数组这边的时间局部性变好了？？？

[meton-robean]

创新二：基于BDFS 提出了一个硬件预取架构 BDFS-HAT

1. HATS 和 core功能解耦，HATS负责基于BDFS对图进行遍历调度。 core则负责和应用相关的图节点数据的处理逻辑。

2.HATS 事先运行， 它会往FIFO Buffer放 图的边信息 （图的边由 soure id, dest id, weight），同时 它还会预取 source 和 dest 的 图节点数据 (vertex data) 放入L2 cache中。

3. core运行时，需要从FIFO中取出图的各条边的信息， 根据这些信息计算得到的 source , dest的访存地址取数， 而此时数据以及被HATS取到了cache中了。