Graph-Waving architecture: Efficient execution of graph applications on GPUs


Yılmazer Metin A.

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, vol.148, pp.69-82, 2021 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 148
  • Publication Date: 2021
  • Doi Number: 10.1016/j.jpdc.2020.10.005
  • Title of Journal : JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
  • Page Numbers: pp.69-82

Abstract

Most existing graph frameworks for GPUs adopt a vertex-centric computing model where vertex to thread mapping is applied. When run with irregular graphs, we observe significant load imbalance within SIMD-groups using vertex to thread mapping. Uneven work distribution within SIMD-groups leads to low utilization of SIMD units and inefficient use of memory bandwidth. We introduce Graph-Waving (GW) architecture to improve support for many graph applications on GPUs. It uses vertex to SIMD-group mapping and Scalar-Waving as a mechanism for efficient execution. It also favors a narrow SIMD-group width with a clustered issue approach and reuse of instructions in the front-end. We thoroughly evaluate GW architecture using timing detailed GPGPU-sim simulator with several graph and non-graph benchmarks from a variety of benchmark suites. Our results show that GW architecture provides an average of 4.4x and a maximum of 10x speedup with graph applications, while it obtains 9% performance improvement with regular and 17% improvement with irregular benchmarks. (C) 2020 Elsevier Inc. All rights reserved.