A correctness condition for high-performance multiprocessors (extended abstract)

ABSTRACT

Hybrid consistency, a new consistency condition for shared memory multiprocessors, attempts to capture the guarantees provided by contemporary high-performance architectures. It combines the expressiveness of strong consistency conditions(e.g., sequential consistency, linearizability) and the efficiency of weak consistency conditions (e.g., Pipelined RAM, causal memory). Memory access operations are classified either strong or weak. A global ordering of strong operations at different processes is guaranteed, but there is very little guarantee on the ordering of weak operations at different processes, except for what is implied by their interleaving with the strong operations. A formal and precise definition of this condition is given. An efficient implementation of hybrid consistency on distributed memory machines is presented. In this implementation, weak opearations are executed instantaneously, while the response time for strong operations is linear in the network delay. (It is proven that this is within a constant factor of the optimal time bounds.) To motivate hybrid consistency it is shown that weakly consistent memories do not support non-cooperative (in particular, non-centralized) algorithms for mutual exclusion.

REFERENCES

• 1: Y. Afek , G. Brown , M. Merritt, A lazy cache algorithm, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.209-222, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72958]
• 2: Mustaque Ahamad , James E. Burns , Phillip W. Hutto , Gil Neiger, Causal Memory, Proceedings of the 5th International Workshop on Distributed Algorithms, p.9-30, October 07-09, 1991
• 3: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 4: M. Ahamad, P. Hutto, and R. John, Implementing and Programming Causal Distributed Shared Memory, Tit GIT-CC-90-49, Georgia Inst. of Tech., December 1990.
• 5: H. Attiya and R. Friedman, A Correctness Condition for High-Performance Multiprocessors, Technical Report #719, Department of Computer Science, The Technion.
• 6: Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.304-315, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113407]
• 7: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 8: R. Bisiani, A. Nowatzyk, and M. Ravishankar, "Coherent Shared Memory on a Distributed Memory Machine," Proc. Internation Conf. on Parallel Processing, 1989, pp. 1-133-141.
• 9: W. Brantley, K. MeAuliffe, and J. Weiss, "RP3 Processor-Memory Element," Proc. Internation Conf. on Parallel Processing, 1985, pp. 782-789.
• 10: L. M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Trans. on Computers, vol. C-27, no. 12, pp. 1112-1118.
• 11: W. W. Collier, "Architectures for Systems of Parallel Processes," IBM TR 00.3253, Poughkeepsie, NY, January 1984.
• 12: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 13: Michel Dubois , Christoph Scheurich, Memory Access Dependencies in Shared-Memory Multiprocessors, IEEE Transactions on Software Engineering, v.16 n.6, p.660-673, June 1990 [doi>10.1109/32.55094]
• 14: 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
• 15: 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]
• 16: 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
• 17: Phillip B. Gibbons , Michael Merritt , Kourosh Gharachorloo, Proving sequential consistency of high-performance shared memories (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.292-303, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113406]
• 18: R. J. Goodman, "Cache Consistency and Sequential Consistency," Computer Science Technical Report #1006, University of Wisconsin, Madison, February 1991.
• 19: Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112602]
• 20: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 21: P. Hutto and M. Ahamad, Slow Memory: Weakening Consistency to Enhance Concurrency in Distributed Shared Memories, TR GIT-ICS- 89/39, Georgia Inst. of Tech., October 1989.
• 22: L. Lamport, "How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs," IEEE Trans. on Computers, vol. C- 28, no. 9, pp. 690-691.
• 23: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 24: R. Lipton and J. Sandberg, PRAM: A Scalable Shared Memory, TR CS-TR-180-88, Princeton University, September 1988.
• 25: S. Min and J. Baer, "A Timestamp-Based Cache Coherence Scheme," Proc. International Conf. on Parallel Processing, 1989, pp. 1-23-32.
• 26: G. L. Peterson. "Myths About The Mutual Exclusion Problem," Information Processing Letters, Vol. 12, No. 3, June 1981, pp. 115-116.
• 27: U. Ramachandran, M. Ahamad, and M. Y. Khalidi, "Coherence of Distributed Shared Memory: Unifying Synchronization and Data Transfer," Proc. International Conf. on Parallel Processing, 1989, pp. II- 160-169.
• 28: M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
• 29: C. Scheurich , M. Dubois, Correct memory operation of cache-based multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.234-243, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30377]
• 30: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Performance, Theory