Hardware and software for distributed and supercomputer systems
Research Article
Justification of methods for accelerating iterative loops nests
Elena Anatol'evna Metelitsa
| Southern Federal University, Rostov-on-Don, Russia | |
|
metelica@sfedu.ru |
Abstract. The acceleration of iterative algorithms, found in solving problems of mathematical physics, mathematical modeling, and image processing, is considered. In the software implementation of these algorithms, there are nested loops (sections of the program that consist of nested loops). These loop nests can be accelerated by combination of optimizing transformations, including tiling, hyperplane method, and parallelization on shared memory. The equivalence of this combination of program transformations is substantiated.
A method for changing the order of tile traversal is proposed and justified. The method provides acceleration by increasing data readings from registers instead of slower memory. Considering this method, a formula for calculating optimal tile sizes is obtained.
The combination of transformations presented in this article results in an acceleration that is 1.4 times greater than the well-known optimization algorithm implemented in PLUTO. In some cases using an 8-core processor, numerical experiments show a significant increase in speed compared to the original sequential algorithms. The findings of this article can be applied to manual and automatic program optimization. (In Russian).
Keywords: tiling, wavefront, parallelization, shared memory, iterative stencil loops
MSC-2020
68W10; 68N20
Acknowledgments: The author is grateful to Dr. B.Ya. Steinberg for leadership of the work and Ar.V. Klimov for his attention and interest in the work.
For citation: Elena A. Metelitsa. Justification of methods for accelerating iterative loops nests. Program Systems: Theory and Applications, 2024, 15:1, pp. 63–94. (In Russ.). https://psta.psiras.ru/2024/1_63-94.
Full text of article (PDF): https://psta.psiras.ru/read/psta2024_1_63-94.pdf.
The article was submitted 21.01.2024; approved after reviewing 13.02.2024; accepted for publication 15.02.2023; published online 26.03.2024.
