src/nmutil/picker.py

   1 """ Priority Picker: optimised back-to-back PriorityEncoder and Decoder
   2     and MultiPriorityPicker: cascading mutually-exclusive pickers
   3
   4     This work is funded through NLnet under Grant 2019-02-012
   5
   6     License: LGPLv3+
   7
   8
   9     PriorityPicker: the input is N bits, the output is N bits wide and
  10     only one is enabled.
  11
  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.
  15
  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.
  21
  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.
  25 """
  26
  27 from nmigen import Module, Signal, Cat, Elaboratable, Array, Const, Mux
  28 from nmigen.cli import verilog, rtlil
  29 import math
  30
  31
  32 class PriorityPicker(Elaboratable):
  33     """ implements a priority-picker.  input: N bits, output: N bits
  34
  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
  38     """
  39     def __init__(self, wid, lsb_mode=False, reverse_i=False, reverse_o=False):
  40         self.wid = wid
  41         # inputs
  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
  48
  49     def elaborate(self, platform):
  50         m = Module()
  51
  52         # works by saying, "if all previous bits were zero, we get a chance"
  53         res = []
  54         ni = Signal(self.wid, reset_less = True)
  55         i = list(self.i)
  56         if self.reverse_i:
  57             i.reverse()
  58         m.d.comb += ni.eq(~Cat(*i))
  59         prange = list(range(0, self.wid))
  60         if self.lsb_mode:
  61             prange.reverse()
  62         for n in prange:
  63             t = Signal(name="t%d" % n, reset_less = True)
  64             res.append(t)
  65             if n == 0:
  66                 m.d.comb += t.eq(i[n])
  67             else:
  68                 m.d.comb += t.eq(~Cat(ni[n], *i[:n]).bool())
  69         if self.reverse_o:
  70             res.reverse()
  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
  75
  76         return m
  77
  78     def __iter__(self):
  79         yield self.i
  80         yield self.o
  81         yield self.en_o
  82
  83     def ports(self):
  84         return list(self)
  85
  86
  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
  90
  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.
  95
  96         Also outputted (optional): an index for each picked "thing".
  97     """
  98     def __init__(self, wid, levels, indices=False, multiin=False):
  99         self.levels = levels
 100         self.wid = wid
 101         self.indices = indices
 102         self.multiin = multiin
 103
 104
 105         if 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)
 110                 i_l.append(i)
 111             self.i = Array(i_l)
 112         else:
 113             # only the one input, but multiple (single) bit outputs
 114             self.i = Signal(self.wid, reset_less=True)
 115
 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)
 120             o_l.append(o)
 121         self.o = Array(o_l)
 122
 123         # add an array of "enables"
 124         self.en_o = Signal(self.levels, name="en_o", reset_less=True)
 125
 126         if not self.indices:
 127             return
 128
 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)
 134             idx_o.append(i)
 135         self.idx_o = Array(idx_o)
 136
 137     def elaborate(self, platform):
 138         m = Module()
 139         comb = m.d.comb
 140
 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
 145         prev_pp = None
 146         p_mask = None
 147         pp_l = []
 148         for j in range(self.levels):
 149             if self.multiin:
 150                 i = self.i[j]
 151             else:
 152                 i = self.i
 153             o = self.o[j]
 154             pp = PriorityPicker(self.wid)
 155             pp_l.append(pp)
 156             setattr(m.submodules, "pp%d" % j, pp)
 157             comb += o.eq(pp.o)
 158             if prev_pp is None:
 159                 comb += pp.i.eq(i)
 160                 p_mask = Const(0, self.wid)
 161             else:
 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
 165                 p_mask = mask
 166             i = pp.i # for input to next round
 167             prev_pp = pp
 168
 169         # accumulate the enables
 170         en_l = []
 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))
 175
 176         if not self.indices:
 177             return m
 178
 179         # for each picker enabled, pass that out and set a cascading index
 180         lidx = math.ceil(math.log2(self.levels))
 181         prev_count = None
 182         for j in range(self.levels):
 183             en_o = pp_l[j].en_o
 184             if prev_count is None:
 185                 comb += self.idx_o[j].eq(0)
 186             else:
 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]
 191
 192         return m
 193
 194     def __iter__(self):
 195         if self.multiin:
 196             yield from self.i
 197         else:
 198             yield self.i
 199         yield from self.o
 200         if not self.indices:
 201             return
 202         yield self.en_o
 203         yield from self.idx_o
 204
 205     def ports(self):
 206         return list(self)
 207
 208
 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:
 213         f.write(vl)
 214     dut = MultiPriorityPicker(5, 4, True)
 215     vl = rtlil.convert(dut, ports=dut.ports())
 216     with open("test_multi_picker.il", "w") as f:
 217         f.write(vl)
 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:
 221         f.write(vl)