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         passsed a list (or tuple) of objects, and calls the objects' eq
 116         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             res.append(ao.eq(ai))
 142     return res
 143
 144
 145 class PipelineBase:
 146     """ Common functions for Pipeline API
 147     """
 148     def __init__(self, stage, in_multi=None):
 149         """ pass in a "stage" which may be either a static class or a class
 150             instance, which has four functions (one optional):
 151             * ispec: returns input signals according to the input specification
 152             * ispec: returns output signals to the output specification
 153             * process: takes an input instance and returns processed data
 154             * setup: performs any module linkage if the stage uses one.
 155
 156             User must also:
 157             * add i_data member to PrevControl and
 158             * add o_data member to NextControl
 159         """
 160         self.stage = stage
 161
 162         # set up input and output IO ACK (prev/next ready/valid)
 163         self.p = PrevControl(in_multi)
 164         self.n = NextControl()
 165
 166     def connect_to_next(self, nxt):
 167         """ helper function to connect to the next stage data/valid/ready.
 168         """
 169         return self.n.connect_to_next(nxt.p)
 170
 171     def connect_in(self, prev):
 172         """ helper function to connect stage to an input source.  do not
 173             use to connect stage-to-stage!
 174         """
 175         return self.p.connect_in(prev.p)
 176
 177     def connect_out(self, nxt):
 178         """ helper function to connect stage to an output source.  do not
 179             use to connect stage-to-stage!
 180         """
 181         return self.n.connect_out(nxt.n)
 182
 183     def set_input(self, i):
 184         """ helper function to set the input data
 185         """
 186         return eq(self.p.i_data, i)
 187
 188     def ports(self):
 189         return [self.p.i_valid, self.n.i_ready,
 190                 self.n.o_valid, self.p.o_ready,
 191                 self.p.i_data, self.n.o_data   # XXX need flattening!
 192                ]
 193
 194
 195 class BufferedPipeline(PipelineBase):
 196     """ buffered pipeline stage.  data and strobe signals travel in sync.
 197         if ever the input is ready and the output is not, processed data
 198         is stored in a temporary register.
 199
 200         stage-1   p.i_valid >>in   stage   n.o_valid out>>   stage+1
 201         stage-1   p.o_ready <<out  stage   n.i_ready <<in    stage+1
 202         stage-1   p.i_data  >>in   stage   n.o_data  out>>   stage+1
 203                               |             |
 204                             process --->----^
 205                               |             |
 206                               +-- r_data ->-+
 207
 208         input data p.i_data is read (only), is processed and goes into an
 209         intermediate result store [process()].  this is updated combinatorially.
 210
 211         in a non-stall condition, the intermediate result will go into the
 212         output (update_output).  however if ever there is a stall, it goes
 213         into r_data instead [update_buffer()].
 214
 215         when the non-stall condition is released, r_data is the first
 216         to be transferred to the output [flush_buffer()], and the stall
 217         condition cleared.
 218
 219         on the next cycle (as long as stall is not raised again) the
 220         input may begin to be processed and transferred directly to output.
 221     """
 222     def __init__(self, stage):
 223         PipelineBase.__init__(self, stage)
 224
 225         # set up the input and output data
 226         self.p.i_data = stage.ispec() # input type
 227         self.n.o_data = stage.ospec()
 228
 229     def elaborate(self, platform):
 230         m = Module()
 231
 232         result = self.stage.ospec()
 233         r_data = self.stage.ospec()
 234         if hasattr(self.stage, "setup"):
 235             self.stage.setup(m, self.p.i_data)
 236
 237         # establish some combinatorial temporaries
 238         o_n_validn = Signal(reset_less=True)
 239         i_p_valid_o_p_ready = Signal(reset_less=True)
 240         p_i_valid = Signal(reset_less=True)
 241         m.d.comb += [p_i_valid.eq(self.p.i_valid_logic()),
 242                      o_n_validn.eq(~self.n.o_valid),
 243                      i_p_valid_o_p_ready.eq(p_i_valid & self.p.o_ready),
 244         ]
 245
 246         # store result of processing in combinatorial temporary
 247         #with m.If(self.p.i_valid): # input is valid: process it
 248         m.d.comb += eq(result, self.stage.process(self.p.i_data))
 249         # if not in stall condition, update the temporary register
 250         with m.If(self.p.o_ready): # not stalled
 251             m.d.sync += eq(r_data, result) # update buffer
 252
 253         #with m.If(self.p.i_rst): # reset
 254         #    m.d.sync += self.n.o_valid.eq(0)
 255         #    m.d.sync += self.p.o_ready.eq(0)
 256         with m.If(self.n.i_ready): # next stage is ready
 257             with m.If(self.p.o_ready): # not stalled
 258                 # nothing in buffer: send (processed) input direct to output
 259                 m.d.sync += [self.n.o_valid.eq(p_i_valid),
 260                              eq(self.n.o_data, result), # update output
 261                             ]
 262             with m.Else(): # p.o_ready is false, and something is in buffer.
 263                 # Flush the [already processed] buffer to the output port.
 264                 m.d.sync += [self.n.o_valid.eq(1),
 265                              eq(self.n.o_data, r_data), # flush buffer
 266                              # clear stall condition, declare register empty.
 267                              self.p.o_ready.eq(1),
 268                             ]
 269                 # ignore input, since p.o_ready is also false.
 270
 271         # (n.i_ready) is false here: next stage is ready
 272         with m.Elif(o_n_validn): # next stage being told "ready"
 273             m.d.sync += [self.n.o_valid.eq(p_i_valid),
 274                          self.p.o_ready.eq(1), # Keep the buffer empty
 275                          # set the output data (from comb result)
 276                          eq(self.n.o_data, result),
 277                         ]
 278         # (n.i_ready) false and (n.o_valid) true:
 279         with m.Elif(i_p_valid_o_p_ready):
 280             # If next stage *is* ready, and not stalled yet, accept input
 281             m.d.sync += self.p.o_ready.eq(~(p_i_valid & self.n.o_valid))
 282
 283         return m
 284
 285
 286 class ExampleAddStage:
 287     """ an example of how to use the buffered pipeline, as a class instance
 288     """
 289
 290     def ispec(self):
 291         """ returns a tuple of input signals which will be the incoming data
 292         """
 293         return (Signal(16), Signal(16))
 294
 295     def ospec(self):
 296         """ returns an output signal which will happen to contain the sum
 297             of the two inputs
 298         """
 299         return Signal(16)
 300
 301     def process(self, i):
 302         """ process the input data (sums the values in the tuple) and returns it
 303         """
 304         return i[0] + i[1]
 305
 306
 307 class ExampleBufPipeAdd(BufferedPipeline):
 308     """ an example of how to use the buffered pipeline, using a class instance
 309     """
 310
 311     def __init__(self):
 312         addstage = ExampleAddStage()
 313         BufferedPipeline.__init__(self, addstage)
 314
 315
 316 class ExampleStage:
 317     """ an example of how to use the buffered pipeline, in a static class
 318         fashion
 319     """
 320
 321     def ispec():
 322         return Signal(16)
 323
 324     def ospec():
 325         return Signal(16)
 326
 327     def process(i):
 328         """ process the input data and returns it (adds 1)
 329         """
 330         return i + 1
 331
 332
 333 class ExampleBufPipe(BufferedPipeline):
 334     """ an example of how to use the buffered pipeline.
 335     """
 336
 337     def __init__(self):
 338         BufferedPipeline.__init__(self, ExampleStage)
 339
 340
 341 class CombPipe(PipelineBase):
 342     """A simple pipeline stage containing combinational logic that can execute
 343     completely in one clock cycle.
 344
 345     Attributes:
 346     -----------
 347     input : StageInput
 348         The pipeline input
 349     output : StageOutput
 350         The pipeline output
 351     r_data : Signal, input_shape
 352         A temporary (buffered) copy of a prior (valid) input
 353     result: Signal, output_shape
 354         The output of the combinatorial logic
 355     """
 356
 357     def __init__(self, stage):
 358         PipelineBase.__init__(self, stage)
 359         self._data_valid = Signal()
 360
 361         # set up the input and output data
 362         self.p.i_data = stage.ispec() # input type
 363         self.n.o_data = stage.ospec() # output type
 364
 365     def elaborate(self, platform):
 366         m = Module()
 367
 368         r_data = self.stage.ispec() # input type
 369         result = self.stage.ospec() # output data
 370         if hasattr(self.stage, "setup"):
 371             self.stage.setup(m, r_data)
 372
 373         p_i_valid = Signal(reset_less=True)
 374         m.d.comb += p_i_valid.eq(self.p.i_valid_logic())
 375         m.d.comb += eq(result, self.stage.process(r_data))
 376         m.d.comb += self.n.o_valid.eq(self._data_valid)
 377         m.d.comb += self.p.o_ready.eq(~self._data_valid | self.n.i_ready)
 378         m.d.sync += self._data_valid.eq(p_i_valid | \
 379                                         (~self.n.i_ready & self._data_valid))
 380         with m.If(self.p.i_valid & self.p.o_ready):
 381             m.d.sync += eq(r_data, self.p.i_data)
 382         m.d.comb += eq(self.n.o_data, result)
 383         return m
 384
 385
 386 class ExampleCombPipe(CombPipe):
 387     """ an example of how to use the combinatorial pipeline.
 388     """
 389
 390     def __init__(self):
 391         CombPipe.__init__(self, ExampleStage)
 392
 393
 394 if __name__ == '__main__':
 395     dut = ExampleBufPipe()
 396     vl = rtlil.convert(dut, ports=dut.ports())
 397     with open("test_bufpipe.il", "w") as f:
 398         f.write(vl)
 399
 400     dut = ExampleCombPipe()
 401     vl = rtlil.convert(dut, ports=dut.ports())
 402     with open("test_combpipe.il", "w") as f:
 403         f.write(vl)