Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы

Валентина Николаевна Алеева, Полина Сергеевна Зотова, Дмитрий Сергеевич Склезнев

Аннотация


Программная Q-система предназначена для исследования ресурса параллелизма численных алгоритмов. С помощью Q-системы можно вычислить ресурс параллелизма любого численного алгоритма, а также найти алгоритм с лучшим ресурсом параллелизма из множества алгоритмов, решающих алгоритмическую проблему. Теоретической основой Q-системы является концепция Q-детерминанта, где Q — множество операций, используемых алгоритмом. Любой численный алгоритм имеет Q-детерминант и может быть представлен в форме Q-детерминанта. Такое представление является универсальным описанием численных алгоритмов. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант делает алгоритм понятным с точки зрения структуры и реализации. Q-система может быть использована для повышения эффективности параллельных вычислений. В статье описаны новые возможности Q-системы. Новая функциональность позволяет использовать классификацию алгоритмов при их исследовании. Также новая функциональность дает возможность вычислять функции для аппроксимации высоты и ширины алгоритмов более точно и создавать их графическое представление. В результате интерфейс пользователя Q-системы стал более удобным, появилось больше возможностей для исследования ресурса параллелизма алгоритмов.

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


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

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

PDF

Литература


Aleeva V.N. Analysis of Parallel Numerical Algorithms. Preprint no. 590. Novosibirsk, Computing Center of the Siberian Branch of the Academy of Sciences of the USSR, 1985. 23 p. (in Russian)

Voevodin V.V., Voevodin Vl.V. Parallel Computing. St.Petersburg, BHV-Petersburg, 2002. 608 p. (in Russian)

Ershov Yu.L., Palyutin E.A. Mathematical Logic. Moscow, Mir, 1984. 303 p.

Open Encyclopedia of Parallel Algorithmic Features. URL: https://algowiki-project.org/en (accessed: 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/jsfi180101.

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 TSystem. Parallel Computing Technologies (PaCT 2007). Lecture Notes in Computer Science. 2007. Vol. 4671. P. 293–302. DOI: 10.1007/978-3-540-73940-1_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 Vl.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.




DOI: http://dx.doi.org/10.14529/cmse210205