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.