Dynamic data distribution with control flow analysis

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: Eduard Ayguadé , Jordi Garcia , Mercè Gironés , Jesús Labarta , Jordi Torres , Mateo Valero, Detecting and Using Affinity in an Automatic Data Distribution Tool, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.61-75, August 08-10, 1994
• 2: Eduard Ayguadé , Jordi Garcia , Mercè Gironès , M. Luz Grande , Jesús Labarta, Data Redistribution in an Automatic Data Distribution Tool, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.407-421, August 10-12, 1995
• 3: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• 4: APR95 Applied Parallel Research, Inc. xHPF Version 2.0. User's Guide, 2.0 edition, January 1995.
• 5: Robert E. Bixby , Ken Kennedy , Ulrich Kremer, Automatic Data Layout Using 0-1 Integer Programming, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.111-122, August 24-26, 1994
• 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: Jordi Garcia , Eduard Ayguadé , Jesus Lebarta, A novel approach towards automatic data distribution, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.78-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224500]
• 8: Jordi Garcia , Eduard Ayguade , Jesus Labarta, A Framework for Automatic Dynamic Data Mapping, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.92, October 23-26, 1996
• 9: Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 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: Alan H. Karp, Programming for parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
• 12: Ken Kennedy , Ulrich Kremer, Automatic data layout for high performance Fortran, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.76-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224495]
• 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: Daniel J. Palermo , Prithviraj Banerjee, Automatic Selection of Dynamic Data Partitioning Schemes for Distributed-Memory Multicomputers, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.392-406, August 10-12, 1995
• 17: T. J. Sheffler , R. Schreiber , J. R. Gilbert , S. Chatterjee, Aligning parallel arrays to reduce communication, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.324, February 06-09, 1995
• 18: Thomas J. Sheffler , Robert Schreiber , William Pugh , John R. Gilbert , Siddhartha Chatterjee, Efficient Distribution Analysis via Graph Contraction, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.377-391, August 10-12, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory