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 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 148
  • Publication Date: 2021
  • Doi Number: 10.1016/j.jpdc.2020.10.005
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Applied Science & Technology Source, Computer & Applied Sciences, INSPEC, zbMATH
  • Page Numbers: pp.69-82
  • Istanbul Technical University Affiliated: Yes


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.