Geodesic
Circular shift of loop body --- programme transformation, promoting parallelism
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 120-132

Voir la notice de l'article provenant de la source Math-Net.Ru

The article deals with the programme transformation executing the circular shift of loop body statements. It can be used for vectorizing or parallelizing. This becomes possible due to the fact that when the order of loop body statements is changed, some of the bottom-up arcs become top-down arcs. Besides, sometimes loop carried dependence arcs are substituted by loop independent ones. It should be pointed out that in executing the circular shift the number of loop iterations is reduced by one. The transformation can be used both independently and in conjunction with other transformations promoting parallelism. These could be "forward substitution", "scalar expansion", "privatization", "array expansion", etc. The transformation under consideration in this article can be used both in hand parallelization and added to a paralleling (optimizing) compiler. Moreover, the application of the transformation results in the equivalent code only for the loops where loop unrolling is the equivalent transformation. Thus, they can contain nested loops, if statements and other programming language statements.
Keywords: parallel computations; programme transformations; dependence graph; scalar expansion; loop distribution. 
@article{VYURU_2017_10_3_a9,
     author = {O. B. Shteinberg},
     title = {Circular shift of loop body --- programme transformation, promoting parallelism},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {120--132},
     publisher = {mathdoc},
     volume = {10},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a9/}
}
TY  - JOUR
AU  - O. B. Shteinberg
TI  - Circular shift of loop body --- programme transformation, promoting parallelism
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2017
SP  - 120
EP  - 132
VL  - 10
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a9/
LA  - en
ID  - VYURU_2017_10_3_a9
ER  - 
%0 Journal Article
%A O. B. Shteinberg
%T Circular shift of loop body --- programme transformation, promoting parallelism
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2017
%P 120-132
%V 10
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a9/
%G en
%F VYURU_2017_10_3_a9
O. B. Shteinberg. Circular shift of loop body --- programme transformation, promoting parallelism. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 120-132. http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a9/