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