00 Introduction

Introduction to Thread-Level Parallelism

Drivers of Multiprocessing and Thread-Level Parallelism

Multiprocessing has become the primary mechanism to scale computational performance due to physical limitations in scaling single-core architectures.

• Key architectural drivers:
  • Inefficiency of ILP: There are severe diminishing returns in silicon area and energy efficiency when attempting to extract further Instruction-Level Parallelism (ILP).
  • Power constraints: The end of Dennard scaling imposes strict thermal and power limits, forcing a shift from fast, complex uniprocessors to multiple efficient cores.
  • Workload shifts: The computing landscape is increasingly dominated by cloud computing, software-as-a-service, and data-intensive applications operating on massive datasets.
  • Design leverage: Multiprocessors offer high cost-performance by replicating commodity processor cores rather than engineering unique monolithic designs.
• Thread-Level Parallelism (TLP):
  • TLP relies on the existence of multiple program counters to execute independent paths of execution concurrently.
  • It is implemented primarily through Multiple Instruction, Multiple Data (MIMD) architectures.

To exploit TLP effectively, independent processor cores must be organized into cohesive systems that share data and memory structures.

Multiprocessor Architecture and Memory Organization

Shared-memory multiprocessors are computers comprising tightly coupled processors that are managed by a single operating system and communicate through a unified shared address space.

• TLP Execution Models:
  • Parallel processing: A tightly coupled set of threads collaborating on a single unified task.
  • Request-level parallelism: Multiple independent processes or applications running concurrently, often driven by separate user queries (multiprogramming).
• Grain Size:
  • Grain size defines the amount of computation assigned to a single thread.
  • TLP threads execute thousands to billions of instructions, operating at a much coarser granularity than ILP.
  • While threads can be used to exploit fine-grained data-level parallelism, the management overhead is prohibitively expensive compared to using dedicated SIMD processors.
• Shared-Memory Topologies:
  • Uniform Memory Access (UMA): All processors experience identical memory access latency. Modern UMA architectures replace legacy shared buses with a shared Last Level Cache (LLC) connected to private caches via an on-chip interconnection network.
  • Nonuniform Memory Access (NUMA): Utilizes Distributed Shared Memory (DSM) spanning multiple chips or nodes. Access latency is highly dependent on the physical distance between the requesting core and the target physical memory. NUMA systems are often combined with Nonuniform Cache Access (NUCA) to distribute the LLC.

Despite flexible memory organizations, scaling these tightly coupled architectures exposes fundamental algorithmic and physical bottlenecks.

Performance Challenges in Parallel Processing

Extracting performance from interacting parallel threads requires overcoming strict limits in available parallelism and physical communication delays.

• Limited Parallelism (Amdahl’s Law):
  • The performance gain of a multiprocessor is strictly limited by the fraction of the computation that must execute sequentially.
  • Theoretical speedup is governed by the equation: $\text{Speedup}=\frac{1}{\frac{{\text{Fraction}}_{\text{enhanced}}}{{\text{Speedup}}_{\text{enhanced}}}+(1-{\text{Fraction}}_{\text{enhanced}})}$
  • Achieving high speedup at scale requires near-zero sequential execution. For example, achieving an $80\times$ speedup on $100$ processors dictates that exactly $99.75$ of the execution must be completely parallel, leaving only $0.25$ for the serial portion.
• Communication Latency:
  • Remote memory accesses incur severe delays due to physical distance and interconnect routing overhead.
  • Communication between distinct cores costs $50$ to $100+$ clock cycles, whereas communication across separate chips can require $500$ to $1000+$ clock cycles.
  • These latencies devastate pipeline efficiency. If a processor with a $0.5$ base CPI and a $2.0\text{ GHz}$ clock ($0.5\text{ ns}$ cycle) encounters a $200\text{ ns}$ remote memory delay ($400$ penalty cycles), an instruction stream with just $0.2$ remote accesses will see its effective CPI degrade from $0.5$ to $1.3$.

Overcoming these strict performance limitations requires coordinated strategies across the entire hardware and software stack to hide or eliminate latency.

Mitigating Parallel Processing Bottlenecks

System designers employ a mix of architectural features and software optimizations to reduce the impact of remote communication latency and insufficient parallelism.

• Software Interventions:
  • Design and implement new algorithms that offer superior parallel scaling.
  • Restructure data layouts to maximize local memory accesses and minimize the frequency of remote communication.
• Hardware Interventions:
  • Caching: Store shared data in local caches to dramatically reduce the frequency of remote memory requests.
  • Multithreading: Rapidly interleave the execution of multiple threads on a single core to tolerate and hide communication latency.
  • Prefetching: Fetch data into local caches prior to explicit demand to mask the latency of data retrieval.