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 from collections.abc import Sequence
  49
  50
  51 class IOAckIn:
  52
  53     def __init__(self):
  54         self.p_valid = Signal() # >>in - comes in from PREVIOUS stage
  55         self.n_ready = Signal() # in<< - comes in from the NEXT stage
  56
  57
  58 class IOAckOut:
  59
  60     def __init__(self):
  61         self.n_valid = Signal() # out>> - goes out to the NEXT stage
  62         self.p_ready = Signal() # <<out - goes out to the PREVIOUS stage
  63
  64
  65 def eq(o, i):
  66     if not isinstance(o, Sequence):
  67         o, i = [o], [i]
  68     res = []
  69     for (ao, ai) in zip(o, i):
  70         res.append(ao.eq(ai))
  71     return res
  72
  73
  74 class BufferedPipeline:
  75     """ buffered pipeline stage.  data and strobe signals travel in sync.
  76         if ever the input is ready and the output is not, processed data
  77         is stored in a temporary register.
  78
  79         stage-1   i.p_valid >>in   stage   o.n_valid out>>   stage+1
  80         stage-1   o.p_ready <<out  stage   i.n_ready <<in    stage+1
  81         stage-1   i.data    >>in   stage   o.data    out>>   stage+1
  82                               |             |
  83                             process --->----^
  84                               |             |
  85                               +-- r_data ->-+
  86
  87         input data i_data is read (only), is processed and goes into an
  88         intermediate result store [process()].  this is updated combinatorially.
  89
  90         in a non-stall condition, the intermediate result will go into the
  91         output (update_output).  however if ever there is a stall, it goes
  92         into r_data instead [update_buffer()].
  93
  94         when the non-stall condition is released, r_data is the first
  95         to be transferred to the output [flush_buffer()], and the stall
  96         condition cleared.
  97
  98         on the next cycle (as long as stall is not raised again) the
  99         input may begin to be processed and transferred directly to output.
 100     """
 101     def __init__(self, stage):
 102         """ pass in a "stage" which may be either a static class or a class
 103             instance, which has three functions:
 104             * ispec: returns input signals according to the input specification
 105             * ispec: returns output signals to the output specification
 106             * process: takes an input instance and returns processed data
 107
 108             i_data -> process() -> result --> o.data
 109                                      |           ^
 110                                      |           |
 111                                      +-> r_data -+
 112         """
 113         # input: strobe comes in from previous stage, ready comes in from next
 114         self.i = IOAckIn()
 115         #self.i.p_valid = Signal()    # >>in - comes in from PREVIOUS stage
 116         #self.i.n_ready = Signal()   # in<< - comes in from the NEXT stage
 117
 118         # output: strobe goes out to next stage, ready comes in from previous
 119         self.o = IOAckOut()
 120         #self.o.n_valid = Signal()    # out>> - goes out to the NEXT stage
 121         #self.o.p_ready = Signal()   # <<out - goes out to the PREVIOUS stage
 122
 123         # set up the input and output data
 124         self.i.data = stage.ispec() # input type
 125         self.r_data = stage.ospec() # all these are output type
 126         self.result = stage.ospec()
 127         self.o.data = stage.ospec()
 128         self.stage = stage
 129
 130     def connect_next(self, nxt):
 131         """ helper function to connect the next stage data/valid/ready
 132         """
 133         return [nxt.i.p_valid.eq(self.o.n_valid),
 134                 self.i.n_ready.eq(nxt.o.p_ready),
 135                 eq(nxt.i.data, self.o.data),
 136                ]
 137
 138     def connect_in(self, prev):
 139         """ helper function to connect stage to an input source.  do not
 140             use to connect stage-to-stage!
 141         """
 142         return [self.i.p_valid.eq(prev.i.p_valid),
 143                 prev.o.p_ready.eq(self.o.p_ready),
 144                 eq(self.i.data, prev.i.data),
 145                ]
 146
 147     def connect_out(self, nxt):
 148         """ helper function to connect stage to an output source.  do not
 149             use to connect stage-to-stage!
 150         """
 151         return [nxt.o.n_valid.eq(self.o.n_valid),
 152                 self.i.n_ready.eq(nxt.i.n_ready),
 153                 eq(nxt.o.data, self.o.data),
 154                ]
 155
 156     def set_input(self, i):
 157         """ helper function to set the input data
 158         """
 159         return eq(self.i.data, i)
 160
 161     def update_buffer(self):
 162         """ copies the result into the intermediate register r_data,
 163             which will need to be outputted on a subsequent cycle
 164             prior to allowing "normal" operation.
 165         """
 166         return eq(self.r_data, self.result)
 167
 168     def update_output(self):
 169         """ copies the (combinatorial) result into the output
 170         """
 171         return eq(self.o.data, self.result)
 172
 173     def flush_buffer(self):
 174         """ copies the *intermediate* register r_data into the output
 175         """
 176         return eq(self.o.data, self.r_data)
 177
 178     def ports(self):
 179         return [self.i.data, self.o.data]
 180
 181     def elaborate(self, platform):
 182         m = Module()
 183
 184         # establish some combinatorial temporaries
 185         o_n_validn = Signal(reset_less=True)
 186         i_p_valid_o_p_ready = Signal(reset_less=True)
 187         m.d.comb += [o_n_validn.eq(~self.o.n_valid),
 188                      i_p_valid_o_p_ready.eq(self.i.p_valid & self.o.p_ready),
 189         ]
 190
 191         # store result of processing in combinatorial temporary
 192         with m.If(self.i.p_valid): # input is valid: process it
 193             m.d.comb += eq(self.result, self.stage.process(self.i.data))
 194         # if not in stall condition, update the temporary register
 195         with m.If(self.o.p_ready): # not stalled
 196             m.d.sync += self.update_buffer()
 197
 198         #with m.If(self.i.p_rst): # reset
 199         #    m.d.sync += self.o.n_valid.eq(0)
 200         #    m.d.sync += self.o.p_ready.eq(0)
 201         with m.If(self.i.n_ready): # next stage is ready
 202             with m.If(self.o.p_ready): # not stalled
 203                 # nothing in buffer: send (processed) input direct to output
 204                 m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 205                              self.update_output(),
 206                             ]
 207             with m.Else(): # o.p_ready is false, and something is in buffer.
 208                 # Flush the [already processed] buffer to the output port.
 209                 m.d.sync += [self.o.n_valid.eq(1),
 210                              self.flush_buffer(),
 211                              # clear stall condition, declare register empty.
 212                              self.o.p_ready.eq(1),
 213                             ]
 214                 # ignore input, since o.p_ready is also false.
 215
 216         # (i.n_ready) is false here: next stage is ready
 217         with m.Elif(o_n_validn): # next stage being told "ready"
 218             m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 219                          self.o.p_ready.eq(1), # Keep the buffer empty
 220                          # set the output data (from comb result)
 221                          self.update_output(),
 222                         ]
 223         # (i.n_ready) false and (o.n_valid) true:
 224         with m.Elif(i_p_valid_o_p_ready):
 225             # If next stage *is* ready, and not stalled yet, accept input
 226             m.d.sync += self.o.p_ready.eq(~(self.i.p_valid & self.o.n_valid))
 227
 228         return m
 229
 230     def ports(self):
 231         return [self.i.p_valid, self.i.n_ready,
 232                 self.o.n_valid, self.o.p_ready,
 233                ]
 234
 235
 236 class ExampleAddStage:
 237     """ an example of how to use the buffered pipeline, as a class instance
 238     """
 239
 240     def ispec(self):
 241         """ returns a tuple of input signals which will be the incoming data
 242         """
 243         return (Signal(16), Signal(16))
 244
 245     def ospec(self):
 246         """ returns an output signal which will happen to contain the sum
 247             of the two inputs
 248         """
 249         return Signal(16)
 250
 251     def process(self, i):
 252         """ process the input data (sums the values in the tuple) and returns it
 253         """
 254         return i[0] + i[1]
 255
 256
 257 class ExampleBufPipeAdd(BufferedPipeline):
 258     """ an example of how to use the buffered pipeline, using a class instance
 259     """
 260
 261     def __init__(self):
 262         addstage = ExampleAddStage()
 263         BufferedPipeline.__init__(self, addstage)
 264
 265
 266 class ExampleStage:
 267     """ an example of how to use the buffered pipeline, in a static class
 268         fashion
 269     """
 270
 271     def ispec():
 272         return Signal(16)
 273
 274     def ospec():
 275         return Signal(16)
 276
 277     def process(i):
 278         """ process the input data and returns it (adds 1)
 279         """
 280         return i + 1
 281
 282
 283 class ExampleBufPipe(BufferedPipeline):
 284     """ an example of how to use the buffered pipeline.
 285     """
 286
 287     def __init__(self):
 288         BufferedPipeline.__init__(self, ExampleStage)
 289
 290
 291 if __name__ == '__main__':
 292     dut = ExampleBufPipe()
 293     vl = rtlil.convert(dut, ports=dut.ports())
 294     with open("test_bufpipe.il", "w") as f:
 295         f.write(vl)