多处理器环境下存储模型与缓存一致性协议详解

需积分: 13 2 浏览量更新于2024-07-24 1 收藏 4.1MB PDF 举报

在多处理器环境下，存储模型与缓存一致性协议是计算机系统设计中的关键组成部分，旨在确保在分布式内存系统中，多个处理器对共享数据的一致性视图。这些协议的主要目标是减少竞态条件和数据不一致，提高系统的并发性能和可靠性。首先，我们需要理解存储模型。在多处理器系统中，常见的存储模型有单一全局地址空间（Single-Global-Address-Space, SGAS）、分布共享内存（Shared-Distributed-Memory, SDM）以及虚拟内存模型（Virtual Memory Model）。SGAS允许所有处理器访问同一物理内存，而SDM则划分了局部内存区域，通过缓存一致性协议协调不同处理器对内存的访问。虚拟内存模型则是通过页表和缓存映射来隐藏底层物理内存的细节。缓存一致性协议是实现这种一致性的重要手段。常见的协议有目录式协议（Directory-Based Protocols）、总线仲裁协议（Bus Arbiter Protocols）、目录映射协议（Directory Mapping Protocols）和MESI（Modified, Exclusive, Shared, Invalidated）等。目录式协议如MESI维护了一个状态机，记录每个缓存块的状态，通过更新状态来同步缓存；总线仲裁协议则通过硬件机制控制缓存之间的通信，避免冲突；目录映射协议利用目录记录块的位置，简化一致性管理。并发验证是评估这些协议效能的关键部分。它涉及到并发程序执行时的数据一致性检查，包括读-写冲突检测、缓存污染（Dirty Caching）和缓存穿透（Cache Misses）等问题。高效的缓存一致性协议应能减少这些并发问题的发生，同时保持较低的开销，不影响系统的整体性能。例如，"A Primer on Memory Consistency and Cache Coherence" 一书中，作者Daniel J. Sorin、Mark D. Hill和David A. Wood深入探讨了这些概念和技术，提供了实用的工具、技术和应用案例。其他著作如"Dynamic Binary Modification: Tools, Techniques, and Applications" 和 "Quantum Computing for Computer Architects, Second Edition" 也涉及到了与存储模型和缓存一致性相关的主题，但可能更侧重于其他领域的技术进展。研究和理解存储模型与缓存一致性协议对于构建高性能、可扩展的并行和分布式系统至关重要，这涵盖了从理论设计到实际应用的方方面面。掌握这些概念和技术有助于优化系统性能，减少故障，并为未来的计算机架构设计提供坚实的基础。

C H A P T E R 1

Many modern computer systems and most multicore chips (chip multiprocessors) support shared

memory in hardware. In a shared memory system, each of the processor cores may read and write to

a single shared address space. These designs seek various goodness properties, such as high perfor-

mance, low power, and low cost. Of course, it is not valuable to provide these goodness properties

without ﬁrst providing correctness. Correct shared memory seems intuitive at a hand-wave level,

but, as this lecture will help show, there are subtle issues in even deﬁning what it means for a shared

memory system to be correct, as well as many subtle corner cases in designing a correct shared

memory implementation. Moreover, these subtleties must be mastered in hardware implementa-

tions where bug ﬁxes are expensive. Even academics should master these subtleties to make it more

likely that their proposed designs will work.

We and many others ﬁnd it useful to separate shared memory correctness into two sub-issues:

consistency and coherence. Computer systems are not required to make this separation, but we ﬁnd

it helps to divide and conquer complex problems, and this separation prevails in many real shared

memory implementations.

It is the job of consistency (memory consistency, memory consistency model, or memory

model) to deﬁne shared memory correctness. Consistency deﬁnitions provide rules about loads and

stores (or memory reads and writes) and how they act upon memory. Ideally, consistency deﬁnitions

would be simple and easy to understand. However, deﬁning what it means for shared memory to

behave correctly is more subtle than deﬁning the correct behavior of, for example, a single-threaded

processor core. The correctness criterion for a single processor core partitions behavior between one

correct result and many incorrect alternatives. This is because the processor’s architecture mandates

that the execution of a thread transforms a given input state into a single well-deﬁned output state,

even on an out-of-order core. Shared memory consistency models, however, concern the loads and

stores of multiple threads and usually allow many correct executions while disallowing many (more)

incorrect ones. The possibility of multiple correct executions is due to the ISA allowing multiple

threads to execute concurrently, often with many possible legal interleavings of instructions from

Introduction to Consistency

and Coherence

2 A PRIMER ON MEMORY CONSISTENCY AND CACHE COHERENCE

different threads. The multitude of correct executions complicates the erstwhile simple challenge of

determining whether an execution is correct. Nevertheless, consistency must be mastered to imple-

ment shared memory and, in some cases, to write correct programs that use it.

Unlike consistency, coherence (or cache coherence) is neither visible to software nor required.

However, as part of supporting a consistency model, the vast majority of shared memory systems

implement a coherence protocol that provides coherence. Coherence seeks to make the caches of

a shared-memory system as functionally invisible as the caches in a single-core system. Correct

coherence ensures that a programmer cannot determine whether and where a system has caches by

analyzing the results of loads and stores. This is because correct coherence ensures that the caches

never enable new or different functional behavior (programmers may still be able to infer likely cache

structure using timing information).

In most systems, coherence protocols play an important role in providing consistency. Thus,

even though consistency is the ﬁrst major topic of this primer, we begin in Chapter 2 with a brief

introduction to coherence. The goal of this chapter is to explain enough about coherence to under-

stand how consistency models interact with coherent caches, but not to explore speciﬁc coherence

protocols or implementations, which are topics we defer until the second portion of this primer in

Chapters 6–9. In Chapter 2, we deﬁne coherence using the single-writer–multiple-reader (SWMR)

invariant. SWMR requires that, at any given time, a memory location is either cached for writing

(and reading) at one cache or cached only for reading at zero to many caches.

1.1 CONSISTENCY (A.K.A., MEMORY CONSISTENCY, MEMORY

CONSISTENCY MODEL, OR MEMORY MODEL)

Consistency models deﬁne correct shared memory behavior in terms of loads and stores (memory

reads and writes), without reference to caches or coherence. To gain some real-world intuition on

why we need consistency models, consider a university that posts its course schedule online. As-

sume that the Computer Architecture course is originally scheduled to be in Room 152. The day

before classes begin, the university registrar decides to move the class to Room 252. The registrar

sends an e-mail message asking the web site administrator to update the online schedule, and a few

minutes later, the registrar sends a text message to all registered students to check the newly updated

schedule. It is not hard to imagine a scenario—if, say, the web site administrator is too busy to post

the update immediately—in which a diligent student receives the text message, immediately checks

the online schedule, and still observes the (old) class location Room 152. Even though the online

schedule is eventually updated to Room 252 and the registrar performed the “writes” in the correct

order, this diligent student observed them in a different order and thus went to the wrong room. A

consistency model deﬁnes whether this behavior is correct (and thus whether a user must take other

INTRODUCTION TO CONSISTENCY AND COHERENCE 3

action to achieve the desired outcome) or incorrect (in which case the system must preclude these

reorderings).

Although this contrived example used multiple media, similar behavior can happen in shared

memory hardware with out-of-order processor cores, write buffers, prefetching, and multiple cache

banks. Thus, we need to deﬁne shared memory correctness—that is, which shared memory behav-

iors are allowed—so that programmers know what to expect and implementors know the limits to

what they can provide.

Shared memory correctness is speciﬁed by a memory consistency model or, more simply,

a memory model. The memory model speciﬁes the allowed behavior of multithreaded programs

executing with shared memory. For a multithreaded program executing with speciﬁc input data,

the memory model speciﬁes what values dynamic loads may return and what possible ﬁnal states of

the memory are. Unlike single-threaded execution, multiple correct behaviors are usually allowed,

making understanding memory consistency models subtle.

Chapter 3 introduces the concept of memory consistency models and presents sequential

consistency (SC), the strongest and most intuitive consistency model. The chapter begins by mo-

tivating the need to specify shared memory behavior and precisely deﬁnes what a memory con-

sistency model is. It next delves into the intuitive SC model, which states that a multithreaded

execution should look like an interleaving of the sequential executions of each constituent thread, as

if the threads were time-multiplexed on a single-core processor. Beyond this intuition, the chapter

formalizes SC and explores implementing SC with coherence in both simple and aggressive ways,

culminating with a MIPS R10000 case study.

In Chapter 4, we move beyond SC and focus on the memory consistency model implemented

by x86 and SPARC systems. This consistency model, called total store order (TSO), is motivated

by the desire to use ﬁrst-in–ﬁrst-out write buffers to hold the results of committed stores before

writing the results to the caches. This optimization violates SC, yet promises enough performance

beneﬁt to inspire architectures to deﬁne TSO, which permits this optimization. In this chapter, we

show how to formalize TSO from our SC formalization, how TSO affects implementations, and

how SC and TSO compare.

Finally, Chapter 5 introduces “relaxed” or “weak” memory consistency models. It motivates

these models by showing that most memory orderings in strong models are unnecessary. If a thread

updates ten data items and then a synchronization ﬂag, programmers usually do not care if the data

items are updated in order with respect to each other but only that all data items are updated before

the ﬂag is updated. Relaxed models seek to capture this increased ordering ﬂexibility to get higher

performance or a simpler implementation. After providing this motivation, the chapter develops

an example relaxed consistency model, called XC, wherein programmers get order only when they

4 A PRIMER ON MEMORY CONSISTENCY AND CACHE COHERENCE

ask for it with a FENCE instruction (e.g., a FENCE after the last data update but before the ﬂag

write). The chapter then extends the formalism of the previous two chapters to handle XC and

discusses how to implement XC (with considerable reordering between the cores and the coher-

ence protocol). The chapter then discusses a way in which many programmers can avoid thinking

about relaxed models directly: if they add enough FENCEs to ensure their program is data-race

free (DRF), then most relaxed models will appear SC. With “SC for DRF,” programmers can get

both the (relatively) simple correctness model of SC with the (relatively) higher performance of

XC. For those who want to reason more deeply, the chapter concludes by distinguishing acquires

from releases, discussing write atomicity and causality, pointing to commercial examples (including

an IBM Power case study), and touching upon high-level language models ( Java and C++).

Returning to the real-world consistency example of the class schedule, we can observe that

the combination of an email system, a human web administrator, and a text-messaging system rep-

resents an extremely weak consistency model. To prevent the problem of a diligent student going to

the wrong room, the university registrar needed to perform a FENCE operation after her email to

ensure that the online schedule was updated before sending the text message.

1.2 COHERENCE (A.K.A., CACHE COHERENCE)

Unless care is taken, a coherence problem can arise if multiple actors (e.g., multiple cores) have access

to multiple copies of a datum (e.g., in multiple caches) and at least one access is a write. Consider

an example that is similar to the memory consistency example. A student checks the online sched-

ule of courses, observes that the Computer Architecture course is being held in Room 152 (reads

the datum), and copies this information into her notebook (caches the datum). Subsequently, the

university registrar decides to move the class to Room 252 and updates the online schedule (writes

to the datum). The student’s copy of the datum is now stale, and we have an incoherent situation.

If she goes to Room 152, she will fail to ﬁnd her class. Examples of incoherence from the world

of computing, but not including computer architecture, include stale web caches and programmers

using un-updated code repositories.

Access to stale data (incoherence) is prevented using a coherence protocol, which is a set of

rules implemented by the distributed set of actors within a system. Coherence protocols come in

many variants but follow a few themes, as developed in Chapters 6–9.

Chapter 6 presents the big picture of cache coherence protocols and sets the stage for the

subsequent chapters on speciﬁc coherence protocols. This chapter covers issues shared by most co-

herence protocols, including the distributed operations of cache controllers and memory controllers

and the common MOESI coherence states: modiﬁed (M), owned (O), exclusive (E), shared (S), and

invalid (I). Importantly, this chapter also presents our table-driven methodology for presenting pro-

tocols with both stable (e.g., MOESI) and transient coherence states. Transient states are required

剩余213页未读，继续阅读

xuxiong1992

粉丝: 0
资源: 2

多处理器环境下存储模型与缓存一致性协议详解

springboot缓存一致性解决

分布式系统缓存一致性设计与应用.pdf

VISU：一种基于自更新的简单有效的缓存一致性协议

Java内存模型：理解CPU缓存与一致性协议

深入理解Java内存模型：缓存一致性与乱序执行

JAVA多线程与并发：内存模型及缓存一致性解析

VISU：简化高效的自更新缓存一致性协议

存储器一致性与缓存一致性

分布式缓存与缓存一致性

内存一致性与缓存一致性基础教程

最新资源