Lazy release consistency for hardware-coherent multiprocessors

ABSTRACT

Release consistency is a widely accepted memory model for distributed shared memory systems. Eager release consistency represents the state of the art in release consistent protocols for hardware-coherent multiprocessors, while lazy release consistency has been shown to provide better performance for software distributed shared memory (DSM). Several of the optimizations performed by lazy protocols have the potential to improve the performance of hardware-coherent multiprocessors as well, but their complexity has precluded a hardware implementation. With the advent of programmable protocol processors it may become possible to use them after all. We present and evaluate a lazy release-consistent protocol suitable for machines with dedicated protocol processors. This protocol admits multiple concurrent writers, sends write notices concurrently with computation, and delays invalidations until acquire operations. We also consider a lazier protocol that delays sending write notices until release operations. Our results indicate that the first protocol outperforms eager release consistency by as much as 20% across a variety of applications. The lazier protocol, on the other hand, is unable to recoup its high synchronization overhead. This represents a qualitative shift from the DSM world, where lazier protocols always yield performance improvements. Based on our results, we conclude that machines with flexible hardware support for coherence should use protocols based on lazy release consistency, but in a less ''aggressively lazy'' form than is appropriate for DSM.

REFERENCES

• 1: S. V. Adve , J. K. Aggarwal, A Unified Formalization of Four Shared-Memory Models, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.613-624, June 1993 [doi>10.1109/71.242161]
• 2: Ricardo Bianchini , Thomas J. LeBlanc, Can High Bandwidth and Latency Justify Large Cache Blocks in Scalable Multiprocessors?, University of Rochester, Rochester, NY, 1994
• 3: R. Bianchini , L. Kontothanassis, Algorithms for categorizing multiprocessor communication under invalidate and update-based coherence protocols, Proceedings of the 28th Annual Simulation Symposium, p.115, April 25-28, 1995
• 4: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 5: K. Dackland, E. Elmroth, B. Kagstrom, and C. V. Loan. Parallel Block Matrix Factorizations on the Shared-Memory Multiprocessor IBM 3090 VF/600J. The International Journal of Supercomputer Applications, 6(1):69--97, Spring 1992.
• 6: Michel, Dubois , Christoph Scheurich , Fayé A. Briggs, Synchronization, Coherence, and Event Ordering in Multiprocessors, Computer, v.21 n.2, p.9-21, February 1988 [doi>10.1109/2.15]
• 7: Michel Dubois , Jin Chin Wang , Luiz A. Barroso , Kangwoo Lee , Yung-Syau Chen, Delayed consistency and its effects on the miss rate of parallel programs, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.197-206, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125941]
• 8: Michel Dubois , Jonas Skeppstedt , Livio Ricciulli , Krishnan Ramamurthy , Per Stenström, The detection and elimination of useless misses in multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.88-97, May 16-19, 1993, San Diego, California, United States
• 9: S. J. Eggers and T. E. Jeremiassen. Eliminating False Sharing. In Proceedings of the 1991 International Conference on Parallel Processing, pages I:377--381, St. Charles, IL, August 1991.
• 10: 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
• 11: K. Gharachorloo, S. V. Adve, A. Gupta, J. L. Hennessy, and M. D. Hill. Programming for Different Memory Consistency Models. Journal of Parallel and Distributed Computing, 15:399--407, 1992.
• 12: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 13: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 14: P. Keleher, A. L. Cox, S. Dwarkadas, and W. Zwaenepoel. TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems. In Proceedings of the USENIX Winter '94 Technical Conference, San Francisco, CA, January 1994.
• 15: L. I. Kontothanassis , M. L. Scott, Software cache coherence for large scale multiprocessors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.286, January 22-25, 1995
• 16: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• 17: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 18: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 19: K. Petersen and K. Li. Cache Coherence for Shared Memory Multiprocessors Based on Virtual Memory Support. In Proceedings of the Seventh International Parallel Processing Symposium, Newport Beach, CA, April 1993.
• 20: S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
• 21: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 22: Jonas Skeppstedt , Per Stenström, Simple compiler algorithms to reduce ownership overhead in cache coherence protocols, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.286-296, October 05-07, 1994, San Jose, California, United States
• 23: Jack E. Veenstra , Robert J. Fowler, MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.201-207, January 31-February 02, 1994

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

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

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Performance

Keywords:
Cache Coherence, Lazy Release Consistency, Protocol Processors, Shared Memory