src/nmutil/plru.py

   1 # based on ariane plru, from tlb.sv
   2
   3 # old PLRU API, once all users have migrated to new API in plru2.py, then
   4 # plru2.py will be renamed to plru.py, replacing this file.
   5
   6 from nmigen import Signal, Module, Cat, Const, Repl, Array
   7 from nmigen.hdl.ir import Elaboratable
   8 from nmigen.cli import rtlil
   9 from nmigen.utils import log2_int
  10 from nmigen.lib.coding import Decoder
  11 from warnings import warn
  12
  13
  14 class PLRU(Elaboratable):
  15     r""" PLRU - Pseudo Least Recently Used Replacement
  16
  17         PLRU-tree indexing:
  18         lvl0        0
  19                    / \
  20                   /   \
  21         lvl1     1     2
  22                 / \   / \
  23         lvl2   3   4 5   6
  24               / \ /\/\  /\
  25              ... ... ... ...
  26     """
  27
  28     def __init__(self, BITS):
  29         warn("nmutil.plru.PLRU is deprecated due to having a broken API, use "
  30              "nmutil.plru2.PLRU instead", DeprecationWarning, stacklevel=2)
  31         self.BITS = BITS
  32         self.acc_i = Signal(BITS)
  33         self.acc_en = Signal()
  34         self.lru_o = Signal(BITS)
  35
  36         self._plru_tree = Signal(self.TLBSZ)
  37         """ exposed only for testing """
  38
  39     @property
  40     def TLBSZ(self):
  41         return 2 * (self.BITS - 1)
  42
  43     def elaborate(self, platform=None):
  44         m = Module()
  45
  46         # Tree (bit per entry)
  47
  48         # Just predefine which nodes will be set/cleared
  49         # E.g. for a TLB with 8 entries, the for-loop is semantically
  50         # equivalent to the following pseudo-code:
  51         # unique case (1'b1)
  52         # acc_en[7]: plru_tree[0, 2, 6] = {1, 1, 1};
  53         # acc_en[6]: plru_tree[0, 2, 6] = {1, 1, 0};
  54         # acc_en[5]: plru_tree[0, 2, 5] = {1, 0, 1};
  55         # acc_en[4]: plru_tree[0, 2, 5] = {1, 0, 0};
  56         # acc_en[3]: plru_tree[0, 1, 4] = {0, 1, 1};
  57         # acc_en[2]: plru_tree[0, 1, 4] = {0, 1, 0};
  58         # acc_en[1]: plru_tree[0, 1, 3] = {0, 0, 1};
  59         # acc_en[0]: plru_tree[0, 1, 3] = {0, 0, 0};
  60         # default: begin /* No hit */ end
  61         # endcase
  62
  63         LOG_TLB = log2_int(self.BITS, False)
  64         hit = Signal(self.BITS, reset_less=True)
  65         m.d.comb += hit.eq(Repl(self.acc_en, self.BITS) & self.acc_i)
  66
  67         for i in range(self.BITS):
  68             # we got a hit so update the pointer as it was least recently used
  69             with m.If(hit[i]):
  70                 # Set the nodes to the values we would expect
  71                 for lvl in range(LOG_TLB):
  72                     idx_base = (1 << lvl)-1
  73                     # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
  74                     shift = LOG_TLB - lvl
  75                     new_idx = Const(~((i >> (shift-1)) & 1), 1)
  76                     plru_idx = idx_base + (i >> shift)
  77                     # print("plru", i, lvl, hex(idx_base),
  78                     #      plru_idx, shift, new_idx)
  79                     m.d.sync += self._plru_tree[plru_idx].eq(new_idx)
  80
  81         # Decode tree to write enable signals
  82         # Next for-loop basically creates the following logic for e.g.
  83         # an 8 entry TLB (note: pseudo-code obviously):
  84         # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
  85         # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
  86         # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
  87         # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
  88         # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
  89         # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
  90         # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
  91         # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
  92         # For each entry traverse the tree. If every tree-node matches
  93         # the corresponding bit of the entry's index, this is
  94         # the next entry to replace.
  95         replace = []
  96         for i in range(self.BITS):
  97             en = []
  98             for lvl in range(LOG_TLB):
  99                 idx_base = (1 << lvl)-1
 100                 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 101                 shift = LOG_TLB - lvl
 102                 new_idx = (i >> (shift-1)) & 1
 103                 plru_idx = idx_base + (i >> shift)
 104                 plru = Signal(reset_less=True,
 105                               name="plru-%d-%d-%d-%d" %
 106                               (i, lvl, plru_idx, new_idx))
 107                 m.d.comb += plru.eq(self._plru_tree[plru_idx])
 108                 if new_idx:
 109                     en.append(~plru)  # yes inverted (using bool() below)
 110                 else:
 111                     en.append(plru)  # yes inverted (using bool() below)
 112             #print("plru", i, en)
 113             # boolean logic manipulation:
 114             # plru0 & plru1 & plru2 == ~(~plru0 | ~plru1 | ~plru2)
 115             replace.append(~Cat(*en).bool())
 116         m.d.comb += self.lru_o.eq(Cat(*replace))
 117
 118         return m
 119
 120     def ports(self):
 121         return [self.acc_en, self.lru_o, self.acc_i]
 122
 123
 124 class PLRUs(Elaboratable):
 125     def __init__(self, n_plrus, n_bits):
 126         warn("nmutil.plru.PLRUs is deprecated due to having a broken API, use "
 127              "nmutil.plru2.PLRUs instead", DeprecationWarning, stacklevel=2)
 128         self.n_plrus = n_plrus
 129         self.n_bits = n_bits
 130         self.valid = Signal()
 131         self.way = Signal(n_bits)
 132         self.index = Signal(n_plrus.bit_length())
 133         self.isel = Signal(n_plrus.bit_length())
 134         self.o_index = Signal(n_bits)
 135
 136     def elaborate(self, platform):
 137         """Generate TLB PLRUs
 138         """
 139         m = Module()
 140         comb = m.d.comb
 141
 142         if self.n_plrus == 0:
 143             return m
 144
 145         # Binary-to-Unary one-hot, enabled by valid
 146         m.submodules.te = te = Decoder(self.n_plrus)
 147         comb += te.n.eq(~self.valid)
 148         comb += te.i.eq(self.index)
 149
 150         out = Array(Signal(self.n_bits, name="plru_out%d" % x)
 151                     for x in range(self.n_plrus))
 152
 153         for i in range(self.n_plrus):
 154             # PLRU interface
 155             m.submodules["plru_%d" % i] = plru = PLRU(self.n_bits)
 156
 157             comb += plru.acc_en.eq(te.o[i])
 158             comb += plru.acc_i.eq(self.way)
 159             comb += out[i].eq(plru.lru_o)
 160
 161         # select output based on index
 162         comb += self.o_index.eq(out[self.isel])
 163
 164         return m
 165
 166     def ports(self):
 167         return [self.valid, self.way, self.index, self.isel, self.o_index]
 168
 169
 170 if __name__ == '__main__':
 171     dut = PLRU(3)
 172     vl = rtlil.convert(dut, ports=dut.ports())
 173     with open("test_plru.il", "w") as f:
 174         f.write(vl)
 175
 176     dut = PLRUs(4, 2)
 177     vl = rtlil.convert(dut, ports=dut.ports())
 178     with open("test_plrus.il", "w") as f:
 179         f.write(vl)