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

Применение метода проектирования 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   |   DOI: 10.14529/cmse230203

Список литературы Применение метода проектирования 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.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp