Automatic parallelization for symmetric shared-memory multiprocessors

ABSTRACT

The trend in workstation hardware is towards symmetric shared-memory multiprocessors (SMPs). User expectations are for (largely) automatic exploitation of parallelism on an SMP, similar to automatic exploitation of modern processor features such as caches and instruction scheduling.In this paper, we present our solution to automatic SMP parallelization. Our solution is unique in its robust support for unbalanced processor loads and nesting of parallel loops and parallel sections, in conjunction with its tight integration with high-order transformations for improved uniprocessor performance, so that the speedup due to parallelism is truly a multiplicative speedup over highly optimized uniprocessor execution times.

REFERENCES

• 1: {1} AIX Version 4.1 General Programming Concepts: Writing and Debugging Programs, 1994.
• 2: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 3: S. F. Hummel , E. Schonberg, Low-overhead scheduling of nested parallelism, IBM Journal of Research and Development, v.35 n.5-6, p.743-765, Sept./Nov. 1991
• 4: Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a practical and robust method for scheduling parallel loops, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.610-632, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126137]
• 5: Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
• 6: Jim Q. Ning , Andre Engberts , W. Voytek Kozaczynski, Automated support for legacy code understanding, Communications of the ACM, v.37 n.5, p.50-57, May 1994 [doi>10.1145/175290.175295]
• 7: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987
• 8: {8} IBM Shared Memory System POWER/4 User's Guide and Technical Reference, 1993.
• 9: V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
• 10: V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
• 11: V. Sarkar, Automatic selection of high-order transformations in the IBM XL FORTRAN compilers, IBM Journal of Research and Development, v.41 n.3, p.233-264, May 1997
• 12: Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
• 13: {13} IBM VS FORTRAN Version 2: Programming Guide for CMS and MVS, 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
      C.1.4 Parallel Architectures

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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