Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы
Автор: Алеева Валентина Николаевна, Зотова Полина Сергеевна, Склезнев Дмитрий Сергеевич
Статья в выпуске: 2 т.10, 2021 года.
Бесплатный доступ
Программная Q-система предназначена для исследования ресурса параллелизма численных алгоритмов. С помощью Q-системы можно вычислить ресурс параллелизма любого численного алгоритма, а также найти алгоритм с лучшим ресурсом параллелизма из множества алгоритмов, решающих алгоритмическую проблему. Теоретической основой Q-системы является концепция Q-детерминанта, где Q - множество операций, используемых алгоритмом. Любой численный алгоритм имеет Q-детерминант и может быть представлен в форме Q-детерминанта. Такое представление является универсальным описанием численных алгоритмов. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант делает алгоритм понятным с точки зрения структуры и реализации. Q-система может быть использована для повышения эффективности параллельных вычислений. В статье описаны новые возможности Q-системы. Новая функциональность позволяет использовать классификацию алгоритмов при их исследовании. Также новая функциональность дает возможность вычислять функции для аппроксимации высоты и ширины алгоритмов более точно и создавать их графическое представление. В результате интерфейс пользователя Q-системы стал более удобным, появилось больше возможностей для исследования ресурса параллелизма алгоритмов.
Q-детерминант алгоритма, представление алгоритма в форме q-детерминанта, q-эффективная реализация алгоритма, высота алгоритма, ширина алгоритма, ресурс параллелизма алгоритма, программная q-система
Короткий адрес: https://sciup.org/147234296
IDR: 147234296 | DOI: 10.14529/cmse210205
Список литературы Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы
- Алеева В.Н. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
- Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987. 336 с.
- Открытая энциклопедия свойств алгоритмов. URL: https://algowiki-project.org/ru (дата обращения: 06.03.2021).
- Akhmed-Zaki D., Lebedev D., Malyshkin V. et al. Automated Construction of High Performance Distributed Programs in LuNA System // Parallel Computing Technologies (PaCT 2019). Lecture Notes in Computer Science. 2019. Vol. 11657. P. 3-9. 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. Communications in Computer and Information Science. 2019. Vol. 965. P. 565-577. 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.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. Communications in Computer and Information Science. 2019. Vol. 1129. P. 641-652. 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). Lecture Notes in Computer Science. 2015. Vol. 9251. P. 3-9. 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/jsfil80101.
- 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). Communications in Computer and Information Science. 2018. Vol. 910. P. 16-30. DOI: 10.1007/978-3-319-99673-8_2.
- Moskovsky A., Roganov V., Abramov S. Parallelism Granules Aggregation with the T-System // Parallel Computing Technologies (PaCT 2007). Lecture Notes in Computer Science. 2007. Vol. 4671. P. 293-302. DOI: 10.1007/978-3-540-73940-l_30.
- 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). 2017. P. 304-309. DOI: 10.1109/I-SMAC.2017.8058360.
- Voevodin V.V., Voevodin VI.V. The V-Ray technology of optimizing programs to parallel computers // Numerical Analysis and Its Applications (WNAA 1996). Lecture Notes in Computer Science. 1997. Vol. 1196. P. 546-556. DOI: 10.1007/3-540-62598-4_136.
- Wang Q., Liu J., Tang X. et al. Accelerating embarrassingly parallel algorithm on Intel MIC // IEEE International Conference on Progress in Informatics and Computing. 2014. P. 213-218. DOI: 10.1109/PIC.2014.6972327.
