Abstract
Feautrier’s scheduling algorithm is the most powerful existing algorithm for parallelism detection and extraction. But it has always been known to be suboptimal. However, the question whether it may miss some parallelism because of its design was still open. We show that this is not the case. Therefore, to find more parallelism than this algorithm does, one needs to get rid of some of the hypotheses underlying its framework.
Chapter PDF
Similar content being viewed by others
References
J. Allen, D. Callahan, and K. Kennedy. Automatic decomposition of scientific programs for parallel execution. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Programming Languages, pages 63–76, Munich, Germany, Jan. 1987.
J. R. Allen and K. Kennedy. PFC: A program to convert Fortran to parallel form. Technical Report MASC-TR82-6, Rice University, Houston, TX, USA, 1982.
A. Darte. De l’organisation des calculs dans les codes répétitifs. Habilitation thesis, ècole normale supérieure de Lyon, 1999.
A. Darte, Y. Robert, and F. Vivien. Scheduling and Automatic Parallelization. Birkhäuser Boston, 2000. ISBN 0-8176-4149-1.
A. Darte and F. Vivien. Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. Int. J. of Parallel Programming, 1997.
P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23–51, 1991.
P. Feautrier. Some efficient solutions to the affine scheduling problem, part I: One-dimensional time. Int. J. Parallel Programming, 21(5):313–348, Oct. 1992.
P. Feautrier. Some efficient solutions to the affine scheduling problem, part II: Multi-dimensional time. Int. J. Parallel Programming, 21(6):389–420, Dec. 1992.
M. Griebl, P. Feautrier, and C. Lengauer. Index set splitting. International Journal of Parallel Programming, 28(6):607–631, 2000.
L. Lamport. The parallel execution of DO loops. Communications of the ACM, 17(2):83–93, Feb. 1974.
V. Loechner and D. K. Wilde. Parameterized polyhedra and their vertices. International Journal of Parallel Programming, 25(6), Dec. 1997.
P. Quinton. Automata Networks in Computer Science, chapter The systematic design of systolic arrays. Manchester University Press, 1987.
A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, New York, 1986.
F. Vivien. On the Optimality of Feautrier’s Scheduling Algorithm. Technical Report 02-04, ICPS-LSIIT, ULP-Strasbourg I, France, rs http://icps.u-strasbg.fr URL, 2002.
M. E. Wolf and M. S. Lam. A data locality optimizing algorithm. In SIGPLAN Conference PLDI, pages 30–44. ACM Press, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vivien, F. (2002). On the Optimality of Feautrier’s Scheduling Algorithm. In: Monien, B., Feldmann, R. (eds) Euro-Par 2002 Parallel Processing. Euro-Par 2002. Lecture Notes in Computer Science, vol 2400. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45706-2_39
Download citation
DOI: https://doi.org/10.1007/3-540-45706-2_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44049-9
Online ISBN: 978-3-540-45706-0
eBook Packages: Springer Book Archive