1 """ nmigen implementation of buffered pipeline stage, based on zipcpu:
2 https://zipcpu.com/blog/2017/08/14/strategies-for-pipelining.html
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.
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.
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
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
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.
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.
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.
40 this allows us to respect a synchronous "travelling STB" with what
41 dan calls a "buffered handshake".
43 it's quite a complex state machine!
46 from nmigen
import Signal
, Cat
, Const
, Mux
, Module
47 from nmigen
.cli
import verilog
, rtlil
48 from nmigen
.hdl
.rec
import Record
, Layout
50 from collections
.abc
import Sequence
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
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
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!
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
),
75 def i_valid_logic(self
):
76 vlen
= len(self
.i_valid
)
77 if vlen
> 1: # multi-bit case: valid only when i_valid is all 1s
78 all1s
= Const(-1, (len(self
.i_valid
), False))
79 return self
.i_valid
== all1s
80 # single-bit i_valid case
85 """ contains the signals that go *to* the next stage (both in and out)
86 * o_valid: output indicating to next stage that data is valid
87 * i_ready: input from next stage indicating that it can accept data
88 * o_data : an output - added by the user of this class
91 self
.o_valid
= Signal(name
="n_o_valid") # self out>> next
92 self
.i_ready
= Signal(name
="n_i_ready") # self <<in next
94 def connect_to_next(self
, nxt
):
95 """ helper function to connect to the next stage data/valid/ready.
96 data/valid is passed *TO* nxt, and ready comes *IN* from nxt.
98 return [nxt
.i_valid
.eq(self
.o_valid
),
99 self
.i_ready
.eq(nxt
.o_ready
),
100 eq(nxt
.i_data
, self
.o_data
),
103 def connect_out(self
, nxt
):
104 """ helper function to connect stage to an output source. do not
105 use to connect stage-to-stage!
107 return [nxt
.o_valid
.eq(self
.o_valid
),
108 self
.i_ready
.eq(nxt
.i_ready
),
109 eq(nxt
.o_data
, self
.o_data
),
114 """ makes signals equal: a helper routine which identifies if it is being
115 passed a list (or tuple) of objects, or signals, or Records, and calls
116 the objects' eq function.
118 complex objects (classes) can be used: they must follow the
119 convention of having an eq member function, which takes the
120 responsibility of further calling eq and returning a list of
123 Record is a special (unusual, recursive) case, where the input
124 is specified as a dictionary (which may contain further dictionaries,
125 recursively), where the field names of the dictionary must match
126 the Record's field spec.
128 if not isinstance(o
, Sequence
):
131 for (ao
, ai
) in zip(o
, i
):
132 #print ("eq", ao, ai)
133 if isinstance(ao
, Record
):
134 for idx
, (field_name
, field_shape
, _
) in enumerate(ao
.layout
):
135 if isinstance(field_shape
, Layout
):
136 rres
= eq(ao
.fields
[field_name
], ai
.fields
[field_name
])
138 rres
= eq(ao
.fields
[field_name
], ai
[field_name
])
142 if not isinstance(rres
, Sequence
):
149 """ pass in a list of stages, and they will automatically be
150 chained together via their input and output specs into a
153 * input to this class will be the input of the first stage
154 * output of first stage goes into input of second
155 * output of second goes into input into third (etc. etc.)
156 * the output of this class will be the output of the last stage
158 def __init__(self
, chain
):
162 return self
.chain
[0].ispec()
165 return self
.chain
[-1].ospec()
167 def setup(self
, m
, i
):
168 for (idx
, c
) in enumerate(self
.chain
):
169 if hasattr(c
, "setup"):
170 c
.setup(m
, i
) # stage may have some module stuff
171 o
= self
.chain
[idx
].ospec() # only the last assignment survives
172 m
.d
.comb
+= eq(o
, c
.process(i
)) # process input into "o"
173 if idx
!= len(self
.chain
)-1:
174 ni
= self
.chain
[idx
+1].ispec() # becomes new input on next loop
175 m
.d
.comb
+= eq(ni
, o
) # assign output to next input
177 self
.o
= o
# last loop is the output
179 def process(self
, i
):
184 """ Common functions for Pipeline API
186 def __init__(self
, stage
, in_multi
=None):
187 """ pass in a "stage" which may be either a static class or a class
188 instance, which has four functions (one optional):
189 * ispec: returns input signals according to the input specification
190 * ispec: returns output signals to the output specification
191 * process: takes an input instance and returns processed data
192 * setup: performs any module linkage if the stage uses one.
195 * add i_data member to PrevControl and
196 * add o_data member to NextControl
200 # set up input and output IO ACK (prev/next ready/valid)
201 self
.p
= PrevControl(in_multi
)
202 self
.n
= NextControl()
204 def connect_to_next(self
, nxt
):
205 """ helper function to connect to the next stage data/valid/ready.
207 return self
.n
.connect_to_next(nxt
.p
)
209 def connect_in(self
, prev
):
210 """ helper function to connect stage to an input source. do not
211 use to connect stage-to-stage!
213 return self
.p
.connect_in(prev
.p
)
215 def connect_out(self
, nxt
):
216 """ helper function to connect stage to an output source. do not
217 use to connect stage-to-stage!
219 return self
.n
.connect_out(nxt
.n
)
221 def set_input(self
, i
):
222 """ helper function to set the input data
224 return eq(self
.p
.i_data
, i
)
227 return [self
.p
.i_valid
, self
.n
.i_ready
,
228 self
.n
.o_valid
, self
.p
.o_ready
,
229 self
.p
.i_data
, self
.n
.o_data
# XXX need flattening!
233 class BufferedPipeline(PipelineBase
):
234 """ buffered pipeline stage. data and strobe signals travel in sync.
235 if ever the input is ready and the output is not, processed data
236 is stored in a temporary register.
238 stage-1 p.i_valid >>in stage n.o_valid out>> stage+1
239 stage-1 p.o_ready <<out stage n.i_ready <<in stage+1
240 stage-1 p.i_data >>in stage n.o_data out>> stage+1
246 input data p.i_data is read (only), is processed and goes into an
247 intermediate result store [process()]. this is updated combinatorially.
249 in a non-stall condition, the intermediate result will go into the
250 output (update_output). however if ever there is a stall, it goes
251 into r_data instead [update_buffer()].
253 when the non-stall condition is released, r_data is the first
254 to be transferred to the output [flush_buffer()], and the stall
257 on the next cycle (as long as stall is not raised again) the
258 input may begin to be processed and transferred directly to output.
260 def __init__(self
, stage
):
261 PipelineBase
.__init
__(self
, stage
)
263 # set up the input and output data
264 self
.p
.i_data
= stage
.ispec() # input type
265 self
.n
.o_data
= stage
.ospec()
267 def elaborate(self
, platform
):
270 result
= self
.stage
.ospec()
271 r_data
= self
.stage
.ospec()
272 if hasattr(self
.stage
, "setup"):
273 self
.stage
.setup(m
, self
.p
.i_data
)
275 # establish some combinatorial temporaries
276 o_n_validn
= Signal(reset_less
=True)
277 i_p_valid_o_p_ready
= Signal(reset_less
=True)
278 p_i_valid
= Signal(reset_less
=True)
279 m
.d
.comb
+= [p_i_valid
.eq(self
.p
.i_valid_logic()),
280 o_n_validn
.eq(~self
.n
.o_valid
),
281 i_p_valid_o_p_ready
.eq(p_i_valid
& self
.p
.o_ready
),
284 # store result of processing in combinatorial temporary
285 m
.d
.comb
+= eq(result
, self
.stage
.process(self
.p
.i_data
))
287 # if not in stall condition, update the temporary register
288 with m
.If(self
.p
.o_ready
): # not stalled
289 m
.d
.sync
+= eq(r_data
, result
) # update buffer
291 with m
.If(self
.n
.i_ready
): # next stage is ready
292 with m
.If(self
.p
.o_ready
): # not stalled
293 # nothing in buffer: send (processed) input direct to output
294 m
.d
.sync
+= [self
.n
.o_valid
.eq(p_i_valid
),
295 eq(self
.n
.o_data
, result
), # update output
297 with m
.Else(): # p.o_ready is false, and something is in buffer.
298 # Flush the [already processed] buffer to the output port.
299 m
.d
.sync
+= [self
.n
.o_valid
.eq(1), # declare reg empty
300 eq(self
.n
.o_data
, r_data
), # flush buffer
301 self
.p
.o_ready
.eq(1), # clear stall condition
303 # ignore input, since p.o_ready is also false.
305 # (n.i_ready) is false here: next stage is ready
306 with m
.Elif(o_n_validn
): # next stage being told "ready"
307 m
.d
.sync
+= [self
.n
.o_valid
.eq(p_i_valid
),
308 self
.p
.o_ready
.eq(1), # Keep the buffer empty
309 eq(self
.n
.o_data
, result
), # set output data
312 # (n.i_ready) false and (n.o_valid) true:
313 with m
.Elif(i_p_valid_o_p_ready
):
314 # If next stage *is* ready, and not stalled yet, accept input
315 m
.d
.sync
+= self
.p
.o_ready
.eq(~
(p_i_valid
& self
.n
.o_valid
))
320 class ExampleAddStage
:
321 """ an example of how to use the buffered pipeline, as a class instance
325 """ returns a tuple of input signals which will be the incoming data
327 return (Signal(16), Signal(16))
330 """ returns an output signal which will happen to contain the sum
335 def process(self
, i
):
336 """ process the input data (sums the values in the tuple) and returns it
341 class ExampleBufPipeAdd(BufferedPipeline
):
342 """ an example of how to use the buffered pipeline, using a class instance
346 addstage
= ExampleAddStage()
347 BufferedPipeline
.__init
__(self
, addstage
)
351 """ an example of how to use the buffered pipeline, in a static class
356 return Signal(16, name
="example_input_signal")
359 return Signal(16, name
="example_output_signal")
362 """ process the input data and returns it (adds 1)
367 class ExampleStageCls
:
368 """ an example of how to use the buffered pipeline, in a static class
373 return Signal(16, name
="example_input_signal")
376 return Signal(16, name
="example_output_signal")
378 def process(self
, i
):
379 """ process the input data and returns it (adds 1)
384 class ExampleBufPipe(BufferedPipeline
):
385 """ an example of how to use the buffered pipeline.
389 BufferedPipeline
.__init
__(self
, ExampleStage
)
392 class CombPipe(PipelineBase
):
393 """A simple pipeline stage containing combinational logic that can execute
394 completely in one clock cycle.
402 r_data : Signal, input_shape
403 A temporary (buffered) copy of a prior (valid) input
404 result: Signal, output_shape
405 The output of the combinatorial logic
408 def __init__(self
, stage
):
409 PipelineBase
.__init
__(self
, stage
)
410 self
._data
_valid
= Signal()
412 # set up the input and output data
413 self
.p
.i_data
= stage
.ispec() # input type
414 self
.n
.o_data
= stage
.ospec() # output type
416 def elaborate(self
, platform
):
419 r_data
= self
.stage
.ispec() # input type
420 result
= self
.stage
.ospec() # output data
421 if hasattr(self
.stage
, "setup"):
422 self
.stage
.setup(m
, r_data
)
424 p_i_valid
= Signal(reset_less
=True)
425 m
.d
.comb
+= p_i_valid
.eq(self
.p
.i_valid_logic())
426 m
.d
.comb
+= eq(result
, self
.stage
.process(r_data
))
427 m
.d
.comb
+= self
.n
.o_valid
.eq(self
._data
_valid
)
428 m
.d
.comb
+= self
.p
.o_ready
.eq(~self
._data
_valid | self
.n
.i_ready
)
429 m
.d
.sync
+= self
._data
_valid
.eq(p_i_valid | \
430 (~self
.n
.i_ready
& self
._data
_valid
))
431 with m
.If(self
.p
.i_valid
& self
.p
.o_ready
):
432 m
.d
.sync
+= eq(r_data
, self
.p
.i_data
)
433 m
.d
.comb
+= eq(self
.n
.o_data
, result
)
437 class ExampleCombPipe(CombPipe
):
438 """ an example of how to use the combinatorial pipeline.
442 CombPipe
.__init
__(self
, ExampleStage
)
445 if __name__
== '__main__':
446 dut
= ExampleBufPipe()
447 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
448 with
open("test_bufpipe.il", "w") as f
:
451 dut
= ExampleCombPipe()
452 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
453 with
open("test_combpipe.il", "w") as f
: