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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 {\textemdash} 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},
     year = {2017},
     volume = {10},
     number = {3},
     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
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
%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/

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

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

[3] Steinberg B. J., Parallelizing Recurrent Program Cycles with Irregular Superposition Computation, Rostov University Publishing House, Rostov-on-Don, 2004, 192 pp.

[4] Duo Liu, Zili Shao, Meng Wang, Minyi Guo, Jingling Xue, “Optimal Loop Parallelization for Maximizing Iteration-Level Parallelism”, Proceedings of International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES 09, ACM, N.Y., 2009, 67–76 | DOI

[5] Steinberg O. B., “Parallelizing Recurrent Program Cycles with Irregular Superposition Computation”, Izvestiya vuzov. Severo-Kavkazskii region. Natural Science, 2009, no. 2, 18–21 (in Russian)

[6] Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue, “Optimally Maximizing Iteration-Level Loop Parallelism”, IEEE Transactions on Parallel and Distributed Systems, 23:3 (2012), 564–572 | DOI

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

[8] Muchnick S. S., Advanced Compiler Design and Implementation, Morgan Kauffman, San Francisco, 1997, 856 pp.

[9] Aho A. V., Lam M. S., Sethi R., Ullman J. D., Compilers: Principles, Techniques, and Tools, Pearson Education, London, 2007, 1014 pp.

[10] Evstigneev V. A., Sprogis S. V., “Vectorizing Programmes”, Vectorizing Programmes: Theory, Methods, Implementation, Mir, M., 1991, 246–267 (in Russian)

[11] Shulzhenko A. M., Researching Information Dependences of Programs for Analyzing Transformations Used for Parallelizing, The Dissertation for Scientific Degree of the Candidate of Technology, Rostov-on-Don, 2006, 200 pp.

[12] Steinberg O. B., Parallelizing Loops Allowing Recurrent Dependences, The Dissertation for Scientific Degree of the Candidate of Physics and Mathematical Science, Institute for System Programming of the Russian Academy of Sciences, M., 2014 | Zbl

[13] Steinberg O. B., “Minimizing the Number of Temporary Arrays in Loop Distribution Problem”, Izvestiya vuzov. Severo-Kavkazskii region. Natural Science, 2011, no. 5, 31–35 (in Russian)

[14] Feautrier P., “Array Expansion”, Proceedings of the 2nd International Conference on Supercomputing, ACM, N.Y., 1988, 429–441 | DOI | MR