Correct memory operation of cache-based multiprocessors

ABSTRACT

This paper shows that cache coherence protocols can implement indivisible synchronization primitives reliably and can also enforce sequential consistency. Sequential consistency provides a commonly accepted model of behavior of multiprocessors. We derive a simple set of conditions needed to enforce sequential consistency in multiprocessors. These conditions are easily applied to prove the correctness of existing cache coherence protocols that rely on one or multiple broadcast buses to enforce atomicity of updates; in these protocols, all processing elements must be connected to the broadcast buses. The conditions are also used in this paper to establish new protocols which do not rely on the atomicity of updates and therefore do not require single access buses to propagate invalidations or to perform distributed WRITEs. It is also shown how such protocols can implement atomic READ&MODIFY operations for synchronization purposes.

REFERENCES

• 1: L.M. Censier and P. Feautrier,"A New Solution to Coherence Problems in Multicache Systems," IEEE Transactions on Computers, Vol. C-27, No.12, December 1978, pp. 1112- 1118.
• 2: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 3: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 4: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 5: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• 6: 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]
• 7: 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
• 8: P. Bitar , A. M. Despain, Multiprocessor cache synchronization: issues, innovations, evolution, Proceedings of the 13th annual international symposium on Computer architecture, p.424-433, June 02-05, 1986, Tokyo, Japan
• 9: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 10: S.J. Frank, "Synapse Tightly Coupled Multiprocessors - A New Approach that Solves Old Problems," Proceedings of NCC, Los Vegas, 1984.
• 11: Mark Hill , Susan Eggers , Jim Larus , George Taylor , Glenn Adams , B. K. Bose , Garth Gibson , Paul Hansen , Jon Keller , Shing Kong , Corinna Lee , Daebum Lee , Joan Pendleton , Scott Ritchie , David Wood , Ben Zorn , Paul Hilfinger , Dave Hodges , Randy Katz , John Ousterhout , Dave Patterson, Design decisions in SPUR, Computer, v.19 n.11, p.8-22, Nov. 1986 [doi>10.1109/MC.1986.1663096]
• 12: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 13: H.T. Kung, "Synchronized and Asynchronous Parallel Algorithms for multiprocessors," in Algorithms and Complexity: New Directions and Recent Results, J.F. Traub Ed., New York: Academic Press, 1976.
• 14: Gerard Maurice Baudet, The design and analysis of algorithms for asynchronous multiprocessors., 1978
• 15: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 16: L. Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," IEEE Transactions on Computers, Vol. C-28, No. 9, September 1979, pp. 690-691.
• 17: W. W. Collier, "Reasoning about Parallel Architectures", submitted to JACM, 1985.
• 18: P. M. Vitanzi and B. Auerbach, "Atomic Shared Register Access by Asynchronous Hardware," Conference on the Foundations of Computer Sciences, 1986.
• 19: M. Dubois and C. Scheurich, "Dependency and Hazard Resolution in Multiprocessors," submitted to IEEE Transactions on Software Engineering. Also, Univ. of Southern Cal. Technical Report CRI 86-20.
• 20: M. Dubois and F.A. Briggs, "Effects of Cache Coherency in Multiprocessors," IEEE Transactions on Computers, Vol. C-31, No.11, November 1982.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization

  K. Computing Milieux
  K.1 THE COMPUTER INDUSTRY
      Subjects: Standards

General Terms:
Design, Performance, Standardization