Abstract
Communication resulting from references to arrays with general cyclic(k) distributions in data-parallel programs is not amenable to existing analyses developed for block and cyclic distributions. The methods for communication generation presented in this paper are based on exploiting the repetitive nature of array accesses. We represent array access patterns as periodic sequences and use these sequences for efficient communication analysis and code generation. Our approach allows us to incorporate message coalescing optimization and to use overlap areas for shift communication. Experimental results from our prototype implementation demonstrate the validity of the proposed techniques.
This work was supported in part by ARPA contract DABT63-92-C-0038, NSF Cooperative Agreement Number CCR-9120008, and NSF/NASA grant# ASC-9213821. The content of this paper does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Chatterjee, J. Gilbert, F. Long, R. Schreiber, and S. Teng. Generating local addresses and communication sets for data-parallel programs. In Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, May 1993.
R. Das, M. Uysal, J. Saitz, and Y-S. Hwang. Communication optimizations for irregular scientific computations on distributed memory architectures. Technical Report CS-TR3163, Dept. of Computer Science, Univ. of Maryland, College Park, October 1993.
M. Gerndt. Updating distributed variables in local computations. Concurrency: Practice and Experience, 2(3):171–193, September 1990.
S.K.S. Gupta, S.D. Kaushik, C.-H. Huang, and P. Sadayappan. On compiling array expressions for efficient execution on distributed-memory machines. Technical Report OSU-CISRC-4/94-TR19, Department of Computer and Information Science, The Ohio State University, April 1994.
S. Hiranandani, K. Kennedy, and C.-W. Tseng. Compiler optimizations for Fortran D on MIMD distributed-memory machines. In Proceedings of Supercomputing ‘81, Albuquerque, NM, November 1991.
S. D. Kaushik. Private communication, April 1995.
K. Kennedy, N. Nedeljković, and A. Sethi. Efficient address generation for block-cyclic distributions. In Proceedings of the 1995 ACM International Conference on Supercomputing, Barcelona, Spain, July 1995.
K. Kennedy, N. Nedeljković, and A. Sethi. A linear-time algorithm for computing the memory access sequence in data-parallel programs. In Proceedings of the Fifth ACM SIGPLANSymposium on Principles and Practice of Parallel Programming, Santa Barbara, CA, July 1995.
J. Stichnoth. Efficient compilation of array statements for private memory multicomputers. Technical Report CMU-CS-93–109, School of Computer Science, Carnegie Mellon University, February 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer Science+Business Media New York
About this chapter
Cite this chapter
Kennedy, K., Nedeljković, N., Sethi, A. (1996). Communication Generation for Cyclic(K) Distributions. In: Szymanski, B.K., Sinharoy, B. (eds) Languages, Compilers and Run-Time Systems for Scalable Computers. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-2315-4_14
Download citation
DOI: https://doi.org/10.1007/978-1-4615-2315-4_14
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-5979-1
Online ISBN: 978-1-4615-2315-4
eBook Packages: Springer Book Archive