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         self.stage = stage
 114
 115         # set up input and output IO ACK (prev/next ready/valid)
 116         self.i = IOAckIn()
 117         self.o = IOAckOut()
 118
 119         # set up the input and output data
 120         self.i.data = stage.ispec() # input type
 121         self.r_data = stage.ospec() # all these are output type
 122         self.result = stage.ospec()
 123         self.o.data = stage.ospec()
 124
 125     def connect_next(self, nxt):
 126         """ helper function to connect to the next stage data/valid/ready.
 127             data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
 128         """
 129         return [nxt.i.p_valid.eq(self.o.n_valid),
 130                 self.i.n_ready.eq(nxt.o.p_ready),
 131                 eq(nxt.i.data, self.o.data),
 132                ]
 133
 134     def connect_in(self, prev):
 135         """ helper function to connect stage to an input source.  do not
 136             use to connect stage-to-stage!
 137         """
 138         return [self.i.p_valid.eq(prev.i.p_valid),
 139                 prev.o.p_ready.eq(self.o.p_ready),
 140                 eq(self.i.data, prev.i.data),
 141                ]
 142
 143     def connect_out(self, nxt):
 144         """ helper function to connect stage to an output source.  do not
 145             use to connect stage-to-stage!
 146         """
 147         return [nxt.o.n_valid.eq(self.o.n_valid),
 148                 self.i.n_ready.eq(nxt.i.n_ready),
 149                 eq(nxt.o.data, self.o.data),
 150                ]
 151
 152     def set_input(self, i):
 153         """ helper function to set the input data
 154         """
 155         return eq(self.i.data, i)
 156
 157     def update_buffer(self):
 158         """ copies the result into the intermediate register r_data,
 159             which will need to be outputted on a subsequent cycle
 160             prior to allowing "normal" operation.
 161         """
 162         return eq(self.r_data, self.result)
 163
 164     def update_output(self):
 165         """ copies the (combinatorial) result into the output
 166         """
 167         return eq(self.o.data, self.result)
 168
 169     def flush_buffer(self):
 170         """ copies the *intermediate* register r_data into the output
 171         """
 172         return eq(self.o.data, self.r_data)
 173
 174     def ports(self):
 175         return [self.i.data, self.o.data]
 176
 177     def elaborate(self, platform):
 178         m = Module()
 179         if hasattr(self.stage, "setup"):
 180             self.stage.setup(m, self.i.data)
 181
 182         # establish some combinatorial temporaries
 183         o_n_validn = Signal(reset_less=True)
 184         i_p_valid_o_p_ready = Signal(reset_less=True)
 185         m.d.comb += [o_n_validn.eq(~self.o.n_valid),
 186                      i_p_valid_o_p_ready.eq(self.i.p_valid & self.o.p_ready),
 187         ]
 188
 189         # store result of processing in combinatorial temporary
 190         with m.If(self.i.p_valid): # input is valid: process it
 191             m.d.comb += eq(self.result, self.stage.process(self.i.data))
 192         # if not in stall condition, update the temporary register
 193         with m.If(self.o.p_ready): # not stalled
 194             m.d.sync += self.update_buffer()
 195
 196         #with m.If(self.i.p_rst): # reset
 197         #    m.d.sync += self.o.n_valid.eq(0)
 198         #    m.d.sync += self.o.p_ready.eq(0)
 199         with m.If(self.i.n_ready): # next stage is ready
 200             with m.If(self.o.p_ready): # not stalled
 201                 # nothing in buffer: send (processed) input direct to output
 202                 m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 203                              self.update_output(),
 204                             ]
 205             with m.Else(): # o.p_ready is false, and something is in buffer.
 206                 # Flush the [already processed] buffer to the output port.
 207                 m.d.sync += [self.o.n_valid.eq(1),
 208                              self.flush_buffer(),
 209                              # clear stall condition, declare register empty.
 210                              self.o.p_ready.eq(1),
 211                             ]
 212                 # ignore input, since o.p_ready is also false.
 213
 214         # (i.n_ready) is false here: next stage is ready
 215         with m.Elif(o_n_validn): # next stage being told "ready"
 216             m.d.sync += [self.o.n_valid.eq(self.i.p_valid),
 217                          self.o.p_ready.eq(1), # Keep the buffer empty
 218                          # set the output data (from comb result)
 219                          self.update_output(),
 220                         ]
 221         # (i.n_ready) false and (o.n_valid) true:
 222         with m.Elif(i_p_valid_o_p_ready):
 223             # If next stage *is* ready, and not stalled yet, accept input
 224             m.d.sync += self.o.p_ready.eq(~(self.i.p_valid & self.o.n_valid))
 225
 226         return m
 227
 228     def ports(self):
 229         return [self.i.p_valid, self.i.n_ready,
 230                 self.o.n_valid, self.o.p_ready,
 231                ]
 232
 233
 234 class ExampleAddStage:
 235     """ an example of how to use the buffered pipeline, as a class instance
 236     """
 237
 238     def ispec(self):
 239         """ returns a tuple of input signals which will be the incoming data
 240         """
 241         return (Signal(16), Signal(16))
 242
 243     def ospec(self):
 244         """ returns an output signal which will happen to contain the sum
 245             of the two inputs
 246         """
 247         return Signal(16)
 248
 249     def process(self, i):
 250         """ process the input data (sums the values in the tuple) and returns it
 251         """
 252         return i[0] + i[1]
 253
 254
 255 class ExampleBufPipeAdd(BufferedPipeline):
 256     """ an example of how to use the buffered pipeline, using a class instance
 257     """
 258
 259     def __init__(self):
 260         addstage = ExampleAddStage()
 261         BufferedPipeline.__init__(self, addstage)
 262
 263
 264 class ExampleStage:
 265     """ an example of how to use the buffered pipeline, in a static class
 266         fashion
 267     """
 268
 269     def ispec():
 270         return Signal(16)
 271
 272     def ospec():
 273         return Signal(16)
 274
 275     def process(i):
 276         """ process the input data and returns it (adds 1)
 277         """
 278         return i + 1
 279
 280
 281 class ExampleBufPipe(BufferedPipeline):
 282     """ an example of how to use the buffered pipeline.
 283     """
 284
 285     def __init__(self):
 286         BufferedPipeline.__init__(self, ExampleStage)
 287
 288
 289 class CombPipe:
 290     """A simple pipeline stage containing combinational logic that can execute
 291     completely in one clock cycle.
 292
 293     Parameters:
 294     -----------
 295     input_shape : int or tuple or None
 296         the shape of ``input.data`` and ``comb_input``
 297     output_shape : int or tuple or None
 298         the shape of ``output.data`` and ``comb_output``
 299     name : str
 300         the name
 301
 302     Attributes:
 303     -----------
 304     input : StageInput
 305         The pipeline input
 306     output : StageOutput
 307         The pipeline output
 308     comb_input : Signal, input_shape
 309         The input to the combinatorial logic
 310     comb_output: Signal, output_shape
 311         The output of the combinatorial logic
 312     """
 313
 314     def __init__(self, stage):
 315         self.stage = stage
 316         self._data_valid = Signal()
 317         # set up input and output IO ACK (prev/next ready/valid)
 318         self.i = IOAckIn()
 319         self.o = IOAckOut()
 320
 321         # set up the input and output data
 322         self.i.data = stage.ispec() # input type
 323         self.r_data = stage.ispec() # input type
 324         self.result = stage.ospec() # output data
 325         self.o.data = stage.ospec() # output type
 326         self.o.data.name = "outdata"
 327
 328     def set_input(self, i):
 329         """ helper function to set the input data
 330         """
 331         return eq(self.i.data, i)
 332
 333     def elaborate(self, platform):
 334         m = Module()
 335         if hasattr(self.stage, "setup"):
 336             self.stage.setup(m, self.r_data)
 337         m.d.comb += eq(self.result, self.stage.process(self.r_data))
 338         m.d.comb += self.o.n_valid.eq(self._data_valid)
 339         m.d.comb += self.o.p_ready.eq(~self._data_valid | self.i.n_ready)
 340         m.d.sync += self._data_valid.eq(self.i.p_valid | \
 341                                         (~self.i.n_ready & self._data_valid))
 342         with m.If(self.i.p_valid & self.o.p_ready):
 343             m.d.sync += eq(self.r_data, self.i.data)
 344         m.d.comb += eq(self.o.data, self.result)
 345         return m
 346
 347     def ports(self):
 348         return [self.i.data, self.o.data]
 349
 350
 351 class ExampleCombPipe(CombPipe):
 352     """ an example of how to use the combinatorial pipeline.
 353     """
 354
 355     def __init__(self):
 356         CombPipe.__init__(self, ExampleStage)
 357
 358
 359 if __name__ == '__main__':
 360     dut = ExampleBufPipe()
 361     vl = rtlil.convert(dut, ports=dut.ports())
 362     with open("test_bufpipe.il", "w") as f:
 363         f.write(vl)
 364
 365     dut = ExampleCombPipe()
 366     vl = rtlil.convert(dut, ports=dut.ports())
 367     with open("test_combpipe.il", "w") as f:
 368         f.write(vl)