0babc074a9eeb9663793bcc4fd1bfdb259d631bc
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
39 def __init__(self
, wid
, lsb_mode
=False, reverse_i
=False, reverse_o
=False):
42 self
.lsb_mode
= lsb_mode
43 self
.reverse_i
= reverse_i
44 self
.reverse_o
= reverse_o
45 self
.i
= Signal(wid
, reset_less
=True)
46 self
.o
= Signal(wid
, reset_less
=True)
47 self
.en_o
= Signal(reset_less
=True) # true if any output is true
49 def elaborate(self
, platform
):
52 # works by saying, "if all previous bits were zero, we get a chance"
54 ni
= Signal(self
.wid
, reset_less
= True)
58 m
.d
.comb
+= ni
.eq(~
Cat(*i
))
59 prange
= list(range(0, self
.wid
))
63 t
= Signal(name
="t%d" % n
, reset_less
= True)
66 m
.d
.comb
+= t
.eq(i
[n
])
68 m
.d
.comb
+= t
.eq(~
Cat(ni
[n
], *i
[:n
]).bool())
71 # we like Cat(*xxx). turn lists into concatenated bits
72 m
.d
.comb
+= self
.o
.eq(Cat(*res
))
73 # useful "is any output enabled" signal
74 m
.d
.comb
+= self
.en_o
.eq(self
.o
.bool()) # true if 1 input is true
87 class MultiPriorityPicker(Elaboratable
):
88 """ implements a multi-input priority picker
89 Mx inputs of N bits, Mx outputs of N bits, only one is set
91 Each picker masks out the one below it, such that the first
92 gets top priority, the second cannot have the same bit that
93 the first has set, and so on. To do this, a "mask" accumulates
94 the output from the chain, masking the input to the next chain.
96 Also outputted (optional): an index for each picked "thing".
98 def __init__(self
, wid
, levels
, indices
=False, multiin
=False):
101 self
.indices
= indices
102 self
.multiin
= multiin
106 # multiple inputs, multiple outputs.
107 i_l
= [] # array of picker outputs
108 for j
in range(self
.levels
):
109 i
= Signal(self
.wid
, name
="i_%d" % j
, reset_less
=True)
113 # only the one input, but multiple (single) bit outputs
114 self
.i
= Signal(self
.wid
, reset_less
=True)
116 # create array of (single-bit) outputs (unary)
117 o_l
= [] # array of picker outputs
118 for j
in range(self
.levels
):
119 o
= Signal(self
.wid
, name
="o_%d" % j
, reset_less
=True)
123 # add an array of "enables"
124 self
.en_o
= Signal(self
.levels
, name
="en_o", reset_less
=True)
129 # add an array of indices
130 lidx
= math
.ceil(math
.log2(self
.levels
))
131 idx_o
= [] # store the array of indices
132 for j
in range(self
.levels
):
133 i
= Signal(lidx
, name
="idxo_%d" % j
, reset_less
=True)
135 self
.idx_o
= Array(idx_o
)
137 def elaborate(self
, platform
):
141 # create Priority Pickers, accumulate their outputs and prevent
142 # the next one in the chain from selecting that output bit.
143 # the input from the current picker will be "masked" and connected
144 # to the *next* picker on the next loop
148 for j
in range(self
.levels
):
154 pp
= PriorityPicker(self
.wid
)
156 setattr(m
.submodules
, "pp%d" % j
, pp
)
160 p_mask
= Const(0, self
.wid
)
162 mask
= Signal(self
.wid
, name
="m_%d" % j
, reset_less
=True)
163 comb
+= mask
.eq(prev_pp
.o | p_mask
) # accumulate output bits
164 comb
+= pp
.i
.eq(i
& ~mask
) # mask out input
166 i
= pp
.i
# for input to next round
169 # accumulate the enables
171 for j
in range(self
.levels
):
172 en_l
.append(pp_l
[j
].en_o
)
173 # concat accumulated enable bits
174 comb
+= self
.en_o
.eq(Cat(*en_l
))
179 # for each picker enabled, pass that out and set a cascading index
180 lidx
= math
.ceil(math
.log2(self
.levels
))
182 for j
in range(self
.levels
):
184 if prev_count
is None:
185 comb
+= self
.idx_o
[j
].eq(0)
187 count1
= Signal(lidx
, name
="count_%d" % j
, reset_less
=True)
188 comb
+= count1
.eq(prev_count
+ Const(1, lidx
))
189 comb
+= self
.idx_o
[j
].eq(Mux(en_o
, count1
, prev_count
))
190 prev_count
= self
.idx_o
[j
]
203 yield from self
.idx_o
209 if __name__
== '__main__':
210 dut
= PriorityPicker(16)
211 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
212 with
open("test_picker.il", "w") as f
:
214 dut
= MultiPriorityPicker(5, 4, True)
215 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
216 with
open("test_multi_picker.il", "w") as f
:
218 dut
= MultiPriorityPicker(5, 4, False, True)
219 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
220 with
open("test_multi_picker_noidx.il", "w") as f
: