Stanford CS149 I Parallel Computing I 2023 I Lecture 11 - Cache Coherence
22 Sep 2024 (4 days ago)
Spark: Distributed Computing Framework
- Spark aims to enable efficient distributed computing for applications that heavily utilize intermediate data, such as iterative algorithms and queries.
- Resilient Distributed Datasets (RDDs) are the key abstraction in Spark, representing read-only, ordered collections of records.
- Spark optimizes for locality through techniques like fusion and tiling to enhance parallel performance.
- Transformations can have wide dependencies that require communication between nodes in a system, for example, a group by key operation.
- If data is partitioned using the same hash partitioner, the runtime system can detect narrow dependencies and perform fusion, reducing communication overhead.
- Spark maintains fault tolerance through lineage, which is a log of transformations applied to RDDs, allowing for data recreation from persistent storage.
- If a node crashes during computation, the system recovers by rerunning the log of operations to recreate lost data partitions. This leverages data replication in HDFS and the coarse-grained nature of the operation log.
- Spark offers significant performance improvements, often orders of magnitude faster than Hadoop, due to its use of in-memory processing and reduced reliance on disk access for iterative tasks.
- Spark's ecosystem includes domain-specific frameworks like Spark SQL for database processing, Spark MLlib for machine learning, and Spark GraphX for graph operations, all built upon the underlying RDD abstraction.
- Spark can be extended beyond transformations and actions to perform tasks like graph analysis and database operations.
- If data fits in memory, using a distributed system like Spark is not recommended due to overheads, as a single system will be more efficient.
Cache Memory: Exploiting Locality
- Modern processors dedicate a significant portion of their chip area to cache (30% or more) to enhance performance by exploiting locality.
- Cache lines are used to exploit spatial locality in program behavior, which is the tendency to access memory locations that are close together.
- The Intel Skylake chip, found in the myth machines, has a 32 kilobyte L1 data cache that is 8-way set associative, meaning that any given cache line can only be stored in one of eight places in the cache.
- Conflict misses occur when the limited associativity of a cache prevents a cache line from being stored in a particular location, even if there are other available locations in the cache.
- Set-associative caches are organized into sets, which can be visualized as buckets, with each set containing a fixed number of cache lines.
- As cache size increases, the set associativity does not always increase proportionally.
- A cache line consists of data and metadata. The metadata includes a tag, which stores the memory address of the data, and a dirty bit, indicating whether the data in the cache has been modified.
- In a write-back cache, data is written to the cache first and only later written to the main memory. In contrast, a write-through cache writes data to both the cache and main memory simultaneously.
- Write-allocate, used with write-back caches, fetches the entire cache line from main memory upon a write miss and then writes the data.
- Right back caches write data to the cache and set a dirty bit, while right through caches write data to both the cache and memory simultaneously, eliminating the need for a dirty bit.
- The tag in a cache represents the address of a cache line, not just a single variable, allowing for spatial locality.
- Higher set associativity in a cache reduces miss rates but increases the complexity of cache lookups.
Cache Coherence: Maintaining Data Consistency
- When multiple processors with individual caches are connected to a main memory, a memory coherence problem can occur.
- If multiple processors read and write to the same memory address, inconsistencies can arise because updates to one cache might not be reflected in other caches or the main memory.
- Determining the "last" value written to a memory address becomes complex in a multi-processor system because simultaneous writes from different processors need a clear order to ensure data consistency.
- For any given memory location, access should be serialized to maintain coherence. This means that reads and writes to a specific address should happen in the order issued by the processor, ensuring subsequent reads reflect the last write to that location.
- Two key invariants are crucial for cache coherence: the single writer multiple reader invariant, which allows only one processor to modify a cache line at a time while permitting multiple readers, and the data value invariant, which ensures that all readers see the last written value during a read-only epoch.
- While software-based solutions using virtual memory pages are possible, they are slow and prone to issues like false sharing. Hardware-based solutions operating at the cache line level, such as snooping and directory-based systems, offer a more efficient approach to maintaining cache coherence.
- A single shared cache for multiple processors can lead to a performance bottleneck due to bandwidth limitations and interference between processors.
- Shared caches can experience both constructive interference, such as pre-fetching data for subsequent iterations, and destructive interference, where one processor's cache misses are caused by another processor.
Snooping Cache Coherence: Using a Bus
- Snooping cache coherence schemes use an interconnect, such as a bus, to connect processors and their caches, allowing them to communicate and maintain data consistency.
- Buses have two important properties for cache coherence: they allow only one transaction at a time, providing serialization, and they broadcast all transactions to all connected devices.
- A bus in computer architecture functions as a broadcast medium, where all processors receive communication from a single source.
- The MSI protocol, used in cache coherence, utilizes three states: Modified, Shared, and Invalid.
- The MSI protocol ensures exclusive access for write operations by using a combination of processor operations (processor read, processor write) and bus transactions (bus read, bus read exclusive, bus write back).