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_n_validn = Signal(reset_less=True)
 154         i_p_valid_o_p_ready = Signal(reset_less=True)
 155         m.d.comb += [o_n_validn.eq(~self.o.n_valid),
 156                      i_p_valid_o_p_ready.eq(self.i.p_valid & self.o.p_ready),
 157         ]
 158
 159         # store result of processing in combinatorial temporary
 160         with m.If(self.i.p_valid): # input is valid: process it
 161             m.d.comb += self.stage.process()
 162         # if not in stall condition, update the temporary register
 163         with m.If(self.o.p_ready): # not stalled
 164             m.d.sync += self.stage.update_buffer()
 165
 166         #with m.If(self.i.p_rst): # reset
 167         #    m.d.sync += self.o.n_valid.eq(0)
 168         #    m.d.sync += self.o.p_ready.eq(0)
 169         with m.If(self.i.n_ready): # next stage is ready
 170             with m.If(self.o.p_ready): # not stalled
 171                 # nothing in buffer: send (processed) input direct to output
 172                 m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 173                              self.stage.update_output(),
 174                             ]
 175             with m.Else(): # o.p_ready is false, and something is in buffer.
 176                 # Flush the [already processed] buffer to the output port.
 177                 m.d.sync += [self.o.n_valid.eq(1),
 178                              self.stage.flush_buffer(),
 179                              # clear stall condition, declare register empty.
 180                              self.o.p_ready.eq(1),
 181                             ]
 182                 # ignore input, since o.p_ready is also false.
 183
 184         # (i.n_ready) is false here: next stage is ready
 185         with m.Elif(o_n_validn): # next stage being told "ready"
 186             m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 187                          self.o.p_ready.eq(1), # Keep the buffer empty
 188                          # set the output data (from comb result)
 189                          self.stage.update_output(),
 190                         ]
 191         # (i.n_ready) false and (o.n_valid) true:
 192         with m.Elif(i_p_valid_o_p_ready):
 193             # If next stage *is* ready, and not stalled yet, accept input
 194             m.d.sync += self.o.p_ready.eq(~(self.i.p_valid & self.o.n_valid))
 195
 196         return m
 197
 198     def ports(self):
 199         return [self.i.p_valid, self.i.n_ready,
 200                 self.o.n_valid, self.o.p_ready,
 201                ]
 202
 203
 204 class BufPipe(BufferedPipeline):
 205
 206     def __init__(self):
 207         BufferedPipeline.__init__(self)
 208         self.stage = ExampleStage()
 209
 210     def ports(self):
 211         return self.stage.ports() + BufferedPipeline.ports(self)
 212
 213
 214 if __name__ == '__main__':
 215     dut = BufPipe()
 216     vl = rtlil.convert(dut, ports=dut.ports())
 217     with open("test_bufpipe.il", "w") as f:
 218         f.write(vl)