Restricted Fetch and Φ operations for parallel processing

ABSTRACT

This paper discusses a restricted form of the general Fetch&&PHgr; operation and how the restricted form can be combined. In this restricted form, all processors participating in the combining have identical Fetch&&PHgr; operations. Most applications of Fetch&&PHgr; proposed in the literature satisfy the restrictions imposed. We show how this restricted form of Fetch&&PHgr; allows an easy implementation of combining, especially in bus-based multiprocessors and multiprocessors with a separate synchronization memory. Applications of the proposed restricted Fetch&&PHgr; operation are also considered.

REFERENCES

• 1: G. S. Almasi , A. Gottlieb, Highly parallel computing, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
• 2: Burroughs Corporation, "Final Report Numerical Aerodynamic Simulation Facility Feasibility Study," March 1979.
• 3: Faith E. Fich, New bounds for parallel prefix circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.100-109, December 1983 [doi>10.1145/800061.808738]
• 4: James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
• 5: A. Gottlieb, et al, "The NYU Ultracomputer-- Designing a MIMD, Shared Memory Parallel Machine," IEEE Transactions on Computers, vol. C-32, pp. 175-189, February 1983.
• 6: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 7: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• 8: J.L. Larson, "Multitasking on the Cray X-MP-2 Multiprocessor," IEEE Computer, pp. 62-69, 1984.
• 9: G. J. Lipovski , P. Vaughan, A fetch-and-op implementation for parallel computers, Proceedings of the 15th Annual International Symposium on Computer architecture, p.384-392, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 10: S. F. Lundstrom, Applications considerations in the system design of highly concurrent multiprocessors, IEEE Transactions on Computers, v.36 n.11, p.1292-1309, Nov. 1987 [doi>10.1109/TC.1987.5009469]
• 11: G.F. Ptister and V. A. Norton, "'Hot-Spot' Contention and Combining in Multistage Interconnecfion Networks," IEEE Transactions on Computers, vol. C-34, pp. 943-948, October 1985.
• 12: G.F. Pfister, et al, "The IBM Research Parallel Processor Prototype (RP3): introduction and architecture,'' Proceedings 1985 International Conference on Parallel Processing, pp. 764- 771, August 1985.
• 13: C.D. Polychronopoulos, "The Impact of Run- Time Overhead on Usable Parallelism," Proceedings 1988 International Conference on Parallel Processing, August 1988.
• 14: R. D. Pribnow, "System for Mul6processor Communication Using Local and Common Semaphore and Information Registers," United States Patent 4,754 398, June 1988.
• 15: H. S. Stone, "Database Applications of the FETCH-AND-ADD Instruction," IEEE Transactions on Computers, vol. C-33, pp. 604-612, July 1984.
• 16: P.-C. Yew , N.-F. Tzeng , D. H. Lawrie, Distributing hot-spot addressing in large-scale multiprocessors, IEEE Transactions on Computers, v.36 n.4, p.388-395, April 1987 [doi>10.1109/TC.1987.1676921]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Management, Performance, Theory