More Web Proxy on the site http://driver.im/

Article

Dynamic data distribution with control flow analysis

Authors:

Eduard Ayguade,

Jesus LabartaAuthors Info & Claims

Supercomputing '96: Proceedings of the 1996 ACM/IEEE conference on Supercomputing

Pages 11 - es

https://doi.org/10.1145/369028.369048

Published: 17 November 1996 Publication History

Abstract

This paper describes the design of a data distribution tool which automatically derives the data mapping for the arrays and the parallelization strategy for the loops in a Fortran 77 program. The layout generated can be static or dynamic, and the distribution is one-dimensional BLOCK or CYCLIC. The tool takes into account the control flow statements in the code in order to better estimate the behavior of the program. All the information regarding data movement and parallelism is contained in a single data structure named Communication-Parallelism Graph (CPG). The CPG is used to model a minimal path problem in which time is the objective function to minimize. It is solved using a general purpose linear programming solver, which finds the optimal solution for the whole problem. The experimental results will illustrate the quality of the solutions generated and the feasibility of the approach in terms of compilation time.

References

[1]

AGG+94 E. Ayguadé, J. Garcia, M. Gironès, J. Labarta, J. Torres, and M. Valero. Detecting and Using Affinity in an Automatic Data Distribution Tool. In K. Pingali et al., editor, Proceedings of the 7th Annual Workshop on Languages and Compilers for Parallel Computing, pages 61-75, Ithaca, NY, August 1994. Lecture Notes in Computer Science Vol. 892, Springer-Verlag.

Digital Library

[2]

AGG+95 E. Ayguadé, J. Garcia, M. Gironès, M. L. Grande, and J. Labarta. Data Redistribution in an Automatic Data Distribution Tool. In C.-H. Huang et al., editor, Proceedings of the 8th Annual Workshop on Languages and Compilers for Parallel Computing, pages 407-421, Columbus, OH, August 1995. Lecture Notes in Computer Science Vol. 1033, Springer-Verlag.

Digital Library

[3]

AL93 J. Anderson and M. S. Lam. Global Optimizations for Parallelism and Locality on Scalable Parallel Machines. In Proceedings of the SIGPLAN'93 Conference on Program Language Design and Implementation, Albuquerque, NM, June 1993.

Digital Library

[4]

APR95 Applied Parallel Research, Inc. xHPF Version 2.0. User's Guide, 2.0 edition, January 1995.

[5]

BKK94 R. Bixby, K. Kennedy, and U. Kremer. Automatic Data Layout Using 0-1 Integer Programming. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, Montreal, Canada, August 1994.

Digital Library

[6]

CP93 P. Crooks and R. H. Perrott. An Automatic Data Distribution Generator for Distributed Memory MIMD Machines. In Proceedings of the 4th International Workshop on Compilers for Parallel Computers, Delft, The Netherlands, December 1993.

[7]

GAL95 J. Garcia, E. Ayguadé, and J. Labarta. A Novel Approach Towards Automatic Data Distribution. In Proceedings of Supercomputing'95, San Diego, CA, December 1995.

Digital Library

[8]

GAL96 J. Garcia, E. Ayguadé, and J. Labarta. A Framework for Automatic Dynamic Data Mapping. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing, New Orleans, Louisiana, October 1996.

Digital Library

[9]

Gup92 M. Gupta. Automatic Data Partitioning on Distributed Memory Multicomputers. PhD thesis, Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign, September 1992.

Digital Library

[10]

HPF93 High Performance Fortran Forum HPFF. High Performance Fortran Language Specification. Version 1.0. Scientific Programming, Vol 2(1 and 2), May 1993.

[11]

Kar87 A. H. Karp. Programming for Parallelism. IEEE Computer, May 1987.

Digital Library

[12]

KK95 K. Kennedy and U. Kremer. Automatic Data Layout for High Performance Fortran. In Proceedings of Supercomputing'95, San Diego, CA, December 1995.

Digital Library

[13]

Kre93 U. Kremer. NP-completeness of Dynamic Remapping. In Proceedings of the 4th International Workshop on Compilers for Parallel Computers, Delft, The Netherlands, December 1993.

[14]

LC90 J. Li and M. Chen. Index Domain Alignment: Minimizing Cost of Cross-Referencing between Distributed Arrays. In Frontiers90: The 3rd Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, October 1990.

[15]

LIN94 LINDO Systems Inc. LINGO Optimization Modeling Language, April 1994.

[16]

PB95 D. J. Palermo and P. Banerjee. Automatic Selection of Dynamic Partitioning Schemes for Distributed-Memory Multicomputers. In Proceedings of the 8th Annual Workshop on Languages and Compilers for Parallel Computing, Columbus, OH, August 1995.

Digital Library

[17]

SSGC95 T. J. Scheffler, R. Schreiber, J. R. Gilbert, and S. Chatterjee. Aligning Parallel Arrays to Reduce Communication. In Frontiers95: The 5th Symposium on the Frontiers of Massively Parallel Computation, McLean, VA, February 1995.

Digital Library

[18]

SSP+95 T. J. Scheffler, R. Schreiber, W. Pugh, J. R. Gilbert, and S. Chatterjee. Efficient Distribution Analysis via Graph Contraction. In Proceedings of the 8th Annual Workshop on Languages and Compilers for Parallel Computing, Columbus, OH, August 1995.

Digital Library

Cited By

Cho D(2011)A Memory Access Pattern Based Data Distribution Technique for Array ProcessorsConvergence and Hybrid Information Technology10.1007/978-3-642-24106-2_80(633-640)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24106-2_80
Choudhary AKandemir M(2010)Compilation for Distributed Memory ArchitecturesThe Compiler Design Handbook10.1201/9781420040579.ch11Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch11
Yang XDu JYan XDeng Y(2009)Matrix-based streamization approach for improving locality and parallelism on FT64 stream processorThe Journal of Supercomputing10.1007/s11227-008-0186-047:2(171-197)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1007/s11227-008-0186-0
Show More Cited By

Recommendations

Loop distribution with arbitrary control flow
Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing

Loop distribution is an integral part of transforming a sequential program into a parallel one. It is used extensively in parallelization, vectorization, and memory management. For loops with control flow, previous methods for loop distribution have ...
ZebraNet and its theoretical analysis on distribution functions of data gathering times
MobiOpp '10: Proceedings of the Second International Workshop on Mobile Opportunistic Networking

We theoretically investigated a general property of data gathering times in a wireless communication system with randomly moving sensors which share data only with nearby ones. We proposed a stochastic model of the system to analyse distribution ...
Agent Based Dynamic Data Storage and Distribution in Data Warehouses
KES-AMSTA '07: Proceedings of the 1st KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications

In this paper, we propose a new approach to manage data storage and distribution in a data warehouse (DWH) environment. This approach deals with the dynamic data distribution of the DWH on a set of servers. The data distribution that we consider is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Supercomputing '96: Proceedings of the 1996 ACM/IEEE conference on Supercomputing

November 1996

898 pages

ISBN:0897918541

Chairman:
Beverly Clayton

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 17 November 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '96

Sponsor:

SIGARCH
IEEE-CS

SC '96: International Conference for High Performance Computing, Networking, Storage and Analysis

January 1, 1996

Pennsylvania, Pittsburgh, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)4

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cho D(2011)A Memory Access Pattern Based Data Distribution Technique for Array ProcessorsConvergence and Hybrid Information Technology10.1007/978-3-642-24106-2_80(633-640)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24106-2_80
Choudhary AKandemir M(2010)Compilation for Distributed Memory ArchitecturesThe Compiler Design Handbook10.1201/9781420040579.ch11Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch11
Yang XDu JYan XDeng Y(2009)Matrix-based streamization approach for improving locality and parallelism on FT64 stream processorThe Journal of Supercomputing10.1007/s11227-008-0186-047:2(171-197)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1007/s11227-008-0186-0
Westermann PSchwoerer LKaufmann A(2007)Applying Data Mapping Techniques to Vector DSPs2007 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/ICSAMOS.2007.4285727(1-8)Online publication date: Jul-2007
https://doi.org/10.1109/ICSAMOS.2007.4285727
Weatherly DLowenthal DNakazawa MLowenthal F(2006)Dyn-MPIJournal of Parallel and Distributed Computing10.1016/j.jpdc.2006.02.00266:6(822-838)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1016/j.jpdc.2006.02.002
Nakazawa MLowenthal DZhou WKramer W(2005)The MHETA Execution Model for Heterogeneous ClustersProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.73Online publication date: 12-Nov-2005
https://dl.acm.org/doi/10.1109/SC.2005.73
Laure EChapman B(2005)Interprocedural array alignment analysisHigh-Performance Computing and Networking10.1007/BFb0037202(747-756)Online publication date: 22-Jun-2005
https://doi.org/10.1007/BFb0037202
Damian-Iordache MPemmaraju S(2005)Automatic data decomposition for message-passing machinesLanguages and Compilers for Parallel Computing10.1007/BFb0032684(64-78)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0032684
Laure EChapman B(2005)Combining inter- and intradimensional alignment analysis to support data distributionHigh-Performance Computing and Networking10.1007/BFb0031654(830-839)Online publication date: 25-Jun-2005
https://doi.org/10.1007/BFb0031654
Kadayif IKandemir M(2004)Quasidynamic Layout Optimizations for Improving Data LocalityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.7015:11(996-1011)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.70
Show More Cited By

View Options

View options

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents