Skip to main content

2019 | OriginalPaper | Buchkapitel

Graph Coloring Using GPUs

verfasst von : Meghana Aparna Sistla, V. Krishna Nandivada

Erschienen in: Euro-Par 2019: Parallel Processing

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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 \).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Literatur
1.
Zurück zum Zitat 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.
Zurück zum Zitat Ç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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM TOMS 38(1), 1 (2011)MathSciNetMATH Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM TOMS 38(1), 1 (2011)MathSciNetMATH
8.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat Jones, M.T., Plassmann, P.E.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654–669 (1993)MathSciNetCrossRef Jones, M.T., Plassmann, P.E.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654–669 (1993)MathSciNetCrossRef
12.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat Nvidia, C.: CuSPARSE Library. NVIDIA Corporation, Santa Clara (2014) Nvidia, C.: CuSPARSE Library. NVIDIA Corporation, Santa Clara (2014)
20.
Zurück zum Zitat 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)
Metadaten
Titel
Graph Coloring Using GPUs
verfasst von
Meghana Aparna Sistla
V. Krishna Nandivada
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-29400-7_27