Skip to main content
Top

2019 | OriginalPaper | Chapter

Graph Coloring Using GPUs

Authors : Meghana Aparna Sistla, V. Krishna Nandivada

Published in: Euro-Par 2019: Parallel Processing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Graph coloring is a widely studied problem that is used in a variety of applications, such as task scheduling, register allocation, eigenvalue computations, social network analysis, and so on. Many of the modern day applications deal with large graphs (with millions of vertices and edges) and researchers have exploited the parallelism provided by multi-core systems to efficiently color such large graphs. GPUs provide a promising parallel infrastructure to run large applications. In this paper, we present new schemes to efficiently color large graphs on GPUs.
We extend the algorithm of Rokos et al. [21] to efficiently color graphs using GPUs. Their approach has to continually resolve conflicts for color assignment. We present a data driven variation of their algorithm and use an improved scheme for conflict resolution. We also propose two optimizations for our algorithm to reduce both the execution time and memory requirements. We have evaluated our scheme (called SIRG) against the NVIDIA cuSPARSE library and the work of Chen et al. [13], and show that SIRG runs significantly faster: geomean 3.42\(\times \) and 1.76\(\times \), respectively. We have also compared SIRG against the scheme of Rokos et al. [21] for CPUs and show that SIRG performs faster on most input graphs: geomean 10.37\(\times \).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Biggs, N.: Some heuristics for graph colouring. In: Nelson, R., Wilson, R.J. (eds.) Graph Colourings, pp. 87–96 (1990) Biggs, N.: Some heuristics for graph colouring. In: Nelson, R., Wilson, R.J. (eds.) Graph Colourings, pp. 87–96 (1990)
2.
go back to reference Çatalyürek, Ü.V., Feo, J., Gebremedhin, A.H., Halappanavar, M., Pothen, A.: Graph coloring algorithms for multi-core and massively multithreaded architectures. Parallel Comput. 38(10–11), 576–594 (2012)MathSciNetCrossRef Çatalyürek, Ü.V., Feo, J., Gebremedhin, A.H., Halappanavar, M., Pothen, A.: Graph coloring algorithms for multi-core and massively multithreaded architectures. Parallel Comput. 38(10–11), 576–594 (2012)MathSciNetCrossRef
3.
go back to reference Chaitin, G.J.: Register allocation & spilling via graph coloring. ACM SIGPLAN Not. 17, 98–105 (1982)CrossRef Chaitin, G.J.: Register allocation & spilling via graph coloring. ACM SIGPLAN Not. 17, 98–105 (1982)CrossRef
4.
go back to reference Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: ICDM, pp. 442–446. SIAM (2004) Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: ICDM, pp. 442–446. SIAM (2004)
5.
go back to reference Chalupa, D.: On the ability of graph coloring heuristics to find substructures in social networks. Inf. Sci. Technol. Bull. ACM Slovak. 3(2), 51–54 (2011) Chalupa, D.: On the ability of graph coloring heuristics to find substructures in social networks. Inf. Sci. Technol. Bull. ACM Slovak. 3(2), 51–54 (2011)
6.
8.
go back to reference Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurr. Pract. Exp. 12(12), 1131–1146 (2000)CrossRef Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurr. Pract. Exp. 12(12), 1131–1146 (2000)CrossRef
9.
go back to reference Grosset, A.V.P., Zhu, P., Liu, S., Venkatasubramanian, S., Hall, M.: Evaluating graph coloring on GPUs. ACM SIGPLAN Not. 46(8), 297–298 (2011)CrossRef Grosset, A.V.P., Zhu, P., Liu, S., Venkatasubramanian, S., Hall, M.: Evaluating graph coloring on GPUs. ACM SIGPLAN Not. 46(8), 297–298 (2011)CrossRef
10.
go back to reference Harris, M., Sengupta, S., Owens, J.D.: Parallel prefix sum (scan) with CUDA. GPU gems 3(39), 851–876 (2007) Harris, M., Sengupta, S., Owens, J.D.: Parallel prefix sum (scan) with CUDA. GPU gems 3(39), 851–876 (2007)
11.
12.
go back to reference Jones, M.T., Plassmann, P.E.: Scalable iterative solution of sparse linear systems. Parallel Comput. 20(5), 753–773 (1994)MathSciNetCrossRef Jones, M.T., Plassmann, P.E.: Scalable iterative solution of sparse linear systems. Parallel Comput. 20(5), 753–773 (1994)MathSciNetCrossRef
13.
go back to reference Li, P., et al.: High performance parallel graph coloring on GPGPUs. In: IPDPS Workshops, pp. 845–854. IEEE (2016) Li, P., et al.: High performance parallel graph coloring on GPGPUs. In: IPDPS Workshops, pp. 845–854. IEEE (2016)
14.
go back to reference Luby, M.: A simple parallel algorithm for the maximal independent set problem. J. Comput. 15(4), 1036–1053 (1986)MathSciNetMATH Luby, M.: A simple parallel algorithm for the maximal independent set problem. J. Comput. 15(4), 1036–1053 (1986)MathSciNetMATH
15.
go back to reference Manne, F.: A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices. In: Kågström, B., Dongarra, J., Elmroth, E., Waśniewski, J. (eds.) PARA 1998. LNCS, vol. 1541, pp. 332–336. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0095354CrossRef Manne, F.: A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices. In: Kågström, B., Dongarra, J., Elmroth, E., Waśniewski, J. (eds.) PARA 1998. LNCS, vol. 1541, pp. 332–336. Springer, Heidelberg (1998). https://​doi.​org/​10.​1007/​BFb0095354CrossRef
16.
go back to reference Marx, D.: Graph colouring problems and their applications in scheduling. Period. Polytech. Electr. Eng. 48(1–2), 11–16 (2004) Marx, D.: Graph colouring problems and their applications in scheduling. Period. Polytech. Electr. Eng. 48(1–2), 11–16 (2004)
17.
go back to reference Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344–354 (1996)CrossRef Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344–354 (1996)CrossRef
18.
go back to reference Nasre, R., Burtscher, M., Pingali, K.: Data-driven versus topology-driven irregular computations on GPUs. In: IPDPS, pp. 463–474. IEEE (2013) Nasre, R., Burtscher, M., Pingali, K.: Data-driven versus topology-driven irregular computations on GPUs. In: IPDPS, pp. 463–474. IEEE (2013)
19.
go back to reference Nvidia, C.: CuSPARSE Library. NVIDIA Corporation, Santa Clara (2014) Nvidia, C.: CuSPARSE Library. NVIDIA Corporation, Santa Clara (2014)
20.
go back to reference Philipsen, W., Stok, L.: Graph coloring using neural networks. In: IEEE International Sympoisum on Circuits and Systems, pp. 1597–1600. IEEE (1991) Philipsen, W., Stok, L.: Graph coloring using neural networks. In: IEEE International Sympoisum on Circuits and Systems, pp. 1597–1600. IEEE (1991)
Metadata
Title
Graph Coloring Using GPUs
Authors
Meghana Aparna Sistla
V. Krishna Nandivada
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-29400-7_27

Premium Partner