src/add/example_buf_pipe.py

   1 """ nmigen implementation of buffered pipeline stage, based on zipcpu:
   2     https://zipcpu.com/blog/2017/08/14/strategies-for-pipelining.html
   3
   4     this module requires quite a bit of thought to understand how it works
   5     (and why it is needed in the first place).  reading the above is
   6     *strongly* recommended.
   7
   8     unlike john dawson's IEEE754 FPU STB/ACK signalling, which requires
   9     the STB / ACK signals to raise and lower (on separate clocks) before
  10     data may proceeed (thus only allowing one piece of data to proceed
  11     on *ALTERNATE* cycles), the signalling here is a true pipeline
  12     where data will flow on *every* clock when the conditions are right.
  13
  14     input acceptance conditions are when:
  15         * incoming previous-stage strobe (i.p_valid) is HIGH
  16         * outgoing previous-stage ready   (o.p_ready) is LOW
  17
  18     output transmission conditions are when:
  19         * outgoing next-stage strobe (o.n_valid) is HIGH
  20         * outgoing next-stage ready   (i.n_ready) is LOW
  21
  22     the tricky bit is when the input has valid data and the output is not
  23     ready to accept it.  if it wasn't for the clock synchronisation, it
  24     would be possible to tell the input "hey don't send that data, we're
  25     not ready".  unfortunately, it's not possible to "change the past":
  26     the previous stage *has no choice* but to pass on its data.
  27
  28     therefore, the incoming data *must* be accepted - and stored: that
  29     is the responsibility / contract that this stage *must* accept.
  30     on the same clock, it's possible to tell the input that it must
  31     not send any more data.  this is the "stall" condition.
  32
  33     we now effectively have *two* possible pieces of data to "choose" from:
  34     the buffered data, and the incoming data.  the decision as to which
  35     to process and output is based on whether we are in "stall" or not.
  36     i.e. when the next stage is no longer ready, the output comes from
  37     the buffer if a stall had previously occurred, otherwise it comes
  38     direct from processing the input.
  39
  40     this allows us to respect a synchronous "travelling STB" with what
  41     dan calls a "buffered handshake".
  42
  43     it's quite a complex state machine!
  44 """
  45
  46 from nmigen import Signal, Cat, Const, Mux, Module
  47 from nmigen.cli import verilog, rtlil
  48
  49
  50 class ExampleStage:
  51     """ an example of how to use the buffered pipeline.  actual names of
  52         variables (i_data, r_data, o_data, result) below do not matter:
  53         the functions however do.
  54
  55         input data i_data is read (only), is processed and goes into an
  56         intermediate result store [process()].  this is updated combinatorially.
  57
  58         in a non-stall condition, the intermediate result will go into the
  59         output (update_output).  however if ever there is a stall, it goes
  60         into r_data instead [update_buffer()].
  61
  62         when the non-stall condition is released, r_data is the first
  63         to be transferred to the output [flush_buffer()], and the stall
  64         condition cleared.
  65
  66         on the next cycle (as long as stall is not raised again) the
  67         input may begin to be processed and transferred directly to output.
  68     """
  69
  70     def __init__(self):
  71         """ i_data can be a DIFFERENT type from everything else
  72             o_data, r_data and result are best of the same type.
  73             however this is not strictly the case.  an intermediate
  74             transformation process could hypothetically be applied, however
  75             it is result and r_data that definitively need to be of the same
  76             (intermediary) type, as it is both result and r_data that
  77             are transferred into o_data:
  78
  79             i_data -> process() -> result --> o_data
  80                                      |           ^
  81                                      |           |
  82                                      +-> r_data -+
  83         """
  84         self.i_data = Signal(16)
  85         self.r_data = Signal(16)
  86         self.o_data = Signal(16)
  87         self.result = Signal(16)
  88
  89     def process(self):
  90         """ process the input data and store it in result.
  91             (not needed to be known: result is combinatorial)
  92         """
  93         return self.result.eq(self.i_data + 1)
  94
  95     def update_buffer(self):
  96         """ copies the result into the intermediate register r_data
  97         """
  98         return self.r_data.eq(self.result)
  99
 100     def update_output(self):
 101         """ copies the (combinatorial) result into the output
 102         """
 103         return self.o_data.eq(self.result)
 104
 105     def flush_buffer(self):
 106         """ copies the *intermediate* register r_data into the output
 107         """
 108         return self.o_data.eq(self.r_data)
 109
 110     def ports(self):
 111         return [self.i_data, self.o_data]
 112
 113 class IOAckIn:
 114
 115     def __init__(self):
 116         self.p_valid = Signal()  # >>in - comes in from PREVIOUS stage
 117         self.n_ready = Signal() # in<< - comes in from the NEXT stage
 118
 119
 120 class IOAckOut:
 121
 122     def __init__(self):
 123         self.n_valid = Signal()  # out>> - goes out to the NEXT stage
 124         self.p_ready = Signal() # <<out - goes out to the PREVIOUS stage
 125
 126
 127 class BufferedPipeline:
 128     """ buffered pipeline stage
 129
 130         stage-1   i.p_valid  >>in   stage   o.n_valid  out>>   stage+1
 131         stage-1   o.p_ready <<out  stage   i.n_ready <<in    stage+1
 132         stage-1   i_data   >>in   stage   o_data   out>>   stage+1
 133                               |             |
 134                               +------->  process
 135                               |             |
 136                               +-- r_data ---+
 137     """
 138     def __init__(self):
 139         # input: strobe comes in from previous stage, ready comes in from next
 140         self.i = IOAckIn()
 141         #self.i.p_valid = Signal()    # >>in - comes in from PREVIOUS stage
 142         #self.i.n_ready = Signal()   # in<< - comes in from the NEXT stage
 143
 144         # output: strobe goes out to next stage, ready comes in from previous
 145         self.o = IOAckOut()
 146         #self.o.n_valid = Signal()    # out>> - goes out to the NEXT stage
 147         #self.o.p_ready = Signal()   # <<out - goes out to the PREVIOUS stage
 148
 149     def elaborate(self, platform):
 150         m = Module()
 151
 152         # establish some combinatorial temporaries
 153         o_p_readyn = Signal(reset_less=True)
 154         o_n_validn = Signal(reset_less=True)
 155         i_n_readyn = Signal(reset_less=True)
 156         i_p_valid_o_p_ready = Signal(reset_less=True)
 157         m.d.comb += [i_n_readyn.eq(~self.i.n_ready),
 158                      o_n_validn.eq(~self.o.n_valid),
 159                      o_p_readyn.eq(~self.o.p_ready),
 160                      i_p_valid_o_p_ready.eq(self.i.p_valid & self.o.p_ready),
 161         ]
 162
 163         # store result of processing in combinatorial temporary
 164         with m.If(self.i.p_valid): # input is valid: process it
 165             m.d.comb += self.stage.process()
 166         # if not in stall condition, update the temporary register
 167         with m.If(self.o.p_ready): # not stalled
 168             m.d.sync += self.stage.update_buffer()
 169
 170         #with m.If(self.i.p_rst): # reset
 171         #    m.d.sync += self.o.n_valid.eq(0)
 172         #    m.d.sync += self.o.p_ready.eq(0)
 173         with m.If(self.i.n_ready): # next stage is ready
 174             with m.If(self.o.p_ready): # not stalled
 175                 # nothing in buffer: send (processed) input direct to output
 176                 m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 177                              self.stage.update_output(),
 178                             ]
 179             with m.Else(): # o.p_ready is false, and something is in buffer.
 180                 # Flush the [already processed] buffer to the output port.
 181                 m.d.sync += [self.o.n_valid.eq(1),
 182                              self.stage.flush_buffer(),
 183                              # clear stall condition, declare register empty.
 184                              self.o.p_ready.eq(1),
 185                             ]
 186                 # ignore input, since o.p_ready is also false.
 187
 188         # (i.n_ready) is false here: next stage is ready
 189         with m.Elif(o_n_validn): # next stage being told "ready"
 190             m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 191                          self.o.p_ready.eq(1), # Keep the buffer empty
 192                          # set the output data (from comb result)
 193                          self.stage.update_output(),
 194                         ]
 195         # (i.n_ready) false and (o.n_valid) true:
 196         with m.Elif(i_p_valid_o_p_ready):
 197             # If next stage *is* ready, and not stalled yet, accept input
 198             m.d.sync += self.o.p_ready.eq(~(self.i.p_valid & self.o.n_valid))
 199
 200         return m
 201
 202     def ports(self):
 203         return [self.i.p_valid, self.i.n_ready,
 204                 self.o.n_valid, self.o.p_ready,
 205                ]
 206
 207
 208 class BufPipe(BufferedPipeline):
 209
 210     def __init__(self):
 211         BufferedPipeline.__init__(self)
 212         self.stage = ExampleStage()
 213
 214     def ports(self):
 215         return self.stage.ports() + BufferedPipeline.ports(self)
 216
 217
 218 if __name__ == '__main__':
 219     dut = BufPipe()
 220     vl = rtlil.convert(dut, ports=dut.ports())
 221     with open("test_bufpipe.il", "w") as f:
 222         f.write(vl)