Dynamic switching of coherent cache protocols and its effects on Doacross loops

ABSTRACT

In multiprocessor systems, overheads caused by interprocessor communication and synchronization have been one of the largest obstacles for efficient execution of parallel programs. To reduce these overheads in shared-memory/shared-bus multiprocessors, we have proposed two hardware mechanisms: the Inter-Cache Snoop Control Mechanism (ICSCM), which dynamically switches snoop-protocols for improving shared-bus utilization, and the Mechanism for Integrated Synchronization and Communication (MISC), which extends ICSCM to support producer-consumer type synchronization efficiently. We have developed an execution-driven multiprocessor simulator for evaluating performance with these mechanisms. Simulation experiments on doacross loops show remarkable speed-ups by ICSCM/MISC mechanisms. Although the proposed mechanisms are originally implemented on a single shared-bus system, they are easily applicable to a clustered multiprocessing systems. The methods used in a clustered system are discussed.

REFERENCES

• 1: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 2: Matsumoto, T.: Fine-Grain Support Mechanisms (in Japanese). IPS Japan SIC Reports, Vol.89, No.60, ARC-77-12, pp. 91-98 (Jul. 1989).
• 3: Matsumoto, T. et al.: A Mechanism for Integrating Communication and Synchroniza~on using Snoopy Cache (in Japanese). IEICE Japan SIG Report, Vol.90, No.144, CPSY 90-42, pp. 25-30 (Jul. 1990).
• 4: Takashi Matsumoto, Efficient execution of fine-grain parallelism on a tightly-coupled multiprocessor, Journal of Information Processing, v.15 n.3, p.475-484, 1992
• 5: Matsumoto, T., et al.: MISC: A Mechanism for Integrated Synchronization and Commun~ation U~ng Snoop Caches. Proc. of the 1991 Int. Conf. on Parallel Proces~n~ Vol. 1, pp. 161-170 (Aug. 1991).
• 6: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 7: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 8: Advanced Micro Devices, Inc.: Am29000 32-Bit S~eam~ned Ins{ruction Processor Users Manual Advanced Micro Devices, Inc., 1988.
• 9: Harry F. Jordan, Performance measurements on HEP - a pipelined MIMD computer, Proceedings of the 10th annual international symposium on Computer architecture, p.207-212, June 13-17, 1983, Stockholm, Sweden
• 10: Arvind , Robert A. Iannucci, A critique of multiprocessing von Neumann style, Proceedings of the 10th annual international symposium on Computer architecture, p.426-436, June 13-17, 1983, Stockholm, Sweden
• 11: NEC Co~p.: ~PD30300 (VR3000) 32 bit Microprocessor User~ Manual-Architecture-(in Japanese). NEC Corp. ( 19 89).
• 12: P. Sweazey , A. J. Smith, A class of compatible cache consistency protocols and their support by the IEEE futurebus, Proceedings of the 13th annual international symposium on Computer architecture, p.414-423, June 02-05, 1986, Tokyo, Japan
• 13: Midkiff, S. P. and Padua, D. A.: Compiler Generated Synchronization for Do Loops. Proc. 1986 Int. Conf. on Parallel Processin~ pp. 544-551 (Aug. 1986).
• 14: Torrellas, J., et al.: Measurement, Analysis and ~mprovement of the Cache Behavior of Shared Data in Coherent Mulhprocessors, Technical Report CSL-TR- 90-412, Stanford Univ., (Feb. 1990).
• 15: Jones, A. K. and Gehringer, E. F.: The Cm* Multiprocessor Project: Research Rev~w. Technical Report CMU-CS-80-131, Carnegie-Mellon Univ., (1980).
• 16: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 17: Li, K.: IVY: A Shared Virtual Memory System for Parariel Computing. Proc. t988 Int. Conf. on ParaHel Processin9, St. Char~, IL, pp. 94-101 (Aug. 1988).
• 18: Lenoski, D., et al.: Design of Stanford DASH Multiprocessor. Technical Report CSL-TR-89-403, Stanibrd Univ. (Dec. 1989).
• 19: Matsumoto, T.: A Multiprocessor System with Memory-Based Processors and Register-Based Processors (in Japanese). Proc. of 43th Annual Convention of IPS Japan, Vol.6, 6Q-3, pp.115-116 (Oct. 1991).
• 20: Matsumoto, T." and Hiraki, K.: A Shared-Memory Architecture for Massively Parallel Computer Systems (in Japanese). IEICE Japan SIC Reports, Vol.92 No.173, CPSY 92-26, pp.47-55 (Aug. 1992).
• 21: Matsumoto, T. and Hiraki, K.: Distributed Shared- Memory Architecture Using Memory-Based Processors (in Japanese). Proc. of Joint Syrup. on Parallel Processing '93, IPSJ/IEICE/JSSST (May 1993).
• 22: Matsumoto, T.: A Study of FGSM: Fine-Grain Support Multiprocessor (in Japanese). IEICE Japan SIC Reports, Vol.89 No.167, CPSY 89-37, pp. 37-42 (Aug. 1989).

INDEX TERMS

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

Additional Classification:
  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.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Performance