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