Parallel Processing and Cache Memory

Understanding Parallel Processing

Parallel processing is a cornerstone of modern computing, enabling faster execution by dividing work among multiple processing units. This course explores the fundamental concepts, types of parallelism, and the challenges that arise when scaling up to many processors.

Types of Parallelism

Parallelism can be classified based on how work is divided and coordinated. The most common categories are:

• Data Parallelism: The same operation is performed simultaneously on different pieces of data. This is the answer to the question "Which type of parallelism executes the same operation on different data elements simultaneously?" – Data parallelism.
• Task (or Function) Parallelism: Independent functions or tasks run at the same time. A program with several independent functions exemplifies Control parallelism, where each function can be scheduled on a separate core.
• Pipeline Parallelism: Stages of a computation are overlapped, similar to an assembly line.
• Speculative Parallelism: Executes possible future paths in parallel, discarding the ones that are not needed.

Challenges in Parallel Systems

When the number of processors exceeds the number of independent parallel tasks, the primary bottleneck is resource dependencies. This occurs because there are not enough parallelizable units of work to keep every processor busy, leading to idle cores and reduced efficiency.

Another critical challenge is communication overhead. If a parallel application suffers from high communication delays, the overall speedup is reduced because the time spent exchanging data dominates the computation.

Parallel Hardware Platforms

Various hardware platforms support parallel execution:

• Clusters: Collections of independent computers linked by a local network. They are ideal for scaling out workloads and answer the question "Which platform consists of many independent computers connected via a local network to work together?" – Cluster.
• GPUs, supercomputers, and grids each have distinct architectures and use‑cases, but clusters remain the most common entry point for distributed parallelism.

Cache Memory Fundamentals

Cache memory bridges the speed gap between the CPU and main memory. Understanding cache policies, replacement algorithms, and write strategies is essential for designing high‑performance parallel systems.

Cache Write Policies

Two main strategies dictate when modified data (a "dirty" cache line) is written back to main memory:

• Write‑Through: Every write updates both the cache and main memory immediately.
• Write‑Back: Modified data stays in the cache until the line is evicted. This answers the quiz question: in a write‑back cache, data is written to main memory when the cache line is evicted.

Write‑back reduces memory traffic, which is especially beneficial in multi‑core environments where many cores share the same memory hierarchy.

Cache Replacement Algorithms

When a cache becomes full, the system must decide which line to discard. The most widely used algorithm is Least Recently Used (LRU), which evicts the line that has not been accessed for the longest time. Other algorithms include FIFO, LFU, and Random, but LRU typically offers the best balance between performance and implementation cost.

Cache Size in Multi‑Core Processors

Multi‑core processors often feature larger caches than single‑core designs. The primary reason is to reduce the frequency of main‑memory accesses across cores. Larger shared or per‑core caches increase the likelihood that needed data resides close to the executing core, lowering latency and improving overall throughput.

Performance Metrics and Speedup

Evaluating parallel systems involves measuring speedup, efficiency, and scalability. Amdahl's Law provides a theoretical limit based on the proportion of serial code, while Gustafson's Law emphasizes scaling problem size with more processors.

Impact of Communication Overhead

High communication delays directly affect speedup. As the number of processors grows, the cost of synchronizing and transferring data can outweigh the benefits of additional compute resources, leading to diminishing returns.

Optimizing for Cache and Parallelism

To achieve optimal performance:

• Design algorithms that maximize data parallelism and minimize inter‑task dependencies.
• Use cache‑friendly data structures and access patterns to exploit spatial and temporal locality.
• Choose appropriate cache replacement policies (e.g., LRU) to keep hot data in the cache.
• Balance the number of tasks with available cores to avoid resource dependency bottlenecks.

Key Takeaways

• Data parallelism applies the same operation to multiple data elements simultaneously.
• Write‑back caches defer writing modified data until eviction, reducing memory traffic.
• Resource dependencies become the main limitation when processors outnumber parallel tasks.
• Control parallelism describes programs with independent functions that can run concurrently.
• L​RU is the standard cache replacement algorithm that evicts the least recently used line.
• Communication overhead reduces speedup in parallel applications.
• Clusters consist of many independent computers linked by a local network.
• Multi‑core processors use larger caches to minimize main‑memory accesses across cores.

By mastering these concepts, you can design and evaluate efficient parallel systems that fully leverage modern multi‑core and distributed architectures.