TY - GEN
T1 - Balanced Coloring for Parallel Computing Applications
AU - Lu, Hao
AU - Halappanavar, Mahantesh
AU - Chavarria-Miranda, Daniel
AU - Gebremedhin, Assefaw
AU - Kalyanaraman, Ananth
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/7/17
Y1 - 2015/7/17
N2 - 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.
AB - 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.
KW - Balanced coloring
KW - Graph algorithms
KW - Tilera manycore architecture
KW - community detection
UR - http://www.scopus.com/inward/record.url?scp=84971467984&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2015.113
DO - 10.1109/IPDPS.2015.113
M3 - Conference contribution
AN - SCOPUS:84971467984
T3 - Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015
SP - 7
EP - 16
BT - Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015
Y2 - 25 May 2015 through 29 May 2015
ER -