Abstract
We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available.
Supported by the CNRS-INRIA project ReMaP.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J.R. Allen and K. Kennedy. Automatic translations of Fortran programs to vector form. ACM Toplas, 9:491–542, 1987.
U. Banerjee. Dependence Analysis for Supercomputing. Kluwer Academic Publishers, Norwell, MA, 1988.
D. Callahan. A Global Approach to Detection of Parallelism. PhD thesis, Dept. of Computer Science, Rice University, Houston, TX, 1987.
Alain Darte and Frédéric Vivien. A classification of nested loops parallelization algorithms. In INRIA-IEEE Symposium on Emerging Technologies and Factory Automation, pages 217–224. IEEE Computer Society Press, 1995.
Alain Darte and Frédéric Vivien. On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. Technical Report 96-05, LIP, ENS-Lyon, France, February 1996. Extended version of Europar'96.
Alain Darte and Frédéric Vivien. Optimal fine and medium grain parallelism in polyhedral reduced dependence graphs. In Proceedings of PACT'96, Boston, MA, October 1996. IEEE Computer Society Press. To appear.
Paul Feautrier. Dataflow analysis of array and scalar references. Int. J. Parallel Programming, 20(1):23–51, 1991.
Paul Feautrier. Some efficient solutions to the affine scheduling problem, part II, multi-dimensional time. Int. J. Parallel Programming, 21(6):389–420, December 1992.
G. Goff, K. Kennedy, and C.W. Tseng. Practical dependence testing. In Proceedings of ACM SIGPLAN'91 Conference on Programming Language Design and Implementation, Toronto, Canada, June 1991.
F. Irigoin, P. Jouvelot, and R. Triolet. Semantical interprocedural parallelization: an overview of the PIPS project. In Proceedings of the 1991 ACM International Conference on Supercomputing, Cologne, Germany, June 1991.
F. Irigoin and R. Triolet. Computing dependence direction vectors and dependence cones with linear systems. Technical Report ENSMP-CAI-87-E94, Ecole des Mines de Paris, Fontainebleau (France), 1987.
R.M. Karp, R.E. Miller, and S. Winograd. The organization of computations for uniform recurrence equations. Journal of the ACM, 14(3):563–590, July 1967.
X.Y. Kong, D. Klappholz, and K. Psarris. The I test: a new test for subscript data dependence. In Padua, editor, Proceedings of 1990 International Conference of Parallel Processing, August 1990.
Leslie Lamport. The parallel execution of DO loops. Communications of the ACM, 17(2):83–93, February 1974.
Z.Y. Li, P.-C. Yew, and C.Q. Zhu. Data dependence analysis on multi-dimensional array references. In Proceedings of the 1989 ACM International Conference on Supercomputing, pages 215–224, Crete, Greece, June 1989.
Y. Muraoka. Parallelism exposure and exploitation in programs. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, February 1971.
William Pugh. The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM, 8:102–114, August 1992.
Michael E. Wolf and Monica S. Lam. A loop transformation theory and an algorithm to maximize parallelism. IEEE Trans. Parallel Distributed Systems, 2(4):452–471, October 1991.
Michael Wolfe. Optimizing Supercompilers for Supercomputers. MIT Press, Cambridge MA, 1989.
Y.-Q. Yang, C. Ancourt, and F. Irigoin. Minimal data dependence abstractions for loop transformations. International Journal of Parallel Programming, 23(4):359–388, August 1995.
Yi-Qing Yang. Tests des dépendances et transformations de programme. PhD thesis, Ecole Nationale Supérieure des Mines de Paris, Fontainebleau, France, 1993.
Hans Zima and Barbara Chapman. Supercompilers for Parallel and Vector Computers. ACM Press, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Darte, A., Vivien, F. (1996). On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. In: Bougé, L., Fraigniaud, P., Mignotte, A., Robert, Y. (eds) Euro-Par'96 Parallel Processing. Euro-Par 1996. Lecture Notes in Computer Science, vol 1123. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61626-8_50
Download citation
DOI: https://doi.org/10.1007/3-540-61626-8_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61626-9
Online ISBN: 978-3-540-70633-5
eBook Packages: Springer Book Archive