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

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)69-82
Number of pages14
JournalJournal of Parallel and Distributed Computing
Publication statusPublished - Feb 2021

Bibliographical note

Publisher Copyright:
© 2020 Elsevier Inc.


  • GPU microarchitecture
  • Graph application
  • Scalar waving
  • SIMD efficiency


Dive into the research topics of 'Graph-Waving architecture: Efficient execution of graph applications on GPUs'. Together they form a unique fingerprint.

Cite this