Parallel Processors from Client to Cloud
6.1 Introduction
Multiprocessor: A computer system containing at least two processors that cooperate to perform work.
Multicore Processor: A single integrated circuit containing multiple processor cores.
Parallel Processing Program: A single program that runs on multiple processing units simultaneously.
Task-Level Parallelism: The use of multiple processors to execute independent programs or tasks concurrently.
Data-Level Parallelism: The simultaneous application of the same operation to multiple data elements.
Cluster: A collection of independent computers connected by a network and used together as one system.
Scalability: The ability of a system to handle more work effectively as processing resources are added.
6.2 The Difficulty of Creating Parallel Processing Programs
1) Parallel Program Development
Decomposition: Dividing a problem into tasks that can execute in parallel.
Data Dependence: A relationship that constrains execution order because one operation uses data produced or modified by another.
Synchronization: Coordination that ensures parallel tasks access shared state in a safe and required order.
Communication: The exchange of data between parallel tasks or processors.
Communication Overhead: Extra time and resources spent transferring data rather than performing useful computation.
Load Balancing: Distributing work so that processing units finish at approximately the same time.
Granularity: The amount of computation performed by a parallel task between communication or synchronization events.
2) Speedup and Scaling
Parallel Speedup: The ratio of execution time on one processor to execution time on processors.
Parallel Efficiency: The achieved speedup divided by the number of processors.
Strong Scaling: Reducing execution time by increasing the number of processors while keeping the total problem size fixed.
Weak Scaling: Increasing the problem size in proportion to the number of processors while attempting to keep execution time constant.
Amdahl's Law: The maximum speedup is limited by the fraction of execution that remains sequential.
is the parallelizable fraction and is the number of processors.
6.3 SISD, MIMD, SIMD, SPMD, and Vector
1) Flynn's Classification
Single Instruction, Single Data (SISD): One processor executes one instruction stream on one data stream.
Single Instruction, Multiple Data (SIMD): One instruction controls operations on multiple data elements simultaneously.
Multiple Instruction, Multiple Data (MIMD): Multiple processors independently execute different instruction streams on different data.
| Model | Instruction streams | Data streams | Typical use |
|---|---|---|---|
| SISD | 1 | 1 | Sequential processor |
| SIMD | 1 | Many | Vector units and GPUs |
| MIMD | Many | Many | Multicore systems and clusters |
2) Programming Models
Single Program, Multiple Data (SPMD): A programming model in which multiple processors run the same program on different portions of data.
Vector Architecture: An architecture with instructions that operate on ordered collections of data elements.
Vector Instruction: A single instruction that specifies an operation on multiple elements of one or more vectors.
Vector Length: The number of data elements operated on by a vector instruction.
Gather: A vector memory operation that loads elements from noncontiguous addresses.
Scatter: A vector memory operation that stores elements to noncontiguous addresses.
6.4 Hardware Multithreading
Hardware Thread: An independently managed architectural execution state within a processor core.
Hardware Multithreading: A technique that allows one core to maintain and execute multiple hardware threads.
Thread-Level Parallelism: Parallel execution of independent instruction streams from multiple threads.
Fine-Grained Multithreading: Switching to a different thread on each clock cycle, often in round-robin order.
Coarse-Grained Multithreading: Switching threads only after a costly stall, such as a last-level cache miss.
Simultaneous Multithreading (SMT): Issuing instructions from multiple threads in the same clock cycle on a multiple-issue processor.
Latency Hiding: Performing work from another thread while one thread waits for a long-latency event.
6.5 Multicore and Other Shared Memory Multiprocessors
1) Shared Memory
Shared Memory Multiprocessor (SMP): A parallel computer in which processors communicate through a shared physical address space.
Uniform Memory Access (UMA): A shared-memory organization in which memory access time is approximately independent of the requesting processor.
Nonuniform Memory Access (NUMA): A shared-memory organization in which access time depends on the location of the processor and memory.
Shared Variable: A memory location accessible by more than one thread or processor.
2) Cache Coherence
Cache Coherence: The property that all processors observe a consistent value for each shared memory location despite private caches.
Coherence Miss: A cache miss caused by another processor's access to the same cache block.
Snooping Protocol: A coherence protocol in which caches monitor transactions on a shared communication medium.
Directory Protocol: A coherence protocol that tracks sharers and owners of cache blocks in a distributed directory.
Write Invalidate: A coherence strategy that invalidates other cached copies before a processor writes a shared block.
False Sharing: Performance loss caused when processors modify different variables that happen to occupy the same cache block.
3) Memory Ordering
Memory Consistency Model: The architectural rules defining the order in which memory operations from different processors may become visible.
Memory Fence: An instruction that restricts reordering of memory operations across a specified point.
Atomic Operation: An operation on shared state that appears indivisible to other processors.
6.6 Introduction to Graphics Processing Units
1) GPU Architecture
Graphics Processing Unit (GPU): A throughput-oriented processor containing many execution units optimized for highly parallel workloads.
Streaming Multiprocessor: A GPU processing unit that schedules and executes groups of threads on shared hardware resources.
Single Instruction, Multiple Threads (SIMT): A GPU execution model in which many threads execute the same instruction while retaining separate thread state.
Warp: A group of GPU threads scheduled and executed together using SIMT hardware.
Thread Block: A group of threads that can cooperate through fast shared memory and synchronization.
Grid: The complete collection of thread blocks launched for one GPU kernel.
Kernel: A function executed in parallel by many GPU threads.
2) GPU Execution
Branch Divergence: A condition in which threads in one warp follow different control-flow paths and must execute those paths separately.
Memory Coalescing: Combining nearby memory requests from multiple GPU threads into fewer wide memory transactions.
Occupancy: The proportion of a GPU's available thread capacity that is active.
GPU Throughput: The rate of completed operations across many parallel threads rather than the latency of one thread.
6.7 Clusters, Warehouse-Scale Computers, and Message Passing
1) Message-Passing Systems
Message Passing: Communication in which processors exchange explicitly sent and received data rather than accessing shared memory directly.
Distributed Memory: A system organization in which each processor or node has private local memory.
Message Passing Interface (MPI): A standardized library interface for communication among processes in distributed-memory programs.
Send and Receive: Basic message-passing operations used to transfer data between processes.
2) Clusters
Compute Node: An independent computer that contributes processors, memory, and network interfaces to a cluster.
Cluster: A group of networked computers used together to run parallel programs or services.
Availability: The probability that a system is operational and able to deliver service when required.
Failover: Transferring work to another component or node after a failure.
3) Warehouse-Scale Computers
Warehouse-Scale Computer (WSC): A datacenter-scale system designed and operated as one large computer.
Scale-Out: Increasing capacity by adding more servers or nodes.
Service-Level Objective (SLO): A target for service behavior such as latency, availability, or throughput.
Tail Latency: The response time experienced by the slowest fraction of requests, often measured with a high percentile.
6.8 Introduction to Multiprocessor Network Topologies
Interconnection Network: Hardware that transports data among processors, memories, or cluster nodes.
Network Topology: The arrangement of nodes and communication links in an interconnection network.
Network Diameter: The maximum number of links on the shortest path between any pair of nodes.
Bisection Bandwidth: The minimum total bandwidth crossing a cut that divides a network into two equal halves.
Link Bandwidth: The amount of data a network link can transfer per unit time.
Network Latency: The time required for a message to travel from source to destination.
| Topology | Main characteristic |
|---|---|
| Bus | All nodes share one communication medium |
| Ring | Each node connects to two neighbors in a cycle |
| Mesh | Nodes connect to nearby nodes in a grid |
| Torus | A mesh with wraparound links |
| Crossbar | Dedicated switching paths connect many inputs and outputs |
| Tree | Hierarchical links connect leaves through switches |
| Fat Tree | Higher tree levels provide increased aggregate bandwidth |
Routing: The process of selecting the path a message takes through a network.
Contention: Competition among messages for the same network resources.
6.9 Communicating to the Outside World: Cluster Networking
Cluster Network: A network connecting compute nodes for message passing, storage access, and system management.
Ethernet: A widely used network technology for general-purpose local and datacenter communication.
InfiniBand: A high-bandwidth, low-latency interconnect commonly used in high-performance computing clusters.
Remote Direct Memory Access (RDMA): Direct transfer between the memories of networked computers with limited CPU involvement.
Network Interface Controller (NIC): Hardware that connects a computer to a network and processes network transfers.
Communication Time: The combination of message startup latency and transfer time.
6.10 Multiprocessor Benchmarks and Performance Models
1) Benchmarking Parallel Systems
Parallel Benchmark: A workload used to measure the performance and scalability of a parallel computer.
Fixed-Size Speedup: Speedup measured while keeping the problem size constant as processors are added.
Scaled Speedup: Performance improvement measured while increasing the problem size with the processor count.
Linear Speedup: A speedup approximately equal to the number of processors.
Superlinear Speedup: A measured speedup greater than the number of processors, often caused by cache effects or differences in the compared implementations.
2) Performance Limits
Serial Fraction: The portion of execution that cannot benefit from additional processors.
Synchronization Overhead: Time spent coordinating parallel tasks.
Load-Imbalance Overhead: Idle time caused by uneven distribution of work.
Communication-to-Computation Ratio: The amount of communication required relative to useful computation.
3) Roofline Model
Roofline Model: A performance model that bounds attainable performance using peak computation rate, memory bandwidth, and arithmetic intensity.
Arithmetic Intensity: The number of arithmetic operations performed per byte transferred from memory.
Attainable Performance: The lower of peak computational performance and the memory-bandwidth limit.
Memory-Bound Workload: A workload limited primarily by data-transfer bandwidth.
Compute-Bound Workload: A workload limited primarily by arithmetic execution capacity.
6.11 Real Stuff: CPU versus GPU Benchmarking
Workload Dependence: The relative performance of CPUs and GPUs depends on an application's parallelism, control flow, arithmetic intensity, precision, and memory-access pattern.
CPU Strength: Low-latency execution, complex control flow, large caches, and strong single-thread performance.
GPU Strength: High throughput for workloads with abundant data parallelism and regular computation.
Peak-Performance Limitation: Theoretical peak operation rates do not predict observed performance without considering memory, control, and synchronization behavior.
Gather-Scatter Support: Hardware support for vector accesses to noncontiguous memory locations.
Benchmark Fairness: Comparisons should use optimized implementations, equivalent numerical requirements, and representative input data on all platforms.
6.12 Going Faster: Multiple Processors and Matrix Multiply
OpenMP: A shared-memory programming interface that uses compiler directives to create and coordinate parallel threads.
Parallel Loop: A loop whose independent iterations are distributed across multiple threads.
Thread Count: The number of concurrent software threads used to execute a parallel region.
Parallel Matrix Multiplication: Matrix multiplication in which independent output blocks or loop iterations are assigned to different threads.
Small-Problem Overhead: A condition in which thread creation, scheduling, and synchronization cost more than the saved computation time.
Combined Optimization: The coordinated use of cache blocking, SIMD, instruction-level parallelism, and multiple threads.
6.13 Fallacies and Pitfalls
Amdahl's-Law Fallacy: Increasing the number of processors cannot eliminate the performance limit imposed by serial work.
Peak-Performance Fallacy: Multiplying per-processor peak performance by processor count does not predict observed application performance.
Software-Readiness Pitfall: Parallel hardware provides little benefit when algorithms, operating systems, libraries, and data structures are not designed for concurrency.
Global-Lock Pitfall: A single coarse-grained lock can serialize otherwise independent work and destroy scalability.
Memory-Bandwidth Pitfall: SIMD, vector, and GPU execution cannot sustain high arithmetic throughput without sufficient data supply from memory.
False-Sharing Pitfall: Independent variables placed in the same cache block can cause unnecessary coherence traffic and severe performance loss.
6.14 Concluding Concepts
Parallelism Requirement: Modern performance growth increasingly depends on multiple cores, SIMD, GPUs, clusters, and distributed services rather than clock-rate growth alone.
Programming Challenge: Effective parallel programs require correct decomposition, synchronization, communication, and load balancing.
Architecture-Programming Model Relationship: Shared-memory systems, message-passing systems, vector processors, and GPUs expose different mechanisms for expressing parallel work.
Scaling Limit: Serial execution, communication, synchronization, load imbalance, and memory bandwidth limit parallel speedup.
Performance per Joule: Useful computation completed per unit of energy, an important design metric for clients, servers, and datacenters.
Parallel Design Trade-off: Parallel systems balance programmability, performance, energy efficiency, communication cost, memory behavior, and dependability.