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
  40     def __init__(self, wid, lsb_mode=False, reverse_i=False, reverse_o=False):
  41         self.wid = wid
  42         # inputs
  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
  49
  50     def elaborate(self, platform):
  51         m = Module()
  52
  53         # works by saying, "if all previous bits were zero, we get a chance"
  54         res = []
  55         ni = Signal(self.wid, reset_less=True)
  56         i = list(self.i)
  57         if self.reverse_i:
  58             i.reverse()
  59         m.d.comb += ni.eq(~Cat(*i))
  60         prange = list(range(0, self.wid))
  61         if self.lsb_mode:
  62             prange.reverse()
  63         for n in prange:
  64             t = Signal(name="t%d" % n, reset_less=True)
  65             res.append(t)
  66             if n == 0:
  67                 m.d.comb += t.eq(i[n])
  68             else:
  69                 m.d.comb += t.eq(~Cat(ni[n], *i[:n]).bool())
  70         if self.reverse_o:
  71             res.reverse()
  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
  76
  77         return m
  78
  79     def __iter__(self):
  80         yield self.i
  81         yield self.o
  82         yield self.en_o
  83
  84     def ports(self):
  85         return list(self)
  86
  87
  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
  91
  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.
  96
  97         Also outputted (optional): an index for each picked "thing".
  98     """
  99
 100     def __init__(self, wid, levels, indices=False, multiin=False):
 101         self.levels = levels
 102         self.wid = wid
 103         self.indices = indices
 104         self.multiin = multiin
 105
 106         if 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)
 111                 i_l.append(i)
 112             self.i = Array(i_l)
 113         else:
 114             # only the one input, but multiple (single) bit outputs
 115             self.i = Signal(self.wid, reset_less=True)
 116
 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)
 121             o_l.append(o)
 122         self.o = Array(o_l)
 123
 124         # add an array of "enables"
 125         self.en_o = Signal(self.levels, name="en_o", reset_less=True)
 126
 127         if not self.indices:
 128             return
 129
 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)
 135             idx_o.append(i)
 136         self.idx_o = Array(idx_o)
 137
 138     def elaborate(self, platform):
 139         m = Module()
 140         comb = m.d.comb
 141
 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
 146         prev_pp = None
 147         p_mask = None
 148         pp_l = []
 149         for j in range(self.levels):
 150             if self.multiin:
 151                 i = self.i[j]
 152             else:
 153                 i = self.i
 154             o = self.o[j]
 155             pp = PriorityPicker(self.wid)
 156             pp_l.append(pp)
 157             setattr(m.submodules, "pp%d" % j, pp)
 158             comb += o.eq(pp.o)
 159             if prev_pp is None:
 160                 comb += pp.i.eq(i)
 161                 p_mask = Const(0, self.wid)
 162             else:
 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
 166                 p_mask = mask
 167             i = pp.i  # for input to next round
 168             prev_pp = pp
 169
 170         # accumulate the enables
 171         en_l = []
 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))
 176
 177         if not self.indices:
 178             return m
 179
 180         # for each picker enabled, pass that out and set a cascading index
 181         lidx = math.ceil(math.log2(self.levels))
 182         prev_count = None
 183         for j in range(self.levels):
 184             en_o = pp_l[j].en_o
 185             if prev_count is None:
 186                 comb += self.idx_o[j].eq(0)
 187             else:
 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]
 192
 193         return m
 194
 195     def __iter__(self):
 196         if self.multiin:
 197             yield from self.i
 198         else:
 199             yield self.i
 200         yield from self.o
 201         if not self.indices:
 202             return
 203         yield self.en_o
 204         yield from self.idx_o
 205
 206     def ports(self):
 207         return list(self)
 208
 209
 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:
 214         f.write(vl)
 215     dut = MultiPriorityPicker(5, 4, True)
 216     vl = rtlil.convert(dut, ports=dut.ports())
 217     with open("test_multi_picker.il", "w") as f:
 218         f.write(vl)
 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:
 222         f.write(vl)