Article

Free access

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

Authors:

Roy FriedmanAuthors Info & Claims

STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

Pages 679 - 690

https://doi.org/10.1145/129712.129778

Published: 01 July 1992 Publication History

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 and M. Merritt, "A Lazy Cache Algorithm," Proc. of the 1989 A CM Symposium On Parallel Algorithms and Architectures, June 1989, pp. 209-222.

Digital Library

[2]

M. Ahamad, J. Burns, P. Hutto, and G. Neiger, "Causal Memory," 5th international Workshop on Distributed Algorithms, October 1991.

Digital Library

[3]

S. Adve and M. Hill, "Weak Ordering---A New Definition," Proc. 17th International Symposium on Computer Architecture, May 1990, pp. 2-14.

Digital Library

[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]

H. Attiya and J. Welch, "Sequential Consistency versus Linearizability," Proc. 3rd A CM Symp. on Parallel Algorithms and Architectures, July 1991, pp. 304-315. Also: Technical Report #674, Department of Computer Science, The Technion, October 1991.

Digital Library

[7]

J. Bennett, J. Carter, and W. Zwaenepoel, "Munin: Distributed Shared Memory Based on Type-Specific Memory Coherence," Proc. 2nd A CM Syrup. on Principle8 and Practice of Parallel Processing, 1990, pp. 168-176.

Digital Library

[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.

Digital Library

[11]

W. W. Collier, "Architectures for Systems of Parallel Processes," IBM TR 00.3253, Poughkeepsie, NY, January 1984.

[12]

E. W. Dijkstra, "A Solution of a Problem in Concurrent Programming Control," Communications of the A CM, Vol. 8, No. 9, September 1965, pp. 569.

Digital Library

[13]

M. Dubois and C. Scheurich, "Memory Access Dependencies in Shared-Memory Multiprocessors", IEEE Trans. on Software Engineering, vol. 16, no. 6 (June 1990), pp. 660-673.

Digital Library

[14]

M. Dubois, C. Seheurieh, and F. A. Briggs, "Memory Access Buffering in Multiproeessors," Proc. 13th Int. Syrup. on Computer Architecture, June 1986, pp. 434-442.

Digital Library

[15]

M. Dubois, C. Scheurich, and F. A. Briggs, "Synchronization, Coherence and Event Ordering in Multiprocessors," IEEE Computer, vol. 21, no. 2, pp. 9-21.

Digital Library

[16]

K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta and J. Hennessey, "Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors," Proc. 17th int. Syrup. on Computer Architecture, 1990, pp. 15-26.

Digital Library

[17]

P. Gibbons, M. Merritt and K. Gharachor- 1oo, "Proving Sequential Consistency of High- Performance Shared Memories," the 3rd A CM Syrup. on Parallel Algorithms and Architectures, July 1991, pp. 292-303.

Digital Library

[18]

R. J. Goodman, "Cache Consistency and Sequential Consistency," Computer Science Technical Report #1006, University of Wisconsin, Madison, February 1991.

[19]

M. Herlihy, "Randomized Wait-Free Concurrent Objects," Proc. 10th A CM Syrup. on Principles of Distributed Computing, 1991, pp. 11-21.

Digital Library

[20]

M. Herlihy and J. Wing, "Linearizability: A Correctness Condition for Concurrent Objects," A CM Trans. on Programming Languages and Systems, Vol. 12, No. 3, pp. 463-492.

Digital Library

[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.

Digital Library

[23]

K. Li and P. Hudak, "Memory Coherence in Shared Virtual Memory Systems," A CM Trans. on Computer Systems, Vol. 7, No. 4, pp. 321- 359.

Digital Library

[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, Algorithms for Mutual Exclusion, MIT Press, 1986.

Digital Library

[29]

C. Scheurich and M. Dubois, "Correct Memory Operation of Cache-Based Multiprocessors," Proc. l#th International Syrup. on Computer Architecture, 1987, pp. 234-243.

Digital Library

[30]

D. Shasha and M. Snir, "Correct and Efficient Execution of Parallel Programs that Share Memory," A CM Trans. on Programmin9 Languages and Systems, Vol. 10, No. 2, April 1988, pp. 282- 312.

Digital Library

Cited By

Liu YGuan XVlassov VHaridi S(2017)MeteorShower: Minimizing Request Latency for Majority Quorum-Based Data Consistency Algorithms in Multiple Data Centers2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2017.112(57-67)Online publication date: Jun-2017
https://doi.org/10.1109/ICDCS.2017.112
Viotti PVukolić M(2016)Consistency in Non-Transactional Distributed Storage SystemsACM Computing Surveys10.1145/292696549:1(1-34)Online publication date: 29-Jun-2016
https://dl.acm.org/doi/10.1145/2926965
Tipparaju VVetter JFeo JFaraboschi PVilla O(2012)GA-GPUProceedings of the 9th conference on Computing Frontiers10.1145/2212908.2212918(53-64)Online publication date: 15-May-2012
https://dl.acm.org/doi/10.1145/2212908.2212918
Show More Cited By

Index Terms

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

Recommendations

A Correctness Condition for High-Performance Multiprocessors

Hybrid consistency, a 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 ...
Imposing minimal memory ordering on multiprocessors
General Properties of Quantum Bit Commitments (Extended Abstract)
Advances in Cryptology – ASIACRYPT 2022
Abstract
While unconditionally-secure quantum bit commitment (allowing both quantum computation and communication) is impossible, researchers turn to study the complexity-based one, a.k.a. computational quantum bit commitment. A computational canonical (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

July 1992

794 pages

ISBN:0897915119

DOI:10.1145/129712

Chairmen:
Rao Kosaraju
Johns Hopkins Univ., Baltimore, MD
,
Mike Fellows
Univ. of Victoria, Victoria, BC, Canada
,
Avi Wigderson
Hebrew University; Princeton Univ., Princeton, NJ
,
John Ellis
Univ. of Victoria, Victoria, BC, Canada

Copyright © 1992 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC92

Sponsor:

SIGACT

STOC92: 24th Annual ACM Symposium on the Theory of Computing 1992

May 4 - 6, 1992

British Columbia, Victoria, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
317
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YGuan XVlassov VHaridi S(2017)MeteorShower: Minimizing Request Latency for Majority Quorum-Based Data Consistency Algorithms in Multiple Data Centers2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2017.112(57-67)Online publication date: Jun-2017
https://doi.org/10.1109/ICDCS.2017.112
Viotti PVukolić M(2016)Consistency in Non-Transactional Distributed Storage SystemsACM Computing Surveys10.1145/292696549:1(1-34)Online publication date: 29-Jun-2016
https://dl.acm.org/doi/10.1145/2926965
Tipparaju VVetter JFeo JFaraboschi PVilla O(2012)GA-GPUProceedings of the 9th conference on Computing Frontiers10.1145/2212908.2212918(53-64)Online publication date: 15-May-2012
https://dl.acm.org/doi/10.1145/2212908.2212918
Serafini MDobre DMajuntke MBokor PSuri NRicha AGuerraoui R(2010)Eventually linearizable shared objectsProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835723(95-104)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835723
Tipparaju VGropp WRitzdorf HThakur RTraff J(2009)Investigating High Performance RMA Interfaces for the MPI-3 StandardProceedings of the 2009 International Conference on Parallel Processing10.1109/ICPP.2009.54(293-300)Online publication date: 22-Sep-2009
https://dl.acm.org/doi/10.1109/ICPP.2009.54
Jiménez EFernández ACholvi V(2008)A parametrized algorithm that implements sequential, causal, and cache memory consistenciesJournal of Systems and Software10.1016/j.jss.2007.03.01281:1(120-131)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1016/j.jss.2007.03.012
Haldar SVidyasankar K(2007)On specification of Read/Write shared variablesJournal of the ACM10.1145/1314690.131469554:6(31-es)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1145/1314690.1314695
Higham LJackson LKawash J(2007)Specifying memory consistency of write buffer multiprocessorsACM Transactions on Computer Systems10.1145/1189736.118973725:1(1-es)Online publication date: 1-Feb-2007
https://dl.acm.org/doi/10.1145/1189736.1189737
Fajstrup LRaußen MGoubault E(2006)Algebraic topology and concurrencyTheoretical Computer Science10.1016/j.tcs.2006.03.022357:1(241-278)Online publication date: 25-Jul-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.03.022
Lee HWelch J(2005)Randomized registers and iterative algorithmsDistributed Computing10.1007/s00446-004-0106-317:3(209-221)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1007/s00446-004-0106-3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents