src/unused/TLB/ariane/plru.py

   1 from nmigen import Signal, Module, Cat, Const
   2 from nmigen.hdl.ir import Elaboratable
   3 from math import log2
   4
   5
   6 class PLRU(Elaboratable):
   7     """ PLRU - Pseudo Least Recently Used Replacement
   8
   9         PLRU-tree indexing:
  10         lvl0        0
  11                    / \
  12                   /   \
  13         lvl1     1     2
  14                 / \   / \
  15         lvl2   3   4 5   6
  16               / \ /\/\  /\
  17              ... ... ... ...
  18     """
  19
  20     def __init__(self, entries):
  21         self.entries = entries
  22         self.lu_hit = Signal(entries)
  23         self.replace_en_o = Signal(entries)
  24         self.lu_access_i = Signal()
  25         # Tree (bit per entry)
  26         self.TLBSZ = 2*(self.entries-1)
  27         self.plru_tree = Signal(self.TLBSZ)
  28         self.plru_tree_o = Signal(self.TLBSZ)
  29
  30     def elaborate(self, platform=None):
  31         m = Module()
  32
  33         # Just predefine which nodes will be set/cleared
  34         # E.g. for a TLB with 8 entries, the for-loop is semantically
  35         # equivalent to the following pseudo-code:
  36         # unique case (1'b1)
  37         # lu_hit[7]: plru_tree[0, 2, 6] = {1, 1, 1};
  38         # lu_hit[6]: plru_tree[0, 2, 6] = {1, 1, 0};
  39         # lu_hit[5]: plru_tree[0, 2, 5] = {1, 0, 1};
  40         # lu_hit[4]: plru_tree[0, 2, 5] = {1, 0, 0};
  41         # lu_hit[3]: plru_tree[0, 1, 4] = {0, 1, 1};
  42         # lu_hit[2]: plru_tree[0, 1, 4] = {0, 1, 0};
  43         # lu_hit[1]: plru_tree[0, 1, 3] = {0, 0, 1};
  44         # lu_hit[0]: plru_tree[0, 1, 3] = {0, 0, 0};
  45         # default: begin /* No hit */ end
  46         # endcase
  47         LOG_TLB = int(log2(self.entries))
  48         print(LOG_TLB)
  49         for i in range(self.entries):
  50             # we got a hit so update the pointer as it was least recently used
  51             hit = Signal(reset_less=True)
  52             m.d.comb += hit.eq(self.lu_hit[i] & self.lu_access_i)
  53             with m.If(hit):
  54                 # Set the nodes to the values we would expect
  55                 for lvl in range(LOG_TLB):
  56                     idx_base = (1 << lvl)-1
  57                     # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
  58                     shift = LOG_TLB - lvl
  59                     new_idx = Const(~((i >> (shift-1)) & 1), (1, False))
  60                     plru_idx = idx_base + (i >> shift)
  61                     print("plru", i, lvl, hex(idx_base),
  62                           plru_idx, shift, new_idx)
  63                     m.d.comb += self.plru_tree_o[plru_idx].eq(new_idx)
  64
  65         # Decode tree to write enable signals
  66         # Next for-loop basically creates the following logic for e.g.
  67         # an 8 entry TLB (note: pseudo-code obviously):
  68         # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
  69         # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
  70         # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
  71         # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
  72         # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
  73         # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
  74         # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
  75         # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
  76         # For each entry traverse the tree. If every tree-node matches
  77         # the corresponding bit of the entry's index, this is
  78         # the next entry to replace.
  79         replace = []
  80         for i in range(self.entries):
  81             en = []
  82             for lvl in range(LOG_TLB):
  83                 idx_base = (1 << lvl)-1
  84                 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
  85                 shift = LOG_TLB - lvl
  86                 new_idx = (i >> (shift-1)) & 1
  87                 plru_idx = idx_base + (i >> shift)
  88                 plru = Signal(reset_less=True,
  89                               name="plru-%d-%d-%d" % (i, lvl, plru_idx))
  90                 m.d.comb += plru.eq(self.plru_tree[plru_idx])
  91                 # en &= plru_tree_q[idx_base + (i>>shift)] == new_idx;
  92                 if new_idx:
  93                     en.append(~plru)  # yes inverted (using bool())
  94                 else:
  95                     en.append(plru)  # yes inverted (using bool())
  96             print("plru", i, en)
  97             # boolean logic manipulation:
  98             # plru0 & plru1 & plru2 == ~(~plru0 | ~plru1 | ~plru2)
  99             replace.append(~Cat(*en).bool())
 100         m.d.comb += self.replace_en_o.eq(Cat(*replace))
 101
 102         return m
 103
 104     def ports(self):
 105         return [self.entries, self.lu_hit, self.replace_en_o,
 106                 self.lu_access_i, self.plru_tree, self.plru_tree_o]