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