Pipelines

Pipeline{K,T}: a computation spread over K cycles

Some arithmetic will not fit in one clock. A wide multiply, a sum of many terms, a popcount over a long register: the logic is too deep for the clock period, and the fix is to register it in the middle — a pipeline. Writing pipelines by hand means deciding where the cuts go, declaring a register for every value that crosses one, and keeping the stages in step. A Pipeline{K,T} does that for you.

Writing to a pipeline

@quartz struct Mac
  @in  a::Bits{16}, b::Bits{16}, c::Bits{16}, d::Bits{16}
  p::Pipeline{2,Bits{33}}
  @out y::Bits{33}
  @out valid::Bool
end

@on Mac posedge(clk) begin
  p ← Bits{33}(a) * b + Bits{33}(c) * d      # two multiplies and an add, over two cycles
  y ← coalesce(p, 0)                         # the latest result, or 0 before the first
  valid ← isnew(p)
end

Write an expression into the pipeline and the result comes out K cycles later. Here the multiplies land in the first stage and the add in the second; the result written at edge 1 is readable at edge 3, and copied to y at edge 4. The compiler cuts the traced expression into K stages of roughly equal depth, and every value that crosses a cut becomes a register.

m = Mac()
for i in 1:5
  m = step(m; a = Bits{16}(i), b = Bits{16}(10), c = Bits{16}(1), d = Bits{16}(i))
  println("edge $i: y = $(Int(m.y)), valid = $(m.valid)")
end

edge 1: y = 0, valid = false
edge 2: y = 0, valid = false
edge 3: y = 0, valid = false
edge 4: y = 11, valid = true
edge 5: y = 22, valid = true

Reading from a pipeline

Read bare, p is the most recent output, or missing before the first one has arrived — so coalesce(p, 0) gives a value either way.
isnew(p) is true on the cycle a new result appears.
isready(p) is true when a result is out and no write is still on its way through, so what p gives is the result of the last write.

Write to a pipeline every cycle and you get a result every cycle, K cycles late. Write to it occasionally and isnew tells you when to look.

Seeing the cuts

stages shows what the compiler did:

stages(Mac, :p)

Pipeline p :: Pipeline{2,Bits{33}} of Mac     path cost 99, cut into 2 stages

stage 1                        cost   66
  in    a, b, c, d
        t1 = Bits{33}(a)         33-bit   [0]
        t2 = t1 * b              33-bit   [66]
        t3 = Bits{33}(c)         33-bit   [0]
        t4 = t3 * d              33-bit   [66]
  out   t2 (33), t4 (33)           66 flops

stage 2                        cost   33
  in    t2, t4
        p = t2 + t4              33-bit   [33]
  out   p (33)                     33 flops

output  p_out (33), p_valid (2), p_hasout (1), p_isnew (1)   37 flops
total   99 + 37 = 136 flops

Each stage lists what it takes in, what it computes, what it registers, and the cost of its longest path; the last line is what the whole pipeline costs in registers. stages(Mac) reports every pipeline in the module.

A single operation cannot be split. If K is larger than the computation can use, the extra stages only delay, the report says so, and writing the Verilog warns:

@quartz struct TooDeep
  @in  a::Bits{8}, b::Bits{8}
  s::Pipeline{3,Bits{9}}
end

@on TooDeep posedge(clk) s ← Bits{9}(a) + b

stages(TooDeep, :s)

Pipeline s :: Pipeline{3,Bits{9}} of TooDeep     path cost 9, cut into 3 stages

stage 1   (computes nothing)   cost    0
  in    a, b
        t1 = Bits{9}(a)           9-bit   [0]
  out   b (8), t1 (9)              17 flops

stage 2   (computes nothing)   cost    0
  in    b, t1
  out   b (8), t1 (9)              17 flops

stage 3                        cost    9
  in    b, t1
        s = t1 + b                9-bit   [9]
  out   s (9)                       9 flops

output  s_out (9), s_valid (3), s_hasout (1), s_isnew (1)   14 flops
total   43 + 14 = 57 flops
warning: pipeline s of TooDeep: stage 1 of 3 computes nothing; 3 stages is more than the computation can use
warning: pipeline s of TooDeep: stage 2 of 3 computes nothing; 3 stages is more than the computation can use

If you know Verilog

The Verilog contains the stage registers and an always block per stage, plus a valid bit that travels with the data — the same code you would write, except the cuts were chosen by measuring the logic rather than by eye. Change the expression and the cuts move with it.

What goes in a pipeline

The expression written into a pipeline may use registers, inputs, locals and helper functions, like any other expression. What it may not do is depend on its own output: a feedback path through a pipeline is a loop with K cycles of delay, and that is a state machine, not a pipeline. Write the feedback as ordinary registers around the pipeline instead.

Multicycle paths: the other answer to slow logic, when the inputs are slower still.

Writing to a pipeline

Reading from a pipeline

Seeing the cuts

What goes in a pipeline

Next