Computer-aided Design and Execution of Effective Programs for Numerical Algorithms
DOI:
https://doi.org/10.14529/cmse230303Keywords:
Q-determinant of algorithm, representation of algorithm in form of Q-determinant, Q-effective implementation of algorithm, parallelism resource of algorithm, software Q-system, parallel computing system, parallel program, Q-effective programAbstract
Designing effective parallel programs for multiprocessor architectures is difficult because there are no clear formal rules to follow. The concept of the Q-determinant can be applied to solve this problem when implementing numerical algorithms. This theory allows for automated analysis of the algorithm parallelism resource, automated comparison of the parallelism resources of algorithms solving the same algorithmic problem. In addition, it makes it possible to design effective programs for the implementation of numerical algorithms using a specially developed design method, improve the efficiency of the implementation of numerical methods and algorithmic problems. The results obtained on the basis of the Q-determinant concept are one of the options for solving the problem of effective implementation of numerical algorithms, methods and algorithmic problems on parallel computing systems. However, the fundamental problem of computer-aided design and execution for any numerical algorithm of a program that implements the algorithm effectively remains unresolved. The paper describes the development of a software system for designing and executing Q-effective programs that is unified for numerical algorithms. A Q-effective program is an effective program designed using the concept of a Q-determinant. The system is intended for use on parallel computing systems with shared memory. It consists of a compiler and a virtual machine. The compiler converts the representation of the algorithm in the form of a Q-determinant into an executable program that uses the algorithm’s parallelism resource completely. The virtual machine executes the program generated by the compiler. The paper also provides an experimental study of the created software system using the SUSU Tornado supercomputer.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)
Aleeva V.N., Zotova P.S., Skleznev D.S. Advancement of Research for the Parallelism Resource of Numerical Algorithms with the Help of Software Q-system. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 2. P. 66–81. (in Russian) DOI: 10.14529/cmse210205.
Aleeva V.N., Shatov M.B. Application of the Q-determinant Concept for Efficient Implementation of Numerical Algorithms by the Example of the Conjugate Gradient Method for Solving Systems of Linear Equations. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 3. P. 56–71. (in Russian) DOI: 10.14529/cmse210304.
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.
Software system compiler repository. URL: https://github.com/yuferovalex/qc (accessed: 29.06.2023).
Software system virtual machine repository. URL: https://github.com/yuferovalex/qvm (accessed: 29.06.2023).
Nedozhogin N.S., Kopysov S.P., Novikov A.K. Parallel Solving of Linear Equations Systems on Hybrid Architecture CPU+GPU. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2020. Vol. 9, no. 2. P. 40–54. (in Russian) DOI: 10.14529/cmse200203.
Open Encyclopedia of Parallel Algorithmic Features. URL: https://algowiki-project.org/en (accessed: 30.05.2023).
“Tornado SUSU” Supercomputer. URL: http://supercomputer.susu.ru/en/computers/tornado/ (accessed: 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 T-System. 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.
