Geodesic
Loop-invariant optimization in the Pifagor language
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 4, pp. 347-357 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper considers methods of program transformation equivalent to optimizing the cycle invariant, applied to the functional data-flow model implemented in the Pifagor programming language. Optimization of the cycle invariant in imperative programming languages is reduced to a displacement from the cycle of computations that do not depend on variables that are changes in the loop. A feature of the functional data flow parallel programming language Pifagor is the absence of explicitly specified cyclic computations (the loop operator). However, recurring calculations in this language can be specified recursively or by applying specific language constructs (parallel lists). Both mechanisms provide the possibility of parallel execution. In the case of optimizing a recursive function, repeated calculations are carried out into an auxiliary function, the main function performing only the calculation of the invariant. When optimizing the invariant in computations over parallel lists, the calculation of the invariant moves from the function that executes over the list items to the function containing the call. The paper provides a definition of ”invariant” applied to the Pifagor language, algorithms for its optimization, and examples of program source codes, their graph representations (the program dependence graph) before and after optimization. The algorithm shown for computations over parallel lists is applicable only to the Pifagor language, because it rests upon specific data structures and the computational model of this language. However, the algorithm for transforming recursive functions may be applied to other programming languages.
Keywords: data driven functional parallel programming, Pifagor programming language, code optimization, loop optimization, invariant optimization, program dependence graph. 
@article{MAIS_2018_25_4_a0,
     author = {V. S. Vasilyev and A. I. Legalov},
     title = {Loop-invariant optimization in the {Pifagor} language},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {347--357},
     year = {2018},
     volume = {25},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a0/}
}
TY  - JOUR
AU  - V. S. Vasilyev
AU  - A. I. Legalov
TI  - Loop-invariant optimization in the Pifagor language
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 347
EP  - 357
VL  - 25
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a0/
LA  - ru
ID  - MAIS_2018_25_4_a0
ER  - 
%0 Journal Article
%A V. S. Vasilyev
%A A. I. Legalov
%T Loop-invariant optimization in the Pifagor language
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 347-357
%V 25
%N 4
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a0/
%G ru
%F MAIS_2018_25_4_a0
V. S. Vasilyev; A. I. Legalov. Loop-invariant optimization in the Pifagor language. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 4, pp. 347-357. http://geodesic.mathdoc.fr/item/MAIS_2018_25_4_a0/

[1] Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison Wesley, 2006, 1000 pp.

[2] Dortman P. A., “Program optimizacion in SFP”, Software tools and mathematical foundations of informatics, Novosibirsk, 2004, 43–49 (in Russian)

[3] Legalov A. I., Matkovsky I. V., Kropacheva M. S., Udalova Y. V., Vasiliev V. M., “Tekhnologicheskie aspekty sozdaniya, preobrazovaniya i vypolneniya funkcionalno-potokovyh parallelnyh programm”, Nauchnyy servis v seti Internet: vse grani parallelizma, Trudy Mezhdunarodnoy superkompyuternoy konferentsii, Izd-vo MGU, M., 2013, 443–447 (in Russian)

[4] Legalov A. I., Vasilyev V. S., Matkovskii I. V., Ushakova M. S., “Support tools for creation and transformation of functional-dataflow parallel programs”, Proceedings of ISP RAS, 29:5 (2017), 165–184 (in Russian)

[5] Legalov A. I., “Functional language for creating of architectural independent parallel programs”, Computational Technologies, 10:1 (2005), 71–89 (in Russian) | Zbl