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 (i.p_stb) is HIGH
  16         * outgoing previous-stage busy   (o.p_busy) is LOW
  17
  18     output transmission conditions are when:
  19         * outgoing next-stage strobe (o.n_stb) is HIGH
  20         * outgoing next-stage busy   (i.n_busy) 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 busy, 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
  49
  50 class ExampleStage:
  51     """ an example of how to use the buffered pipeline.  actual names of
  52         variables (i_data, r_data, o_data, result) below do not matter:
  53         the functions however do.
  54
  55         input data i_data is read (only), is processed and goes into an
  56         intermediate result store [process()].  this is updated combinatorially.
  57
  58         in a non-stall condition, the intermediate result will go into the
  59         output (update_output).  however if ever there is a stall, it goes
  60         into r_data instead [update_buffer()].
  61
  62         when the non-stall condition is released, r_data is the first
  63         to be transferred to the output [flush_buffer()], and the stall
  64         condition cleared.
  65
  66         on the next cycle (as long as stall is not raised again) the
  67         input may begin to be processed and transferred directly to output.
  68     """
  69
  70     def __init__(self):
  71         """ i_data can be a DIFFERENT type from everything else
  72             o_data, r_data and result must be of the same type
  73         """
  74         self.i_data = Signal(16)
  75         self.r_data = Signal(16)
  76         self.o_data = Signal(16)
  77         self.result = Signal(16)
  78
  79     def process(self):
  80         """ process the input data and store it in result.
  81             (not needed to be known: result is combinatorial)
  82         """
  83         return self.result.eq(self.i_data + 1)
  84
  85     def update_buffer(self):
  86         """ copies the result into the intermediate register r_data
  87         """
  88         return self.r_data.eq(self.result)
  89
  90     def update_output(self):
  91         """ copies the (combinatorial) result into the output
  92         """
  93         return self.o_data.eq(self.result)
  94
  95     def flush_buffer(self):
  96         """ copies the *intermediate* register r_data into the output
  97         """
  98         return self.o_data.eq(self.r_data)
  99
 100     def ports(self):
 101         return [self.i_data, self.o_data]
 102
 103 class IOAckIn:
 104
 105     def __init__(self):
 106         self.p_stb = Signal()  # >>in - comes in from PREVIOUS stage
 107         self.n_busy = Signal() # in<< - comes in from the NEXT stage
 108
 109
 110 class IOAckOut:
 111
 112     def __init__(self):
 113         self.n_stb = Signal()  # out>> - goes out to the NEXT stage
 114         self.p_busy = Signal() # <<out - goes out to the PREVIOUS stage
 115
 116
 117 class BufferedPipeline:
 118     """ buffered pipeline stage
 119
 120         stage-1   i.p_stb  >>in   stage   o.n_stb  out>>   stage+1
 121         stage-1   o.p_busy <<out  stage   i.n_busy <<in    stage+1
 122         stage-1   i_data   >>in   stage   o_data   out>>   stage+1
 123                               |             |
 124                               +------->  process
 125                               |             |
 126                               +-- r_data ---+
 127     """
 128     def __init__(self):
 129         # input: strobe comes in from previous stage, busy comes in from next
 130         self.i = IOAckIn()
 131         #self.i.p_stb = Signal()    # >>in - comes in from PREVIOUS stage
 132         #self.i.n_busy = Signal()   # in<< - comes in from the NEXT stage
 133
 134         # output: strobe goes out to next stage, busy comes in from previous
 135         self.o = IOAckOut()
 136         #self.o.n_stb = Signal()    # out>> - goes out to the NEXT stage
 137         #self.o.p_busy = Signal()   # <<out - goes out to the PREVIOUS stage
 138
 139     def elaborate(self, platform):
 140         m = Module()
 141
 142         # establish some combinatorial temporaries
 143         o_p_busyn = Signal(reset_less=True)
 144         o_n_stbn = Signal(reset_less=True)
 145         i_n_busyn = Signal(reset_less=True)
 146         i_p_stb_o_p_busyn = Signal(reset_less=True)
 147         m.d.comb += [i_n_busyn.eq(~self.i.n_busy),
 148                      o_n_stbn.eq(~self.o.n_stb),
 149                      o_p_busyn.eq(~self.o.p_busy),
 150                      i_p_stb_o_p_busyn.eq(self.i.p_stb & o_p_busyn),
 151         ]
 152
 153         # store result of processing in combinatorial temporary
 154         with m.If(self.i.p_stb): # input is valid: process it
 155             m.d.comb += self.stage.process()
 156         # if not in stall condition, update the temporary register
 157         with m.If(o_p_busyn): # not stalled
 158             m.d.sync += self.stage.update_buffer()
 159
 160         #with m.If(self.i.p_rst): # reset
 161         #    m.d.sync += self.o.n_stb.eq(0)
 162         #    m.d.sync += self.o.p_busy.eq(0)
 163         with m.If(i_n_busyn): # next stage is not busy
 164             with m.If(o_p_busyn): # not stalled
 165                 # nothing in buffer: send (processed) input direct to output
 166                 m.d.sync += [self.o.n_stb.eq(self.i.p_stb),
 167                              self.stage.update_output(),
 168                             ]
 169             with m.Else(): # o.p_busy is true, and something is in our buffer.
 170                 # Flush the [already processed] buffer to the output port.
 171                 m.d.sync += [self.o.n_stb.eq(1),
 172                              self.stage.flush_buffer(),
 173                              # clear stall condition, declare register empty.
 174                              self.o.p_busy.eq(0),
 175                             ]
 176                 # ignore input, since o.p_busy is also true.
 177
 178         # (i.n_busy) is true here: next stage is busy
 179         with m.Elif(o_n_stbn): # next stage being told "not busy"
 180             m.d.sync += [self.o.n_stb.eq(self.i.p_stb),
 181                          self.o.p_busy.eq(0), # Keep the buffer empty
 182                          # set the output data (from comb result)
 183                          self.stage.update_output(),
 184                         ]
 185         # (i.n_busy) and (o.n_stb) both true:
 186         with m.Elif(i_p_stb_o_p_busyn):
 187             # If next stage *is* busy, and not stalled yet, accept input
 188             m.d.sync += self.o.p_busy.eq(self.i.p_stb & self.o.n_stb)
 189
 190         return m
 191
 192     def ports(self):
 193         return [self.i.p_stb, self.i.n_busy,
 194                 self.o.n_stb, self.o.p_busy,
 195                ]
 196
 197
 198 class BufPipe(BufferedPipeline):
 199
 200     def __init__(self):
 201         BufferedPipeline.__init__(self)
 202         self.stage = ExampleStage()
 203
 204     def ports(self):
 205         return self.stage.ports() + BufferedPipeline.ports(self)
 206
 207
 208 if __name__ == '__main__':
 209     dut = BufPipe()
 210     vl = rtlil.convert(dut, ports=dut.ports())
 211     with open("test_bufpipe.il", "w") as f:
 212         f.write(vl)