Graph Prefetching Using Data Structure Knowledge
Graph Prefetching Using Data Structure Knowledge
复制标题
DOI：
10.1145/2925426.2926254
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
S. Ainsworth;Timothy M. Jones
中科院分区：
文献类型：
--
作者：
S. Ainsworth;Timothy M. Jones
由于许多高延迟DRAM访问，在大图上的搜索是内存延迟的严重绑定。由于涉及的访问模式的高度不规则性质，硬件和软件的缓存和预摘要在图形工作负载上的性能较差。这导致大部分时间CPU停滞不前。但是，在许多情况下，数据访问模式是可以预先定义和可预测的，其中许多属于一小部分简单模式。尽管现有的隐式预摘要无法带来巨大的好处，但拥有了解数据结构和访问模式的预定器可以准确地预测应用程序的遍历以引入适当的数据。本文介绍了明确配置的预定器的设计，以提高在高效且常用的压缩稀疏行格格式上进行广度优先搜索和顺序迭代的性能。通过窥探L1缓存访问核心的访问并对从其自己的预取返回的数据做出反应，预取用器可以在需要的应用程序之前安排及时的数据。对于一系列应用和图形尺寸，我们的预摘要的平均加速度为2.3倍，最高3.3倍，对内存带宽要求的影响很小。
Searches on large graphs are heavily memory latency bound, as a result of many high latency DRAM accesses. Due to the highly irregular nature of the access patterns involved, caches and prefetchers, both hardware and software, perform poorly on graph workloads. This leads to CPU stalling for the majority of the time. However, in many cases the data access pattern is well defined and predictable in advance, many falling into a small set of simple patterns. Although existing implicit prefetchers cannot bring significant benefit, a prefetcher armed with knowledge of the data structures and access patterns could accurately anticipate applications' traversals to bring in the appropriate data. This paper presents a design of an explicitly configured prefetcher to improve performance for breadth-first searches and sequential iteration on the efficient and commonly-used compressed sparse row graph format. By snooping L1 cache accesses from the core and reacting to data returned from its own prefetches, the prefetcher can schedule timely loads of data in advance of the application needing it. For a range of applications and graph sizes, our prefetcher achieves average speedups of 2.3x, and up to 3.3x, with little impact on memory bandwidth requirements.