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 i...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
MIREA - Russian Technological University
2022-12-01
|
| Series: | Российский технологический журнал |
| Subjects: | |
| Online Access: | https://www.rtj-mirea.ru/jour/article/view/578 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543427537928192 |
|---|---|
| author | V. M. Bakanov |
| author_facet | V. M. Bakanov |
| author_sort | V. M. Bakanov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-6fa886820f0f47f58026c3807103ba4d |
| institution | Kabale University |
| issn | 2500-316X |
| language | Russian |
| publishDate | 2022-12-01 |
| publisher | MIREA - Russian Technological University |
| record_format | Article |
| series | Российский технологический журнал |
| spelling | doaj-art-6fa886820f0f47f58026c3807103ba4d2025-02-03T11:45:50ZrusMIREA - Russian Technological UniversityРоссийский технологический журнал2500-316X2022-12-0110671910.32362/2500-316X-2022-10-6-7-19346Computational complexity when constructing rational plans for program execution in a given field of parallel computersV. M. Bakanov0MIREA – Russian Technological UniversityObjectives. 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.https://www.rtj-mirea.ru/jour/article/view/578algorithm graphfine information structure of programstacked-parallel form of graphrational execution parameters of parallel programexecution plan of parallel program |
| spellingShingle | V. M. Bakanov Computational complexity when constructing rational plans for program execution in a given field of parallel computers Российский технологический журнал algorithm graph fine information structure of program stacked-parallel form of graph rational execution parameters of parallel program execution plan of parallel program |
| title | Computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| title_full | Computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| title_fullStr | Computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| title_full_unstemmed | Computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| title_short | Computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| title_sort | computational complexity when constructing rational plans for program execution in a given field of parallel computers |
| topic | algorithm graph fine information structure of program stacked-parallel form of graph rational execution parameters of parallel program execution plan of parallel program |
| url | https://www.rtj-mirea.ru/jour/article/view/578 |
| work_keys_str_mv | AT vmbakanov computationalcomplexitywhenconstructingrationalplansforprogramexecutioninagivenfieldofparallelcomputers |