Advancement of Research for the Parallelism Resource of Numerical Algorithms with the Help of Software Q-system
DOI:
https://doi.org/10.14529/cmse210205Keywords:
Q-determinant of algorithm, representation of algorithm in form of Q-determinant, Q-effective implementation of algorithm, algorithm height, algorithm width, parallelism resource of algorithm, software Q-systemAbstract
The software Q-system is designed to study the parallelism resource of numerical algorithms. By use of Q-system, we can calculate the parallelism resource of any numerical algorithm. Also, for the set of algorithms solving a given algorithmic problem, we can find an algorithm with the best parallelism resource. The theoretical basis of the Q-system is the concept of Q-determinant where Q is the set of operations used by the algorithm. Any numerical algorithm has a Q-determinant and can be represented in the form of a Q-determinant. Such a representation is a universal description of numerical algorithms. The Q-determinant consists of Q-terms. Their number is equal to the number of output data items. Each Q-term describes all possible ways to calculate one of the output data items based on the input data. Q-determinant makes the algorithm transparent in terms of structure and implementation. The Q-system can be used for the improvement of parallel computing efficiency. In this paper we describe new features of the Q-system. With the new functionality, we can use the classification of algorithms when studying them. Also with the new functionality, we can calculate the functions for approximating the height and width of the algorithms more precisely and create a graphical representation of them. As a result, we have a more convenient user interface of the Q-system and more opportunities to study the parallelism resource of algorithms.
References
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.
