内存一致性与缓存协调基础

5星 · 超过95%的资源需积分: 50 68 浏览量更新于2024-07-18 5 收藏 3.88MB PDF 举报

"《A Primer on Memory Consistency and Cache Coherence》是由Mark D. Hill、Daniel J. Sorin和David A. Wood合著的一本经典书籍，由Morgan Claypool Publishers出版，属于SYNTHESIS LECTURES ON COMPUTER ARCHITECTURE系列。该书深入浅出地介绍了内存一致性（Memory Consistency）和缓存一致性（Cache Coherence）这两个关键的计算机体系结构概念。" 内存一致性是指在多处理器系统中，所有处理器对共享内存的访问看起来像是按照某种顺序进行的，这种顺序对于所有处理器来说都是可见和一致的。内存一致性是多处理器系统中正确执行并发程序的基础，它确保了数据的一致性，避免了由于不同处理器之间缓存的数据版本不同而可能导致的错误。缓存一致性则是指当多个处理器都有本地缓存时，如何维护这些缓存中的共享数据副本的一致性。当一个处理器更新了缓存中的数据，其他处理器的相应缓存副本也需要同步更新，以确保所有处理器看到的内存状态是相同的。实现缓存一致性通常通过协议来完成，如MSI（Modified, Shared, Invalid）、MESI（Modified, Exclusive, Shared, Invalid）或MESIF（Modified, Exclusive, Shared, Invalid, Forward）等。书中可能会涵盖以下主题： 1. 内存模型：解释各种内存模型，如Sequential Consistency（SC），它是最强的一致性模型，以及弱一致性模型，如TSO（Total Store Order）和PSO（Processor Store Order）等，它们允许处理器在某些情况下重新排序内存操作。 2. 缓存一致性协议：详细讨论如何通过协议确保缓存一致性，包括协议的工作原理、状态转移图以及在多处理器系统中的实现。 3. 缓存的分类与工作方式：介绍写通（Write-Through）和写回（Write-Back）策略，以及写分配（Write-Allocation）和无写分配（No-Write-Allocation）的区别。 4. 冲突和伪共享：探讨缓存行大小对冲突的影响，以及如何处理伪共享，即多个处理器访问相同缓存行的不同部分导致的不必要同步。 5. 性能优化：分析一致性对系统性能的影响，并讨论如何通过缓存设计优化一致性策略，提高系统性能。 6. 实例与案例研究：可能包括实际系统中的例子，如Intel的MESI协议在x86架构上的应用，以及在解决实际问题中如何考虑一致性。 7. 实验与模拟：介绍如何使用工具进行内存一致性模型的验证和缓存一致性协议的模拟，以理解其行为。该书适合对计算机体系结构感兴趣的读者，特别是那些想要深入理解多处理器系统中内存和缓存行为的硬件和软件工程师。通过阅读，读者将能够更好地理解和解决多处理器环境中的数据一致性问题，从而设计出更高效、更可靠的系统。

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页未读，继续阅读

C将考虑

粉丝: 2
资源: 4

内存一致性与缓存协调基础

A Primer on Memory Consistency and Cache Coherence

00-A Primer on Memory Consistency and Cache Coherence

A Cache Primer.pdf

a primer on memory consistency and cache coherence

a primer on memory consistency and cache coherence pdf

a primer on memory consistency pdf

a primer on compression in the memory hierarchy这本书的中文版

C Primer Plus

c primer plus

Embedded Linux Primer: A Practical, Real-World Approach

最新资源