src/nmutil/plru.py

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