Top

International Journal of Parallel Programming

Published in:

27-11-2021

Accelerating Computation of Steiner Trees on GPUs

Authors: Rajesh Pandian Muniasamy, Rupesh Nasre, N. S. Narayanaswamy

Published in: International Journal of Parallel Programming | Issue 1/2022

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

search-config

AI-assisted search

Off

Abstract

The Steiner Tree Problem (STP) is a well studied graph theoretic problem. It computes a minimum-weighted tree of a given graph such that the tree spans a given subset of vertices called terminals. STP is NP-hard. Due to its wide applicability, it has been a challenge problem in the 11th DIMACS implementation challenge and the PACE 2018 challenge. Due to its importance, polynomial-time approximation algorithms have been devised for solving the STP. One of the most popular algorithms is by Kou, Markowsky and Berman (KMB) which provides a 2-approximation to STP. In practice, a naïve implementation of the KMB algorithm is prohibitively slow for large graphs. Our goal in this work is to improve KMB algorithm’s practical utility by parallelizing it on GPU and reduce its execution time on real-world graphs. This parallelization faces several challenges due to the inherent irregular nature of computation, as well as critical design decisions affecting the algorithm choice and optimizations. We overcome these challenges with interesting algorithmic observations and by exploiting parallelization within sub-steps, and develop the first GPU-based efficient approach to computing Steiner trees using KMB. We illustrate the effectiveness of our approach using several graph benchmarks from the DIMACS Challenge, the PACE Challenge, SteinLib, and SNAP. Our highly optimized GPU implementation achieves an average 20\(\times\) speedup over the CPU-sequential Open Graph algorithms and Data structure (OGDF)’s KMB implementation. In addition to this, our optimized CPU implementation achieves an average 4\(\times\) over OGDF’s KMB, the only published open-source KMB implementation.

previous article A Profile-Based AI-Assisted Dynamic Scheduling Approach for Heterogeneous Architectures

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!

inform now

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!

inform now

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!

inform now

One may further explore algorithmic variants such as \(\varDelta\)-stepping, which may suit their setup.

Diameter is the maximum eccentricity. Eccentricity(v) is the largest distance from v to all the vertices in V, i.e., d(v, V). Here, diameter over terminal means \(\max d(v,L)\).

Hwang, F. K., Richards, D. S., Winter, P.: Monograph. In: The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53. Elsevier (1992). https://doi.org/10.1016/S0167-5060(08)70188-2. http://www.sciencedirect.com/science/article/pii/S0167506008701894

Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195–207 (1971)MathSciNetCrossRef

Fuchs, B., Kern, W., Molle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theor. Comput. Syst. 41(3), 493–500 (2007). https://doi.org/10.1007/s00224-007-1324-4MathSciNetCrossRefMATH

Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)

Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer Publishing Company, Incorporated, Cham (2015)CrossRef

Johnson, D.S., Koch, T., Werneck, R.F., Zachariasen, M.: 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems. (2014). [Online; accessed 27-Mar-2019]

Bonnet, É., Sikora, F.: The 3rd Parameterized Algorithms and Computational Experiments Challenge. https://pacechallenge.org/2018/ (2018). [Online; accessed 27-Mar-2019]

Bonnet, É., Sikora, F.: The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. In: C. Paul, M. Pilipczuk (eds.) 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 115, pp. 26:1–26:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https://doi.org/10.4230/LIPIcs.IPEC.2018.26. http://drops.dagstuhl.de/opus/volltexte/2019/10227

Mehlhorn, K.: A faster approximation algorithm for the steiner problem in graphs. Inf. Process. Lett. 27(3), 125–128 (1988). https://doi.org/10.1016/0020-0190(88)90066-XMathSciNetCrossRefMATH

10.

Borradaile, G., Klein, P.N., Mathieu, C.: An On (n log n) approximation scheme for steiner tree in planar graphs. ACM Trans. Algorithms 5(3), 1–31 (2009). https://doi.org/10.1145/1541885.1541892CrossRefMATH

11.

Zelikovsky, A.: An 11/6-approximation algorithm for the network steiner problem. Algorithmica 9(5), 463–470 (1993). https://doi.org/10.1007/BF01187035MathSciNetCrossRefMATH

12.

Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA., pp. 770–779 (2000). http://dl.acm.org/citation.cfm?id=338219.338638

13.

Agrawal, A., Klein, P.N., Ravi, R.: When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24(3), 440–456 (1995). https://doi.org/10.1137/S0097539792236237MathSciNetCrossRefMATH

14.

Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 15(2), 141–145 (1981). https://doi.org/10.1007/BF00288961MathSciNetCrossRefMATH

15.

Koch, T., Martin, A., Voß, S.: Steinlib Testdata Library (2015). http://steinlib.zib.de/steinlib.php. Online; Accessed 27-March-2019

16.

Beyer, S., Chimani, M.: Strong steiner tree approximations in practice. J. Exp. Algorithmics (JEA) 24(1), 1–33 (2019). https://doi.org/10.1145/3299903MathSciNetCrossRefMATH

17.

Romero Ruiz, E., Antonio Cuevas, E., EnriqueVillalobos López, I., Segura González, C.: (CIMAT Team from the Center for Researchin Mathematics, Guanajuato). https://github.com/HeathcliffAC/SteinerTreeProblem (2018). [Online; accessed 21-April-2020]

18.

Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 543–569. Chapman and Hall/CRC, London (2013)

19.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms 3rd Edition. MIT Press , Cambridge (2009). http://mitpress.mit.edu/books/introduction-algorithms

20.

Lenharth, A., Nguyen, D., Pingali, K.: Priority queues are not good concurrent priority schedulers. In: J.L. Träff, S. Hunold, F. Versaci (eds.) Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, Proceedings, Lecture Notes in Computer Science, vol. 9233, pp. 209–221. Springer (2015). https://doi.org/10.1007/978-3-662-48096-0_17

21.

Harish, P., Narayanan, P.J.: Accelerating large graph algorithms on the GPU using CUDA. In: High Performance Computing - HiPC 2007, 14th International Conference, Goa, India, Proceedings, pp. 197–208 (2007). https://doi.org/10.1007/978-3-540-77220-0_21

22.

Martín, P.J., Torres, R., Gavilanes, A.: CUDA solutions for the SSSP problem. In: Computational Science - ICCS 2009, 9th International Conference, Baton Rouge, LA, USA, May 25-27, 2009, Proceedings, Part I, pp. 904–913 (2009). https://doi.org/10.1007/978-3-642-01970-8_91

23.

Nasre, R., Burtscher, M., Pingali, K.: Data-driven versus topology-driven irregular computations on gpus. In: 27th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2013, Cambridge, MA, USA, pp. 463–474 (2013). https://doi.org/10.1109/IPDPS.2013.28

24.

Acar, U.A., Blelloch, G.E.: Algorithms: Parallel and Sequential. Online-Draft (2019). http://www.algorithms-book.com/

25.

Jia, Z., Kwon, Y., Shipman, G.M., McCormick, P.S., Erez, M., Aiken, A.: A distributed multi-gpu system for fast graph processing. Proc. VLDB Endow. 11(3), 297–310 (2017)https://doi.org/10.14778/3157794.3157799CrossRef

26.

Salvador, G., Darvin, W.H., Huzaifa, M., Alsop, J., Sinclair, M.D., Adve, S.V.: Specializing Coherence, Consistency, and Push/pull for GPU Graph Analytics. In: IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2020, Boston, MA, USA, August 23-25, 2020, pp. 123–125. IEEE (2020). https://doi.org/10.1109/ISPASS48437.2020.00027http://dimacs11.zib.de/home.html

27.

Merrill, D., Garland, M., Grimshaw, A.S.: Scalable GPU graph traversal. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2012, New Orleans, LA, USA, pp. 117–128 (2012). https://doi.org/10.1145/2145816.2145832

28.

Wang, Y., Pan, Y., Davidson, A.A., Wu, Y., Yang, C., Wang, L., Osama, M., Yuan, C., Liu, W., Riffel, A.T., Owens, J.D.: Gunrock: GPU graph analytics. ACM Trans. Parallel Comput. 4(1), 1–49 (2017). https://doi.org/10.1145/3108140CrossRef

29.

Gunrock Developers: (CIMAT Team from the Center for Researchin Mathematics, Guanajuato). https://github.com/gunrock/gunrock/releases/tag/v1.0 (2019). [Online; accessed 21-April-2020]

30.

Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data (2014)

31.

Vineet, V., Harish, P., Patidar, S., Narayanan, P.J.: Fast Minimum Spanning Tree for Large Graphs on the GPU. In: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on High Performance Graphics 2009, New Orleans, Louisiana, USA, pp. 167–171 (2009). https://doi.org/10.2312/EGGH/HPG09/167-172

32.

Dekel, E., Nassimi, D., Sahni, S.: Parallel matrix and graph algorithms. SIAM J. Comput. 10(4), 657–675 (1981). https://doi.org/10.1137/0210049MathSciNetCrossRefMATH

33.

Ramalingam, G., Rangan, C.P.: New sequential and parallel algorithms for interval graph recognition. Inf. Process. Lett. 34(4), 215–219 (1990). https://doi.org/10.1016/0020-0190(90)90163-RMathSciNetCrossRefMATH

34.

Quinn, M.J., Deo, N.: Parallel graph algorithms. ACM Comput. Surv. (CSUR) 16(3), 319–348 (1984). https://doi.org/10.1145/2514.2515MathSciNetCrossRefMATH

35.

Pawan Harish, V.V., Narayanan, P.J.: Large Graph Algorithms for Massively Multithreaded Architectures. In: (Technical Report), IIIT-H, IIIT/TR/2009/74 (2009). https://researchweb.iiit.ac.in/~harishpk/PDF/TR-2009_74.pdf

36.

Barnat, J., Bauch, P., Brim, L., Jr., Cesika, M.: Computing strongly connected components in parallel on CUDA. In: 25th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2011, Anchorage, Alaska, USA, 16-20 May, 2011 - Conference Proceedings, pp. 544–555 (2011). https://doi.org/10.1109/IPDPS.2011.59

37.

Dhulipala, L., Blelloch, G.E., Shun, J.: Theoretically efficient parallel graph algorithms can be fast and scalable. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, pp. 393–404 (2018). https://doi.org/10.1145/3210377.3210414

38.

van der Zanden, T.C., Bodlaender, H.L.: Computing Treewidth on the GPU. In: 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Vienna, Austria, pp. 1–13 (2017). https://doi.org/10.4230/LIPIcs.IPEC.2017.29

39.

Fischetti,M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M. : Approximate the steiner tree using the KMB heuristic. https://homepage.univie.ac.at/ivana.ljubic/research/staynerd/StayNerd.html (2015). [Online; accessed 21-April-2019]

40.

Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out steiner trees: a node-based model for uniform edge costs. Math. Program. Comput. 9(2), 203–229 (2017). https://doi.org/10.1007/s12532-016-0111-0MathSciNetCrossRefMATH

41.

Koch, T., Martin, A., Voß, S.: SteinLib: An Updated Library on Steiner Tree Problems in Graphs, pp. 285–325. Springer US (2001). https://doi.org/10.1007/978-1-4613-0255-1_9

42.

Suzuki, H., Yamanaka, C., Nishizeki, T.: Parallel Algorithms for Finding Steiner Forests in Planar Graphs. In: Algorithms, International Symposium SIGAL ’90, Tokyo, Japan, Proceedings, pp. 458–467 (1990). https://doi.org/10.1007/3-540-52921-7_95

43.

Dahlhaus, E.: A parallel algorithm for computing steiner trees in strongly chordal graphs. Discret. Appl. Math. 51(1–2), 47–61 (1994). https://doi.org/10.1016/0166-218X(94)90093-0MathSciNetCrossRefMATH

44.

Hauptmann, M., Karpinski, M.: A Compendium on Steiner Tree Problems. http://theory.cs.uni-bonn.de/info5/steinerkompendium/ (2015). http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf. [Online; accessed 27-Dec-2020]

45.

Park, J., Ro, W.W., Lee, H., Park, N.: Parallel Algorithms for Steiner Tree Problem. In: Third International Conference on Convergence and Hybrid Information Technology, vol. 1, pp. 453–455 (2008). https://doi.org/10.1109/ICCIT.2008.167

46.

Makki, K., Been, K., Pissinou, N.: A Parallel Algorithm for the Steiner Tree Problem. In: Computing and Information - ICCI’93, Fifth International Conference on Computing and Information, Sudbury, Ontario, Canada, May 27-29, 1993, Proceedings, pp. 380–384 (1993)

47.

Bezensek, M., Robic, B.: A survey of parallel and distributed algorithms for the steiner tree problem. Int. J. Parallel Program. 42(2), 287–319 (2014). https://doi.org/10.1007/s10766-013-0243-zCrossRef

48.

Chow, W., Li, L., Young, E.F.Y., Sham, C.: Obstacle-avoiding rectilinear steiner tree construction in sequential and parallel approach. Integration 47(1), 105–114 (2014). https://doi.org/10.1016/j.vlsi.2013.08.001CrossRef

49.

Mathieu, C., Klusch, M.: Accelerated steiner tree problem solving on GPU with CUDA. In: Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Zhangjiajie, China, Proceedings, Part II, pp. 444–457 (2015). https://doi.org/10.1007/978-3-319-27122-4_31

Title: Accelerating Computation of Steiner Trees on GPUs
Authors: Rajesh Pandian Muniasamy
Rupesh Nasre
N. S. Narayanaswamy
Publication date: 27-11-2021
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 1/2022
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-021-00723-0

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2022

A Profile-Based AI-Assisted Dynamic Scheduling Approach for Heterogeneous Architectures

Statistical Analysis Based Intrusion Detection System for Ultra-High-Speed Software Defined Network

Lightweight Artificial Intelligence Technology for Health Diagnosis of Agriculture Vehicles: Parallel Evolving Artificial Neural Networks by Genetic Algorithm

Enhancing the Effectiveness of Inlining in Automatic Parallelization

A Comparative Survey of Big Data Computing and HPC: From a Parallel Programming Model to a Cluster Architecture

Premium Partner