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