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

Yılmazer Metin A.

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, cilt.148, ss.69-82, 2021 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 148
  • Basım Tarihi: 2021
  • Doi Numarası: 10.1016/j.jpdc.2020.10.005
  • Dergi Adı: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Applied Science & Technology Source, Computer & Applied Sciences, INSPEC, zbMATH
  • Sayfa Sayıları: ss.69-82
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

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.