Автоматизированное проектирование и исполнение эффективных программ для численных алгоритмов
Автор: Алеева В.Н.
Статья в выпуске: 3 т.12, 2023 года.
Бесплатный доступ
Проектировать эффективные параллельные программы для многопроцессорных архитектур сложно, так как нет четких формальных правил, которых необходимо придерживаться. Для решения этой проблемы при реализации численных алгоритмов может применяться концепция Q-детерминанта. Данная теория позволяет проводить автоматизированный анализ ресурса параллелизма алгоритма, автоматизированное сравнение ресурсов параллелизма алгоритмов, решающих одну и ту же алгоритмическую проблему, проектировать эффективные программы для реализации алгоритмов с помощью специально разработанного метода проектирования, повысить эффективность реализации численных методов и алгоритмических проблем. Результаты, полученные на основе концепции Q-детерминанта, представляют собой один из вариантов решения проблемы эффективной реализации численных алгоритмов, методов и алгоритмических проблем на параллельных вычислительных системах. Однако пока остается не решенной фундаментальная проблема автоматизированного проектирования и исполнения для любого численного алгоритма программы, реализующей алгоритм эффективно. В статье описана разработка единой для численных алгоритмов программной системы проектирования и исполнения Q-эффективных программ - эффективных программ, спроектированных с помощью концепции Q-детерминанта. Система предназначена для использования на параллельных вычислительных системах с общей памятью. Она состоит из компилятора и виртуальной машины. Компилятор преобразует представление алгоритма в форме Q-детерминанта в исполняемую программу, использующую ресурс параллелизма алгоритма полностью. Виртуальная машина исполняет программу, полученную с помощью компилятора. В статье также приведено экспериментальное исследование созданной программной системы с применением суперкомпьютера «Торнадо ЮУрГУ».
Q-детерминант алгоритма, представление алгоритма в форме q-детерминанта, q-эффективная реализация алгоритма, ресурс параллелизма алгоритма, программная q-система, параллельная вычислительная система, параллельная программа, q-эффективная программа
Короткий адрес: https://sciup.org/147241760
IDR: 147241760 | DOI: 10.14529/cmse230303
Список литературы Автоматизированное проектирование и исполнение эффективных программ для численных алгоритмов
- Алеева В.Н. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
- Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66–81. DOI: 10.14529/cmse210205.
- Алеева В.Н., Шатов М.Б. Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56–71. DOI: 10.14529/cmse210304.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
- Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987. 336 с.
- Репозиторий компилятора программной системы. URL: https://github.com/yuferovalex/qc (дата обращения: 29.06.2023).
- Репозиторий виртуальной машины программной системы. URL: https://github.com/yuferovalex/qvm (дата обращения: 29.06.2023).
- Недожогин Н.С., Копысов С.П., Новиков А.К. Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2020. Т. 9, № 2. С. 40–54. DOI: 10.14529/cmse200203.
- Открытая энциклопедия свойств алгоритмов. URL: https://algowiki-project.org/ru (дата обращения: 30.05.2023).
- Суперкомпьютер «Торнадо ЮУрГУ». URL: http://supercomputer.susu.ru/computers/tornado/ (дата обращения: 30.05.2023).
- Afanasyev I.V., Voevodin V.V., Komatsu K., et al. Distributed Graph Algorithms for Multiple Vector Engines of NEC SX-Aurora TSUBASA Systems // Supercomputing Frontiers and Innovations. 2021. Vol. 8, no. 2. P. 95–113. DOI: 10.14529/jsfi210206.
- Akhmed-Zaki D., Lebedev D., Malyshkin V., et al. Automated Construction of High Performance Distributed Programs in LuNA System // Parallel Computing Technologies (PaCT 2019). Vol. 11657. Springer, 2019. P. 3–9. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-25636-4_1.
- Aleeva V. Designing a Parallel Programs on the Base of the Conception of Q-Determinant // Supercomputing. RuSCDays 2018. Vol. 965. Springer, 2019. P. 565–577. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-05807-4_48.
- Aleeva V.N. Improving Parallel Computing Efficiency // Proceedings – 2020 Global Smart Industry Conference, GloSIC 2020. IEEE, 2020. P. 113–120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828.
- Aleeva V., Aleev R. Investigation and Implementation of Parallelism Resources of Numerical Algorithms // ACM Transactions on Parallel Computing. 2023. Vol. 10. no. 2. Article number 8. P. 1–64. DOI: 10.1145/3583755.
- Aleeva V.N., Aleev R.Zh. High-Performance Computing Using Application of Q-determinant of Numerical Algorithms // Proceedings – 2018 Global Smart Industry Conference, GloSIC 2018. IEEE, 2018. 8 p. Article number 8570160. DOI: 10.1109/GloSIC.2018.8570160.
- Aleeva V., Bogatyreva E., Skleznev A., et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism // Supercomputing. RuSCDays 2019. Vol. 1129. Springer, 2019. P. 641–652. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-36592-9_52.
- Aleeva V.N., Sharabura I.S., Suleymanov D.E. Software System for Maximal Parallelization of Algorithms on the Base of the Conception of Q-determinant // Parallel Computing Technologies (PaCT 2015). Vol. 9251. Springer, 2015. P. 3–9. Lecture Notes in Computer Science. DOI: 10.1007/978-3-319-21909-7_1.
- Antonov A.S., Dongarra J., Voevodin V.V. 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.
- Balaprakash P., Dongarra J., Gamblin T., et al. Autotuning in High-Performance Computing Applications // Proceedings of the IEEE. 2018. Vol. 106, no. 11. P. 2068–2083. DOI: 10.1109/JPROC.2018.2841200.
- Bauer M., Treichler S., Slaughter E., Aiken A. Legion: Expressing locality and independence with logical regions // SC ’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2012. P. 1–11. DOI: 10.1109/SC.2012.71.
- Bosilca G., Bouteiller A., Danalis A., et al. Flexible Development of Dense Linear Algebra
- Algorithms on Massively Parallel Architectures with DPLASMA // 2011 IEEE International Symposium on Parallel and Distributed ProcessingWorkshops and Phd Forum. 2011. P. 1432–1441. DOI: 10.1109/IPDPS.2011.299.
- Bosilca G., Bouteiller A., Danalis A., et al. PaRSEC: Exploiting Heterogeneity to Enhance Scalability // Computing in Science & Engineering. 2013. Vol. 15, no. 6. P. 36–45. DOI: 10.1109/MCSE.2013.98.
- Legalov A.I., Vasilyev V.S., Matkovskii I.V., et al. A Toolkit for the Development of Data-Driven Functional Parallel Programmes // Parallel Computational Technologies (PCT’2018). Vol. 910. Springer, 2018. P. 16–30. Communications in Computer and Information Science. DOI: 10.1007/978-3-319-99673-8_2.
- Moore G. Cramming More Components onto Integrated Circuits // Electronics Magazine. 1965. Vol. 38, no. 8. P. 114–117.
- Moskovsky A., Roganov V., Abramov S. Parallelism Granules Aggregation with the TSystem // Parallel Computing Technologies (PaCT 2007). Vol. 4671. Springer, 2007. P. 293–302. Lecture Notes in Computer Science. DOI: 10.1007/978-3-540-73940-1_30.
