Известия высших учебных заведений. Поволжский регион:Технические науки (Aug 2023)
Building execution plans for programs with maximum code density on a fixed set of parallel computers
Abstract
Background. The construction of rational plans (schedules) for the execution of parallel programs is (due to the multivariance of solutions) a difficult task. In this paper, we consider the construction of such plans from the point of view of obtaining the highest code density (in fact, the mode of maximum use of computing resources - the employment of computing blocks of a parallel computer). The relevance of the work is related to the problems of import independence in the field of improving instrumental software for domestic processors with explicit parallelism in data processing. Materials and methods. In the presented work, the main technique for constructing execution plans for parallel programs is the construction, analysis and purposeful transformation of the tiered-parallel form of information graphs of algorithms. The transformation of a tiered-parallel form is carried out by transferring operators from a tier to a tier of a tiered-parallel form, while maintaining the invariability of information links in the algorithm (equivalent transformations), for the implementation of this technique, targeted author’s software has been developed. As a transformation tool, the method of creating scripts for purposeful transformation of a tieredparallel form in a scripting programming language is used. Scenarios are created on the basis of a heuristic approach and use a set of API functions of the developed software system, which allow to comprehensively study the parameters of the information graphs of algorithms and its tiered-parallel form-representations for the subsequent construction of rational execution plans for parallel programs on a given set of parallel computers. Results. The results of computational experiments have revealed the features of the internal properties of algorithms that affect the efficiency of transformations of a tiered-parallel form. Comparative indicators of code density are proposed and obtained when using various scenarios for converting a tiered-parallel form. An iterative approach to improving heuristic methods promises an opportunity to get closer to optimal schemes for solving the target problem. The scope of the research results is the development of tool software for parallel data processing processors (for example, microprocessors of the ELBRUS series developed in Russia within the framework of import independence for use in the state and defense sectors and for the implementation of supercomputing). Conclusions. In general, the developed software package confirmed its effectiveness in studying the parameters of hidden parallelism in arbitrary algorithms and its rational use in calculations. The approach of using a scripting language to develop heuristic methods (scenarios) for the purposeful transformation of information graphs of algorithms forms has shown greater flexibility and transparency in research. Concrete results are obtained for constructing execution plans for parallel programs with maximum code density. the possibility of studying the practical feasibility of using the potential of internal (hidden) parallelism limit by improving heuristic methods for constructing plans for the execution of parallel programs, taking into account the set goals and limitations, is a noteworthy aspect.
Keywords
