search

meton-robean / PaperNotes

记录阅读各类paper的想法笔记（关注体系结构，机器学习系统，深度学习，计算机视觉）
23 stars 1 forks source link

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

Open meton-robean opened 4 years ago

meton-robean commented 4 years ago

Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling Selection_047

meton-robean commented 4 years ago

演讲PPT

meton-robean commented 4 years ago

传统图算法的图表示

image

meton-robean commented 4 years ago

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

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

meton-robean commented 4 years ago

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

image Selection_077

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

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

meton-robean commented 4 years ago

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

Selection_078

Selection_079

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中了。