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

Алеева Валентина Николаевна; Манатин Павел Андреевич; Aleeva V.N.; Manatin P.A.

doi:10.14529/cmse230203

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 2 т.12, 2023 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/147240874

IDR: 147240874 | УДК: 004.021, | DOI: 10.14529/cmse230203

Application of the design method for q-efficient programs implementing Dijkstra's algorithm

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.

Еще

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

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.
Алеева B.H., Алеев Р.Ж. Применение Q-детерминанта численных алгоритмов для параллельных вычислений // Параллельные вычислительные технологии (ПаВТ’2019): Труды международной научной конференции, Калининград, 2-4 апреля 2019. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. С. 133-145.
Алеева В.Н. Основные положения технологии Q-эффективного программирования // Наука ЮУрГУ. Секции технических наук: материалы 71-й научной конференции, Челябинск, апрель 2019. Челябинск: Издательский центр ЮУрГУ, 2019. С. 334-342.
Алеева В.Н., Шатов М.Б. Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56-71. DOI: 10.14529/cmse210304.
Aleeva V.N. Improving Parallel Computing Efficiency // Proceedings - 2020 Global Smartlndustry 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 VI.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.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
Voevodin VI., 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/jsfil50101.
Voevodin VI., 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/jshl80101.
Абрамов С.М., Адамович А.И., Коваленко М. Р. Т-система - среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей / / Программирование. 1999. Т. 25, № 2. С. 100-107.
Абрамов С.М., Васенин В.А., Мамчиц Е.Е. и др. Динамическое распараллеливание программ на базе параллельной редукции графов. Архитектура программного обеспечения новой версии Т-системы // Научная сессия МИФИ-2001, 22-26 января 2001: Сборник научных трудов. Т. 2. 2001. С. 234.
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.
Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии. 2005. Т. 1, № 10. С. 71-89.
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 М., 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/sl0766-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-l_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/ (дата обращения: 14.03.2023).
Биленко P.B., Долганина Н.Ю., Иванова Е.В., Рекачинский А.И. Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университета / / Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. С. 15-30. DOI: 10.14529/cmse220102.
Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы / / Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66-81. DOI: 10.14529/cmse210205.
Aleeva V., Bogatyreva Е., 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.

Еще