Abstract
When parallelizing loop nests for distributed memory parallel computers, we have to specify when the different computations are carried out (computation scheduling), where they are carried out (computation mapping), and where the data are stored (data mapping). We show that even the “best” scheduling and mapping functions can lead to a sequential execution when combined, if they are independently chosen. We characterize when combined scheduling and mapping functions actually lead to a parallel execution. We present an algorithm which computes a scheduling compatible with a given computation mapping, if such a schedule exists.
Chapter PDF
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 translation of Fortran programs to vector form. A CM TOPLAS, 9(4):491–542, Oct. 1987.
J. M. Anderson and M. S. Lam. Global optimizations for parallelism and locality on scalable parallel machines. ACM Sigplan Notices, 28(6):112–125, June 1993.
D. Bau, I. Kodukula, V. Kotlyar, K. Pingali, and P. Stodghill. Solving alignment using elementary linear algebra. In K. Pingali, U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and compilers for parallel computing-7th international workshop, volume LNCS 892, pages 46–60. Springer Verlag, 1994.
A. Darte, C. Diderich, M. Gengler, and F. Vivien. Scheduling the computations of a loop nest with respect to a given mapping. Technical Report 00-04, ICPS, University of Strasbourg, France, 2000.
A. Darte and F. Vivien. Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs. Int. J. Parallel Programming, 25(6), 1997.
C. G. Diderich and M. Gengler. The alignment problem in a linear algebra framework. In Proceedings of the Hawaï International Conference on System Sciences (HICSS-30), Software Technology Track, pages 586–595, Wailea, HI, Jan. 1997. IEEE Computer Society Press.
M. Dion and Y. Robert. Mapping affine loop nests: New results. In B. Hertzberger and G. Serazzi, editors, High-Performance Computing and Networking, International Conference and Exhibition, volume LCNS 919, pages 184–189. Springer-Verlag, 1995.
P. Feautrier. Some efficient solutions to the affine scheduling problem, part II: multi-dimensional time. Int. J. Parallel Programming, 21(6):389–420, 1992.
P. Feautrier. Towards automatic distribution. Parallel Processing Letters, 4(3):233–244, 1994.
A. W. Lim and M. S. Lam. Maximizing parallelism and minimizing synchronization with affine transforms. In Proceedings of the 24th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 1997.
J. Ramanujam and P. Sadayappan. Compile-time techniques for data distribution in distributed memory machines. IEEE TPDS, 2(4):472–482, Oct. 1991.
M. E. Wolf and M. S. Lam. A loop transformation theory and an algorithm to maximize parallelism. IEEE TPDS, 2(4):452–471, Oct. 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Darte, A., Diderich, C., Gengler, M., Vivien, F. (2000). Scheduling the Computations of a Loop Nest with Respect to a Given Mapping. In: Bode, A., Ludwig, T., Karl, W., Wismüller, R. (eds) Euro-Par 2000 Parallel Processing. Euro-Par 2000. Lecture Notes in Computer Science, vol 1900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44520-X_52
Download citation
DOI: https://doi.org/10.1007/3-540-44520-X_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67956-1
Online ISBN: 978-3-540-44520-3
eBook Packages: Springer Book Archive