Abstract
To improve the performances of parallelizing compilers, one must detect recurrences in scientific programs and subject them to special parallelization methods. We present a method for detecting recurrences which is based on the analysis of Systems of Recurrence Equations. This method identifies recurrences on arrays, recurrences of arbitrary order and multi-equations recurrences. We explain how to associate a SRE to a restricted class of imperative programs. We present a normalization of such SRE that allows the detection of recurrences by simple inspection of equations. When detected, a recurrence may be replaced by a symbolic expression of its solution. To iterate the process can lead to the identification of multi-dimensional recurrences.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Berge. Graphes. Gauthier-Villars, 1987.
A.J. Bernstein. Analysis of programs for parallel processing. IEEE Trans. on El. Computers, EC-15, 1966.
G.E. Blelloch. Scans as primitive parallel operations. IEEE Trans. on Computers, 38(11):1526–1539, 1989.
Paul Feautrier. Dataflow analysis of scalar and array references. Int. Journal of Parallel Programming, 20(1):23–53, February 1991.
Pierre Jouvelot and Babak Dehbonei. A unified semantic approach for the vectorization and parallelization of generalized reductions. In Procs. of the 3rd Int. Conf. on Supercomputing, pages 186–194. ACM Press, 1989.
H. Leverge. Reduction operators in alpha. In D. Etiemble and J.-C. Syre, editors, Lecture notes in Computer Science No 605, pages 397–411, 1992.
Hervé Leverge. A note on chernikova's algorithm. Technical Report 1992, INRIA, May 1992. Référence à vérifier.
Christophe Mauras. Alpha: un langage équationnel pour la conception et la programmation d'architectures parallèles synchrones. PhD thesis, Université de Rennes I, December 1989.
Shlomit S. Pinter and Ron Y. Pinter. Program optimization and parallelization using idioms. In POPL'91, 1991. to appear.
X. Redon. Détection des réductions. Technical Report MASI 92-52, Institut Blaise Pascal, September 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Redon, X., Feautrier, P. (1993). Detection of recurrences in sequential programs with loops. In: Bode, A., Reeve, M., Wolf, G. (eds) PARLE '93 Parallel Architectures and Languages Europe. PARLE 1993. Lecture Notes in Computer Science, vol 694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56891-3_11
Download citation
DOI: https://doi.org/10.1007/3-540-56891-3_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56891-9
Online ISBN: 978-3-540-47779-2
eBook Packages: Springer Book Archive