1 """ Priority Picker: optimised back-to-back PriorityEncoder and Decoder
2 and MultiPriorityPicker: cascading mutually-exclusive pickers
4 PriorityPicker: the input is N bits, the output is N bits wide and
7 MultiPriorityPicker: likewise except that there are M pickers and
8 each output is guaranteed mutually exclusive. Optionally:
9 an "index" (and enable line) is also outputted.
11 MultiPriorityPicker is designed for port-selection, when there are
12 multiple "things" (of width N) contending for access to M "ports".
13 When the M=0 "thing" requests a port, it gets allocated port 0
14 (always). However if the M=0 "thing" does *not* request a port,
15 this gives the M=1 "thing" the opportunity to gain access to port 0.
17 Given that N may potentially be much greater than M (16 bits wide
18 where M may be e.g. only 4) we can't just ok, "ok so M=N therefore
19 M=0 gets access to port 0, M=1 gets access to port 1" etc.
22 from nmigen
import Module
, Signal
, Cat
, Elaboratable
, Array
, Const
, Mux
23 from nmigen
.cli
import verilog
, rtlil
26 class PriorityPicker(Elaboratable
):
27 """ implements a priority-picker. input: N bits, output: N bits
29 def __init__(self
, wid
):
32 self
.i
= Signal(wid
, reset_less
=True)
33 self
.o
= Signal(wid
, reset_less
=True)
34 self
.en_o
= Signal(reset_less
=True) # true if any output is true
36 def elaborate(self
, platform
):
39 # works by saying, "if all previous bits were zero, we get a chance"
41 ni
= Signal(self
.wid
, reset_less
= True)
42 m
.d
.comb
+= ni
.eq(~self
.i
)
43 for i
in range(0, self
.wid
):
44 t
= Signal(name
="t%d" % i
, reset_less
= True)
47 m
.d
.comb
+= t
.eq(self
.i
[i
])
49 m
.d
.comb
+= t
.eq(~
Cat(ni
[i
], *self
.i
[:i
]).bool())
51 # we like Cat(*xxx). turn lists into concatenated bits
52 m
.d
.comb
+= self
.o
.eq(Cat(*res
))
53 # useful "is any output enabled" signal
54 m
.d
.comb
+= self
.en_o
.eq(self
.o
.bool()) # true if 1 input is true
66 class MultiPriorityPicker(Elaboratable
):
67 """ implements a multi-input priority picker
68 Mx inputs of N bits, Mx outputs of N bits, only one is set
70 Each picker masks out the one below it, such that the first
71 gets top priority, the second cannot have the same bit that
72 the first has set, and so on. To do this, a "mask" accumulates
73 the output from the chain, masking the input to the next chain.
75 Also outputted (optional): an index for each picked "thing".
77 def __init__(self
, wid
, levels
, indices
=False):
80 self
.indices
= indices
82 # only the one input, but multiple (single) bit outputs
83 self
.i
= Signal(self
.wid
, reset_less
=True)
85 # create array of (single-bit) outputs (unary)
86 o_l
= [] # array of picker outputs
87 for j
in range(self
.levels
):
88 o
= Signal(self
.wid
, name
="o_%d" % j
, reset_less
=True)
95 # add an array of "enables" and indices
96 self
.en_o
= Signal(self
.levels
, name
="en_o", reset_less
=True)
97 lidx
= math
.ceil(math
.log2(self
.levels
))
98 idx_o
= [] # store the array of indices
99 for j
in range(self
.levels
):
100 i
= Signal(lidx
, name
="idxo_%d" % j
, reset_less
=True)
102 self
.idx_o
= Array(idx_o
)
104 def elaborate(self
, platform
):
108 # create Priority Pickers, accumulate their outputs and prevent
109 # the next one in the chain from selecting that output bit.
110 # the input from the current picker will be "masked" and connected
111 # to the *next* picker on the next loop
116 for j
in range(self
.levels
):
118 pp
= PriorityPicker(self
.wid
)
120 setattr(m
.submodules
, "pp%d" % j
, pp
)
124 p_mask
= Const(0, self
.wid
)
126 mask
= Signal(self
.wid
, name
="m_%d" % j
, reset_less
=True)
127 comb
+= mask
.eq(prev_pp
.o | p_mask
) # accumulate output bits
128 comb
+= pp
.i
.eq(i
& ~mask
) # mask out input
130 i
= pp
.i
# for input to next round
136 # for each picker enabled, pass that out and set a cascading index
137 lidx
= math
.ceil(math
.log2(self
.levels
))
140 for j
in range(self
.levels
):
143 if prev_count
is None:
144 comb
+= self
.idx_o
[j
].eq(0)
146 count1
= Signal(lidx
, name
="count_%d" % j
, reset_less
=True)
147 comb
+= count1
.eq(prev_count
+ Const(1, lidx
))
148 comb
+= self
.idx_o
[j
].eq(Mux(en_o
, count1
, prev_count
))
149 prev_count
= self
.idx_o
[j
]
151 # concat accumulated enable bits
152 comb
+= self
.en_o
.eq(Cat(*en_o
))
162 yield from self
.idx_o
168 if __name__
== '__main__':
169 dut
= MultiPriorityPicker(5, 4, True)
170 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
171 with
open("test_multi_picker.il", "w") as f
: