Preview

Modeling and Analysis of Information Systems

Advanced search

Loop-invariant Optimization in the Pifagor Language

https://doi.org/10.18255/1818-1015-2018-4-347-357

Abstract

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.

About the Authors

Vladimir S. Vasilev
Siberian Federal University, Institute of Space and Information Technology
Russian Federation
graduate student


Alexander I. Legalov
Siberian Federal University, Institute of Space and Information Technology
Russian Federation
doctor of science


References

1. In English: 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).


Review

For citations:


Vasilev V.S., Legalov A.I. Loop-invariant Optimization in the Pifagor Language. Modeling and Analysis of Information Systems. 2018;25(4):347-357. (In Russ.) https://doi.org/10.18255/1818-1015-2018-4-347-357

Views: 939


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)