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