src/nmutil/picker.py

   1 """ Priority Picker: optimised back-to-back PriorityEncoder and Decoder
   2     and MultiPriorityPicker: cascading mutually-exclusive pickers
   3
   4     PriorityPicker: the input is N bits, the output is N bits wide and
   5     only one is enabled.
   6
   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.
  10
  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.
  16
  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.
  20 """
  21
  22 from nmigen import Module, Signal, Cat, Elaboratable, Array, Const, Mux
  23 from nmigen.cli import verilog, rtlil
  24 import math
  25
  26
  27 class PriorityPicker(Elaboratable):
  28     """ implements a priority-picker.  input: N bits, output: N bits
  29
  30         * lsb_mode is for a LSB-priority picker
  31         * reverse_i=True is for convenient reverseal of the input bits
  32         * reverse_o=True is for convenient reversal of the output bits
  33     """
  34     def __init__(self, wid, lsb_mode=False, reverse_i=False, reverse_o=False):
  35         self.wid = wid
  36         # inputs
  37         self.lsb_mode = lsb_mode
  38         self.reverse_i = reverse_i
  39         self.reverse_o = reverse_o
  40         self.i = Signal(wid, reset_less=True)
  41         self.o = Signal(wid, reset_less=True)
  42         self.en_o = Signal(reset_less=True) # true if any output is true
  43
  44     def elaborate(self, platform):
  45         m = Module()
  46
  47         # works by saying, "if all previous bits were zero, we get a chance"
  48         res = []
  49         ni = Signal(self.wid, reset_less = True)
  50         i = list(self.i)
  51         if self.reverse_i:
  52             i.reverse()
  53         m.d.comb += ni.eq(~Cat(*i))
  54         prange = list(range(0, self.wid))
  55         if self.lsb_mode:
  56             prange.reverse()
  57         for n in prange:
  58             t = Signal(name="t%d" % n, reset_less = True)
  59             res.append(t)
  60             if n == 0:
  61                 m.d.comb += t.eq(i[n])
  62             else:
  63                 m.d.comb += t.eq(~Cat(ni[n], *i[:n]).bool())
  64         if self.reverse_o:
  65             res.reverse()
  66         # we like Cat(*xxx).  turn lists into concatenated bits
  67         m.d.comb += self.o.eq(Cat(*res))
  68         # useful "is any output enabled" signal
  69         m.d.comb += self.en_o.eq(self.o.bool()) # true if 1 input is true
  70
  71         return m
  72
  73     def __iter__(self):
  74         yield self.i
  75         yield self.o
  76         yield self.en_o
  77
  78     def ports(self):
  79         return list(self)
  80
  81
  82 class MultiPriorityPicker(Elaboratable):
  83     """ implements a multi-input priority picker
  84         Mx inputs of N bits, Mx outputs of N bits, only one is set
  85
  86         Each picker masks out the one below it, such that the first
  87         gets top priority, the second cannot have the same bit that
  88         the first has set, and so on.  To do this, a "mask" accumulates
  89         the output from the chain, masking the input to the next chain.
  90
  91         Also outputted (optional): an index for each picked "thing".
  92     """
  93     def __init__(self, wid, levels, indices=False, multiin=False):
  94         self.levels = levels
  95         self.wid = wid
  96         self.indices = indices
  97         self.multiin = multiin
  98
  99
 100         if multiin:
 101             # multiple inputs, multiple outputs.
 102             i_l = [] # array of picker outputs
 103             for j in range(self.levels):
 104                 i = Signal(self.wid, name="i_%d" % j, reset_less=True)
 105                 i_l.append(i)
 106             self.i = Array(i_l)
 107         else:
 108             # only the one input, but multiple (single) bit outputs
 109             self.i = Signal(self.wid, reset_less=True)
 110
 111         # create array of (single-bit) outputs (unary)
 112         o_l = [] # array of picker outputs
 113         for j in range(self.levels):
 114             o = Signal(self.wid, name="o_%d" % j, reset_less=True)
 115             o_l.append(o)
 116         self.o = Array(o_l)
 117
 118         # add an array of "enables"
 119         self.en_o = Signal(self.levels, name="en_o", reset_less=True)
 120
 121         if not self.indices:
 122             return
 123
 124         # add an array of indices
 125         lidx = math.ceil(math.log2(self.levels))
 126         idx_o = [] # store the array of indices
 127         for j in range(self.levels):
 128             i = Signal(lidx, name="idxo_%d" % j, reset_less=True)
 129             idx_o.append(i)
 130         self.idx_o = Array(idx_o)
 131
 132     def elaborate(self, platform):
 133         m = Module()
 134         comb = m.d.comb
 135
 136         # create Priority Pickers, accumulate their outputs and prevent
 137         # the next one in the chain from selecting that output bit.
 138         # the input from the current picker will be "masked" and connected
 139         # to the *next* picker on the next loop
 140         prev_pp = None
 141         p_mask = None
 142         pp_l = []
 143         for j in range(self.levels):
 144             if self.multiin:
 145                 i = self.i[j]
 146             else:
 147                 i = self.i
 148             o = self.o[j]
 149             pp = PriorityPicker(self.wid)
 150             pp_l.append(pp)
 151             setattr(m.submodules, "pp%d" % j, pp)
 152             comb += o.eq(pp.o)
 153             if prev_pp is None:
 154                 comb += pp.i.eq(i)
 155                 p_mask = Const(0, self.wid)
 156             else:
 157                 mask = Signal(self.wid, name="m_%d" % j, reset_less=True)
 158                 comb += mask.eq(prev_pp.o | p_mask) # accumulate output bits
 159                 comb += pp.i.eq(i & ~mask)          # mask out input
 160                 p_mask = mask
 161             i = pp.i # for input to next round
 162             prev_pp = pp
 163
 164         # accumulate the enables
 165         en_l = []
 166         for j in range(self.levels):
 167             en_l.append(pp_l[j].en_o)
 168         # concat accumulated enable bits
 169         comb += self.en_o.eq(Cat(*en_l))
 170
 171         if not self.indices:
 172             return m
 173
 174         # for each picker enabled, pass that out and set a cascading index
 175         lidx = math.ceil(math.log2(self.levels))
 176         prev_count = None
 177         for j in range(self.levels):
 178             en_o = pp_l[j].en_o
 179             if prev_count is None:
 180                 comb += self.idx_o[j].eq(0)
 181             else:
 182                 count1 = Signal(lidx, name="count_%d" % j, reset_less=True)
 183                 comb += count1.eq(prev_count + Const(1, lidx))
 184                 comb += self.idx_o[j].eq(Mux(en_o, count1, prev_count))
 185             prev_count = self.idx_o[j]
 186
 187         return m
 188
 189     def __iter__(self):
 190         if self.multiin:
 191             yield from self.i
 192         else:
 193             yield self.i
 194         yield from self.o
 195         if not self.indices:
 196             return
 197         yield self.en_o
 198         yield from self.idx_o
 199
 200     def ports(self):
 201         return list(self)
 202
 203
 204 if __name__ == '__main__':
 205     dut = PriorityPicker(16)
 206     vl = rtlil.convert(dut, ports=dut.ports())
 207     with open("test_picker.il", "w") as f:
 208         f.write(vl)
 209     dut = MultiPriorityPicker(5, 4, True)
 210     vl = rtlil.convert(dut, ports=dut.ports())
 211     with open("test_multi_picker.il", "w") as f:
 212         f.write(vl)
 213     dut = MultiPriorityPicker(5, 4, False, True)
 214     vl = rtlil.convert(dut, ports=dut.ports())
 215     with open("test_multi_picker_noidx.il", "w") as f:
 216         f.write(vl)