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