Application of the Design Method for Q-effective Programs Implementing Dijkstra’s Algorithm

Pavel A. Manatin

Valentina N. Aleeva


Abstract


The problem of improving the efficiency of parallel computing is extremely relevant. The article demonstrates the initial application of the concept of Q-determinant for the effective implementation of graph algorithms. The concept of the Q-determinant is based on a unified representation of numerical algorithms in the form of the Q-determinant. The Q-determinant allows to express and evaluate the internal parallelism of the algorithm, as well as to show the method of its parallel execution. The article gives the main notions of the Q-determinant concept necessary for better understanding of our research. Also, we describe a method of designing effective programs for numerical algorithms on the base of the concept of the Q-determinant. As a result, we obtain the program, which uses the parallelism resource of the algorithm completely, and this program is called Q-effective. As the initial application of the method for design of Q-effective programs implementing graph algorithms, we describe the designing programs for Dijkstra’s algorithm implementation on parallel computing systems with shared and distributed memory. Finally, for the developed programs, we present the results of experiments on the Tornado SUSU supercomputer. Analyzing the results of the experimental study, we determine the effectiveness of the developed programs and identify features of their execution. The research described in the article leads to the conclusion that the application of the Q-determinant concept for the development of effective programs is possible not only for numerical algorithms, but also for graph algorithms.

Keywords


improving parallel computing efficiency; Q-determinant of algorithm; representation of algorithm in the form of Q-determinant; Q-effective implementation of algorithm; parallelism resource of algorithm; Q-effective program; Dijkstra's algorithm

References


Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik. 1959. Vol. 1, no. 1. P. 269–271. DOI: 10.1007/BF01386390.

Aleeva V.N., Aleev R.Zh. Application of the Q-determinant of numerical algorithms for parallel computing. Parallel Computational Technologies (PCT’2019): Proceedings of the International Conference, Kaliningrad, Russia, April 2–4, 2019. Short articles and poster descriptions. Chelyabinsk: SUSU Publishing Center, 2019. P. 133–145. (in Russian)

Aleeva V.N. The fundamentals of Q-effective programming technology. Science of SUSU. Sections of Technical Sciences: materials of the 71st Scientific Conference, Chelyabinsk, Russia, April 2019. Chelyabinsk: SUSU Publishing Center, 2019. P. 334–342. (in Russian)

Aleeva V.N., Shatov M.B. Application of the Q-determinant Concept for Efficient Implementation of Numerical Algorithms by the Example of the Conjugate Gradient Method for Solving Systems of Linear Equations. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 3. P. 56–71. (in Russian) DOI: 10.14529/cmse210304.

Aleeva V.N. Improving Parallel Computing Efficiency. Proceedings – 2020 Global Smart Industry Conference, GloSIC 2020, Chelyabinsk, Russia, November 17–19, 2020. IEEE, 2020. P. 113–120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828.

Voevodin V.V., Voevodin Vl.V. The V-Ray technology of optimizing programs to parallel computers. Numerical Analysis and Its Applications. WNAA 1996. Vol. 1196 / ed. by L.G. Vulkov, P. Yalamov, J. Wasniewski. Springer, 1997. P. 546–556. LNCS. DOI: 10.1007/3- 540-62598-4_136.

Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg: BHV-Petersburg, 2002. 608 p. (in Russian)

Voevodin Vl., Antonov A., Dongarra J. AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features. Supercomputing Frontiers and Innovations. 2015. Vol. 2, no. 1. P. 4–18. DOI: 10.14529/jsfi150101.

Voevodin Vl., Antonov A., Dongarra J. AlgoWiki Project as an Extension of the Top500 Methodology. Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 1. P. 4–10. DOI: 10.14529/jsfi180101.

Abramov S.M., Adamovich A.I., Kovalenko M. R. T-system programming environment with support for automatic dynamic parallelization of programs. An example of the implementation of an algorithm for constructing images by ray tracing. Programming. 1999. Vol. 25, no. 2. P. 100–107. (in Russian)

Abramov S.M., Vasenin V.A., Mamchits E.E., et al. Dynamic parallelization of programs based on parallel graph reduction. Software architecture of the new version of the T-system. Scientific session of MEPhI–2001, January 22–26, 2001: Collection of scientific papers. Vol. 2. 2001. P. 234. (in Russian)

Malyshkin V.E., Perepelkin V.A., Schukin G.F. Distributed Algorithm of Data Allocation in the Fragmented Programming. Parallel Computing Technologies (PaCT’2015): Proceedings of the 13th International Scientific Conference, Petrozavodsk, Russia, August 31 – September 4, 2015. Proceedings. Vol. 9251 / ed. by V. Malyshkin. Springer, 2015. P. 80–85. LNCS. DOI: 10.1007/978-3-319-21909-7_8.

Malyshkin V.E., Perepelkin V.A., Tkacheva A.A. Control Flow Usage to Improse Performanse of Fragmented. Parallel Computing Technologies (PaCT’2015): Proceedings of the 13th International Conference, Petrozavodsk, Russia, August 31 – September 4, 2015. Proceedings. Vol. 9251 / ed. by V. Malyshkin. Springer, 2015. P. 86–90. LNCS. DOI: 10.1007/978-3-319-21909-7_9.

Legalov A.I. Functional language for architecturally independent parallel programs creating. Computational Technologies. 2005. Vol. 1, no. 10. P. 71–89. (in Russian)

Gurieva Y.L., Il’in V.P. On Parallel Computational Technologies of Augmented Domain Decomposition Methods. Parallel Computing Technologies (PaCT’2015): Proceedings of the 13th International Conference, Petrozavodsk, Russia, August 31 – September 4, 2015. Proceedings. Vol. 9251. / ed. by V. Malyshkin. Springer, 2015. P. 35–46. LNCS. DOI: 10.1007/978-3-319-21909-7_4.

Schlueter M., Munetomo M. Parallelization strategies for evolutionary algorithms for MINLP. IEEE Congress on Evolutionary Computation, Cancun, Mexico, June 23–25, 2013. P. 635–641. DOI: 10.1109/CEC.2013.6557628.

Wang Q., Liu J., Tang X., et al. Accelerating embarrassingly parallel algorithm on Intel MIC. IEEE International Conference on Progress in Informatics and Computing, Shanghai, China, May 16–18, 2014. P. 213–218. DOI: 10.1109/PIC.2014.6972327.

Li Y., Dou W., Yang K., et al. Optimized Data I/O Strategy of the Algorithm of Parallel Digital Terrain Analysis. 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, Xi’an, China, November 24–27, 2014. P. 34–37. DOI: 10.1109/DCABES.2014.10.

Prifti V., Bala R., Tafa I., et al. The time profit obtained by parallelization of quicksort algorithm used for numerical sorting. Science and Information Conference (SAI), London, UK, July 28–30, 2015. P. 897–901. DOI: 10.1109/SAI.2015.7237248.

Rajashri A. Parallelization of shortest path algorithm using OpenMP and MPI. International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC), Palladam, India, February 10–11, 2017. P. 304–309. DOI: 10.1109/I-SMAC.2017.8058360.

Fazio M., Buzachis A., Galletta A., et al. A Map-Reduce Approach for the Dijkstra Algorithm in SDN Over Osmotic Computing Systems. International Journal of Parallel Programming. 2021. Vol. 49, no. 3. P. 347–375. DOI: 10.1007/s10766-021-00693-3.

Zhang W., Zhang L., Chen Y. Asynchronous Parallel Dijkstra’s Algorithm on Intel Xeon Phi Processor International Conference on Algorithms and Architectures for Parallel Processing. 2018. P. 337–357. DOI: 10.1007/978-3-030-05051-1_24.

Jasika N., Alispahic N., Elma A., et al. Dijkstra’s shortest path algorithm serial and parallel execution performance analysis. 2012 Proceedings of the 35th International Convention MIPRO, Opatija, Croatia, May 21–25, 2012. P. 1811–1815. URL: https://ieeexplore.ieee.org/document/6240942/ (accessed: 14.03.2023).

Bilenko R.V., Dolganina N.Yu., Ivanova E.V., Rekachinsky A.I. High-performance computing resources of South Ural State University. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2022. Vol. 11, no. 1. P. 15–30. DOI: 10.14529/cmse220102.

Aleeva V.N., Zotova P.S., Skleznev D.S. Advancement of research for the parallelism resourceof numerical algorithms with help of software Q-system. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 2. P. 66–81. (in Russian) DOI: 10.14529/cmse210205.

Aleeva V., Bogatyreva E., Skleznev A., et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism. Supercomputing. Vol. 1129 / ed. by V. Voevodin, S. Sobolev. Springer, 2019. P. 641–652. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-36592-9_52.




DOI: http://dx.doi.org/10.14529/cmse230203