1 # based on ariane plru, from tlb.sv
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
10 class PLRU(Elaboratable
):
11 """ PLRU - Pseudo Least Recently Used Replacement
24 def __init__(self
, BITS
):
26 self
.acc_i
= Signal(BITS
)
27 self
.acc_en
= Signal()
28 self
.lru_o
= Signal(BITS
)
30 def elaborate(self
, platform
=None):
33 # Tree (bit per entry)
34 TLBSZ
= 2*(self
.BITS
-1)
35 plru_tree
= Signal(TLBSZ
)
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:
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
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
)
56 for i
in range(self
.BITS
):
57 # we got a hit so update the pointer as it was least recently used
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, ...
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
)
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.
85 for i
in range(self
.BITS
):
87 for lvl
in range(LOG_TLB
):
88 idx_base
= (1 << lvl
)-1
89 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
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
])
98 en
.append(~plru
) # yes inverted (using bool() below)
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
))
110 return [self
.acc_en
, self
.lru_o
, self
.acc_i
]
113 class PLRUs(Elaboratable
):
114 def __init__(self
, n_plrus
, n_bits
):
115 self
.n_plrus
= n_plrus
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
)
123 def elaborate(self
, platform
):
124 """Generate TLB PLRUs
129 if self
.n_plrus
== 0:
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
)
137 out
= Array(Signal(self
.n_bits
, name
="plru_out%d" % x
) \
138 for x
in range(self
.n_plrus
))
140 for i
in range(self
.n_plrus
):
142 m
.submodules
["plru_%d" % i
] = plru
= PLRU(self
.n_bits
)
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
)
148 # select output based on index
149 comb
+= self
.o_index
.eq(out
[self
.isel
])
154 return [self
.valid
, self
.way
, self
.index
, self
.isel
, self
.o_index
]
157 if __name__
== '__main__':
159 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
160 with
open("test_plru.il", "w") as f
:
165 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
166 with
open("test_plrus.il", "w") as f
: