Geodesic
Parallelization of recurrent loops due to the preliminary computation of superpositions
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 13 (2020) no. 3, pp. 59-67 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 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. In modern processors, the execution time of arithmetic operations is an order of magnitude faster than reading the arguments of these operations from RAM. This article provides estimates of the complexity of accessing memory for the described algorithm. The parallel algorithm presented in the article is more efficient in accessing memory than the algorithm described by the author earlier.
Keywords: recurrent loops, numerical methods, parallel computation, recurrent sequences.
Mots-clés : program transformations 
@article{VYURU_2020_13_3_a4,
     author = {O. B. Shteinberg},
     title = {Parallelization of recurrent loops due to the preliminary computation of superpositions},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {59--67},
     year = {2020},
     volume = {13},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2020_13_3_a4/}
}
TY  - JOUR
AU  - O. B. Shteinberg
TI  - Parallelization of recurrent loops due to the preliminary computation of superpositions
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2020
SP  - 59
EP  - 67
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURU_2020_13_3_a4/
LA  - ru
ID  - VYURU_2020_13_3_a4
ER  - 
%0 Journal Article
%A O. B. Shteinberg
%T Parallelization of recurrent loops due to the preliminary computation of superpositions
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2020
%P 59-67
%V 13
%N 3
%U http://geodesic.mathdoc.fr/item/VYURU_2020_13_3_a4/
%G ru
%F VYURU_2020_13_3_a4
O. B. Shteinberg. Parallelization of recurrent loops due to the preliminary computation of superpositions. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 13 (2020) no. 3, pp. 59-67. http://geodesic.mathdoc.fr/item/VYURU_2020_13_3_a4/

[1] R. Allen, K. Kennedy, Optimizing Compilers for Modern Architectures, Morgan Kaufmann Publishers, San Francisco–San Diego–New York–Boston–London–Sidney–Tokyo, 2002

[2] M. Wolfe, High Performance Compilers for Parallel Computing, Addison-Wesley Publishing Company, Redwood City, 1996 | Zbl

[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, 10:3 (2017), 120–132 | DOI

[4] Steinberg B. Y., “Parallelizing Recurrence Loops with Conditional Statements”, Automation and Telemechanics, 1995, no. 6, 176–184 (in Russian) | Zbl

[5] Steinberg O. B., “Parallelizing Recurrent Program Loops with Irregular Superposition Computation”, University News. North-Caucasian Region. Natural Sciences Series, 2009, no. 2, 18–21 (in Russian) | Zbl

[6] Steinberg O. B., Sukhoverkhov S. E., “Recurrent Program Loops with Stability Check”, Information Technologies, 2010, no. 1, 40–45 (in Russian)

[7] Steinberg O. B., Parallelizing Loops Allowing Recurrent Dependences, PhD Thesis, Institute for System Programming of the Russian Academy of Sciences, M., 2014 (in Russian)

[8] Steinberg B. J., Parallelizing Recurrent Program Loops with Irregular Superposition Computation, Rostov University Publishing House, Rostov-on-Don, 2004 (in Russian)

[9] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: a Foundation for Computer Science, Addison-Welsey, New York, 1994 | MR | Zbl

[10] Samarskiy A. A., Introduction to Numerical Methods, Nauka, M., 1997 (in Russian)

[11] S.L. Graham, M. Snir, C.A. Patterson, Getting Up to Speed: the Future of Supercomputing, National Academies Press, Washington, 2005

[12] Optimizing Parallelizing System (accessed 1.07.2020)

[13] Optimizing Compiler Pluto (accessed 1.07.2020)

[14] ROSE Compiler (accessed 1.07.2020)