Parallel Vertex Color Update on Large Dynamic Networks

Arindam Khanda, Sanjukta Bhowmick, Xin Liang, Sajal K. Das

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We present the first GPU-based parallel algorithm to efficiently update vertex coloring on large dynamic networks. For single GPU, we introduce the concept of loosely maintained vertex color update that reduces computation and memory requirements. For multiple GPUs, in distributed environments, we propose priority-based ordering of vertices to reduce the communication time. We prove the correctness of our algorithms and experimentally demonstrate that for graphs of over 16 million vertices and over 134 million edges on a single GPU, our dynamic algorithm is as much as 20x faster than state-of-the-art algorithm on static graphs. For larger graphs with over 130 million vertices and over 260 million edges, our distributed implementation with 8 GPUs produces updated color assignments within 160 milliseconds. In all cases, the proposed parallel algorithms produce comparable or fewer colors than state-of-the-art algorithms.

Original languageEnglish
Title of host publicationProceedings - 2022 IEEE 29th International Conference on High Performance Computing, Data, and Analytics, HiPC 2022
Pages115-124
Number of pages10
ISBN (Electronic)9781665494236
DOIs
StatePublished - 2022
Event29th Annual IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2022 - Bangalore, India
Duration: Dec 18 2022Dec 21 2022

Publication series

NameProceedings - 2022 IEEE 29th International Conference on High Performance Computing, Data, and Analytics, HiPC 2022

Conference

Conference29th Annual IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2022
Country/TerritoryIndia
CityBangalore
Period12/18/2212/21/22

Bibliographical note

Publisher Copyright:
© 2022 IEEE.

Keywords

  • Dynamic networks
  • Parallel/distributed algorithm
  • Vertex coloring

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Information Systems and Management
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Parallel Vertex Color Update on Large Dynamic Networks'. Together they form a unique fingerprint.

Cite this