Computational complexity when constructing rational plans for program execution in a given field of parallel computers

Objectives. The construction of rational plans (schedules) for parallel program execution (PPE) represents a challenging problem due to its ambiguity. The aim of this work is to create methods for developing such plans and specialized software for implementing these methods, which are based on the internal properties of algorithms, primarily on the property of internal (hidden) parallelism.
Methods. The main method for developing PPE plans was the construction, analysis, and purposeful transformation of the stacked-parallel form (SPF) of information graphs of algorithms (IGA). The SPF was transformed by transferring operators from tier to tier of the SPF (this event was taken as an elementary step in determining the computational complexity of scenario execution). As a transformation tool, a method for developing transformation scenarios in the scripting programming language Lua was used. Scenarios were created by a heuristic approach using a set of Application Programming Interface (API) functions of the developed software system. These functions formed the basis for a comprehensive study of the parameters of the IGA and its SPF representation for the subsequent construction of a PPE plan applying to a given field of parallel computers.
Results. Features of the internal properties of the algorithms that affect the efficiency of SPF transformations were identified during the course of computational experiments. Comparative indices of the computational complexity of obtaining PPE plans and other parameters (including code density, etc.) were obtained for various SPF transformation scenarios. An iterative approach to improving heuristic methods favors developing optimal schemes for solving the objective problem.
Conclusions. The developed software system confirmed its efficiency for studying the parameters of hidden parallelism in arbitrary algorithms and rational use in data processing. The approach of using a scripting language to develop heuristic methods (scenarios) for the purposeful transformation of IGA forms showed great flexibility and transparency for the researcher. The target consumers of the developed methods for generating schedules for parallel execution of programs are, first of all, developers of translators and virtual machines, and researchers of the properties of algorithms (for identifying and exploiting the potential of their hidden parallelism). The developed software and methods have been successfully used for a number of years for increasing student competence in data processing parallelization at Russian universities.

1. Voevodin V.V., Voevodin Vl.V. Parallel’nye vychisleniya (Parallel computing). St. Petersburg: BHV-Petersburg; 2004. 608 p. (in Russ.).

2. Bakanov V. Research and selection of rational methods for obtaining framework of schedules for the parallel programs execution. In: Silhavy R., Silhavy P., Prokopova Z. (Eds.). Data Science and Intelligent Systems. CoMeSySo 2021. Lecture Notes in Networks and Systems. V. 231. Springer, Cham. https://doi.org/10.1007/978-3-030-90321-3_22

3. Fedotov I.E. Parallel’noe programmirovanie. Modeli i priemy (Parallel programming. Models and techniques). Moscow: SOLON-Press; 2018. 390 p. (in Russ.). ISBN 978-5-91359-222-4

4. Bakanov V.M. Dynamics control computing in the processors data flow architecture for different types of algorithms. Programmnaya inzheneriya = Software Engineering. 2015;9:20–24 (in Russ.).

5. Bakanov V.M. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Comput. Sci. 2018;8(1): 228–234. https://doi.org/10.1515/comp-2018-0019

6. Padua D. (Ed.). Encyclopedia of parallel computing. NY: Springer; 2012. 2195 p. https://doi.org/10.1007/978-0-387-09766-4

7. Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor. In: Proc. Second Annual Symp. Computer Architecture (ISCA ́75). 1975. P. 126–132. https://doi.org/10.1145/642089.642111

8. Kukunas J. Power and performance: Software analysis and optimization. Morgan Kaufman, Elsevier Inc.; 2015. 300 p.

9. McNairy C., Soltis D. Itanium 2 processor microarchitecture. IEEE Micro. 2003;23(2):44–55. https://doi.org/10.1109/MM.2003.1196114

10. Tanenbaum E., Ostin T. Arkhitektura komp’yutera (Computer architecture). Transl. from Eng. St. Petersburg: Piter; 2019. 816 p. (in Russ.). ISBN 978-5-4461-1103-9

11. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. 3rd ed. London: MIT Press; 2009. 1292 p.

12. McConnell J.J. Analysis of algorithms: An active learning approach. Jones & Bartlett Publishers; 2008. 451 p.

13. Garey M., Johnson D. Vychislitel’nye mashiny i trudnoreshaemye zadachi ( Computing machines and difficult tasks). Transl. from Eng. Moscow: Kniga po trebovaniyu; 2012. 420 р. (in Russ.). ISBN 978-5-458- 26100-5 [Garey M., Johnson D. Computers and intractability. San Francisco; 1979. 338 p.]

14. Ierusalimschy R. Programming in Lua. 3rd ed. PUC-Rio, Brasil, Rio de Janeiro; 2013. 348 p.

15. Fisher J.A. Very long instruction word architectures and the ELI-512. In: Proceedings of the 10th Annual International Symposium on Computer Architecture (ISCA ’83). 1983. P. 140–150. https://doi.org/10.1145/800046.801649

16. Babb R.I. Parallel processing with large-grain data flow techniques. Computer. 1984;17(7):55–61. https://doi.org/10.1109/MC.1984.1659186