A framework for determining useful parallelism

ABSTRACT

An approach to finding and forming parallel processes for both sequential and parallel programs is presented. The approach is presented in a framework that can create useful parallelism for a variety of parallel architectures. The framework makes use of a control dependence graph to capture maximal parallelism, a process tree to expose useful parallelism, renaming and storage segregation to reduce data dependencies, and an architecture-specific cost analyzer to evaluate the effectiveness of the potential processes. The framework is currently being implemented.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 3: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 4: Utpal Banerjee, Speedup of ordinary programs, 1979
• 5: Michael Burke. An Interval Analysis Approach Toward Interprocedural Data Flow, IBM Research, 1984. Report RC10640.
• 6: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 7: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 8: Michael Burke, Ron Cytron, Jeanne Ferrante, and Wilson Hsieh. Automatic Determination of Private and Shared Variables for Nested Processes, IBM T. J. Watson Research Center, 1987. Research Report RC 13194.
• 9: Michael Burke , Ron Cytron , Jeanne Ferrante , Wilson Hsieh , Vivek Sarkar , David Shields, Automatic discovery of parallelism: a tool and an experiment (extended abstract), Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.77-84, July 19-21, 1988, New Haven, Connecticut, United States
• 10: Ron Cytron and Jeanne Ferrante. What's in a Name? Or the Value of Renaming for Parallelism Detection and Storage Allocation. Proceedings of the 1987 International Conference on Parallel Processing, pages 19-27, St. Charles, IL, August 1987.
• 11: Ron Cytron and Jeanne Ferrante. An Improved Control Dependence Algorithm, IBM, 1987. Tech. Report RC 13291.
• 12: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 13: R.L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17(2)'416-429, March 1969.
• 14: Wilson C. Hsieh. Extracting Parallelism from Sequential Programs, Massachusetts Institute of Technology, 1988. Master's thesis in progress.
• 15: IBM. Parallel Fortran Language and Library Reference, international Business Machines, March 1988. Pub. No. SC23-0431-0.
• 16: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 17: V. Sarkar, Partitioning and scheduling parallel programs for execution on multiprocessors, Stanford University, Stanford, CA, 1987
• 18: V. Sarkar, Synchronization using counting semaphores, Proceedings of the 2nd international conference on Supercomputing, p.627-637, June 1988, St. Malo, France [doi>10.1145/55364.55426]
• 19: Vivek Sarkar , John Hennessy, Partitioning parallel programs for macro-dataflow, Proceedings of the 1986 ACM conference on LISP and functional programming, p.202-211, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319863]
• 20: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Synchronization

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Design