Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1863))
Included in the following conference series:
346Accesses
Abstract
Nowadays NUMA architectures are widely accepted. For such multiprocessors exploiting data locality is clearly a key issue. In this work, we present a method for automatically selecting the iteration/data distributions for a sequential F77 code, while minimizing the parallel execution overhead (communications and load unbalance). We formulate an integer programming problem to achieve that minimum parallel overhead. The constraints of the integer programming problem are derived directly from a graph known as theLocality-Communication Graph (LCG), which captures the memory locality, as well as the communication patterns, of a parallel program. In addition, our approach use theLCG to automatically schedule the communication operations required during the program execution, once the iteration/data distributions have been selected. The aggregation of messages in blocks is also dealt in our approach. The TFFT2 code, from NASA benchmarks, that includes non-affine access functions and non-affine index bounds, and repeated subroutine calls inside loops, has been correctly handled by our approach. With the iteration/data distributions derived from our method, this code achieves parallel efficiencies of over 69% for 16 processors, in a Cray T3E, an excellent performance for a complex real code.
This work was supported by the Ministry of Education and Science (CICYT) of Spain (TIC96-1125-C03) and by the European Union (EU ESPRIT IV Working Group No. 29488)
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
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
J.M. Anderson and M.S. Lam. Global optimizations for parallelism and locality on scalable parallel machines. InProceedings of SIGPLAN’93 Conference on Programming Language Design and Implementation (PLDI), Alburquerque, New Mexico, June 1993.
D. Bau, I. Kodukula, V. Kotlyar, K. Pingali, and Stodghill. Solving alignment using elementary linear algebra. In K. Pingali et al., editor,Proceedings of LCPC’94, number 892 in LNCS. Springer Verlag, Ithaca, N.Y., August 1994.
W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, T. Lawrence, J. Lee, D. Padua, Y. Paek, W. Pottenger, L. Rauchwerger, and P. Tu. Parallel programming with Polaris.IEEE Computer, pages 78–82, Dec 1996.
J. Garcia, E. Ayguade, and J. Labarta. Dynamic data distribution with control flow analysis. InProceedings of Supercomputing, Pittsburgh, PA, November 1996.
K. Kennedy and U. Kremer. Automatic data layout using 0-1 integer programming. InInt’l Conf. Parallel Architectures and Compilation Techniques, Montréal, Canada, Aug. 1994.
A. Navarro, R. Asenjo, E. Zapata, and D. Padua. Access descriptor based locality analysis for distributed-shared memory multiprocessors. InInternational Conference on Parallel Processing (ICPP’99), pages 86–94, Aizu-akamatzu, Japan, September 21–24 1999.
Angeles G. Navarro and E.L. Zapata. An automatic iteration/data distribution method based on access descriptors for DSM multiprocessors. Technical Report UMA-DAC-99/07, Department of Computer Architecture, University of Málaga, 1999.
Y. Paek, J. Hoeflinger, and D. Padua. Simplification of array access patterns for compiler optimizations. InProceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 1994.
Author information
Authors and Affiliations
Dept. de Arquitectura de Computadores, Universidad de Málaga, Spain
Angeles G. Navarro & Emilio L. Zapata
- Angeles G. Navarro
You can also search for this author inPubMed Google Scholar
- Emilio L. Zapata
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, 92093-0114, USA
Larry Carter & Jeanne Ferrante &
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Navarro, A.G., Zapata, E.L. (2000). An Automatic Iteration/Data Distribution Method Based on Access Descriptors for DSMM. In: Carter, L., Ferrante, J. (eds) Languages and Compilers for Parallel Computing. LCPC 1999. Lecture Notes in Computer Science, vol 1863. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44905-1_9
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-67858-8
Online ISBN:978-3-540-44905-8
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative