src/nmutil/plru.py

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