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