9. Multicore, Multiprocessor, and Distributed-System Architecture

Introduction and Context

For several decades, processor performance improved primarily through higher clock frequencies and increasingly sophisticated instruction-level parallelism. Physical limits on power dissipation, signal propagation, and transistor leakage eventually made frequency scaling less attractive. The dominant strategy therefore shifted toward parallelism: placing multiple processing cores in one chip, connecting several processors through a shared memory system, or distributing computation across networked machines.

This shift changes the central question of computer design. Instead of asking only how quickly one instruction stream can execute, architects must ask how independent activities can be identified, scheduled, synchronized, supplied with data, and coordinated without excessive communication overhead. Parallel systems can deliver substantial performance, but only when their software, memory system, interconnection network, and programming model work together.

This chapter examines thread-level and data-level parallelism, shared-memory multiprocessors, cache coherence, memory consistency, synchronization, non-uniform memory access (NUMA), clusters, and distributed architectures. It also considers the architectural foundations of cloud and high-performance computing (HPC), where performance, scalability, availability, energy efficiency, and isolation must be balanced.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Distinguish instruction-, data-, thread-, and task-level parallelism.

2. Explain multicore and multiprocessor organization, including interconnection and memory-system choices.

3. Analyze cache-coherence protocols and distinguish coherence from consistency.

4. Compare sequential consistency, weak consistency, and release consistency.

5. Explain atomic operations, locks, barriers, and lock-free synchronization.

6. Evaluate UMA, NUMA, distributed shared memory, clusters, and cloud architectures.

7. Identify scalability bottlenecks using speedup, efficiency, and memory-access behavior.

8. Apply architectural principles to HPC and cloud-computing scenarios.

9. Recognize reliability, security, governance, and energy considerations in parallel systems.

From a Single Core to Many Computing Agents

Parallelism exists at several levels. Instruction-level parallelism overlaps independent instructions within one thread through pipelining, superscalar issue, and out-of-order execution. Data-level parallelism applies one operation to many data elements, as in vector extensions and graphics processors. Thread-level parallelism executes multiple threads concurrently, while task-level parallelism assigns distinct computational tasks to different workers.

A multicore processor integrates multiple independent cores on one package. Each core may have private registers and private L1 caches, while larger caches can be private, shared by a subset of cores, or shared by all cores. A multiprocessor system uses two or more processing units; these units may be cores on one chip, sockets in one server, or separate machines. The term multiprocessing therefore describes a broader class than multicore processing.

Parallel performance is constrained by both the amount of available parallel work and the cost of coordinating it. Amdahl’s law expresses the limit imposed by a serial fraction. If fraction s of a program must execute serially and the remainder can use p processors, ideal speedup is

S(p) = 1 / [s + (1 − s)/p].

Even infinitely many processors cannot produce speedup greater than 1/s. Gustafson’s law provides a complementary perspective: for a fixed execution time, larger systems can often solve proportionally larger problems, so the effective parallel fraction may increase with problem size. Neither law captures every practical effect; contention, load imbalance, synchronization, communication, and memory bandwidth may reduce performance further.

Shared-Memory Multiprocessor Organization

In a shared-memory multiprocessor, processors communicate by reading and writing a common address space. The programming model is attractive because data structures can be shared directly rather than explicitly exchanged as messages. However, the apparent simplicity of a common address space hides complex implementation requirements.

In a uniform memory access (UMA) system, the access time to main memory is approximately the same for all processors. UMA is suitable for small systems, but a single bus or centralized memory controller becomes a bottleneck as processor count increases. Modern systems commonly use switched interconnects, multiple memory channels, and hierarchical cache structures rather than one shared bus.

NUMA systems distribute physical memory among processor sockets. A core accesses its local memory faster than memory attached to another socket. All memory may still be visible through one global address space, making the system a cache-coherent NUMA (ccNUMA) machine. NUMA improves scalability by distributing bandwidth, but performance depends on placement. A thread executing on one socket may suffer repeated remote accesses if its data was allocated on another socket.

Operating systems and runtimes therefore use processor affinity, first-touch allocation, page migration, and memory policies such as local allocation or interleaving. Application developers should arrange computation near the data it uses, avoid unnecessary sharing, and measure local and remote access behavior rather than assuming that a single address space implies uniform cost.

Cache Coherence: Keeping Copies Meaningful

Caches are essential because processor speed is much greater than main-memory latency. In a shared-memory system, however, several caches may contain copies of the same cache line. If one core writes a value, other cached copies must not remain silently usable as if they were current. Cache coherence addresses this problem.

A coherent system generally satisfies three intuitive properties. A write by a processor should eventually become visible to other processors; writes to the same location should be observed in a consistent order; and a processor should not read an obsolete value indefinitely. Coherence is concerned with a particular memory location or cache line, not with the ordering of all memory operations.

Snooping protocols allow caches to observe a shared bus or broadcast medium. They are simple for small systems but scale poorly because broadcasts consume bandwidth. Directory-based protocols maintain a directory recording which caches hold a line. A request is then sent selectively to relevant sharers, making directories more suitable for larger systems.

The widely used MESI protocol assigns each cache line one of four states: Modified, Exclusive, Shared, or Invalid. A Modified line is present only in one cache and differs from memory. Exclusive means one cache has the line and it agrees with memory. Shared means multiple caches may hold clean copies. Invalid means the copy cannot be used. MOESI extends this family with an Owned state, allowing one cache to supply modified data to other readers without immediately writing it back to memory.

A write-invalidate protocol invalidates other copies before a writer modifies a line. This works well when a processor performs several writes to the same line. A write-update protocol broadcasts new values to other caches, which may benefit readers but creates more traffic. False sharing is a common performance problem: two unrelated variables occupy one cache line, and writes by different cores repeatedly invalidate one another’s copies. Padding, alignment, and data partitioning can reduce false sharing.

Coherence traffic can be classified as useful communication, such as a producer passing data to a consumer, or harmful interference, such as repeated ownership transfer caused by poorly placed locks. Consequently, a coherent design can be functionally correct yet perform badly.

Memory Consistency and the Meaning of “Before”

Cache coherence does not determine the order in which different memory locations become visible. Memory consistency specifies the rules governing the apparent ordering of reads and writes.

Sequential consistency requires that the result of execution be equivalent to some interleaving of each processor’s operations in program order. It is conceptually straightforward but can restrict hardware reordering and reduce performance. Modern processors often use store buffers, speculative execution, and out-of-order execution, so they provide weaker models.

A weak or relaxed consistency model allows selected operations to be observed out of program order. Synchronization instructions, fences, or language-level atomic operations establish ordering where required. Release consistency distinguishes acquire and release operations. An acquire prevents subsequent operations from moving before it, while a release ensures that earlier operations become visible before the release is completed. This permits ordinary data operations to be reordered while preserving the behavior of correctly synchronized programs.

The distinction is essential in producer–consumer communication. Suppose a producer writes a data item and then sets a flag. A consumer that observes the flag must also observe the data written before it. Without a release by the producer and an acquire by the consumer, a compiler or processor may reorder operations so that the consumer sees the flag but stale data. Correct concurrent programs must use the guarantees of the programming language and hardware memory model rather than relying on accidental ordering.

Synchronization and Concurrent Progress

Synchronization coordinates threads that access shared state. Mutual exclusion ensures that only one thread at a time enters a critical section. A mutex or spinlock can implement this property, but the appropriate choice depends on expected waiting time. A spinlock wastes processor cycles while waiting but avoids context-switch overhead for very short critical sections. A blocking mutex suspends the waiting thread and is generally preferable when contention or wait duration is substantial.

Atomic read-modify-write instructions, such as compare-and-swap, test-and-set, and fetch-and-add, provide the primitive operations from which locks, counters, queues, and other structures can be built. A compare-and-swap changes a memory location only if it still contains an expected value, enabling optimistic algorithms.

A barrier causes participating threads to wait until all members reach a specified point. Barriers are useful in iterative numerical algorithms, but frequent barriers can expose load imbalance and serialize progress. Condition variables allow a thread to sleep until a predicate becomes true; the predicate must be checked in a loop because wake-up does not itself prove that the condition holds.

Correctness properties include safety and liveness. Safety means that undesirable events, such as two threads entering a critical section simultaneously, never occur. Liveness means that desirable progress eventually occurs. Deadlock violates liveness when threads wait in a cycle. Starvation occurs when a thread waits indefinitely while others progress. Livelock occurs when threads remain active but repeatedly interfere without completing useful work.

Lock-free and wait-free algorithms reduce dependence on conventional locks. A lock-free algorithm guarantees that some thread makes progress; a wait-free algorithm guarantees that every operation completes within a bounded number of steps. These methods can improve scalability but are difficult to design because of memory reclamation, the ABA problem, and subtle ordering requirements.

Distributed Shared Memory, Clusters, and Message Passing

A distributed-memory system gives each node private memory. Nodes communicate through a network using message passing. The Message Passing Interface (MPI) is widely used in HPC because it makes communication explicit and supports point-to-point operations, collective operations, communicators, and fault-aware application structures.

Distributed shared memory (DSM) presents a shared address-space abstraction over physically distributed memories. DSM simplifies some programming tasks but must detect ownership, migrate pages or cache lines, and manage coherence over a network. Network latency is much higher than local cache or DRAM latency, so a DSM abstraction may hide costs that are crucial to performance.

A cluster is a collection of independent computers connected by a high-speed network. Clusters may be designed for high performance, high availability, or load balancing. A compute cluster emphasizes throughput and parallel execution; a failover cluster emphasizes service continuity; a storage cluster distributes data and replication. Unlike a tightly coupled shared-memory machine, a cluster can scale by adding nodes, but it must deal explicitly with communication delay, partial failure, data placement, and distributed coordination.

Distributed systems differ from shared-memory systems in an important way: a node may fail while other nodes continue running, and communication may be delayed or lost. Distributed algorithms therefore require timeouts, retries, idempotent operations, replication, leader election, or consensus mechanisms. A system cannot generally assume that absence of a response means that a remote process has failed.

Architecture for Cloud and High-Performance Computing

Cloud computing combines virtualization, pooled resources, software-defined infrastructure, and service-oriented access. A cloud platform may expose virtual machines, containers, managed databases, serverless functions, or specialized accelerators. The underlying architecture is still built from multicore servers, NUMA memory, networks, storage systems, and management software.

Virtual machines provide strong isolation through a hypervisor, while containers share the host kernel and usually have lower startup overhead. Both introduce scheduling and resource-management questions. A virtual machine may be allocated virtual CPUs that compete for physical cores; simultaneous multithreading may expose logical processors whose resources are not equivalent to full cores. Cloud performance can therefore vary with co-located workloads, memory pressure, noisy neighbors, and network contention.

HPC applications often use MPI across nodes and thread-level parallelism within each node, commonly through OpenMP, threading libraries, or accelerator programming models. Performance depends on arithmetic intensity, memory bandwidth, interconnect latency, collective communication, synchronization frequency, and load balance. A useful design principle is to minimize communication, overlap communication with computation, partition data carefully, and select a decomposition that preserves locality.

The roofline model provides an analytical way to reason about performance. It relates attainable performance to operational intensity—the number of operations performed per byte transferred—and to hardware limits such as peak compute throughput and memory bandwidth. A low-intensity workload is usually memory-bound; increasing arithmetic units will not help unless data movement is improved. A high-intensity workload may be compute-bound and benefit from more cores or vector capability.

An Illustrative Case: NUMA-Aware Scientific Analytics

Background

Consider an illustrative research organization that processes large climate-simulation arrays on a dual-socket server. Each socket has many cores and locally attached memory. The application divides a three-dimensional grid into blocks and applies the same numerical stencil repeatedly.

Situation and Problem

The application scales well from one to eight threads but gains little beyond that. Monitoring shows high remote-memory traffic, frequent cache-line invalidations, and unequal CPU utilization. The developers initially suspect insufficient processor frequency.

Analysis

The grid was allocated by one initialization thread on the first socket. Under first-touch NUMA policy, most pages therefore reside in that socket’s memory. When threads on the second socket process their assigned blocks, they repeatedly access remote pages. In addition, adjacent blocks update boundary metadata stored in the same cache lines, creating false sharing. A global barrier at every iteration forces fast threads to wait for the slowest thread.

Approach

The team changes initialization so that worker threads touch the pages they will later process. The grid is partitioned into spatial tiles mapped to cores and sockets, and the scheduler uses affinity to keep threads near their data. Boundary metadata is padded so that independent counters occupy separate cache lines. The algorithm exchanges only necessary halo regions and combines two short phases to reduce barrier frequency. Profiling is performed using hardware counters for cache misses, memory bandwidth, remote accesses, and synchronization time.

Outcome

The redesign improves scaling because memory locality and cache-line ownership are aligned with the computation. The example does not imply a universal speedup; its lesson is methodological. Performance diagnosis must distinguish computational capacity from data movement, placement, contention, and synchronization.

Learning Points

1. A shared address space does not guarantee equal access cost.

2. Thread placement and data placement should be designed together.

3. Cache-line granularity matters even when variables are logically independent.

4. Profiling should measure causes of lost scalability rather than only elapsed time.

Challenges, Risks, and Design Trade-offs

Parallel systems introduce several failure and performance risks. Excessive synchronization can reduce parallelism. Fine-grained tasks may cost more to schedule than they contribute to useful work. Coarse-grained tasks improve locality but may create load imbalance. Shared mutable state simplifies communication but increases coherence traffic and correctness risk.

Scalability is also limited by bandwidth and interconnect topology. A design that works on one socket may fail across sockets because of remote latency. A design that works on one node may fail across a cluster because network communication is orders of magnitude slower than cache access. Benchmark results must therefore specify problem size, processor count, placement, compiler, input distribution, and whether initialization and communication are included.

Reliability becomes harder as component count increases. Memory errors, link failures, node failures, and software faults can occur during long-running jobs. HPC systems use checkpointing, redundancy, error-correcting memory, and job restart mechanisms. Cloud platforms add automated replacement, replication, health monitoring, and capacity management.

Security concerns include side-channel leakage through shared caches, speculative-execution vulnerabilities, insecure management interfaces, weak tenant isolation, and unauthorized access to distributed data. Mitigations may reduce performance, so security requirements must be considered in architectural and deployment decisions rather than added after implementation.

Ethically and professionally, designers should report performance honestly, disclose resource assumptions, minimize unnecessary energy consumption, and protect sensitive scientific or personal data. Governance policies should define data location, access control, retention, auditability, and responsibility for failures in multi-tenant environments.

Emerging Directions and Best Practices

Current systems increasingly combine general-purpose cores with GPUs, tensor accelerators, programmable network devices, and high-bandwidth memory. Heterogeneous systems require explicit decisions about data movement and workload placement. Accelerator performance may be excellent when parallelism and locality are high, but transfers and synchronization can dominate irregular workloads.

Memory-centric designs, chiplet-based processors, composable infrastructure, persistent-memory technologies, and near-data processing seek to reduce the cost of moving data. At the software level, task runtimes can dynamically schedule work and express dependencies, while machine-learning methods are being explored for workload placement and resource prediction. These developments do not remove fundamental issues of locality, consistency, failure, and synchronization.

Sound engineering practice includes the following:

• Start with a clear parallel decomposition and ownership model.
• Minimize shared mutable state and prefer immutable or partitioned data where practical.
• Match synchronization strength to the required correctness guarantee.
• Measure cache behavior, bandwidth, locality, load balance, and communication separately.
• Treat NUMA placement and processor affinity as performance decisions.
• Use scalable algorithms rather than merely adding processors.
• Test under realistic contention, failure, and workload conditions.
• Document memory-model assumptions and synchronization protocols.
• Include energy, security, reliability, and operational cost in system evaluation.

Chapter Summary

Multicore, multiprocessor, and distributed architectures exploit parallelism at thread, data, and task levels. Their performance depends not only on processor count but also on the serial fraction of a program, memory bandwidth, locality, communication, synchronization, and load balance. Shared-memory systems provide convenient communication through a common address space, but cache coherence keeps copies of individual locations consistent while memory consistency defines ordering across locations. UMA is simple but difficult to scale; NUMA scales memory bandwidth at the cost of non-uniform access time.

Atomic operations, locks, barriers, condition variables, and non-blocking algorithms provide different synchronization guarantees and costs. Distributed-memory systems and clusters scale through explicit communication, but they must address network latency, partial failure, and data placement. Cloud and HPC platforms combine multicore nodes, NUMA memory, virtualization, accelerators, and high-speed networks. Effective design is therefore an exercise in coordinating computation with data, communication, correctness, reliability, security, and energy efficiency.

Key Terms

Cache coherence: The mechanism that ensures multiple cached copies of a memory location remain mutually compatible.

Cache consistency: A commonly used synonym for coherence, although formal usage may vary by context.

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

MESI: A cache-coherence protocol with Modified, Exclusive, Shared, and Invalid states.

False sharing: Performance interference caused when unrelated variables share a cache line.

UMA: Uniform memory access, in which memory-access time is approximately independent of processor location.

NUMA: Non-uniform memory access, in which local and remote memory have different costs.

ccNUMA: A NUMA system that maintains hardware cache coherence across nodes or sockets.

Thread-level parallelism: Concurrent execution of multiple independent or cooperating threads.

Data-level parallelism: Applying one operation concurrently to multiple data elements.

Amdahl’s law: A model showing how a serial fraction limits speedup on additional processors.

Sequential consistency: A memory model in which execution appears as an interleaving that preserves each processor’s program order.

Acquire: A synchronization operation that prevents later operations from moving before it.

Release: A synchronization operation that orders earlier operations before synchronization completion.

Atomic operation: An indivisible operation that cannot be observed halfway through by another thread.

Barrier: A synchronization point at which participating threads wait for one another.

Deadlock: A state in which processes wait indefinitely for resources held by one another.

Cluster: A group of networked computers cooperating for computation, availability, or load distribution.

Operational intensity: The number of computational operations performed per byte of data movement.

Roofline model: A performance model relating operational intensity to compute and bandwidth ceilings.

Review Questions

Short Answer Questions

1. How does cache coherence differ from memory consistency?

2. What are the four states in the MESI protocol?

3. Why can false sharing reduce multicore performance?

4. What is the purpose of an acquire operation?

5. Why is memory placement important in a NUMA system?

Long Answer Questions

1. Explain the organization and scalability trade-offs of UMA and NUMA multiprocessors.

2. Describe snooping and directory-based coherence protocols and compare their scalability.

3. Explain sequential, weak, and release consistency with a producer–consumer example.

4. Discuss locks, barriers, condition variables, and lock-free algorithms as synchronization mechanisms.

5. Compare shared-memory multiprocessors, distributed-memory clusters, and cloud platforms.

Analytical / Application Questions

1. A program contains a serial fraction of 0.08. Use Amdahl’s law to determine its ideal speedup with 16 processors and explain why measured speedup may be lower.

2. A NUMA application has high remote-memory traffic and poor scaling beyond one socket. Propose a diagnostic and redesign plan.

3. An HPC workload performs few arithmetic operations per byte transferred. Using the roofline concept, identify its likely bottleneck and recommend architectural or algorithmic changes.

22. Multiple Choice Questions with Answers

Question 1

Which statement best distinguishes cache coherence from memory consistency?

A. Coherence orders operations to different addresses, while consistency concerns only one address.

B. Coherence concerns the visibility of copies of a location, while consistency concerns ordering across memory operations.

C. Coherence is implemented by software, while consistency is implemented only by caches.

D. They are identical terms with no architectural distinction.

Correct Answer: B. Coherence concerns the visibility of copies of a location, while consistency concerns ordering across memory operations.

Question 2

In a MESI protocol, a cache line in the Modified state is one that:

A. Exists in several caches and is identical to memory.

B. Exists only in one cache and differs from main memory.

C. Cannot be accessed until a barrier completes.

D. Is present only in main memory.

Correct Answer: B. Exists only in one cache and differs from main memory.

Question 3

Which change most directly reduces false sharing?

A. Increasing the number of global barriers

B. Padding independently updated variables onto separate cache lines

C. Replacing local variables with shared variables

D. Reducing the cache size

Correct Answer: B. Padding independently updated variables onto separate cache lines

Question 4

A producer writes data and then sets a flag. Which synchronization pairing ensures that a consumer observing the flag can also observe the earlier data?

A. Producer acquire and consumer acquire

B. Producer release and consumer acquire

C. Producer release and consumer release

D. Two unrelated ordinary stores

Correct Answer: B. Producer release and consumer acquire

Question 5

Why does first-touch allocation matter on a NUMA system?

A. It determines the instruction-set architecture of each core.

B. It can place pages near the processor that first accesses them.

C. It disables cache coherence between sockets.

D. It guarantees that all memory accesses have identical latency.

Correct Answer: B. It can place pages near the processor that first accesses them.

Question 6

Which situation is most appropriate for a spinlock?

A. A critical section that may wait for disk input

B. A long operation with substantial contention

C. A very short critical section where the expected wait is brief

D. A thread that must sleep until an external event occurs

Correct Answer: C. A very short critical section where the expected wait is brief

Question 7

What is the principal advantage of a directory-based coherence protocol over broadcast snooping in a large system?

A. It eliminates the need for caches.

B. It sends coherence actions selectively rather than broadcasting to all caches.

C. It guarantees sequential consistency automatically.

D. It makes remote memory faster than local memory.

Correct Answer: B. It sends coherence actions selectively rather than broadcasting to all caches.

Question 8

An application has high operational intensity and reaches the compute ceiling in a roofline analysis. Which improvement is most likely to help?

A. Adding compute capability or improving arithmetic utilization

B. Increasing only network latency

C. Reducing the number of useful operations

D. Introducing more unnecessary barriers

Correct Answer: A. Adding compute capability or improving arithmetic utilization

Question 9

Which characteristic most clearly differentiates a distributed-memory cluster from a shared-memory multiprocessor?

A. Each node has private memory and communicates explicitly over a network.

B. All processors must share one cache line.

C. It cannot execute parallel tasks.

D. It requires sequential consistency for every operation.

Correct Answer: A. Each node has private memory and communicates explicitly over a network.

Question 10

A lock-free algorithm guarantees that:

A. Every thread completes each operation in a fixed number of steps.

B. No thread can ever be delayed.

C. The system as a whole makes progress even if individual threads may be delayed.

D. All operations are free of memory-ordering requirements.

Correct Answer: C. The system as a whole makes progress even if individual threads may be delayed.