Multicore Systems, Coherence and Consistency

Introduction

The growth of processor performance has shifted from relying primarily on higher clock frequencies to integrating multiple processing cores on one chip. A multicore processor can execute several instruction streams concurrently, but parallel execution introduces a central architectural problem: different cores may hold different copies of the same memory location in their private caches. The system must determine when these copies are equivalent, when updates become visible, and in what order memory operations are observed.

Three concepts must therefore be distinguished:

• Parallelism concerns the simultaneous execution of computation.
• Cache coherence concerns agreement about the value of a single memory location.
• Memory consistency concerns the ordering and visibility of operations to multiple memory locations.

A system may be coherent but still provide a weak consistency model. Conversely, a programming language may offer a high-level memory model whose guarantees are implemented through hardware protocols, compiler transformations, and synchronization libraries.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Explain multicore organization, shared-memory models, and cache hierarchies.
2. Distinguish cache coherence from memory consistency.
3. Analyse snooping and directory-based coherence protocols.
4. Explain MSI, MESI, MOESI, and related state machines.
5. Evaluate synchronization, atomicity, false sharing, and scalability.
6. Apply quantitative performance models to parallel execution and coherence traffic.
7. Analyse a realistic multicore design problem and justify architectural decisions.

1. Multicore Organization

A multicore system contains several computational cores connected to a memory subsystem. Each core commonly has private L1 instruction and data caches, while L2 or L3 caches may be private, shared, or distributed among cores. A typical organization includes:

1. cores and their pipeline structures;
2. private, low-latency caches;
3. a shared last-level cache or distributed cache slices;
4. an interconnection network;
5. memory controllers and external memory channels; and
6. coherence, synchronization, and interrupt mechanisms.

The basic performance benefit of multicore execution can be approximated by Amdahl’s law. If fraction p of a program is parallelizable and N cores are used, the ideal speedup is

Here, S(N) is speedup, p is the parallel fraction, and N is the number of cores. The equation assumes balanced work, no communication overhead, no synchronization cost, and identical cores. Real speedup is lower because of cache misses, coherence traffic, load imbalance, operating-system overhead, and serial bottlenecks.

A useful extended model is

where O(N) represents overhead as a fraction of single-core execution time. This is not a universal law; it is a modelling abstraction used to expose scalability limits.

Shared-memory models

In a shared-memory multiprocessor, all cores use a common address space. A load obtains a value from a register, cache, or memory hierarchy, while a store modifies a logical memory location. Shared memory simplifies communication compared with explicit message passing, but it requires rules governing visibility and ordering.

Systems may be:

• Uniform memory access (UMA): approximately similar access latency for all cores.
• Non-uniform memory access (NUMA): latency depends on the physical location of data relative to the requesting core.
• Cache-coherent NUMA (ccNUMA): NUMA systems that maintain coherence across distributed caches.

NUMA-aware software attempts to place threads near the data they use. Poor placement can make remote accesses and coherence communication dominant costs.

2. Cache Coherence

Suppose cores C₀ and C₁ both cache address X. If C₀ writes a new value while C₁ retains the old value, subsequent reads by C₁ may be incorrect. A cache-coherent system ensures that writes to a location are eventually reflected consistently in other cached copies, subject to the system’s specified rules.

A coherence protocol normally satisfies three conceptual properties:

1. Write propagation: a write eventually becomes observable to relevant processors.
2. Write serialization: writes to the same address are observed in a single order.
3. Read consistency: a read returns an allowed value according to the protocol and memory model.

Coherence is normally defined per cache line rather than per byte. If one word in a 64-byte line is modified, the protocol may transfer or invalidate the entire line.

Coherence versus consistency

Coherence asks: “What values may be returned for one address?” Consistency asks: “In what order may operations on possibly different addresses be observed?”

For example, consider initially X = 0 and Y = 0:

Core 0: X = 1; r1 = Y
Core 1: Y = 1; r2 = X

A coherent system may permit r1 = 0 and r2 = 0 under a weak memory model, because the writes concern different locations and the loads may be reordered or observed before the remote writes become visible. Sequential consistency would disallow this result because it requires one global order preserving each core’s program order.

3. Coherence Protocol Design

Two broad implementation strategies are used.

Snooping protocols

In a snooping protocol, caches observe transactions on a shared bus or logically broadcast interconnect. When one cache requests a line, other caches inspect the request and respond according to their state. Snooping is conceptually simple and effective for small systems, but broadcast traffic and shared arbitration limit scalability.

Directory protocols

A directory maintains information about which caches hold a copy of each line. On a request, the directory sends targeted messages to sharers or the owner. Directory protocols reduce unnecessary broadcasts and scale better, but require directory storage, additional network traffic, and more complex failure handling.

A full bit-vector directory uses one bit per potential core for each cache line. If a system has N cores, the sharer vector requires N bits per line, ignoring metadata overhead. For 1,024 cores, this is 128 bytes merely for sharer bits, which can be substantial relative to a 64-byte data line. Sparse, limited-pointer, or hierarchical directories reduce this cost at the price of additional protocol complexity.

4. MSI and MESI State Machines

Coherence protocols represent the status of a cache line using states. The classic MSI protocol contains:

A read miss usually obtains a line in S if another cache has a copy, or M/E-like ownership under an optimized protocol. A write to an S line requires invalidating other sharers before modification. A write miss on an I line obtains ownership and transitions to M.

MESI adds the Exclusive (E) state:

• E: one cache has the line and its value agrees with memory.
• A read hit in E can be serviced locally.
• A write hit in E can transition silently to M, avoiding an invalidation transaction.

MOESI adds Owned (O). An O line is dirty but may be shared; the owner supplies data to requesting caches and is responsible for eventual write-back. This can avoid writing dirty data to memory before another cache reads it.

Representative MESI transitions

The exact transitions depend on whether the protocol is write-invalidate or write-update and on implementation details such as silent evictions and intervention.

Write-invalidate and write-update

A write-invalidate protocol invalidates other copies before allowing a writer to modify a line. It is efficient when a processor performs several writes because ownership is acquired once. A write-update protocol sends each new value to other caches. It may benefit readers of frequently updated data but can generate substantial traffic.

Modern general-purpose processors predominantly use write-invalidate protocols because they reduce repeated data movement for write-intensive sharing.

5. Coherence Transactions and Atomicity

A cache miss is not merely a local event. It may initiate requests such as:

• read-for-shared-data;
• read-for-ownership;
• upgrade from shared to modified;
• invalidation acknowledgements;
• write-back of dirty data; and
• eviction or replacement notifications.

These transactions must be coordinated atomically at the coherence level. If two cores simultaneously request write ownership, the coherence system must serialize them. Otherwise both could believe they possess exclusive permission.

Atomic read-modify-write instructions, including compare-and-swap, load-linked/store-conditional, and fetch-and-add, provide indivisible operations. A compare-and-swap can be expressed as:

CAS(A, expected, new):
    atomically:
        if A = expected then
            A ← new
            return true
        else
            return false

The operation succeeds only if the value has not changed since the expected value was observed. Atomicity does not automatically provide a desired ordering for all surrounding operations; ordering depends on the instruction’s memory-order semantics.

6. Memory Consistency Models

A memory consistency model specifies the permitted order and visibility of memory operations.

Sequential consistency

Sequential consistency requires that the result of execution be equivalent to some interleaving of operations from all processors, with each processor’s operations appearing in program order. It is intuitive but can restrict hardware optimizations.

Relaxed consistency

Relaxed models permit selected reorderings. A processor may allow a later load to complete before an earlier store becomes globally visible. Compilers and hardware can exploit this freedom to improve throughput, but synchronization must explicitly constrain ordering.

Important ordering mechanisms include:

• Acquire: later memory operations cannot move before the acquire.
• Release: earlier memory operations cannot move after the release.
• Sequentially consistent fence: imposes a stronger global ordering.
• Relaxed atomic operation: guarantees atomicity but minimal ordering.

A lock usually has acquire semantics on successful acquisition and release semantics on unlock. The programming language model, not merely the hardware instruction, determines what transformations are valid.

Happens-before reasoning

If operation A happens-before operation B, then B must observe the effects required by the language and hardware model. A typical chain is:

Thread 0: data = 42; release(store flag = 1)
Thread 1: acquire(load flag); read data

If Thread 1 observes flag = 1 through the acquire operation, the write of data is ordered before the read of data. Without release/acquire ordering, the flag and data accesses may be observed in an unsafe order.

7. Synchronization and Performance

Locks, barriers, semaphores, and atomic operations coordinate concurrent threads. However, synchronization has costs:

• coherence traffic for lock ownership;
• serialization at contended locks;
• pipeline stalls and speculation barriers;
• scheduler and operating-system overhead; and
• reduced locality when threads migrate.

Amdahl’s law can be applied to a serialized synchronization region. If a fraction s is inherently serial, the maximum speedup cannot exceed 1/s, regardless of the number of cores.

False sharing

False sharing occurs when independent variables used by different cores occupy the same cache line. Each core modifies a different word, but the coherence protocol transfers ownership of the entire line. The data are logically independent but physically coupled.

Mitigations include padding, alignment, structure-of-arrays layouts, per-core counters, and reducing the frequency of shared updates. Padding increases memory use, so it should be applied after profiling confirms coherence-induced contention.

True sharing

True sharing occurs when multiple cores genuinely access the same variable. Padding cannot eliminate it. Appropriate techniques include batching updates, using local aggregation followed by reduction, partitioning ownership, read-copy-update methods, or redesigning the algorithm.

8. Quantitative Analysis of Coherence Cost

A simple average memory access time model is

where T_hit is hit time, m is the miss rate per access, and T_miss is the additional miss penalty. In a multicore system, T_miss may include directory lookup, network traversal, invalidation acknowledgements, data transfer, and queuing delay.

For a two-level cache, a common form is

where T₁ and T₂ are the access times of levels one and two, m₁ and m₂ are conditional miss rates, and T_mem is main-memory access time. The formula assumes serial lookup and independent interpretation of conditional miss rates; inclusive, victim, and nonblocking caches require more detailed models.

Worked example

Assume a processor has L1 hit time 1 ns, L1 miss rate 4%, L2 hit time 8 ns, and an L2 local miss penalty of 70 ns. Then:

This is an idealized result. If coherence invalidations add an average 10 ns to 20% of L1 misses, the additional expected cost is:

The adjusted estimate is 4.20 ns, assuming the coherence delay is additive and independent. Real systems may exhibit queueing and overlap, so measurement is essential.

9. Applied Case: A Multicore Web-Service Counter

Background

Consider an illustrative online service running on 32 cores. Each request increments a global request counter and updates per-user statistics. Throughput initially improves with additional cores but falls sharply after 16 cores.

Problem

Performance profiling shows high cache-to-cache transfers and frequent invalidations of the global counter’s cache line. Threads are also migrating between cores, causing ownership to move repeatedly.

Analysis

The counter is a true-sharing hotspot: every increment requires exclusive ownership under a write-invalidate protocol. In addition, several unrelated statistics occupy the same cache line, producing false sharing. The global lock protecting the counter further serializes updates.

Approach and solution

The design is changed as follows:

1. Each core maintains a local, cache-line-aligned counter.
2. Requests update the local counter using relaxed atomic operations where language semantics permit.
3. A periodic aggregation thread sums local counters.
4. User statistics are partitioned by hash across cores.
5. Thread affinity reduces migration.
6. Monitoring records invalidations, remote hits, lock wait time, and throughput.

If exact instantaneous global values are required, aggregation frequency must be balanced against accuracy and synchronization cost. If approximate monitoring is acceptable, delayed aggregation provides much better scalability.

Outcome

The redesign reduces ownership transfers on the hot path and eliminates false sharing. The global counter is no longer a serialization point, although aggregation introduces bounded staleness. The result illustrates a general principle: coherence protocols preserve correctness, but data placement and ownership determine performance.

Learning points

• A correct coherent implementation can still scale poorly.
• Logical independence should be reflected in physical cache-line placement.
• Per-core accumulation is effective for associative operations such as addition.
• Performance claims should be supported by hardware-counter measurements rather than throughput alone.

10. Verification, Debugging and Best Practices

Coherence and consistency bugs are difficult because failures may be rare and timing-dependent. Recommended practices include:

• define the required memory-order semantics before coding;
• use language-standard atomic and synchronization primitives;
• avoid undocumented assumptions about cache behavior;
• test under high contention and varied core counts;
• use race detectors, stress tests, model checkers, and litmus tests;
• inspect hardware performance counters for misses, invalidations, and remote accesses;
• document ownership and lifetime of shared data; and
• distinguish correctness tests from performance benchmarks.

A data race is not simply a performance problem. In many language environments, unsynchronized conflicting accesses produce undefined or otherwise non-portable behavior. Compiler optimization can expose errors that appear absent on one processor or under one build configuration.

11. Contemporary Directions and Critical Issues

Modern processors increasingly combine coherence domains, chiplets, heterogeneous cores, high-bandwidth memory, and accelerators. Full-system coherence between CPUs, GPUs, and specialized engines can simplify programming but increases protocol, verification, and power complexity.

Research directions include:

• hierarchical and region-based coherence;
• coherence filtering and predictive snooping;
• non-inclusive and directory-assisted cache hierarchies;
• hardware transactional memory;
• persistent-memory ordering;
• near-memory and processing-in-memory architectures; and
• heterogeneous memory models for CPUs, GPUs, and accelerators.

Security is also relevant. Coherence and shared caches can create timing channels through which one security domain infers another’s activity. Isolation techniques, cache partitioning, scheduling policies, and constant-time software reduce but do not universally eliminate such risks. In cloud systems, resource governance must therefore consider both performance interference and information leakage.

Chapter Summary

Multicore systems improve throughput by executing multiple instruction streams, but shared data creates coherence and consistency challenges. Cache coherence maintains an acceptable relationship among copies of one cache line, whereas memory consistency defines ordering across operations and addresses. Snooping protocols are effective for smaller systems; directory protocols scale better by replacing broadcast with targeted communication. MSI, MESI, and MOESI use state machines to manage ownership, sharing, invalidation, and dirty data.

Atomic operations provide indivisible updates, while acquire, release, and fence semantics control ordering. True sharing, false sharing, synchronization, NUMA placement, and thread migration can substantially reduce scalability. Quantitative models such as Amdahl’s law and AMAT provide initial estimates, but real systems require profiling and workload-specific measurement. Effective multicore design combines protocol correctness, memory-model discipline, data placement, workload partitioning, and security-aware governance.

Key Terms

Cache coherence: The mechanism that maintains permitted agreement among cached copies of a memory location.

Memory consistency: Rules specifying the order and visibility of memory operations.

Multicore processor: A processor containing multiple independently executing cores.

UMA: Uniform memory access organization with approximately equal access latency.

NUMA: Organization in which access latency depends on memory location.

Snooping protocol: Coherence protocol in which caches observe shared transactions.

Directory protocol: Protocol using metadata to identify sharers or owners of cache lines.

Cache line: The unit of transfer and coherence in a cache hierarchy.

MSI: Coherence protocol with Modified, Shared, and Invalid states.

MESI: MSI extended with an Exclusive state.

MOESI: MESI extended with an Owned state.

Write-invalidate: Protocol that invalidates other copies before a write.

Write-update: Protocol that distributes new written data to other caches.

False sharing: Coherence interference caused by independent data sharing one cache line.

True sharing: Performance interference caused by genuine access to the same data.

Acquire: Ordering operation preventing later operations from moving before it.

Release: Ordering operation preventing earlier operations from moving after it.

Atomic operation: Indivisible operation that cannot be observed in a partially completed state.

Amdahl’s law: Model relating speedup to parallel and serial fractions.

Happens-before: An ordering relation used to establish visibility and synchronization.

Review Questions

Short Answer Questions

1. Distinguish cache coherence from memory consistency.
2. What information does a directory maintain?
3. Explain the purpose of the Exclusive state in MESI.
4. Define false sharing and give one mitigation.
5. What is the role of an acquire operation?

Long Answer Questions

1. Explain snooping and directory-based coherence, including their scalability trade-offs.
2. Describe the MSI, MESI, and MOESI protocols and compare their state spaces.
3. Explain sequential consistency and relaxed consistency with an illustrative execution.
4. Analyse how synchronization and NUMA placement affect multicore performance.
5. Discuss the relationship among atomicity, coherence, consistency, and language memory models.

Analytical / Application Questions

1. A workload has parallel fraction p = 0.9. Calculate ideal speedup for 8 cores using Amdahl’s law and explain why measured speedup may be lower.
2. Design a scalable counter for a 64-core monitoring system. State whether exact or approximate results are required and justify the synchronization strategy.
3. A benchmark exhibits frequent cache-line transfers although threads update different variables. Develop a diagnostic procedure to determine whether false sharing is responsible and propose corrective actions.

Multiple Choice Questions with Answers

Question 1

Which statement best distinguishes cache coherence from memory consistency?

A. Coherence concerns one memory location, while consistency concerns ordering across memory operations.

B. Coherence concerns instruction decoding, while consistency concerns branch prediction.

C. Coherence applies only to NUMA systems, while consistency applies only to UMA systems.

D. Coherence guarantees sequential consistency in every processor.

Correct Answer: A. Coherence concerns one memory location, while consistency concerns ordering across memory operations.

Question 2

Which MESI state indicates that one cache has the only clean copy of a line?

A. Modified

B. Shared

C. Exclusive

D. Invalid

Correct Answer: C. Exclusive

Question 3

What is the principal scalability advantage of a directory protocol over a broadcast snooping protocol?

A. It eliminates the need for cache lines.

B. It can send coherence actions to relevant sharers rather than broadcasting to all caches.

C. It guarantees zero coherence latency.

D. It prevents all write misses.

Correct Answer: B. It can send coherence actions to relevant sharers rather than broadcasting to all caches.

Question 4

Initially X = 0 and Y = 0. Under a weak memory model, which result may be possible for the operations Core 0: X = 1; r1 = Y and Core 1: Y = 1; r2 = X?

A. r1 = 0 and r2 = 0

B. r1 = 2 and r2 = 2

C. r1 = 1 and r2 = 3

D. The stores cannot execute concurrently.

Correct Answer: A. r1 = 0 and r2 = 0

Question 5

A processor has a 1 ns L1 hit time, a 4% L1 miss rate, an 8 ns L2 hit time, and a 70 ns memory penalty after an L2 miss. Using AMAT = T₁ + m₁ × (T₂ + T_mem), what is the AMAT?

A. 1.32 ns

B. 4.12 ns

C. 8.04 ns

D. 79 ns

Correct Answer: B. 4.12 ns

Question 6

Which situation is an example of false sharing?

A. Two cores read the same immutable cache line.

B. Two cores update different words located in the same cache line.

C. A core misses in both L1 and L2.

D. A directory has no entry for an uncached line.

Correct Answer: B. Two cores update different words located in the same cache line.

Question 7

What does a release operation primarily ensure?

A. Earlier memory operations are not moved after the release.

B. All later operations are discarded.

C. The cache line becomes permanently modified.

D. The processor switches to sequential execution.

Correct Answer: A. Earlier memory operations are not moved after the release.

Question 8

For a program with parallel fraction p = 0.8 running ideally on 4 cores, what is the Amdahl speedup?

A. 1.25

B. 2.00

C. 2.50

D. 4.00

Correct Answer: C. 2.50

Question 9

Why can a global incrementing counter limit multicore scalability?

A. It causes repeated ownership and coherence traffic on one cache line.

B. It cannot be represented in binary.

C. It prevents instruction fetching.

D. It automatically disables all private caches.

Correct Answer: A. It causes repeated ownership and coherence traffic on one cache line.

Question 10

Which technique most directly reduces contention for an approximate high-throughput counter?

A. Place every update under one global lock.

B. Use per-core counters followed by periodic aggregation.

C. Force all threads onto one core.

D. Increase the frequency of global invalidations.

Correct Answer: B. Use per-core counters followed by periodic aggregation.