380ffb8051289a962976dc308af8b02af8e3fff0
1 """ Priority Picker: optimised back-to-back PriorityEncoder and Decoder
2 and MultiPriorityPicker: cascading mutually-exclusive pickers
4 This work is funded through NLnet under Grant 2019-02-012
9 PriorityPicker: the input is N bits, the output is N bits wide and
12 MultiPriorityPicker: likewise except that there are M pickers and
13 each output is guaranteed mutually exclusive. Optionally:
14 an "index" (and enable line) is also outputted.
16 MultiPriorityPicker is designed for port-selection, when there are
17 multiple "things" (of width N) contending for access to M "ports".
18 When the M=0 "thing" requests a port, it gets allocated port 0
19 (always). However if the M=0 "thing" does *not* request a port,
20 this gives the M=1 "thing" the opportunity to gain access to port 0.
22 Given that N may potentially be much greater than M (16 bits wide
23 where M may be e.g. only 4) we can't just ok, "ok so M=N therefore
24 M=0 gets access to port 0, M=1 gets access to port 1" etc.
27 from nmigen
import Module
, Signal
, Cat
, Elaboratable
, Array
, Const
, Mux
28 from nmigen
.cli
import verilog
, rtlil
32 class PriorityPicker(Elaboratable
):
33 """ implements a priority-picker. input: N bits, output: N bits
35 * lsb_mode is for a LSB-priority picker
36 * reverse_i=True is for convenient reverseal of the input bits
37 * reverse_o=True is for convenient reversal of the output bits
40 def __init__(self
, wid
, lsb_mode
=False, reverse_i
=False, reverse_o
=False):
43 self
.lsb_mode
= lsb_mode
44 self
.reverse_i
= reverse_i
45 self
.reverse_o
= reverse_o
46 self
.i
= Signal(wid
, reset_less
=True)
47 self
.o
= Signal(wid
, reset_less
=True)
48 self
.en_o
= Signal(reset_less
=True) # true if any output is true
50 def elaborate(self
, platform
):
53 # works by saying, "if all previous bits were zero, we get a chance"
55 ni
= Signal(self
.wid
, reset_less
=True)
59 m
.d
.comb
+= ni
.eq(~
Cat(*i
))
60 prange
= list(range(0, self
.wid
))
64 t
= Signal(name
="t%d" % n
, reset_less
=True)
67 m
.d
.comb
+= t
.eq(i
[n
])
69 m
.d
.comb
+= t
.eq(~
Cat(ni
[n
], *i
[:n
]).bool())
72 # we like Cat(*xxx). turn lists into concatenated bits
73 m
.d
.comb
+= self
.o
.eq(Cat(*res
))
74 # useful "is any output enabled" signal
75 m
.d
.comb
+= self
.en_o
.eq(self
.o
.bool()) # true if 1 input is true
88 class MultiPriorityPicker(Elaboratable
):
89 """ implements a multi-input priority picker
90 Mx inputs of N bits, Mx outputs of N bits, only one is set
92 Each picker masks out the one below it, such that the first
93 gets top priority, the second cannot have the same bit that
94 the first has set, and so on. To do this, a "mask" accumulates
95 the output from the chain, masking the input to the next chain.
97 Also outputted (optional): an index for each picked "thing".
100 def __init__(self
, wid
, levels
, indices
=False, multiin
=False):
103 self
.indices
= indices
104 self
.multiin
= multiin
107 # multiple inputs, multiple outputs.
108 i_l
= [] # array of picker outputs
109 for j
in range(self
.levels
):
110 i
= Signal(self
.wid
, name
="i_%d" % j
, reset_less
=True)
114 # only the one input, but multiple (single) bit outputs
115 self
.i
= Signal(self
.wid
, reset_less
=True)
117 # create array of (single-bit) outputs (unary)
118 o_l
= [] # array of picker outputs
119 for j
in range(self
.levels
):
120 o
= Signal(self
.wid
, name
="o_%d" % j
, reset_less
=True)
124 # add an array of "enables"
125 self
.en_o
= Signal(self
.levels
, name
="en_o", reset_less
=True)
130 # add an array of indices
131 lidx
= math
.ceil(math
.log2(self
.levels
))
132 idx_o
= [] # store the array of indices
133 for j
in range(self
.levels
):
134 i
= Signal(lidx
, name
="idxo_%d" % j
, reset_less
=True)
136 self
.idx_o
= Array(idx_o
)
138 def elaborate(self
, platform
):
142 # create Priority Pickers, accumulate their outputs and prevent
143 # the next one in the chain from selecting that output bit.
144 # the input from the current picker will be "masked" and connected
145 # to the *next* picker on the next loop
149 for j
in range(self
.levels
):
155 pp
= PriorityPicker(self
.wid
)
157 setattr(m
.submodules
, "pp%d" % j
, pp
)
161 p_mask
= Const(0, self
.wid
)
163 mask
= Signal(self
.wid
, name
="m_%d" % j
, reset_less
=True)
164 comb
+= mask
.eq(prev_pp
.o | p_mask
) # accumulate output bits
165 comb
+= pp
.i
.eq(i
& ~mask
) # mask out input
167 i
= pp
.i
# for input to next round
170 # accumulate the enables
172 for j
in range(self
.levels
):
173 en_l
.append(pp_l
[j
].en_o
)
174 # concat accumulated enable bits
175 comb
+= self
.en_o
.eq(Cat(*en_l
))
180 # for each picker enabled, pass that out and set a cascading index
181 lidx
= math
.ceil(math
.log2(self
.levels
))
183 for j
in range(self
.levels
):
185 if prev_count
is None:
186 comb
+= self
.idx_o
[j
].eq(0)
188 count1
= Signal(lidx
, name
="count_%d" % j
, reset_less
=True)
189 comb
+= count1
.eq(prev_count
+ Const(1, lidx
))
190 comb
+= self
.idx_o
[j
].eq(Mux(en_o
, count1
, prev_count
))
191 prev_count
= self
.idx_o
[j
]
204 yield from self
.idx_o
210 if __name__
== '__main__':
211 dut
= PriorityPicker(16)
212 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
213 with
open("test_picker.il", "w") as f
:
215 dut
= MultiPriorityPicker(5, 4, True)
216 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
217 with
open("test_multi_picker.il", "w") as f
:
219 dut
= MultiPriorityPicker(5, 4, False, True)
220 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
221 with
open("test_multi_picker_noidx.il", "w") as f
: