2-Stage Pipeline

The basic pipeline shape

A pipeline breaks a computation into stages separated by registers, so a new input can enter every cycle even though the result of any single input takes multiple cycles to appear. This problem is the minimal, generic version of that idea: no arithmetic, just a clean 2-register boundary carrying valid alongside data so downstream logic can tell a real result from a “nothing here yet” bubble.

Unlike the Handshaking category’s pipeline stages, there is no ready/backpressure here — this pipeline always accepts new input every cycle and always produces its (possibly invalid) output two cycles later. That fixed-latency, no-stall shape is extremely common for arithmetic and datapath pipelines (see the Pipelined Multiplier and Pipelined Adder problems in this category) where every stage is guaranteed to take exactly one cycle and nothing ever needs to wait.

Interface

Latency vs. throughput

• Latency: how long it takes one item to travel from input to output — here, exactly 2 clock cycles.
• Throughput: how often a new result can appear — here, 1 result per cycle, even though each individual result took 2 cycles, because a new item can enter every single cycle while earlier items are still “in flight” in the other stage.

These are different numbers and it’s a common interview trip-up to conflate them: adding pipeline stages generally increases latency but does not have to reduce throughput at all, as this problem demonstrates directly, and as the 4-Stage Pipeline problem in this category explores further.

Correctness constraints

• out_valid/out_data must reflect in_valid/in_data from exactly 2 clock cycles earlier — no more, no less.
• The pipeline must accept a new in_data every single cycle with no stalling logic of any kind.
• A in_valid bubble (low cycle) must propagate through as an out_valid low exactly 2 cycles later, without corrupting the data of surrounding valid cycles.