An approach to synchronization for parallel computing

ABSTRACT

This paper proposes an approach to minimally constrained synchronization for the parallel execution of imperative programs in a shared-memory environment. Anti-dependencies and output-dependencies arising from array references within loops are completely removed, using run-time analysis if necessary. A parallel reference-pattern generation scheme based on one proposed in [13] is used in conjunction with dynamic allocation and binding of storage, to completely remove non-intrinsic data dependencies during execution.

REFERENCES

• 1: Ronald Gary Cytron, Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing), 1984
• 2: A. Gottlieb et.~ al. The NYU Ultra Computer- Designing an MIMD Shared Memory Parallel Computer. 1EEE Trans. Gomput., C-32(2):175- 189, 1983.
• 3: Anita K. Jones , Peter Schwarz, Experience Using Multiprocessor Systems—A Status Report, ACM Computing Surveys (CSUR), v.12 n.2, p.121-165, June 1980 [doi>10.1145/356810.356813]
• 4: 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]
• 5: D.L. Kuck et.al. Parallel Supercomputing Today and the CEDAR approach. Science, 231(2):967- 974, 1986.
• 6: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 7: G. Pfister et. al. The IBM Research Parallel Pro- ~essor Prototype (RP3): Introduction Architecture. In Proc. 1985 Int. Conf. ou Parallel Processing, pages 764-771, 1985.
• 8: J. Pier and D.D. Gajski. Data Flow Execution of FORTRAN Loops. In Proc. 1st Int. Conf. on Supercomputers, pages 129-138, 1985.
• 9: B.j. Smith. A Pipelined, Shared Resource MIMD Computer. In Proc. 1978 Int. Con1. on Parallel Processing, pages 6-8, 1978.
• 10: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 11: Michael Wolfe, Multiprocessor Synchronization for Concurrent Loops, IEEE Software, v.5 n.1, p.34-42, January 1988 [doi>10.1109/52.1992]
• 12: M.J. Wolfe. Techniques for Improving lhe Inherent Parallelism in Programs. Master's thesis, University of illinois, Urbana-Champaign, July 1978.
• 13: Chuan-Qi Zhu , Pen-Chung Yew, A scheme to enforce data dependence on large multiprocessor systems, IEEE Transactions on Software Engineering, v.13 n.6, p.726-739, June 1987 [doi>10.1109/TSE.1987.233477]
• 14: C.Q. Zhu and P.C. Yew. A Synchronization Scheme and its Applications for Large Multiprocessor Systems. in Proc. 4~h Int. Conf. on Distributed Computing Systems, pages 486-493, 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

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: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Design, Theory