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