src/add/example_buf_pipe.py

   1 """ Pipeline and BufferedPipeline implementation, conforming to the same API.
   2
   3     eq:
   4     --
   5
   6     a strategically very important function that is identical in function
   7     to nmigen's Signal.eq function, except it may take objects, or a list
   8     of objects, or a tuple of objects, and where objects may also be
   9     Records.
  10
  11     Stage API:
  12     ---------
  13
  14     stage requires compliance with a strict API that may be
  15     implemented in several means, including as a static class.
  16     the methods of a stage instance must be as follows:
  17
  18     * ispec() - Input data format specification
  19                 returns an object or a list or tuple of objects, or
  20                 a Record, each object having an "eq" function which
  21                 takes responsibility for copying by assignment all
  22                 sub-objects
  23     * ospec() - Output data format specification
  24                 requirements as for ospec
  25     * process(m, i) - Processes an ispec-formatted object
  26                 returns a combinatorial block of a result that
  27                 may be assigned to the output, by way of the "eq"
  28                 function
  29     * setup(m, i) - Optional function for setting up submodules
  30                 may be used for more complex stages, to link
  31                 the input (i) to submodules.  must take responsibility
  32                 for adding those submodules to the module (m).
  33                 the submodules must be combinatorial blocks and
  34                 must have their inputs and output linked combinatorially.
  35
  36     StageChain:
  37     ----------
  38
  39     A useful combinatorial wrapper around stages that chains them together
  40     and then presents a Stage-API-conformant interface.
  41
  42     UnbufferedPipeline:
  43     ------------------
  44
  45     A simple stalling clock-synchronised pipeline that has no buffering
  46     (unlike BufferedPipeline).  A stall anywhere along the line will
  47     result in a stall back-propagating down the entire chain.
  48
  49     The BufferedPipeline by contrast will buffer incoming data, allowing
  50     previous stages one clock cycle's grace before also having to stall.
  51
  52     BufferedPipeline:
  53     ----------------
  54
  55     nmigen implementation of buffered pipeline stage, based on zipcpu:
  56     https://zipcpu.com/blog/2017/08/14/strategies-for-pipelining.html
  57
  58     this module requires quite a bit of thought to understand how it works
  59     (and why it is needed in the first place).  reading the above is
  60     *strongly* recommended.
  61
  62     unlike john dawson's IEEE754 FPU STB/ACK signalling, which requires
  63     the STB / ACK signals to raise and lower (on separate clocks) before
  64     data may proceeed (thus only allowing one piece of data to proceed
  65     on *ALTERNATE* cycles), the signalling here is a true pipeline
  66     where data will flow on *every* clock when the conditions are right.
  67
  68     input acceptance conditions are when:
  69         * incoming previous-stage strobe (p.i_valid) is HIGH
  70         * outgoing previous-stage ready   (p.o_ready) is LOW
  71
  72     output transmission conditions are when:
  73         * outgoing next-stage strobe (n.o_valid) is HIGH
  74         * outgoing next-stage ready   (n.i_ready) is LOW
  75
  76     the tricky bit is when the input has valid data and the output is not
  77     ready to accept it.  if it wasn't for the clock synchronisation, it
  78     would be possible to tell the input "hey don't send that data, we're
  79     not ready".  unfortunately, it's not possible to "change the past":
  80     the previous stage *has no choice* but to pass on its data.
  81
  82     therefore, the incoming data *must* be accepted - and stored: that
  83     is the responsibility / contract that this stage *must* accept.
  84     on the same clock, it's possible to tell the input that it must
  85     not send any more data.  this is the "stall" condition.
  86
  87     we now effectively have *two* possible pieces of data to "choose" from:
  88     the buffered data, and the incoming data.  the decision as to which
  89     to process and output is based on whether we are in "stall" or not.
  90     i.e. when the next stage is no longer ready, the output comes from
  91     the buffer if a stall had previously occurred, otherwise it comes
  92     direct from processing the input.
  93
  94     this allows us to respect a synchronous "travelling STB" with what
  95     dan calls a "buffered handshake".
  96
  97     it's quite a complex state machine!
  98 """
  99
 100 from nmigen import Signal, Cat, Const, Mux, Module
 101 from nmigen.cli import verilog, rtlil
 102 from nmigen.hdl.rec import Record, Layout
 103
 104 from collections.abc import Sequence
 105
 106
 107 class PrevControl:
 108     """ contains signals that come *from* the previous stage (both in and out)
 109         * i_valid: previous stage indicating all incoming data is valid.
 110                    may be a multi-bit signal, where all bits are required
 111                    to be asserted to indicate "valid".
 112         * o_ready: output to next stage indicating readiness to accept data
 113         * i_data : an input - added by the user of this class
 114     """
 115
 116     def __init__(self, i_width=1):
 117         self.i_valid = Signal(i_width, name="p_i_valid") # prev   >>in  self
 118         self.o_ready = Signal(name="p_o_ready") # prev   <<out self
 119
 120     def connect_in(self, prev):
 121         """ helper function to connect stage to an input source.  do not
 122             use to connect stage-to-stage!
 123         """
 124         return [self.i_valid.eq(prev.i_valid),
 125                 prev.o_ready.eq(self.o_ready),
 126                 eq(self.i_data, prev.i_data),
 127                ]
 128
 129     def i_valid_logic(self):
 130         vlen = len(self.i_valid)
 131         if vlen > 1: # multi-bit case: valid only when i_valid is all 1s
 132             all1s = Const(-1, (len(self.i_valid), False))
 133             return self.i_valid == all1s
 134         # single-bit i_valid case
 135         return self.i_valid
 136
 137
 138 class NextControl:
 139     """ contains the signals that go *to* the next stage (both in and out)
 140         * o_valid: output indicating to next stage that data is valid
 141         * i_ready: input from next stage indicating that it can accept data
 142         * o_data : an output - added by the user of this class
 143     """
 144     def __init__(self):
 145         self.o_valid = Signal(name="n_o_valid") # self out>>  next
 146         self.i_ready = Signal(name="n_i_ready") # self <<in   next
 147
 148     def connect_to_next(self, nxt):
 149         """ helper function to connect to the next stage data/valid/ready.
 150             data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
 151         """
 152         return [nxt.i_valid.eq(self.o_valid),
 153                 self.i_ready.eq(nxt.o_ready),
 154                 eq(nxt.i_data, self.o_data),
 155                ]
 156
 157     def connect_out(self, nxt):
 158         """ helper function to connect stage to an output source.  do not
 159             use to connect stage-to-stage!
 160         """
 161         return [nxt.o_valid.eq(self.o_valid),
 162                 self.i_ready.eq(nxt.i_ready),
 163                 eq(nxt.o_data, self.o_data),
 164                ]
 165
 166
 167 def eq(o, i):
 168     """ makes signals equal: a helper routine which identifies if it is being
 169         passed a list (or tuple) of objects, or signals, or Records, and calls
 170         the objects' eq function.
 171
 172         complex objects (classes) can be used: they must follow the
 173         convention of having an eq member function, which takes the
 174         responsibility of further calling eq and returning a list of
 175         eq assignments
 176
 177         Record is a special (unusual, recursive) case, where the input may be
 178         specified as a dictionary (which may contain further dictionaries,
 179         recursively), where the field names of the dictionary must match
 180         the Record's field spec.  Alternatively, an object with the same
 181         member names as the Record may be assigned: it does not have to
 182         *be* a Record.
 183     """
 184     if not isinstance(o, Sequence):
 185         o, i = [o], [i]
 186     res = []
 187     for (ao, ai) in zip(o, i):
 188         #print ("eq", ao, ai)
 189         if isinstance(ao, Record):
 190             for idx, (field_name, field_shape, _) in enumerate(ao.layout):
 191                 if isinstance(field_shape, Layout):
 192                     val = ai.fields
 193                 else:
 194                     val = ai
 195                 if hasattr(val, field_name): # check for attribute
 196                     val = getattr(val, field_name)
 197                 else:
 198                     val = val[field_name] # dictionary-style specification
 199                 rres = eq(ao.fields[field_name], val)
 200                 res += rres
 201         else:
 202             rres = ao.eq(ai)
 203             if not isinstance(rres, Sequence):
 204                 rres = [rres]
 205             res += rres
 206     return res
 207
 208
 209 class StageChain:
 210     """ pass in a list of stages, and they will automatically be
 211         chained together via their input and output specs into a
 212         combinatorial chain.
 213
 214         * input to this class will be the input of the first stage
 215         * output of first stage goes into input of second
 216         * output of second goes into input into third (etc. etc.)
 217         * the output of this class will be the output of the last stage
 218     """
 219     def __init__(self, chain):
 220         self.chain = chain
 221
 222     def ispec(self):
 223         return self.chain[0].ispec()
 224
 225     def ospec(self):
 226         return self.chain[-1].ospec()
 227
 228     def setup(self, m, i):
 229         for (idx, c) in enumerate(self.chain):
 230             if hasattr(c, "setup"):
 231                 c.setup(m, i)               # stage may have some module stuff
 232             o = self.chain[idx].ospec()     # only the last assignment survives
 233             m.d.comb += eq(o, c.process(i)) # process input into "o"
 234             if idx != len(self.chain)-1:
 235                 ni = self.chain[idx+1].ispec() # becomes new input on next loop
 236                 m.d.comb += eq(ni, o)          # assign output to next input
 237                 i = ni
 238         self.o = o                             # last loop is the output
 239
 240     def process(self, i):
 241         return self.o
 242
 243
 244 class PipelineBase:
 245     """ Common functions for Pipeline API
 246     """
 247     def __init__(self, stage=None, in_multi=None):
 248         """ pass in a "stage" which may be either a static class or a class
 249             instance, which has four functions (one optional):
 250             * ispec: returns input signals according to the input specification
 251             * ispec: returns output signals to the output specification
 252             * process: takes an input instance and returns processed data
 253             * setup: performs any module linkage if the stage uses one.
 254
 255             User must also:
 256             * add i_data member to PrevControl and
 257             * add o_data member to NextControl
 258         """
 259         self.stage = stage
 260
 261         # set up input and output IO ACK (prev/next ready/valid)
 262         self.p = PrevControl(in_multi)
 263         self.n = NextControl()
 264
 265     def connect_to_next(self, nxt):
 266         """ helper function to connect to the next stage data/valid/ready.
 267         """
 268         return self.n.connect_to_next(nxt.p)
 269
 270     def connect_in(self, prev):
 271         """ helper function to connect stage to an input source.  do not
 272             use to connect stage-to-stage!
 273         """
 274         return self.p.connect_in(prev.p)
 275
 276     def connect_out(self, nxt):
 277         """ helper function to connect stage to an output source.  do not
 278             use to connect stage-to-stage!
 279         """
 280         return self.n.connect_out(nxt.n)
 281
 282     def set_input(self, i):
 283         """ helper function to set the input data
 284         """
 285         return eq(self.p.i_data, i)
 286
 287     def ports(self):
 288         return [self.p.i_valid, self.n.i_ready,
 289                 self.n.o_valid, self.p.o_ready,
 290                 self.p.i_data, self.n.o_data   # XXX need flattening!
 291                ]
 292
 293
 294 class BufferedPipeline(PipelineBase):
 295     """ buffered pipeline stage.  data and strobe signals travel in sync.
 296         if ever the input is ready and the output is not, processed data
 297         is stored in a temporary register.
 298
 299         Argument: stage.  see Stage API above
 300
 301         stage-1   p.i_valid >>in   stage   n.o_valid out>>   stage+1
 302         stage-1   p.o_ready <<out  stage   n.i_ready <<in    stage+1
 303         stage-1   p.i_data  >>in   stage   n.o_data  out>>   stage+1
 304                               |             |
 305                             process --->----^
 306                               |             |
 307                               +-- r_data ->-+
 308
 309         input data p.i_data is read (only), is processed and goes into an
 310         intermediate result store [process()].  this is updated combinatorially.
 311
 312         in a non-stall condition, the intermediate result will go into the
 313         output (update_output).  however if ever there is a stall, it goes
 314         into r_data instead [update_buffer()].
 315
 316         when the non-stall condition is released, r_data is the first
 317         to be transferred to the output [flush_buffer()], and the stall
 318         condition cleared.
 319
 320         on the next cycle (as long as stall is not raised again) the
 321         input may begin to be processed and transferred directly to output.
 322
 323     """
 324     def __init__(self, stage):
 325         PipelineBase.__init__(self, stage)
 326
 327         # set up the input and output data
 328         self.p.i_data = stage.ispec() # input type
 329         self.n.o_data = stage.ospec()
 330
 331     def elaborate(self, platform):
 332         m = Module()
 333
 334         result = self.stage.ospec()
 335         r_data = self.stage.ospec()
 336         if hasattr(self.stage, "setup"):
 337             self.stage.setup(m, self.p.i_data)
 338
 339         # establish some combinatorial temporaries
 340         o_n_validn = Signal(reset_less=True)
 341         i_p_valid_o_p_ready = Signal(reset_less=True)
 342         p_i_valid = Signal(reset_less=True)
 343         m.d.comb += [p_i_valid.eq(self.p.i_valid_logic()),
 344                      o_n_validn.eq(~self.n.o_valid),
 345                      i_p_valid_o_p_ready.eq(p_i_valid & self.p.o_ready),
 346         ]
 347
 348         # store result of processing in combinatorial temporary
 349         m.d.comb += eq(result, self.stage.process(self.p.i_data))
 350
 351         # if not in stall condition, update the temporary register
 352         with m.If(self.p.o_ready): # not stalled
 353             m.d.sync += eq(r_data, result) # update buffer
 354
 355         with m.If(self.n.i_ready): # next stage is ready
 356             with m.If(self.p.o_ready): # not stalled
 357                 # nothing in buffer: send (processed) input direct to output
 358                 m.d.sync += [self.n.o_valid.eq(p_i_valid),
 359                              eq(self.n.o_data, result), # update output
 360                             ]
 361             with m.Else(): # p.o_ready is false, and something is in buffer.
 362                 # Flush the [already processed] buffer to the output port.
 363                 m.d.sync += [self.n.o_valid.eq(1),      # declare reg empty
 364                              eq(self.n.o_data, r_data), # flush buffer
 365                              self.p.o_ready.eq(1),      # clear stall condition
 366                             ]
 367                 # ignore input, since p.o_ready is also false.
 368
 369         # (n.i_ready) is false here: next stage is ready
 370         with m.Elif(o_n_validn): # next stage being told "ready"
 371             m.d.sync += [self.n.o_valid.eq(p_i_valid),
 372                          self.p.o_ready.eq(1), # Keep the buffer empty
 373                          eq(self.n.o_data, result), # set output data
 374                         ]
 375
 376         # (n.i_ready) false and (n.o_valid) true:
 377         with m.Elif(i_p_valid_o_p_ready):
 378             # If next stage *is* ready, and not stalled yet, accept input
 379             m.d.sync += self.p.o_ready.eq(~(p_i_valid & self.n.o_valid))
 380
 381         return m
 382
 383
 384 class ExampleAddStage:
 385     """ an example of how to use the buffered pipeline, as a class instance
 386     """
 387
 388     def ispec(self):
 389         """ returns a tuple of input signals which will be the incoming data
 390         """
 391         return (Signal(16), Signal(16))
 392
 393     def ospec(self):
 394         """ returns an output signal which will happen to contain the sum
 395             of the two inputs
 396         """
 397         return Signal(16)
 398
 399     def process(self, i):
 400         """ process the input data (sums the values in the tuple) and returns it
 401         """
 402         return i[0] + i[1]
 403
 404
 405 class ExampleBufPipeAdd(BufferedPipeline):
 406     """ an example of how to use the buffered pipeline, using a class instance
 407     """
 408
 409     def __init__(self):
 410         addstage = ExampleAddStage()
 411         BufferedPipeline.__init__(self, addstage)
 412
 413
 414 class ExampleStage:
 415     """ an example of how to use the buffered pipeline, in a static class
 416         fashion
 417     """
 418
 419     def ispec():
 420         return Signal(16, name="example_input_signal")
 421
 422     def ospec():
 423         return Signal(16, name="example_output_signal")
 424
 425     def process(i):
 426         """ process the input data and returns it (adds 1)
 427         """
 428         return i + 1
 429
 430
 431 class ExampleStageCls:
 432     """ an example of how to use the buffered pipeline, in a static class
 433         fashion
 434     """
 435
 436     def ispec(self):
 437         return Signal(16, name="example_input_signal")
 438
 439     def ospec(self):
 440         return Signal(16, name="example_output_signal")
 441
 442     def process(self, i):
 443         """ process the input data and returns it (adds 1)
 444         """
 445         return i + 1
 446
 447
 448 class ExampleBufPipe(BufferedPipeline):
 449     """ an example of how to use the buffered pipeline.
 450     """
 451
 452     def __init__(self):
 453         BufferedPipeline.__init__(self, ExampleStage)
 454
 455
 456 class UnbufferedPipeline(PipelineBase):
 457     """ A simple pipeline stage with single-clock synchronisation
 458         and two-way valid/ready synchronised signalling.
 459
 460         Note that a stall in one stage will result in the entire pipeline
 461         chain stalling.
 462
 463         Also that unlike BufferedPipeline, the valid/ready signalling does NOT
 464         travel synchronously with the data: the valid/ready signalling
 465         combines in a *combinatorial* fashion.  Therefore, a long pipeline
 466         chain will lengthen propagation delays.
 467
 468         Argument: stage.  see Stage API, above
 469
 470         stage-1   p.i_valid >>in   stage   n.o_valid out>>   stage+1
 471         stage-1   p.o_ready <<out  stage   n.i_ready <<in    stage+1
 472         stage-1   p.i_data  >>in   stage   n.o_data  out>>   stage+1
 473                               |             |
 474                             r_data        result
 475                               |             |
 476                               +--process ->-+
 477
 478         Attributes:
 479         -----------
 480         p.i_data : StageInput, shaped according to ispec
 481             The pipeline input
 482         p.o_data : StageOutput, shaped according to ospec
 483             The pipeline output
 484         r_data : input_shape according to ispec
 485             A temporary (buffered) copy of a prior (valid) input.
 486             This is HELD if the output is not ready.  It is updated
 487             SYNCHRONOUSLY.
 488         result: output_shape according to ospec
 489             The output of the combinatorial logic.  it is updated
 490             COMBINATORIALLY (no clock dependence).
 491     """
 492
 493     def __init__(self, stage):
 494         PipelineBase.__init__(self, stage)
 495         self._data_valid = Signal()
 496
 497         # set up the input and output data
 498         self.p.i_data = stage.ispec() # input type
 499         self.n.o_data = stage.ospec() # output type
 500
 501     def elaborate(self, platform):
 502         m = Module()
 503
 504         r_data = self.stage.ispec() # input type
 505         result = self.stage.ospec() # output data
 506         if hasattr(self.stage, "setup"):
 507             self.stage.setup(m, r_data)
 508
 509         p_i_valid = Signal(reset_less=True)
 510         m.d.comb += p_i_valid.eq(self.p.i_valid_logic())
 511         m.d.comb += eq(result, self.stage.process(r_data))
 512         m.d.comb += self.n.o_valid.eq(self._data_valid)
 513         m.d.comb += self.p.o_ready.eq(~self._data_valid | self.n.i_ready)
 514         m.d.sync += self._data_valid.eq(p_i_valid | \
 515                                         (~self.n.i_ready & self._data_valid))
 516         with m.If(self.p.i_valid & self.p.o_ready):
 517             m.d.sync += eq(r_data, self.p.i_data)
 518         m.d.comb += eq(self.n.o_data, result)
 519         return m
 520
 521
 522 class ExamplePipeline(UnbufferedPipeline):
 523     """ an example of how to use the combinatorial pipeline.
 524     """
 525
 526     def __init__(self):
 527         UnbufferedPipeline.__init__(self, ExampleStage)
 528
 529
 530 if __name__ == '__main__':
 531     dut = ExampleBufPipe()
 532     vl = rtlil.convert(dut, ports=dut.ports())
 533     with open("test_bufpipe.il", "w") as f:
 534         f.write(vl)
 535
 536     dut = ExamplePipeline()
 537     vl = rtlil.convert(dut, ports=dut.ports())
 538     with open("test_combpipe.il", "w") as f:
 539         f.write(vl)