More Web Proxy on the site http://driver.im/

research-article

Location Consistency-A New Memory Model and Cache Consistency Protocol

Authors:

Vivek SarkarAuthors Info & Claims

IEEE Transactions on Computers, Volume 49, Issue 8

Pages 798 - 813

https://doi.org/10.1109/12.868026

Published: 01 August 2000 Publication History

Abstract

Existing memory models and cache consistency protocols assume the memory coherence property which requires that all processors observe the same ordering of write operations to the same location. In this paper, we address the problem of defining a memory model that does not rely on the memory coherence assumption and also the problem of designing a cache consistency protocol based on such a memory model. We define a new memory consistency model, called Location Consistency (LC), in which the state of a memory location is modeled as a partially ordered multiset (pomset) of write and synchronization operations. We prove that LC is strictly weaker than existing memory models, but is still equivalent to stronger models for the common case of parallel programs that have no data races. We also describe a new multiprocessor cache consistency protocol based on the LC memory model. We prove that this LC protocol obeys the LC memory model. The LC protocol does not need to enforce single write ownership of memory blocks. As a result, the LC protocol is simpler and more scalable than existing snooping and directory-based cache consistency protocols.

References

[1]

S.V. Adve and M.D. Hill, “A Unified Formalization of Four Shared-Memory Models,” IEEE Trans. Parallel and Distributed Systems, vol. 3, pp. 613-624, June 1993.

Digital Library

[2]

B. Bershad M. Zekauskas and W. Sawdon, “The Midway Distributed Shared Memory System,” Proc. IEEE COMPCON, 1993.

[3]

R.D. Blumofe M. Frigo C.F. Joerg C.E. Leiserson and K.H. Randall, “An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms,” Proc. Eighth Ann. ACM Symp. Parallel Algorithms and Architectures, pp. 297-308, June 1996.

Digital Library

[4]

P.B. Hansen, “The Programming Language Concurrent Pascal,” IEEE Trans. Software Eng., vol. 1, no. 2, pp. 199-206, June 1975.

Digital Library

[5]

J.B. Carter J.K. Bennett and W. Zwaenepoel, “Implementation and Performance of Munin,” Proc. 13th ACM Symp. Operating Systems Principles, pp. 152-164, Oct. 1991. Operating Systems Review, vol. 25, no. 5, 1991.

Digital Library

[6]

D.E. Culler and J.P. Singh, Parallel Computer Architecture. first ed. Morgan Kaufmann, 1999.

Digital Library

[7]

F. Darema D.A. George V.A. Norton and G.F. Pfister, “A Single-Program-Multiple-Data Computational Model for EPEX/FORTRAN,” Parallel Computing, vol. 7, pp. 11-24, Apr. 1988.

[8]

Java in a Nutshell, Paula Ferguson, ed. Sebastopol, Calif.: O'Reilly & Associates, 1996.

[9]

J. Ferrante K.J. Ottenstein and J.D. Warren, “The Program Dependence Graph and Its Use in Optimization,” ACM Trans. Programming Languages and Systems, vol. 9, no. 3, pp. 319-349, July 1987.

Digital Library

[10]

M. Frigo, “The Weakest Reasonable Memory Model,” master's thesis, Massachusetts Inst. of Technology, 1998.

[11]

G.R. Gao and V. Sarkar, “Location Consistency: Stepping beyond the Barriers of Memory Coherence and Serializability,” ACAPS Technical Memo 78, School of Computer Science, McGill Univ., Montréal, Québec, Canada, Dec. 1993, revised Dec. 1994.

[12]

G.R. Gao and V. Sarkar, “Location Consistency: Stepping beyond Memory Coherence Barrier,” Proc. 1995 Int'l Conf. Parallel Processing, vol. II, pp. 73-76, Aug. 1995.

[13]

G.R. Gao and V. Sarkar, “On the Importance of an End-to-End View of Memory Consistency in Future Computer Systems,” Proc. Int'l Symp. High Performance Computing, pp. 30-41, 1997.

Digital Library

[14]

K. Gharachorloo D. Lenoski J. Laudon P. Gibbons A. Gupta and J. Hennessy, “Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors,” Proc. 17th Ann. Int'l Symp. Computer Architecture, pp. 15-26, May 1990.

Digital Library

[15]

J.L. Hennessy and D.A. Patterson, Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 1990.

Digital Library

[16]

J.L. Hennessy and D.A. Patterson, Computer Architecture: A Quantitative Approach, second ed. Morgan Kaufmann, 1996.

Digital Library

[17]

A.H. Karp and V. Sarkar, “Data Merging for Shared-Memory Multiprocessors,” Proc. 26th Hawaii Int'l Conf. System Sciences, Volume I (Architecture), pp. 244-256, Jan. 1993.

[18]

P. Keleher A.L. Cox and W. Zwaenepoel, “Lazy Release Consistency for Software Distributed Shared Memory,” Proc. 19th Ann. Int'l Symp. Computer Architecture, pp. 13-21, May 1992.

Digital Library

[19]

L. Lamport, “How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs,” IEEE Trans. Computers, vol. 28, no. 9, pp. 690-691, Sept. 1979.

Digital Library

[20]

D. Lenoski K. Gharachorloo J. Laudon A. Gupta J. Hennessy M. Horowitz and M. Lam, “Design of Scalable Shared-Memory Multiprocessors: The DASH Approach,” Digest of Papers, 35th IEEE Computer Society Int'l Conf., COMPCON Spring '90, pp. 62-67, Feb.-Mar. 1990.

[21]

S. Merali, “Designing and Implementing Memory Consistency Models for Shared-Memory Multiprocessors,” master's thesis, McGill Univ., Montréal, Québec, Canada, Apr. 1996.

[22]

W. Pugh, “The Java Memory Model,” http://www.cs.umd.edu/~pugh/java/memoryModel, 1999.

[23]

V. Sarkar, “A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs,” Proc. Fifth Int'l Workshop Languages and Compilers for Parallel Computing, pp. 16-30, Aug. 1992.

Digital Library

[24]

A.C. Shaw, The Logical Design of Operating Systems. Prentice Hall, 1974.

Digital Library

[25]

P. Tang and P.-C. Yew, “Processor Self-Scheduling for Multiple-Nested Parallel Loops,” Proc. 1986 Int'l Conf. Parallel Processing, Feb. 1986.

Cited By

Ranganath KFiroz JSuetterlein JManzano JMarquez ARaugas MWong D(2021)LC-MEMENTO: A Memory Model for Accelerated ArchitecturesLanguages and Compilers for Parallel Computing10.1007/978-3-030-99372-6_5(67-82)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-99372-6_5
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
Qu PYan JGao G(2016)Toward a Parallel Turing Machine ModelNetwork and Parallel Computing10.1007/978-3-319-47099-3_16(191-204)Online publication date: 28-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-319-47099-3_16
Show More Cited By

Index Terms

Location Consistency-A New Memory Model and Cache Consistency Protocol

Recommendations

A lock-based cache coherence protocol for scope consistency
Abstract
Directory protocols are widely adopted to maintain cache coherence of distributed shared memory multiprocessors. Although scalable to a certain extent, directory protocols are complex enough to prevent it from being used in very large scale ...
A Primer on Memory Consistency and Cache Coherence
Efficient sequential consistency using conditional fences
PACT '10: Proceedings of the 19th international conference on Parallel architectures and compilation techniques

Among the various memory consistency models, the sequential consistency (SC) model, in which memory operations appear to take place in the order specified by the program, is the most intuitive and enables programmers to reason about their parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 49, Issue 8

August 2000

95 pages

ISSN:0018-9340

Editor:
Jean-Luc Gaudiot
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Copyright © Copyright © 2000 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 August 2000

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ranganath KFiroz JSuetterlein JManzano JMarquez ARaugas MWong D(2021)LC-MEMENTO: A Memory Model for Accelerated ArchitecturesLanguages and Compilers for Parallel Computing10.1007/978-3-030-99372-6_5(67-82)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-99372-6_5
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
Qu PYan JGao G(2016)Toward a Parallel Turing Machine ModelNetwork and Parallel Computing10.1007/978-3-319-47099-3_16(191-204)Online publication date: 28-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-319-47099-3_16
Chavarría-Miranda DManzano JKrishnamoorthy SVishnu ABarker KHoisie A(2014)SCaLeMProceedings of the 20 Years of Beowulf Workshop on Honor of Thomas Sterling's 65th Birthday10.1145/2737909.2737910(34-43)Online publication date: 13-Oct-2014
https://dl.acm.org/doi/10.1145/2737909.2737910
Giorgi RBadia RBodin FCohen AEvripidou PFaraboschi PFechner BGao GGarbade AGayatri RGirbal SGoodman DKhan BKoliaï SLandwehr JLê NLi FLujàn MMendelson AMorin LNavarro NPatejko TPop ATrancoso PUngerer TWatson IWeis SZuckerman SValero M(2014)TERAFLUXMicroprocessors & Microsystems10.1016/j.micpro.2014.04.00138:8(976-990)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.micpro.2014.04.001
Barik RZhao JSarkar VFensch CO'Boyle MSeznec ABodin F(2013)Interprocedural strength reduction of critical sections in explicitly-parallel programsProceedings of the 22nd international conference on Parallel architectures and compilation techniques10.5555/2523721.2523729(29-40)Online publication date: 7-Oct-2013
https://dl.acm.org/doi/10.5555/2523721.2523729
Wang CWu Y(2013)TSO_ATOMICITYACM SIGPLAN Notices10.1145/2499368.245117248:4(509-520)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451172
Wang CWu Y(2013)TSO_ATOMICITYACM SIGARCH Computer Architecture News10.1145/2490301.245117241:1(509-520)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2490301.2451172
Wang CWu YSarkar VBodik R(2013)TSO_ATOMICITYProceedings of the eighteenth international conference on Architectural support for programming languages and operating systems10.1145/2451116.2451172(509-520)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2451116.2451172
Nandivada VShirako JZhao JSarkar V(2013)A Transformation Framework for Optimizing Task-Parallel ProgramsACM Transactions on Programming Languages and Systems10.1145/2450136.245013835:1(1-48)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1145/2450136.2450138
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents