src/nmutil/picker.py

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