pipeline parallelism

**Pipeline Parallelism** — decomposing a computation into sequential stages that operate concurrently on different data items, analogous to an assembly line. **Concept** ``` Time → T1 T2 T3 T4 T5 Stage 1: [D1] [D2] [D3] [D4] [D5] Stage 2: [D1] [D2] [D3] [D4] Stage 3: [D1] [D2] [D3] ``` - Each stage processes a different data item simultaneously - Latency for one item: same as sequential - Throughput: One result per stage time (N stages → Nx throughput) **Hardware Pipelines** - CPU instruction pipeline: Fetch → Decode → Execute → Memory → Writeback (5+ stages). Modern CPUs: 15-20 stages - GPU shader pipeline: Vertex → geometry → rasterization → fragment - Fixed-function accelerators: Common in network processors, AI chips **Software Pipelines** - Deep learning training: Split model layers across GPUs (GPipe, PipeDream) - GPU 0: Layers 1-10, GPU 1: Layers 11-20, GPU 2: Layers 21-30 - Micro-batches flow through the pipeline - Data processing: ETL pipelines (extract → transform → load) - Unix pipes: `cat file | grep pattern | sort | uniq -c` **Challenges** - **Pipeline bubble**: All stages idle during startup and drain - **Stage imbalance**: Slowest stage determines throughput - **Inter-stage buffering**: Need queues between stages **Pipeline parallelism** is one of the three fundamental forms of parallelism alongside data parallelism and task parallelism.