A methodology for parallelizing programs for multicomputers and complex memory multiprocessors

ABSTRACT

The availability of large distributed memory multiprocessors and parallel computers with complex memory hierarchies have left the programmer with the difficult task of planning the detailed parallel execution of a program; for example, in the case of distributed memory machines, the programmer is forced to manually distribute code and data in addition to managing communication among tasks explicitly. Current work in compiler support for this task has focused on automating task partitioning, assuming a fixed data partition or a programmer-specified (in the form of annotations) data partition. This paper argues that one of the reasons for inefficient parallel execution is the lack of synergism between task partitioning and data partitioning and allocation; hence data and task allocation should both be influenced by the inherent dependence structure of the computation (which is the source of synergism). We present a methodology based on a unified approach to task and data partitioning; we show how to derive data and task partitions for computations expressed as nested loops that exhibit regular dependencies and how to map these onto distributed memory multiprocessors. Based on the mapping, we show how to derive code for the nodes of a distributed memory machine with appropriate message transmission constructs. We also discuss related communication optimizations.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 3: D. Callahan and K. Kennedy, "Compiling Programs for Distributed-Memory Multiprocessors," The Journal of Supercomputing, Vol. 2, Oct. 1988, pp. 151-169.
• 4: Marina C. Chen, A design methodology for synthesizing parallel algorithms and architectures, Journal of Parallel and Distributed Computing, v.3 n.4, p.461-491, December 1, 1986 [doi>10.1016/0743-7315(86)90010-9]
• 5: M. Chen, Y. Choo and J. Li, "Compiling Parallel Programs by Optimizing Performance," The Journal of Supercomputing, 2, 1988, pp. 171-207.
• 6: Ronald Gary Cytron, Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing), 1984
• 7: R. Cytron, "Limited Processor Scheduling of Doacross Loops," Proc. 1987 International Conference on Paral. lel Processing, S. Sahni (Ed.), Aug. 1987, pp. 226-234.
• 8: J. Fortes and D. Moldown, "ParaUehsm Detection and Transformation Techniques Useful for VLSI Algorithms," Journal of Parallel and D~stributed Computing, Vol. 2, 1985, pp. 277-301.
• 9: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 10: K. Gallivan , W. Jalby , D. Gannon, On the problem of optimizing data transfers for complex memory systems, Proceedings of the 2nd international conference on Supercomputing, p.238-253, June 1988, St. Malo, France [doi>10.1145/55364.55388]
• 11: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 12: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 13: Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
• 14: B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Syslems Technical Journal, Vol. 49, No. 2, 1970, pp. 291-308.
• 15: Charles Koelbel , Piyush Mehrotra , John van Rosendale, Semi-automatic process partitioning for parallel computation, International Journal of Parallel Programming, v.16 n.5, p.365-382, October 1987 [doi>10.1007/BF01407902]
• 16: C. Koelbel and P. Mehrotra, "Semi-automatic Process Decomposition for Non-shared Memory Machines," in Proc. 1989 Inlernational Conference on Supercomputing, May 1989.
• 17: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 18: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 19: Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
• 20: W L. Miranker , A Winkler, Spacetime representations of computational structures, Computing, v.32 n.2, p.93-114, 1984 [doi>10.1007/BF02253685]
• 21: D. Padua, D. Kuck and D. Lawrie, "High-speed Multiprocessors and Compilation Techniques," IEEE Trans. Computers, Vol. C-29, No. 9, Sep. 1980, pp. 763-776.
• 22: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 23: A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
• 24: P. Sadayappan, F. Ercal ~nd J. Ramanujam, "Cluster Partitioning Approaches to Mapping Parallel Programs onto a Hypercube," to appear in Parallel Computing.
• 25: C. Shen and W. Tsai, "A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minmax Criterion," IEEE Trans. on Computers, Vol. C-34, No. 3, Mar. 1985, pp. 197-203.
• 26: B.J. Smith, "A Pipelined, Shared Resource MIMD Computer," Proc. 1978 International Conference on Parallel Processing, pp. 6-8.
• 27: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 28: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 29: Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS

General Terms:
Design, Languages, Performance