Zhao, Jin, Yang, Yun, Zhang, Yu, Liao, Xiaofei, Gu, Lin, He, Ligang, He, Bingsheng, Jin, Hai, Liu, Haikun, Jiang, Xinyu and Yu, Hui (2022) TDGraph : a topology-driven accelerator for high-performance streaming graph processing. In: 49th Annual International Symposium on Computer Architecture, New York, USA, 18–22 Jun 2022. Published in: ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture pp. 116-129. ISBN 9781450386104. doi:10.1145/3470496.3527409
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Many solutions have been recently proposed to support the processing of streaming graphs. However, for the processing of each graph snapshot of a streaming graph, the new states of the vertices affected by the graph updates are propagated irregularly along the graph topology. Despite the years' research efforts, existing approaches still suffer from the serious problems of redundant computation overhead and irregular memory access, which severely underutilizes a many-core processor. To address these issues, this paper proposes a topology-driven programmable accelerator TDGraph, which is the first accelerator to augment the many-core processors to achieve high performance processing of streaming graphs. Specifically, we propose an efficient topology-driven incremental execution approach into the accelerator design for more regular state propagation and better data locality. TDGraph takes the vertices affected by graph updates as the roots to prefetch other vertices along the graph topology and synchronizes the incremental computations of them on the fly. In this way, most state propagations originated from multiple vertices affected by different graph updates can be conducted together along the graph topology, which help reduce the redundant computations and data access cost. Besides, through the efficient coalescing of the accesses to vertex states, TDGraph further improves the utilization of the cache and memory bandwidth. We have evaluated TDGraph on a simulated 64-core processor. The results show that, the state-of-the-art software system achieves the speedup of 7.1~21.4 times after integrating with TDGraph, while incurring only 0.73% area cost. Compared with four cutting-edge accelerators, i.e., HATS, Minnow, PHI, and DepGraph, TDGraph gains the speedups of 4.6~12.7, 3.2~8.6, 3.8~9.7, and 2.3~6.1 times, respectively.
| Item Type: | Conference Item (Paper) |
|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Journal or Publication Title: | ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture |
| Publisher: | ACM |
| ISBN: | 9781450386104 |
| Book Title: | Proceedings of the 49th Annual International Symposium on Computer Architecture |
| Official Date: | June 2022 |
| Dates: | Date Event June 2022 Published 11 June 2022 Available |
| Page Range: | pp. 116-129 |
| DOI: | 10.1145/3470496.3527409 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Conference Paper Type: | Paper |
| Title of Event: | 49th Annual International Symposium on Computer Architecture |
| Type of Event: | Conference |
| Location of Event: | New York, USA |
| Date(s) of Event: | 18–22 Jun 2022 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/167674/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |