Formal and adaptive methods of constructing high-performance parallel programs
P.I. Andon, А.Yu. Doroshenko, V. G. Akulovskiy, P.А. Ivanenko, Olena Yatsenko · 2023
In the monograph, the authors summarize their and foreign recent experience in the application of formal and adaptive methods for automating the construction of high-performance parallel programs. The basics of algebraic programming, the algebra of algorithms, and other formal models of parallel programs, important for the automated development of software for multiprocessor computing systems, are outlined. Algebras of algorithms intended for the formalized description of structural and non-structural schemes presented in analytical, linguistic, and graphical forms are considered. Algebra of algorithms with data is designed, focused on a consistent description of control flows and processed data in designed algorithms and programs. Algebra-dynamic models of parallel computing, models of distributed asynchronous memory, and methods of efficient organization of mixed multi-level memory for parallel processing are considered. An overview of software tools for rewriting rules is given and the main directions of application of instrumental tools for rewriting terms are characterized. An important place in the monograph is the use of coordination tools and models to achieve high-performance indicators of parallel programs, in particular, the facilities for adaptation and auto-tuning of programs to a target parallel computing platform. Software tools to support the developed models and methods in the development of high-performance parallel programs are considered, and the results of using these tools both in solving fundamental problems of computer science and in the technology of programming applied problems are demonstrated. In particular, examples of the use of the auto-tuning system for sorting problems, Brownian motion modeling, and meteorological forecasting are provided. The methods and tools for the optimization of block-recursive algorithms using the actor model are proposed. The analysis of the scaling of the legacy code for cloud platforms using the rewriting rules technique was performed. A system architecture using Web services choreography is developed, which allows unlimited system scaling and reduces messaging overhead. As an experiment, an application program on quantum chemistry, designed for calculating the orbitals of atoms, was used. The book is intended for scientists and specialists engaged in the development of high-performance parallel software in various subject areas, as well as for teachers, graduate students, and students of relevant specialties.