[BSV] Pipelining Complex Combinational Circuits

What is Pipelining?

In previous posts, we have seen examples of simple combinational and sequential circuits described in BSV (Bluespec SystemVerilog). In designing hardware, we desire high throughput, the amount of workload a hardware can handle per unit time. It is determined by the length of the clock cycle, and throughput per cycle.

Assume we have a long combinational circuit. The longer the circuit, the longer the propagation delay. This delay limits our clock frequency, and thereby limits our throughput.

Then, how do we reduce the propagation delay and improve the throughput? How about dividing the combinational circuit into multiple stages, and running each stage sequentially? This way, we can reduce the length of each clock cycle. (Also, in some cases, we may 'reuse' some stages to make a 'folded' circuit. This will save the chip area as shown in the figure.) However, the amount of the clock cycles needed for processing each workload increases. So the overall throughput is not enhanced.

Pipelining is an alternative approach. Similarly to sequential circuits, we divide the circuit into multiple stages. However, here we process multiple workloads at the same time. For example, we feed data1 into the pipelined circuit at the beginning of the first clock cycle. During the first cycle, data1 reaches the stage 1 register. We feed data2 at the second cycle, and it reaches the stage 1 register. At that time, data1 is further processed and reaches the stage 2 register. This way, we can process multiple input data at the same time (up to the amount of divided stages.) Although the time it takes to process a single data becomes longer (due to register delay), the overall throughput is significantly improved.

There are two styles in pipelining: inelastic pipelining and elastic pipelining. Inelastic pipelining is a method in which we control all the stage registers strictly and synchronously. In other words, we manage the entire pipeline in a single rule. In contrast, elastic pipelining uses multiple rules to control each stage register independently. Each of the styles have pros and cons. Now let's look at pipelining examples in BSV.

Pipeline Bubbles and the Maybe# Type

There are occasions where the the next data can't be fed into the pipeline on time. We call such vacancy of data pipeline bubbles. When implementing a pipeline, we have to deal with pipeline bubbles as well as valid data.

BSV provides the Maybe#() type, which is defined as:

typedef union tagged {
  void Invalid;
  data_T Valid;
} Maybe#(type data_T);

The Maybe# type puts 'tags' on data, indicating if it is a valid data or an invalid bubble. It also provides useful functions such as:

Maybe#(Bit#(64)) m = tagged Valid 123;
let a = isValid(m);    // returns true
let b = validValue(m); // returns 123

Also, we can use the pattern matching syntax to handle maybe types like this:

case (m) matches
  tagged Invalid:  return 0;
  tagged Valid .x: return x;
endcase

Using the Maybe# type, we can implement a simple inelastic pipeline (shown in the figure above) as follows:

typedef Bit#(64) Data;

module mkPipeline1(Empty);
  Fifo#(2, Data) inQ <- mkFifo;  
  Fifo#(2, Data) outQ <- mkFifo;

  Reg#(Maybe#(Data)) stage1Reg <- mkReg(tagged Invalid);
  Reg#(Maybe#(Data)) stage2Reg <- mkReg(tagged Invalid);
  
  function Data f1(Data d);
...
  endfunction
  function Data f2(Data d);
...
  endfunction
  function Data f3(Data d);
...
  endfunction
     
  rule syncPipeline (True);
    if (inQ.notEmpty()) begin
      stage1Reg <= tagged Valid f1(inQ.first);
      inQ.deq();
    end
    else stage1Reg <= tagged Invalid;

    case (stage1Reg) matches
      tagged Valid .sx1: stage2Reg <= tagged Valid f2(sx1);
      tagged Invalid: stage2Reg <= tagged Invalid;
    endcase

    case (stage2Reg) matches
      tagged Valid .sx2: outQ.enq(f3(sx2));
    endcase
  endrule
endmodule

If we replace the stage registers with FIFOs and write an individual rule for each stage, it becomes an elastic pipeline.

module mkPipeline2(Empty);
  Fifo#(2, Data) inQ <- mkFifo;  
  Fifo#(2, Data) outQ <- mkFifo;

  Fifo#(2, Data) fifo1 <- mkFifo;
  Fifo#(2, Data) fifo2 <- mkFifo;

  function Data f1(Data d);
...
  endfunction
  function Data f2(Data d);
...
  endfunction
  function Data f3(Data d);
...
  endfunction
     
  rule stage1 (True);
    fifo1.enq(f1(inQ.first());
    inQ.deq();
  endrule

  rule stage2 (True);
    fifo2.enq(f2(fifo1.first());
    fifo1.deq();
  endrule

  rule stage3 (True);
    outQ.enq(f1(fifo2.first());
    fifo2.deq();
  endrule

endmodule

Elastic pipelines can be implemented in simpler ways compared to inelastic pipelines. However, it is harder to guarantee concurrent executions of the stages, wheras inelastic pipelines always operate concurrently due to the atomicity of rules.

I hope this post helped you understand the concept of pipelining and the way to implement it in BSV.

References

1. Rishiyur. S. Nikhil, Kathy Czeck. "BSV by Example". Bluespec(2010).
2. Bluespec SystemVerilog Reference Guide
3. Class materials of SNU CSE (2025)