src/nmutil/plru2.py

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