Lune

ISCA2020Top-tier venue

GraphABCD: Scaling Out Graph Analytics with Asynchronous Block Coordinate Descent

Yifan Yang, Zhaoshi Li, Yangdong Deng, Zhiwei Liu, Shouyi Yin, Shaojun Wei, Leibo Liu

Abstract

It is of vital importance to efficiently process large graphs for many data-intensive applications. As a result, a large collection of graph analytic frameworks has been proposed to improve the per-iteration performance on a single kind of computation resource. However, heavy coordination and synchronization overhead make it hard to scale out graph analytic frameworks from single platform to heterogeneous platforms. Furthermore, increasing the convergence rate, i.e. reducing the number of iterations, which is equally vital for improving the overall performance of iterative graph algorithms, receives much less attention.

In this paper, we introduce the Block Coordinate Descent (BCD) view of graph algorithms and propose an asynchronous heterogeneous graph analytic framework, GraphABCD, using the BCD view. The BCD view offers key insights and trade-offs on achieving high convergence rate of iterative graph algorithms. GraphABCD features fast convergence under the algorithm design options suggested by BCD. GraphABCD offers algorithm and architectural supports for asynchronous execution, without undermining its fast convergence properties. With minimum synchronization overhead, GraphABCD is able to scale out to heterogeneous and distributed accelerators efficiently. To demonstrate GraphABCD, we prototype its whole system on Intel HARPv2 CPU-FPGA heterogeneous platform. Evaluations on HARPv2 show that GraphABCD achieves geo-mean speedups of 4.8x and 2.0x over GraphMat, a state-of-the-art framework in terms of convergence rate and execution time, respectively.

Index Terms-graph analytics, hardware accelerator, FPGA, heterogeneous architecture Yifan Yang is now at MIT CSAIL.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • GCNAX: A Flexible and Energy-efficient Accelerator for Graph Convolutional Neural Networks cites HyGCN: A GCN Accelerator with Hybrid Architecture
  • SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems cites HyGCN: A GCN Accelerator with Hybrid Architecture
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. GCNAX: A Flexible and Energy-efficient Accelerator for Graph Convolutional Neural NetworksJiajun Li, Ahmed Louri, Avinash Karanth, Razvan C. BunescuHPCA 2021 · 147 citations
  2. SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory SystemsMaciej Besta, Raghavendra Kanakagiri, Grzegorz Kwasniewski, Rachata Ausavarungnirun et al.MICRO 2021 · 78 citations
  3. PolyGraph: Exposing the Value of Flexibility for Graph Processing AcceleratorsVidushi Dadu, Sihao Liu, Tony NowatzkiISCA 2021 · 60 citations
  4. FlexMiner: A Pattern-Aware Accelerator for Graph Pattern MiningXuhao Chen, Tianhao Huang, Shuotao Xu, Thomas Bourgeat et al.ISCA 2021 · 41 citations
  5. SpZip: Architectural Support for Effective Data Compression In Irregular ApplicationsYifan Yang, Joel S. Emer, Daniel SánchezISCA 2021 · 31 citations

Builds on1

  1. HyGCN: A GCN Accelerator with Hybrid ArchitectureMingyu Yan, Lei Deng, Xing Hu, Ling Liang et al.HPCA 2020 · 338 citations

Related papers

  1. Efficient Graph Query Processing over Geo-Distributed DatacentersYe Yuan, Delong Ma, Zhenyu Wen, Yuliang Ma et al.SIGIR 2020 · 11 citations
  2. GraphPulse: An Event-Driven Hardware Accelerator for Asynchronous Graph ProcessingShafiur Rahman, Nael B. Abu-Ghazaleh, Rajiv GuptaMICRO 2020 · 67 citations
  3. ACGraph: An Efficient Asynchronous Out-of-Core Graph Processing FrameworkDechuang Chen, Sibo Wang, Qintian GuoSIGMOD 2026 · 3 citations
  4. Large-Scale Graph Processing on FPGAs with Caches for Thousands of Simultaneous MissesMikhail Asiatici, Paolo IenneISCA 2021 · 28 citations
  5. GX-Plug: a Middleware for Plugging Accelerators to Distributed Graph ProcessingKai Zou, Xike Xie, Qi Li, Deyu KongICDE 2022 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines