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 nmigen.hdl.rec import Record, Layout
  49
  50 from collections.abc import Sequence
  51
  52
  53 class PrevControl:
  54     """ contains signals that come *from* the previous stage (both in and out)
  55         * i_valid: previous stage indicating all incoming data is valid.
  56                    may be a multi-bit signal, where all bits are required
  57                    to be asserted to indicate "valid".
  58         * o_ready: output to next stage indicating readiness to accept data
  59         * i_data : an input - added by the user of this class
  60     """
  61
  62     def __init__(self, i_width=1):
  63         self.i_valid = Signal(i_width, name="p_i_valid") # prev   >>in  self
  64         self.o_ready = Signal(name="p_o_ready") # prev   <<out self
  65
  66     def connect_in(self, prev):
  67         """ helper function to connect stage to an input source.  do not
  68             use to connect stage-to-stage!
  69         """
  70         return [self.i_valid.eq(prev.i_valid),
  71                 prev.o_ready.eq(self.o_ready),
  72                 eq(self.i_data, prev.i_data),
  73                ]
  74
  75     def i_valid_logic(self):
  76         vlen = len(self.i_valid)
  77         if vlen > 1: # multi-bit case: valid only when i_valid is all 1s
  78             all1s = Const(-1, (len(self.i_valid), False))
  79             return self.i_valid == all1s
  80         # single-bit i_valid case
  81         return self.i_valid
  82
  83
  84 class NextControl:
  85     """ contains the signals that go *to* the next stage (both in and out)
  86         * o_valid: output indicating to next stage that data is valid
  87         * i_ready: input from next stage indicating that it can accept data
  88         * o_data : an output - added by the user of this class
  89     """
  90     def __init__(self):
  91         self.o_valid = Signal(name="n_o_valid") # self out>>  next
  92         self.i_ready = Signal(name="n_i_ready") # self <<in   next
  93
  94     def connect_to_next(self, nxt):
  95         """ helper function to connect to the next stage data/valid/ready.
  96             data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
  97         """
  98         return [nxt.i_valid.eq(self.o_valid),
  99                 self.i_ready.eq(nxt.o_ready),
 100                 eq(nxt.i_data, self.o_data),
 101                ]
 102
 103     def connect_out(self, nxt):
 104         """ helper function to connect stage to an output source.  do not
 105             use to connect stage-to-stage!
 106         """
 107         return [nxt.o_valid.eq(self.o_valid),
 108                 self.i_ready.eq(nxt.i_ready),
 109                 eq(nxt.o_data, self.o_data),
 110                ]
 111
 112
 113 def eq(o, i):
 114     """ makes signals equal: a helper routine which identifies if it is being
 115         passed a list (or tuple) of objects, or signals, or Records, and calls
 116         the objects' eq function.
 117
 118         complex objects (classes) can be used: they must follow the
 119         convention of having an eq member function, which takes the
 120         responsibility of further calling eq and returning a list of
 121         eq assignments
 122
 123         Record is a special (unusual, recursive) case, where the input
 124         is specified as a dictionary (which may contain further dictionaries,
 125         recursively), where the field names of the dictionary must match
 126         the Record's field spec.
 127     """
 128     if not isinstance(o, Sequence):
 129         o, i = [o], [i]
 130     res = []
 131     for (ao, ai) in zip(o, i):
 132         #print ("eq", ao, ai)
 133         if isinstance(ao, Record):
 134             for idx, (field_name, field_shape, _) in enumerate(ao.layout):
 135                 if isinstance(field_shape, Layout):
 136                     rres = eq(ao.fields[field_name], ai.fields[field_name])
 137                 else:
 138                     rres = eq(ao.fields[field_name], ai[field_name])
 139                 res += rres
 140         else:
 141             rres = ao.eq(ai)
 142             if not isinstance(rres, Sequence):
 143                 rres = [rres]
 144             res += rres
 145     return res
 146
 147
 148 class StageChain:
 149     """ pass in a list of stages, and they will automatically be
 150         chained together via their input and output specs into a
 151         combinatorial chain.
 152
 153         * input to this class will be the input of the first stage
 154         * output of first stage goes into input of second
 155         * output of second goes into input into third (etc. etc.)
 156         * the output of this class will be the output of the last stage
 157     """
 158     def __init__(self, chain):
 159         self.chain = chain
 160
 161     def ispec(self):
 162         return self.chain[0].ispec()
 163
 164     def ospec(self):
 165         return self.chain[-1].ospec()
 166
 167     def setup(self, m, i):
 168         for (idx, c) in enumerate(self.chain):
 169             if hasattr(c, "setup"):
 170                 c.setup(m, i)               # stage may have some module stuff
 171             o = self.chain[idx].ospec()     # only the last assignment survives
 172             m.d.comb += eq(o, c.process(i)) # process input into "o"
 173             if idx != len(self.chain)-1:
 174                 ni = self.chain[idx+1].ispec() # becomes new input on next loop
 175                 m.d.comb += eq(ni, o)          # assign output to next input
 176                 i = ni
 177         self.o = o                             # last loop is the output
 178
 179     def process(self, i):
 180         return self.o
 181
 182
 183 class PipelineBase:
 184     """ Common functions for Pipeline API
 185     """
 186     def __init__(self, stage, in_multi=None):
 187         """ pass in a "stage" which may be either a static class or a class
 188             instance, which has four functions (one optional):
 189             * ispec: returns input signals according to the input specification
 190             * ispec: returns output signals to the output specification
 191             * process: takes an input instance and returns processed data
 192             * setup: performs any module linkage if the stage uses one.
 193
 194             User must also:
 195             * add i_data member to PrevControl and
 196             * add o_data member to NextControl
 197         """
 198         self.stage = stage
 199
 200         # set up input and output IO ACK (prev/next ready/valid)
 201         self.p = PrevControl(in_multi)
 202         self.n = NextControl()
 203
 204     def connect_to_next(self, nxt):
 205         """ helper function to connect to the next stage data/valid/ready.
 206         """
 207         return self.n.connect_to_next(nxt.p)
 208
 209     def connect_in(self, prev):
 210         """ helper function to connect stage to an input source.  do not
 211             use to connect stage-to-stage!
 212         """
 213         return self.p.connect_in(prev.p)
 214
 215     def connect_out(self, nxt):
 216         """ helper function to connect stage to an output source.  do not
 217             use to connect stage-to-stage!
 218         """
 219         return self.n.connect_out(nxt.n)
 220
 221     def set_input(self, i):
 222         """ helper function to set the input data
 223         """
 224         return eq(self.p.i_data, i)
 225
 226     def ports(self):
 227         return [self.p.i_valid, self.n.i_ready,
 228                 self.n.o_valid, self.p.o_ready,
 229                 self.p.i_data, self.n.o_data   # XXX need flattening!
 230                ]
 231
 232
 233 class BufferedPipeline(PipelineBase):
 234     """ buffered pipeline stage.  data and strobe signals travel in sync.
 235         if ever the input is ready and the output is not, processed data
 236         is stored in a temporary register.
 237
 238         stage-1   p.i_valid >>in   stage   n.o_valid out>>   stage+1
 239         stage-1   p.o_ready <<out  stage   n.i_ready <<in    stage+1
 240         stage-1   p.i_data  >>in   stage   n.o_data  out>>   stage+1
 241                               |             |
 242                             process --->----^
 243                               |             |
 244                               +-- r_data ->-+
 245
 246         input data p.i_data is read (only), is processed and goes into an
 247         intermediate result store [process()].  this is updated combinatorially.
 248
 249         in a non-stall condition, the intermediate result will go into the
 250         output (update_output).  however if ever there is a stall, it goes
 251         into r_data instead [update_buffer()].
 252
 253         when the non-stall condition is released, r_data is the first
 254         to be transferred to the output [flush_buffer()], and the stall
 255         condition cleared.
 256
 257         on the next cycle (as long as stall is not raised again) the
 258         input may begin to be processed and transferred directly to output.
 259     """
 260     def __init__(self, stage):
 261         PipelineBase.__init__(self, stage)
 262
 263         # set up the input and output data
 264         self.p.i_data = stage.ispec() # input type
 265         self.n.o_data = stage.ospec()
 266
 267     def elaborate(self, platform):
 268         m = Module()
 269
 270         result = self.stage.ospec()
 271         r_data = self.stage.ospec()
 272         if hasattr(self.stage, "setup"):
 273             self.stage.setup(m, self.p.i_data)
 274
 275         # establish some combinatorial temporaries
 276         o_n_validn = Signal(reset_less=True)
 277         i_p_valid_o_p_ready = Signal(reset_less=True)
 278         p_i_valid = Signal(reset_less=True)
 279         m.d.comb += [p_i_valid.eq(self.p.i_valid_logic()),
 280                      o_n_validn.eq(~self.n.o_valid),
 281                      i_p_valid_o_p_ready.eq(p_i_valid & self.p.o_ready),
 282         ]
 283
 284         # store result of processing in combinatorial temporary
 285         m.d.comb += eq(result, self.stage.process(self.p.i_data))
 286
 287         # if not in stall condition, update the temporary register
 288         with m.If(self.p.o_ready): # not stalled
 289             m.d.sync += eq(r_data, result) # update buffer
 290
 291         with m.If(self.n.i_ready): # next stage is ready
 292             with m.If(self.p.o_ready): # not stalled
 293                 # nothing in buffer: send (processed) input direct to output
 294                 m.d.sync += [self.n.o_valid.eq(p_i_valid),
 295                              eq(self.n.o_data, result), # update output
 296                             ]
 297             with m.Else(): # p.o_ready is false, and something is in buffer.
 298                 # Flush the [already processed] buffer to the output port.
 299                 m.d.sync += [self.n.o_valid.eq(1),      # declare reg empty
 300                              eq(self.n.o_data, r_data), # flush buffer
 301                              self.p.o_ready.eq(1),      # clear stall condition
 302                             ]
 303                 # ignore input, since p.o_ready is also false.
 304
 305         # (n.i_ready) is false here: next stage is ready
 306         with m.Elif(o_n_validn): # next stage being told "ready"
 307             m.d.sync += [self.n.o_valid.eq(p_i_valid),
 308                          self.p.o_ready.eq(1), # Keep the buffer empty
 309                          eq(self.n.o_data, result), # set output data
 310                         ]
 311
 312         # (n.i_ready) false and (n.o_valid) true:
 313         with m.Elif(i_p_valid_o_p_ready):
 314             # If next stage *is* ready, and not stalled yet, accept input
 315             m.d.sync += self.p.o_ready.eq(~(p_i_valid & self.n.o_valid))
 316
 317         return m
 318
 319
 320 class ExampleAddStage:
 321     """ an example of how to use the buffered pipeline, as a class instance
 322     """
 323
 324     def ispec(self):
 325         """ returns a tuple of input signals which will be the incoming data
 326         """
 327         return (Signal(16), Signal(16))
 328
 329     def ospec(self):
 330         """ returns an output signal which will happen to contain the sum
 331             of the two inputs
 332         """
 333         return Signal(16)
 334
 335     def process(self, i):
 336         """ process the input data (sums the values in the tuple) and returns it
 337         """
 338         return i[0] + i[1]
 339
 340
 341 class ExampleBufPipeAdd(BufferedPipeline):
 342     """ an example of how to use the buffered pipeline, using a class instance
 343     """
 344
 345     def __init__(self):
 346         addstage = ExampleAddStage()
 347         BufferedPipeline.__init__(self, addstage)
 348
 349
 350 class ExampleStage:
 351     """ an example of how to use the buffered pipeline, in a static class
 352         fashion
 353     """
 354
 355     def ispec():
 356         return Signal(16, name="example_input_signal")
 357
 358     def ospec():
 359         return Signal(16, name="example_output_signal")
 360
 361     def process(i):
 362         """ process the input data and returns it (adds 1)
 363         """
 364         return i + 1
 365
 366
 367 class ExampleStageCls:
 368     """ an example of how to use the buffered pipeline, in a static class
 369         fashion
 370     """
 371
 372     def ispec(self):
 373         return Signal(16, name="example_input_signal")
 374
 375     def ospec(self):
 376         return Signal(16, name="example_output_signal")
 377
 378     def process(self, i):
 379         """ process the input data and returns it (adds 1)
 380         """
 381         return i + 1
 382
 383
 384 class ExampleBufPipe(BufferedPipeline):
 385     """ an example of how to use the buffered pipeline.
 386     """
 387
 388     def __init__(self):
 389         BufferedPipeline.__init__(self, ExampleStage)
 390
 391
 392 class CombPipe(PipelineBase):
 393     """ A simple pipeline stage with single-clock synchronisation
 394         and two-way valid/ready synchronised signalling.  The stage
 395         requires a combinatorial block.
 396
 397         Argument: stage.
 398
 399         stage requires compliance with a strict API that may be
 400         implemented in several means, including as a static class.
 401         the methods of a stage instance must be as follows:
 402
 403         * ispec() - Input data format specification
 404                     returns an object or a list or tuple of objects, or
 405                     a Record, each object having an "eq" function which
 406                     takes responsibility for copying by assignment all
 407                     sub-objects
 408         * ospec() - Output data format specification
 409                     requirements as for ospec
 410         * process(m, i) - Processes an ispec-formatted object
 411                     returns a combinatorial block of a result that
 412                     may be assigned to the output, by way of the "eq"
 413                     function
 414         * setup(m, i) - Optional function for setting up submodules
 415                     may be used for more complex stages, to link
 416                     the input (i) to submodules.  must take responsibility
 417                     for adding those submodules to the module (m).
 418                     the submodules must be combinatorial blocks and
 419                     must have their inputs and output linked combinatorially.
 420
 421         Attributes:
 422         -----------
 423         p.i_data : StageInput, shaped according to ispec
 424             The pipeline input
 425         p.o_data : StageOutput, shaped according to ospec
 426             The pipeline output
 427         r_data : input_shape according to ispec
 428             A temporary (buffered) copy of a prior (valid) input
 429         result: output_shape according to ospec
 430             The output of the combinatorial logic
 431     """
 432
 433     def __init__(self, stage):
 434         PipelineBase.__init__(self, stage)
 435         self._data_valid = Signal()
 436
 437         # set up the input and output data
 438         self.p.i_data = stage.ispec() # input type
 439         self.n.o_data = stage.ospec() # output type
 440
 441     def elaborate(self, platform):
 442         m = Module()
 443
 444         r_data = self.stage.ispec() # input type
 445         result = self.stage.ospec() # output data
 446         if hasattr(self.stage, "setup"):
 447             self.stage.setup(m, r_data)
 448
 449         p_i_valid = Signal(reset_less=True)
 450         m.d.comb += p_i_valid.eq(self.p.i_valid_logic())
 451         m.d.comb += eq(result, self.stage.process(r_data))
 452         m.d.comb += self.n.o_valid.eq(self._data_valid)
 453         m.d.comb += self.p.o_ready.eq(~self._data_valid | self.n.i_ready)
 454         m.d.sync += self._data_valid.eq(p_i_valid | \
 455                                         (~self.n.i_ready & self._data_valid))
 456         with m.If(self.p.i_valid & self.p.o_ready):
 457             m.d.sync += eq(r_data, self.p.i_data)
 458         m.d.comb += eq(self.n.o_data, result)
 459         return m
 460
 461
 462 class ExampleCombPipe(CombPipe):
 463     """ an example of how to use the combinatorial pipeline.
 464     """
 465
 466     def __init__(self):
 467         CombPipe.__init__(self, ExampleStage)
 468
 469
 470 if __name__ == '__main__':
 471     dut = ExampleBufPipe()
 472     vl = rtlil.convert(dut, ports=dut.ports())
 473     with open("test_bufpipe.il", "w") as f:
 474         f.write(vl)
 475
 476     dut = ExampleCombPipe()
 477     vl = rtlil.convert(dut, ports=dut.ports())
 478     with open("test_combpipe.il", "w") as f:
 479         f.write(vl)