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}
  @out y::Bits{33}
  @out valid::Bool
  p::Pipeline{2,Bits{33}}
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.

let 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))
    @info "edge $i: y = $(Int(m.y)), valid = $(m.valid)"
  end
end

[ Info: edge 1: y = 0, valid = false
[ Info: edge 2: y = 0, valid = false
[ Info: edge 3: y = 0, valid = false
[ Info: edge 4: y = 11, valid = true
[ Info: 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 — with the cuts chosen by measuring the depth of the logic. 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