Применение метода проектирования Q-эффективных программ для алгоритма Дейкстры

Павел Андреевич Манатин, Валентина Николаевна Алеева

Аннотация


Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции Q-детерминанта для эффективной реализации алгоритма на графах. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве первого применения метода проектирования Q-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции Q-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.

Ключевые слова


повышение эффективности параллельных вычислений; Q-детерминант алгоритма; представление алгоритма в форме Q-детерминанта; Q-эффективная реализация алгоритма; ресурс параллелизма алгоритма; Q-эффективная программа; алгоритм Дейкстры

Полный текст:

PDF

Литература


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