Computer System Architecture Part 7— Thread Level Parallelism

Computer System Architecture: Where bits and bytes embark on a cosmic road trip, and processors throw a party in the shared-memory realm. It’s the place where cache blocks mingle, and threads perform a synchronized dance. Join the tech-fiesta — where CPUs have more cores than a pineapple and memory consistency is the ultimate relationship goal. Remember, in this architecture, even the zeros and ones have a sense of humor, and the only thing more consistent than memory is the laughter echoing through the circuits.

Contents

1. Introduction
2. Centralized Shared-Memory Architectures
3. Performance of Symmetric Shared-Memory Multiprocessors
4. Distributed Shared-Memory and Directory-Based Coherence
5. Synchronization: The Basics
6. Models of Memory Consistency: An Introduction
7. Cross-Cutting Issues
8. The Future of Multicore Scaling
9. Conclusion
10. Appendix

Introduction

The significance of multiprocessors experienced a notable ascent in the 1990s as designers sought to develop servers and supercomputers that could surpass the performance of a single microprocessor. This pursuit aimed to harness the considerable cost-performance advantages offered by commodity microprocessors. However, the convergence of Amdahl’s Law effects and the cessation of Dennard scaling raises questions about the long-term viability of multicore architectures as a means of scaling up the performance of individual applications.

This article concentrates on the strategic utilization of thread-level parallelism (TLP), a concept predicated on the existence of multiple program counters and primarily exploited through Multiple Instruction, Multiple Data (MIMD) architectures. Our primary focus is on multiprocessors, defined here as tightly coupled computer systems whose coordination and utilization are typically overseen by a single operating system. These systems share memory through a unified address space, facilitating the exploitation of thread-level parallelism via two distinct software models.

The first model involves the execution of a closely-knit set of threads collaborating on a singular task, commonly referred to as parallel processing. The second model entails the execution of multiple, relatively independent processes originating from one or more users, representing a form of request-level parallelism. This form may be harnessed by a single application running on multiple processors, as exemplified by a database responding to queries, or by multiple applications operating independently, a practice often termed multiprogramming.

The multiprocessors examined in this article encompass a spectrum ranging from dual processors to systems comprising dozens, and occasionally hundreds, of processors. Communication and coordination within these systems are facilitated through shared memory. While shared memory implies a unified address space, it does not necessarily mandate a single physical memory. These multiprocessors include both single-chip systems with multiple cores, commonly known as multicore, and computers composed of multiple chips, each typically featuring multiple cores.

Multiprocessor Architecture: Issues and Approach

Maximizing the potential of Multiple Instruction, Multiple Data (MIMD) multiprocessors with n processors requires careful consideration of numerous factors. Typically, a minimum of n threads or processes is necessary for efficient execution, and in contemporary multicore chips featuring multithreading, this requirement can be 2–4 times higher. Thread identification within a single process is often the responsibility of the programmer or is autonomously generated by the operating system in response to multiple independent requests. Threads can range from being composed of a few iterations of a loop to encompassing hundreds to millions of instructions executed in parallel, highlighting the qualitative distinction of thread-level parallelism from instruction-level parallelism.

While threads are versatile for exploiting data-level parallelism, the associated overhead can be higher compared to Single Instruction, Multiple Data (SIMD) processors or Graphics Processing Units (GPUs). This necessitates a careful consideration of the grain size, ensuring it is sufficiently large to efficiently exploit the parallelism.

Shared-memory multiprocessors are categorized into two classes based on the number of processors involved. Symmetric (shared-memory) multiprocessors (SMPs), or centralized shared-memory multiprocessors, typically feature small to moderate numbers of cores, often 32 or fewer. In multicore chips, memory is commonly shared centrally among the cores, with some featuring Nonuniform Cache Access (NUCA). However, as the number of processors grows, the centralized approach becomes less attractive, leading to the adoption of distributed memory in the form of distributed shared memory (DSM) architectures.

Basic structure of a centralized shared-memory multiprocessor based on a multicore chip.

In DSM multiprocessors, memory distribution among processors becomes crucial for supporting larger processor counts while maintaining bandwidth and minimizing access latency. This design, also known as Nonuniform Memory Access (NUMA), acknowledges that access times vary based on the location of data in memory.

The basic architecture of a distributed-memory multiprocessor.

Whether employing SMP or DSM architectures, communication among threads is facilitated through a shared address space. This shared memory concept implies that any processor can make a memory reference to any location, assuming the correct access rights. The term “shared memory” in both SMP and DSM contexts emphasizes the collaborative nature of the address space. Understanding these nuances is paramount for architects and developers navigating the complexities of multiprocessor systems in pursuit of optimal performance.

Challenges of Parallel Processing

The deployment of multiprocessors spans a spectrum from executing independent tasks with minimal communication to running parallel programs where effective communication among threads is imperative for task completion. Two significant challenges characterize the landscape of parallel processing, necessitating strategic considerations.

The first challenge pertains to the inherent limitations in program parallelism, posing a formidable barrier to achieving substantial speedups in any parallel processor. Adapting Amdahl’s Law for parallel processing, the speedup in enhanced mode is directly proportional to the number of processors, while the fraction of time spent in parallel mode influences the overall performance.

Speedup in enhanced mode is simply the number of processors, whereas the fraction of enhanced mode is the time spent in parallel mode.

Amdahl’s Law with more terms.

The second major challenge revolves around the substantial latency associated with remote access in parallel processors. In shared-memory multiprocessors, data communication between distinct cores incurs a cost of 35–50 clock cycles, and among cores on separate chips, this latency can range from 100 to over 300 clock cycles, contingent upon factors such as the communication mechanism, interconnection network type, and the scale of the multiprocessor.

To quantify the overall performance of a multiprocessor, the effective cycles per instruction (CPI) must be calculated.

Where,

The paramount issues of insufficient parallelism and extended remote communication latency emerge as the predominant performance challenges in the realm of multiprocessors.

Addressing the dearth of application parallelism necessitates a concerted effort in software development, involving the creation of novel algorithms that enhance parallel performance. Additionally, software systems must optimize the utilization of processors, ensuring they operate at maximum capacity. Mitigating the impact of remote latency demands a multifaceted approach, incorporating both architectural enhancements and programmer interventions. Hardware mechanisms, such as caching shared data, and software strategies, like data restructuring to localize accesses, are pivotal in alleviating the effects of prolonged remote latency, contributing to the overall efficiency of parallel processing systems.

Centralized Shared-Memory Architectures

In the realm of recent, high-performance processors, the escalating memory demands have surpassed the capacity of conventional buses. Modern microprocessors address this challenge by directly connecting memory to a single chip, often referred to as a backside or memory bus, distinct from the I/O bus. Symmetric shared-memory machines play a pivotal role in this architecture, accommodating both shared and private data caching. Private data is exclusive to a single processor, while shared data facilitates communication among processors through shared data reads and writes.

Caching private data enhances program performance by migrating the data to the cache, reducing average access time and minimizing memory bandwidth requirements. In contrast, caching shared data involves replicating the shared value across multiple caches, not only reducing access latency and memory bandwidth but also alleviating contention among processors concurrently accessing shared data items. This architectural approach optimizes program behavior in a multiprocessor environment.

What Is Multiprocessor Cache Coherence?

In the context of multiprocessor systems, the challenge of maintaining a consistent view of memory arises due to the individual caches held by distinct processors. This issue, commonly known as the cache coherence problem, stems from the fact that processors may perceive different values for the same memory location based on their respective caches. The underlying complexity results from the coexistence of a global state, primarily governed by the main memory, and a local state, inherent in the private caches exclusive to each processor core.

Informally, a memory system is considered coherent when any read operation returns the most recently written value for the corresponding data item. Coherence, defining the values returned by a read, and consistency, determining when a written value is returned by a read, are integral aspects of a coherent memory system.

A memory system is deemed coherent if certain conditions are met, such as:

1. A read by processor P to location X that follows a write by P to X, with no writes of X by another processor occurring between the write and the read by P, always returns the value written by P.
2. A read by a processor to location X that follows a write by another processor to X returns the written value if the read and write are sufficiently separated in time and no other writes to X occur between the two accesses.
3. Writes to the same location are serialized; that is, two writes to the same location by any two processors are seen in the same order by all processors; this property is called write serialization.

Furthermore, coherence is intricately connected with consistency. While coherence governs the behavior of reads and writes to the same memory location, consistency defines the behavior of reads and writes concerning accesses to other memory locations.

Basic Schemes for Enforcing Coherence

In a multi-processor environment, a program typically stores identical data copies in various caches. In a well-designed and coherent multiprocessor system, caches play a dual role, facilitating both the migration and replication of shared data items.

Protocols dedicated to preserving coherence across multiple processors are known as cache coherence protocols. There exist two primary classes of these protocols, each employing distinct techniques to monitor the sharing status:

1. Directory-Based Protocol: This involves maintaining the sharing status of a specific block of physical memory in a centralized location known as the directory.
2. Snooping Protocol: Instead of consolidating the sharing state in a single directory, each cache holding a copy of data from a block of physical memory monitors the sharing status of that block.

Snooping protocols gained prominence in multiprocessor systems utilizing microprocessors (single core) and caches linked to a shared memory via a bus. The bus served as a practical broadcast medium for implementing snooping protocols.

There are two methodologies to meet the coherence requirement outlined. One approach ensures that a processor attains exclusive access to a data item before writing, known as a write invalidate protocol. If two processors attempt to write the same data simultaneously, one emerges victorious, invalidating the copy held by the other processor. To complete its write, the latter processor must acquire a new copy containing the updated value, thereby enforcing write serialization.

The alternative protocol to the write invalidate method is the write update or write broadcast protocol. This approach involves updating all cached copies of a data item when the item is written. Each of these protocols contributes distinct advantages and considerations to the pursuit of maintaining coherence in multiprocessor systems.

Basic Implementation Techniques

To implement an invalidate protocol in a multicore system, the key is to use the bus, or another broadcast method, for invalidations. In older multiprocessors with multiple chips, the bus for coherence is the shared-memory access bus. Here’s how it works: when a processor needs to invalidate data, it gets access to the bus and shares the address to be invalidated. All processors monitor the bus and check if the address is in their cache. If it is, they invalidate the corresponding data in their cache.

If two processors try to write to the same data simultaneously, their attempts to invalidate will be ordered when they compete for bus access. The first processor to get access will invalidate other copies of the data block. If both processors were trying to write the same block, the bus’s ordering will also order their writes.

For a write-back cache, finding the most recent data value is trickier, as it can be in a private cache rather than in shared cache or memory. Fortunately, write-back caches can use the same snooping scheme for cache misses and writes. Each processor checks every address on the shared bus.

To minimize interference, one can duplicate the cache tags, directing snoop accesses to these duplicates. Alternatively, a directory at the shared L3 cache can be used, indicating whether a block is shared and which cores have copies. With this directory information, invalidates can be directed only to caches with copies of the data block. This approach requires L3 always to have a copy of any data item in L1 or L2, known as inclusion.

An Example Protocol

A snooping coherence protocol is a way of ensuring that data stays consistent in a multiprocessor system. In this setup, each core has a controller that manages the state of its cache block based on requests from the processor and the shared bus. The protocol we’re discussing here has three states for the data block: invalid, shared, and modified.

1. Invalid State: This means the data in the private cache is not valid.
2. Shared State: The block in the private cache could be shared with other cores.
3. Modified State: The block has been updated in the private cache, and it’s exclusive to that core.

No matter if the level out from the private caches is a shared cache or memory, all core accesses go through that level.

The protocol assumes that actions are atomic, meaning they can happen without any interruption. This is crucial to avoid potential deadlocks where the protocol can’t continue.

Cache coherence state diagram with the state transitions induced by the local processor shown in black and by the bus activities shown in gray.

The coherence protocol we’ve discussed is a simple three-state MSI (Modified, Shared, Invalid) protocol. There are more advanced versions like MESI (adding Exclusive) and MOESI (adding Owned) that optimize certain behaviors for potentially better performance.

1. MESI adds the state Exclusive to the basic MSI protocol, yielding four states (Modified, Exclusive, Shared, and Invalid). The exclusive state indicates that a cache block is resident in only a single cache but is clean.
2. MOESI adds the state Owned to the MESI protocol to indicate that the associated block is owned by that cache and out-of-date in memory.

Limitations in Symmetric Shared-Memory Multiprocessors and Snooping Protocols

As the number of processors in a multiprocessor system increases or the memory demands of each processor grow, a centralized resource in the system, such as a single shared bus, can become a bottleneck. In the case of multicores, even with just a few cores, a single shared bus can limit performance. Consequently, modern multicore designs utilize higher bandwidth interconnection schemes and multiple independent memories to accommodate larger numbers of cores.

Several techniques address the challenge of increasing snoop bandwidth:

1. Tag Duplication: Duplicating tags to enhance the efficiency of snooping operations.
2. Distributed Caching: Distributing the outermost cache (usually L3) so that each processor manages a portion of the memory and handles snoops for that specific address space segment.
3. Directory Placement: Introducing a directory at the level of the outermost shared cache to facilitate snooping operations.

To prevent conflicts when two processors attempt to write the same block simultaneously, known as a race condition, a strict order must be maintained. In multicore systems using multiple buses, races can be avoided by associating each memory block with a single bus. This ensures that attempts to access the same block are serialized by the common bus. The ability to restart the miss handling of the loser in a race, along with this property, is crucial for implementing snooping cache coherence without relying on a shared bus.

Performance of Symmetric Shared-Memory Multiprocessors

In a multicore system utilizing a snooping coherence protocol, various factors contribute to overall performance. The overall cache performance is influenced by both uniprocessor cache miss traffic and the traffic resulting from inter-processor communication, leading to invalidations and subsequent cache misses. Altering the processor count, cache size, and block size can impact these components differently, influencing the system’s behavior as a combination of both effects.

Misses stemming from inter-processor communication, known as coherence misses, have two distinct sources:

1. True Sharing Misses: These occur when data is communicated through the cache coherence mechanism. In an invalidation-based protocol, the first write by a processor to a shared cache block triggers an invalidation to establish ownership. Additionally, when another processor attempts to read a modified word in that cache block, a miss occurs, classifying both misses as true sharing misses due to direct data sharing among processors.
2. False Sharing: Resulting from the use of an invalidation-based coherence algorithm with a single valid bit per cache block. False sharing happens when a block is invalidated (resulting in a subsequent miss) because a word other than the one being read is written into.

Considering the performance of multiprogramming and operating system workloads, the behavior of the operating system can lead to more cache misses than user processes. This is attributed to the larger code size, lack of locality, and the kernel’s initialization of pages before allocating them to a user. Kernel data sharing also contributes to a nontrivial coherence miss rate. Increasing data cache size impacts the user miss rate more than the kernel miss rate. Larger block sizes benefit both miss rates, particularly for compulsory and capacity misses.

The effects of increasing block size on coherence misses are relatively small, suggesting that false sharing effects are likely insignificant, although they may offset some gains from reducing true sharing misses. In a multiprogram workload, the operating system places more demands on the memory system.

Distributed Shared-Memory and Directory-Based Coherence

In a snooping protocol, each cache communicates with all others on every cache miss, involving potential writes to shared data. While this approach is cost-effective, its Achilles’ heel lies in scalability due to the lack of a centralized data structure tracking cache states.

To enhance memory and interconnection bandwidth, distributing memory separates local and remote traffic, easing demands on the memory system and network. An alternative to snooping is the directory protocol, where a directory maintains the state of each cache block, including which caches have copies and whether it’s dirty.

Directory-Based Cache Coherence Protocols: The Basics

Similar to snooping, a directory protocol focuses on handling read misses and writes to shared, clean cache blocks. States in a simple protocol include:

1. Shared: Multiple nodes have the cached block, and memory is up to date.
2. Uncached: No node holds a copy of the cache block.
3. Modified: One node owns the block, having written it, rendering the memory copy outdated.

Nodes involved are the local node (request origin) and the home node (where memory and directory entries reside). With a statically distributed physical address space, accessing the directory is necessary when the home node is local, as copies may exist in a remote node.

Synchronization: The Basics

Synchronization methods are commonly developed using user-level software routines that rely on hardware-supplied synchronization instructions. In smaller multiprocessors or situations with low contention, a crucial hardware capability involves an uninterruptible instruction or sequence capable of atomically retrieving and changing a value. Software synchronization mechanisms are then crafted using this capability.

Lock and unlock operations can be directly applied to establish mutual exclusion and to implement more intricate synchronization methods.

Basic Hardware Primitives

In multiprocessors, a vital requirement for synchronization is a set of hardware primitives with the ability to atomically read and modify a memory location. The absence of such a capability would result in high costs for building basic synchronization primitives, particularly as the processor count increases.

An example of a typical operation for building synchronization operations is the atomic exchange, which swaps a value in a register with a value in memory.

Implementing Locks Using Coherence

Once an atomic operation is available, coherence mechanisms in a multiprocessor can be utilized to implement spin locks — locks that a processor continually attempts to acquire by spinning around a loop until successful. Spin locks are employed when programmers anticipate the lock to be held for a brief period and desire low latency in the locking process when the lock is available.

Models of Memory Consistency: An Introduction

Cache coherence ensures a consistent memory view across multiple processors. One fundamental model for memory consistency is sequential consistency. It requires that the result of any execution matches if the memory accesses by each processor were sequentially ordered, and the accesses among different processors were arbitrarily interleaved.

The simplest way to achieve sequential consistency is to make a processor delay the completion of any memory access until all invalidations caused by that access are finished.

Note — Waiting for invalidations makes each write take the sum of ownership time plus the time to complete the invalidates.

The Programmer’s View

An efficient implementation is possible with a programming model assuming programs are synchronized. A program is synchronized if all accesses to shared data are ordered by synchronization operations. Data reference is ordered by a synchronization operation if, in every execution, a write by one processor and an access by another processor are separated by synchronization operations.

Cases where variables may update without ordering by synchronization are called data races. Synchronized programs, which use standard synchronization primitives, behave as if implemented with sequential consistency, even if the hardware employs a more relaxed consistency model.

Relaxed Consistency Models: The Basics and Release Consistency

Relaxed consistency models allow out-of-order completion for reads and writes, using synchronization operations to enforce ordering. Sequential consistency requires maintaining four orderings: R → W, R → R, W → R, and W → W. Relaxed models are defined by the subset they relax:

1. Relaxing only W → R yields total store ordering or processor consistency.
2. Relaxing both W → R and W → W yields partial store order.
3. Relaxing all four orderings leads to various models, including weak ordering, PowerPC consistency, and release consistency (RISC V consistency).

Release consistency distinguishes between synchronization operations for acquiring access and those for releasing an object to allow another processor to acquire access. It’s based on the observation that, in synchronized programs, an acquire operation precedes the use of shared data, and a release operation follows updates to shared data and precedes the next acquire.

Note — An acquire typically reads and atomically updates a synchronization variable, while a release usually only writes it.

Cross-Cutting Issues

Multiprocessors redefine various system characteristics, such as performance assessment, memory latency, and scalability importance, leading to design challenges that impact both hardware and software.

Defining a memory consistency model helps specify legal compiler optimizations for shared data. Speculation, a dynamic scheduling technique, can hide memory latency and provide benefits similar to a relaxed memory model. In speculation, processors reorder memory references using dynamic scheduling, allowing potential out-of-order execution. If an invalidation occurs before a memory reference is committed, speculation recovery is employed to backtrack and restart with the invalidated memory reference.

Multilevel cache hierarchies are a common feature in multiprocessors to reduce global interconnect demand and cache miss latency. With multilevel inclusion, where each cache hierarchy level is a subset of the level farther from the processor, contention between coherence traffic and processor traffic is reduced. This occurs when snoops and processor cache accesses compete for the cache.

The Future of Multicore Scaling

For over three decades, researchers and designers have anticipated the decline of uniprocessors and the rise of multiprocessors. Until the early 2000s, this expectation consistently proved incorrect. While multicore architectures don’t inherently resolve the power challenge, as they increase both transistor count and active transistors switching — key contributors to power consumption — thereby challenging power efficiency.

The limitations of CMOS scaling primarily stem from thermal power constraints, comprising static leakage power and dynamic power dominance. Power is given by:

Where Energy = Capacitive Load x Voltage²

Conclusion

In conclusion, while multicore architectures don’t offer a magical solution to the power problem due to increased transistor count and active transistors switching, they introduce a shift in the paradigm. Dennard scaling’s failure intensifies the challenge, but multicore systems provide avenues for improved power efficiency. The ability to put idle cores in power-saving mode, as demonstrated in this chapter, offers some relief. For instance, shutting down cores in processors like the Intel i7 enables others to operate in Turbo mode, allowing a flexible trade-off between higher clock rates and fewer processors or more processors with lower clock rates.

Moreover, multicore architecture changes the dynamics of processor utilization. It places a greater emphasis on Thread-Level Parallelism (TLP), requiring applications and programmers to identify opportunities for parallel execution. This shift from Instruction-Level Parallelism (ILP) to TLP benefits metaprogrammes and highly parallel workloads, particularly those capable of mitigating Amdahl’s Law effects.

Appendix

Equation for the number of cache cycles that can be used (where CMR is the coherence miss rate):

Terminologies Explained

1. True Sharing Miss: Definition: Occurs when multiple processors attempt to access the same data simultaneously, leading to cache coherence issues.
2. False Sharing Miss: Definition: Refers to a situation where different processors modify different variables residing on the same cache line, causing unnecessary cache invalidations.
3. Hit: Definition: Denotes a successful data retrieval operation from the cache, indicating that the required data was found in the cache without accessing the main memory.
4. Cache Block: Definition: The smallest unit of data that can be stored in the cache, also known as a cache line. It is usually a contiguous section of main memory copied to the cache for quick access.
5. Shared State: Definition: Indicates that a cache block is present in the caches of multiple processors, allowing them to read the data without accessing the main memory.