Explain pipeline parallelism as a way to organize concurrent work: what a stage is, how items move between stages, and what determines how many items the arrangement finishes per second once it runs steadily.
answer
- Items move, workers stay
- Concurrency across items, not within one
- Fill / steady state / drain
- Throughput = 1 / slowest stage
- Latency = sum of stages, unchanged
basics
~20 sSplit a repeated job into ordered steps called stages, each with its own worker and a queue in front of it. Different items sit in different stages at the same time, so all workers run at once. Steady-state throughput is one item per slowest stage's time.
solid answer
~50 sA **pipeline** cuts a repeated job into an ordered chain of **stages**; each stage has its own worker and a buffer in front of it. One item still goes through stage 1, then 2, then 3, in order. The concurrency is *across items*: while stage 3 handles item 1, stage 2 handles item 2 and stage 1 has already started item 3. With n stages, up to n items are in flight, one per stage. There is a **fill** phase (stages start one after another), a **steady state** (every stage busy), and a **drain** at the end. In steady state the pipeline emits one item per cycle, and the cycle equals the **slowest stage's** service time: throughput = 1 / max(stage time), not 1 / sum(stage times). Per-item latency does not improve — it is still the sum of the stages plus handoff and waiting. Pipelining buys **throughput** on work whose steps are strictly ordered, not a faster single item.
code
text · 6 linesqueueA = bounded_queue(cap)
queueB = bounded_queue(cap)
worker S1: for item in source: queueA.put(parse(item))
worker S2: for x in queueA: queueB.put(enrich(x))
worker S3: for y in queueB: write(y)go deeper
Be able to draw the timeline and say: items flow through ordered stages, several items are in flight at once, throughput is set by the slowest stage.
Add the arithmetic — throughput = 1/max, latency = sum, speedup = sum/max — and note that unequal stages waste worker capacity.
Frame it as a throughput technique that trades latency and complexity, and mention buffers, ordering, cache locality and shutdown/drain semantics.
Discuss when the shape is right at all: heterogeneous resources per stage, serialized resources, and the operational cost of tuning and observing a multi-stage system versus simpler alternatives.
## What a pipeline is A **pipeline** is a decomposition of a job you perform many times over a stream of items. Instead of one worker doing every step for one item, you cut the job into an ordered sequence of steps called **stages**. Each stage has its own worker — a thread, a process, or a machine — and a **buffer** (a queue) in front of it. An item enters the first stage; when that stage finishes with it, the item is handed to the next stage's buffer, and so on until it leaves the last stage. The items move; the workers stay put. ## Where the concurrency comes from Nothing about a *single* item runs in parallel. Item X visits stage 1, then stage 2, then stage 3, strictly in order, exactly as it would have in a sequential program. The parallelism appears *between* items: at any instant, several different items are in different stages. That is the whole trick — pipelining extracts concurrency from work whose steps are strictly dependent and cannot be reordered or run simultaneously for one item. ## Fill, steady state, drain With three balanced stages of one time unit each: ``` time: 1 2 3 4 5 6 S1: i1 i2 i3 i4 i5 i6 S2: i1 i2 i3 i4 i5 S3: i1 i2 i3 i4 ``` During **fill** (times 1–2) the later stages are idle. From time 3 the pipeline is in **steady state**: every stage is busy and one item completes per unit of time. At the end of a finite stream there is a symmetric **drain**. For m items and n balanced stages of time T, total time is about (m + n − 1)·T versus m·n·T sequentially. When m is large the speedup approaches n; for a short batch (m comparable to n) fill and drain dominate and the speedup is much smaller. ## What sets the rate In steady state, every item must pass through every stage, so no stage can emit faster than it can serve. The stage with the largest service time is the **bottleneck**, and: - **throughput = 1 / max(stage service time)** - every other stage idles for (max − its own time) per item Sequential processing gives 1 / sum(times). So the pipeline's speedup over sequential is sum(times) / max(time), which equals n only if all stages take the same time. A useful metric is **balance efficiency** = sum(times) / (n · max(time)): with stages of 10, 50 and 10 ms it is 70 / 150 ≈ 47%, meaning half the worker capacity is wasted waiting. ## Per-item latency The time one item spends in the system is the sum of all stage times **plus** handoff cost plus any time it waits in buffers. Pipelining never makes an individual item faster; it usually makes it slightly slower. It is a throughput technique. ## When the shape fits Pipelines suit streams where per-item steps are ordered and dependent, and especially where stages use **different resources** — parse (CPU), fetch (network), write (disk). Each stage can then be sized for its own resource, and resources stay busy simultaneously instead of alternating. A stage that must be serialized (a single writer, a device, an ordering requirement) is a natural stage with one worker while other stages run many. ## Costs Handoffs are not free: queueing, wakeups, and moving an item's data between cores costs cache locality that a single worker carrying one item end-to-end would keep. Buffers cost memory and add latency. Ordering is preserved only if each stage is single-threaded and its queue is FIFO. Shutdown needs care: you must stop feeding, drain each stage in order, and signal end-of-stream downstream.
- If each of three stages takes 10 ms, what is the throughput and what is the latency for one item?Throughput is one item per 10 ms, i.e. 100 items/second, because the pipeline emits one item per slowest-stage time in steady state. Latency for a single item is at least 30 ms — it must still pass through all three stages in order — plus handoff and any queue waiting. Throughput went up 3x; latency did not go down at all.
- You have only 20 items to process. Does a 4-stage pipeline still give roughly 4x?No. With n stages and m items, completion takes about (m + n − 1) cycles instead of m·n, so the speedup is m·n / (m + n − 1). For m = 20, n = 4 that is 80/23 ≈ 3.5x, and it degrades quickly as m approaches n. Fill and drain are pure overhead, so pipelines pay off on long or unbounded streams, not short batches.
A car wash: wash, rinse, dry, each with its own crew. One car still takes all three steps in order, but three cars are in the tunnel at once, and cars leave at the pace of the slowest bay.
saying these in an interview costs you the question
- Saying throughput equals 1 divided by the sum of stage times — that is the sequential rate, not the pipelined one
- Claiming a pipeline makes each individual item faster
- Thinking the steps of one item run simultaneously
- Assuming n stages always give n× speedup regardless of how uneven the stages are
- Ignoring fill and drain when the stream is short