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 (p.i_valid) is HIGH
  16         * outgoing previous-stage ready   (p.o_ready) is LOW
  17
  18     output transmission conditions are when:
  19         * outgoing next-stage strobe (n.o_valid) is HIGH
  20         * outgoing next-stage ready   (n.i_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 PrevControl:
  52     """ contains signals that come *from* the previous stage (both in and out)
  53         * i_valid: input from previous stage indicating incoming data is valid
  54         * o_ready: output to next stage indicating readiness to accept data
  55         * i_data : an input - added by the user of this class
  56     """
  57
  58     def __init__(self):
  59         self.i_valid = Signal(name="p_i_valid") # >>in
  60         self.o_ready = Signal(name="p_o_ready") # <<out
  61
  62
  63 class NextControl:
  64     """ contains the signals that go *to* the next stage (both in and out)
  65         * o_valid: output indicating to next stage that data is valid
  66         * i_ready: input from next stage indicating that it can accept data
  67         * o_data : an output - added by the user of this class
  68     """
  69     def __init__(self):
  70         self.o_valid = Signal(name="n_o_valid") # out>>
  71         self.i_ready = Signal(name="n_i_ready") # <<in
  72
  73     def connect_to_next(self, nxt):
  74         """ helper function to connect to the next stage data/valid/ready.
  75             data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
  76         """
  77         return [nxt.i_valid.eq(self.o_valid),
  78                 self.i_ready.eq(nxt.o_ready),
  79                 eq(nxt.data, self.data),
  80                ]
  81
  82
  83 def eq(o, i):
  84     if not isinstance(o, Sequence):
  85         o, i = [o], [i]
  86     res = []
  87     for (ao, ai) in zip(o, i):
  88         res.append(ao.eq(ai))
  89     return res
  90
  91
  92 class BufferedPipeline:
  93     """ buffered pipeline stage.  data and strobe signals travel in sync.
  94         if ever the input is ready and the output is not, processed data
  95         is stored in a temporary register.
  96
  97         stage-1   p.i_valid >>in   stage   n.o_valid out>>   stage+1
  98         stage-1   p.o_ready <<out  stage   n.i_ready <<in    stage+1
  99         stage-1   p.data    >>in   stage   n.data    out>>   stage+1
 100                               |             |
 101                             process --->----^
 102                               |             |
 103                               +-- r_data ->-+
 104
 105         input data p.data is read (only), is processed and goes into an
 106         intermediate result store [process()].  this is updated combinatorially.
 107
 108         in a non-stall condition, the intermediate result will go into the
 109         output (update_output).  however if ever there is a stall, it goes
 110         into r_data instead [update_buffer()].
 111
 112         when the non-stall condition is released, r_data is the first
 113         to be transferred to the output [flush_buffer()], and the stall
 114         condition cleared.
 115
 116         on the next cycle (as long as stall is not raised again) the
 117         input may begin to be processed and transferred directly to output.
 118     """
 119     def __init__(self, stage):
 120         """ pass in a "stage" which may be either a static class or a class
 121             instance, which has three functions:
 122             * ispec: returns input signals according to the input specification
 123             * ispec: returns output signals to the output specification
 124             * process: takes an input instance and returns processed data
 125
 126             p.data -> process() -> result --> n.data
 127                                      |           ^
 128                                      |           |
 129                                      +-> r_data -+
 130         """
 131         self.stage = stage
 132
 133         # set up input and output IO ACK (prev/next ready/valid)
 134         self.p = PrevControl()
 135         self.n = NextControl()
 136
 137         # set up the input and output data
 138         self.p.data = stage.ispec() # input type
 139         self.r_data = stage.ospec() # all these are output type
 140         self.result = stage.ospec()
 141         self.n.data = stage.ospec()
 142
 143     def connect_to_next(self, nxt):
 144         """ helper function to connect to the next stage data/valid/ready.
 145             data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
 146         """
 147         return self.n.connect_to_next(nxt.p)
 148
 149     def connect_in(self, prev):
 150         """ helper function to connect stage to an input source.  do not
 151             use to connect stage-to-stage!
 152         """
 153         return [self.p.i_valid.eq(prev.p.i_valid),
 154                 prev.p.o_ready.eq(self.p.o_ready),
 155                 eq(self.p.data, prev.p.data),
 156                ]
 157
 158     def connect_out(self, nxt):
 159         """ helper function to connect stage to an output source.  do not
 160             use to connect stage-to-stage!
 161         """
 162         return [nxt.n.o_valid.eq(self.n.o_valid),
 163                 self.n.i_ready.eq(nxt.n.i_ready),
 164                 eq(nxt.n.data, self.n.data),
 165                ]
 166
 167     def set_input(self, i):
 168         """ helper function to set the input data
 169         """
 170         return eq(self.p.data, i)
 171
 172     def update_buffer(self):
 173         """ copies the result into the intermediate register r_data,
 174             which will need to be outputted on a subsequent cycle
 175             prior to allowing "normal" operation.
 176         """
 177         return eq(self.r_data, self.result)
 178
 179     def update_output(self):
 180         """ copies the (combinatorial) result into the output
 181         """
 182         return eq(self.n.data, self.result)
 183
 184     def flush_buffer(self):
 185         """ copies the *intermediate* register r_data into the output
 186         """
 187         return eq(self.n.data, self.r_data)
 188
 189     def ports(self):
 190         return [self.p.data, self.n.data]
 191
 192     def elaborate(self, platform):
 193         m = Module()
 194         if hasattr(self.stage, "setup"):
 195             self.stage.setup(m, self.p.data)
 196
 197         # establish some combinatorial temporaries
 198         o_n_validn = Signal(reset_less=True)
 199         i_p_valid_o_p_ready = Signal(reset_less=True)
 200         m.d.comb += [o_n_validn.eq(~self.n.o_valid),
 201                      i_p_valid_o_p_ready.eq(self.p.i_valid & self.p.o_ready),
 202         ]
 203
 204         # store result of processing in combinatorial temporary
 205         with m.If(self.p.i_valid): # input is valid: process it
 206             m.d.comb += eq(self.result, self.stage.process(self.p.data))
 207         # if not in stall condition, update the temporary register
 208         with m.If(self.p.o_ready): # not stalled
 209             m.d.sync += self.update_buffer()
 210
 211         #with m.If(self.p.i_rst): # reset
 212         #    m.d.sync += self.n.o_valid.eq(0)
 213         #    m.d.sync += self.p.o_ready.eq(0)
 214         with m.If(self.n.i_ready): # next stage is ready
 215             with m.If(self.p.o_ready): # not stalled
 216                 # nothing in buffer: send (processed) input direct to output
 217                 m.d.sync += [self.n.o_valid.eq(self.p.i_valid),
 218                              self.update_output(),
 219                             ]
 220             with m.Else(): # p.o_ready is false, and something is in buffer.
 221                 # Flush the [already processed] buffer to the output port.
 222                 m.d.sync += [self.n.o_valid.eq(1),
 223                              self.flush_buffer(),
 224                              # clear stall condition, declare register empty.
 225                              self.p.o_ready.eq(1),
 226                             ]
 227                 # ignore input, since p.o_ready is also false.
 228
 229         # (n.i_ready) is false here: next stage is ready
 230         with m.Elif(o_n_validn): # next stage being told "ready"
 231             m.d.sync += [self.n.o_valid.eq(self.p.i_valid),
 232                          self.p.o_ready.eq(1), # Keep the buffer empty
 233                          # set the output data (from comb result)
 234                          self.update_output(),
 235                         ]
 236         # (n.i_ready) false and (n.o_valid) true:
 237         with m.Elif(i_p_valid_o_p_ready):
 238             # If next stage *is* ready, and not stalled yet, accept input
 239             m.d.sync += self.p.o_ready.eq(~(self.p.i_valid & self.n.o_valid))
 240
 241         return m
 242
 243     def ports(self):
 244         return [self.p.i_valid, self.n.i_ready,
 245                 self.n.o_valid, self.p.o_ready,
 246                ]
 247
 248
 249 class ExampleAddStage:
 250     """ an example of how to use the buffered pipeline, as a class instance
 251     """
 252
 253     def ispec(self):
 254         """ returns a tuple of input signals which will be the incoming data
 255         """
 256         return (Signal(16), Signal(16))
 257
 258     def ospec(self):
 259         """ returns an output signal which will happen to contain the sum
 260             of the two inputs
 261         """
 262         return Signal(16)
 263
 264     def process(self, i):
 265         """ process the input data (sums the values in the tuple) and returns it
 266         """
 267         return i[0] + i[1]
 268
 269
 270 class ExampleBufPipeAdd(BufferedPipeline):
 271     """ an example of how to use the buffered pipeline, using a class instance
 272     """
 273
 274     def __init__(self):
 275         addstage = ExampleAddStage()
 276         BufferedPipeline.__init__(self, addstage)
 277
 278
 279 class ExampleStage:
 280     """ an example of how to use the buffered pipeline, in a static class
 281         fashion
 282     """
 283
 284     def ispec():
 285         return Signal(16)
 286
 287     def ospec():
 288         return Signal(16)
 289
 290     def process(i):
 291         """ process the input data and returns it (adds 1)
 292         """
 293         return i + 1
 294
 295
 296 class ExampleBufPipe(BufferedPipeline):
 297     """ an example of how to use the buffered pipeline.
 298     """
 299
 300     def __init__(self):
 301         BufferedPipeline.__init__(self, ExampleStage)
 302
 303
 304 class CombPipe:
 305     """A simple pipeline stage containing combinational logic that can execute
 306     completely in one clock cycle.
 307
 308     Parameters:
 309     -----------
 310     input_shape : int or tuple or None
 311         the shape of ``input.data`` and ``comb_input``
 312     output_shape : int or tuple or None
 313         the shape of ``output.data`` and ``comb_output``
 314     name : str
 315         the name
 316
 317     Attributes:
 318     -----------
 319     input : StageInput
 320         The pipeline input
 321     output : StageOutput
 322         The pipeline output
 323     comb_input : Signal, input_shape
 324         The input to the combinatorial logic
 325     comb_output: Signal, output_shape
 326         The output of the combinatorial logic
 327     """
 328
 329     def __init__(self, stage):
 330         self.stage = stage
 331         self._data_valid = Signal()
 332         # set up input and output IO ACK (prev/next ready/valid)
 333         self.p = PrevControl()
 334         self.n = NextControl()
 335
 336         # set up the input and output data
 337         self.p.data = stage.ispec() # input type
 338         self.r_data = stage.ispec() # input type
 339         self.result = stage.ospec() # output data
 340         self.n.data = stage.ospec() # output type
 341         self.n.data.name = "outdata"
 342
 343     def set_input(self, i):
 344         """ helper function to set the input data
 345         """
 346         return eq(self.p.data, i)
 347
 348     def elaborate(self, platform):
 349         m = Module()
 350         if hasattr(self.stage, "setup"):
 351             self.stage.setup(m, self.r_data)
 352         m.d.comb += eq(self.result, self.stage.process(self.r_data))
 353         m.d.comb += self.n.o_valid.eq(self._data_valid)
 354         m.d.comb += self.p.o_ready.eq(~self._data_valid | self.n.i_ready)
 355         m.d.sync += self._data_valid.eq(self.p.i_valid | \
 356                                         (~self.n.i_ready & self._data_valid))
 357         with m.If(self.p.i_valid & self.p.o_ready):
 358             m.d.sync += eq(self.r_data, self.p.data)
 359         m.d.comb += eq(self.n.data, self.result)
 360         return m
 361
 362     def ports(self):
 363         return [self.p.data, self.n.data]
 364
 365
 366 class ExampleCombPipe(CombPipe):
 367     """ an example of how to use the combinatorial pipeline.
 368     """
 369
 370     def __init__(self):
 371         CombPipe.__init__(self, ExampleStage)
 372
 373
 374 if __name__ == '__main__':
 375     dut = ExampleBufPipe()
 376     vl = rtlil.convert(dut, ports=dut.ports())
 377     with open("test_bufpipe.il", "w") as f:
 378         f.write(vl)
 379
 380     dut = ExampleCombPipe()
 381     vl = rtlil.convert(dut, ports=dut.ports())
 382     with open("test_combpipe.il", "w") as f:
 383         f.write(vl)