Parallelization of Recurrent Loops Due to the Preliminary Computation of Superpositions

As a rule, sections of code that take a lot of time to compute are loops. Therefore, it is precisely on them that special efforts are directed when accelerating programs, in particular, through parallelization.

Keywords

The article describes the parallelization algorithm for loops calculating the elements of a recursively given sequence. The recurrent loops considered in the article cannot be directly parallelized. With the help of auxiliary transformations, they can sometimes be reduced to loops that allow parallel execution. Earlier, the author of the article published another algorithm for parallelizing loops that calculate the elements of a recursively given sequence.

References

1. Allen R., Kennedy K. Optimizing Compilers for Modern Architectures. San Francisco, San Diego, New York, Boston, London, Sidney, Tokyo, Morgan Kaufmann Publishers, 2002.
2. Wolfe M. High Performance Compilers for Parallel Computing. Redwood City, Addison-Wesley Publishing Company, 1996.
3. Steinberg O.B. Circular Shift of Loop Body-Programme Transformation, Promoting Parallelism. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2017, vol. 10, no. 3, pp. 120-132. DOI: 10.14529/mmp170310
4. Steinberg B.Y. [Parallelizing Recurrence Loops with Conditional Statements]. Automation and Telemechanics, 1995, no. 6, pp. 176-184. (in Russian)
5. Steinberg O.B. [Parallelizing Recurrent Program Loops with Irregular Superposition Computation]. University News. North-Caucasian Region. Natural Sciences Series, 2009, no. 2, pp. 18-21. (in Russian)
6. Steinberg O.B., Sukhoverkhov S.E. [Recurrent Program Loops with Stability Check]. Information Technologies, 2010, no. 1, pp. 40-45. (in Russian)
7. Steinberg O.B. Parallelizing Loops Allowing Recurrent Dependences. PhD Thesis. Moscow, Institute for System Programming of the Russian Academy of Sciences, 2014. (in Russian)
8. Steinberg B.J. Matematicheskie metody rasparallelivaniya rekurrentnykh programnykh tsiklov na superkompyutery s parallel'noy pamyatyu [Parallelizing Recurrent Program Loops with Irregular Superposition Computation]. Rostov-on-Don, Rostov University Publishing House, 2004. (in Russian)
9. Graham R.L., Knuth D.E., Patashnik O. Concrete Mathematics: a Foundation for Computer Science. N.Y., Addison-Welsey, 1994.
10. Samarskiy A.A. Vvedenie v chislennye metody [Introduction to Numerical Methods]. Moscow, Nauka, 1997. (in Russian)
11. Graham S.L., Snir M., Patterson C.A. Getting up to Speed: the Future of Supercomputing. Washington, National Academies Press, 2005.
12. Optimizing Parallelizing System. Available at: http://ops.rsu.ru (accessed 1.07.2020).
13. Optimizing Compiler Pluto. Available at: http://pluto-compiler.sourcefofge.net (accessed 1.07.2020).
14. ROSE Compiler. Available at: http://rosecompiler.org/ (accessed 1.07.2020).