Balanced Coloring for Parallel Computing Applications

Hao Lu, Mahantesh Halappanavar, Daniel Chavarria-Miranda, Assefaw Gebremedhin, Ananth Kalyanaraman

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

15 Scopus citations

Abstract

Graph colouring is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional colouring heuristics aim to reduce the number of colours used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable colouring is a theoretical formulation of colouring that guarantees a perfect balance among color classes, and its practical relaxation is referred to as balanced colouring. In this paper, we revisit the problem of balanced colouring in the context of parallel computing. The goal is to achieve a balanced colouring of an input graph without increasing the number of colours that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced colouring, present parallelization approaches for multi-core and manicure architectures, and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced colouring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. The thorough treatment of balanced colouring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using colouring.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages7-16
Number of pages10
ISBN (Electronic)9781479986484
DOIs
StatePublished - Jul 17 2015
Externally publishedYes
Event29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015 - Hyderabad, India
Duration: May 25 2015May 29 2015

Publication series

NameProceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015

Conference

Conference29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015
Country/TerritoryIndia
CityHyderabad
Period05/25/1505/29/15

Keywords

  • Balanced coloring
  • Graph algorithms
  • Tilera manycore architecture
  • community detection

Fingerprint

Dive into the research topics of 'Balanced Coloring for Parallel Computing Applications'. Together they form a unique fingerprint.

Cite this