3 Online simulator of 4-way set-associative cache:
4 http://www.ntu.edu.sg/home/smitha/ParaCache/Paracache/sa4.html
6 Python simulator of a N-way set-associative cache:
7 https://github.com/vaskevich/CacheSim/blob/master/cachesim.py
10 from nmigen
import Array
, Cat
, Memory
, Module
, Signal
, Mux
, Elaboratable
11 from nmigen
.compat
.genlib
import fsm
12 from nmigen
.cli
import main
13 from nmigen
.cli
import verilog
, rtlil
15 from .AddressEncoder
import AddressEncoder
16 from .MemorySet
import MemorySet
18 # TODO: use a LFSR that advances continuously and picking the bottom
19 # few bits from it to select which cache line to replace, instead of PLRU
20 # http://bugs.libre-riscv.org/show_bug.cgi?id=71
21 from .ariane
.plru
import PLRU
22 from .LFSR
import LFSR
, LFSR_POLY_24
24 SA_NA
= "00" # no action (none)
29 class SetAssociativeCache(Elaboratable
):
30 """ Set Associative Cache Memory
32 The purpose of this module is to generate a memory cache given the
33 constraints passed in. This will create a n-way set associative cache.
34 It is expected for the SV TLB that the VMA will provide the set number
35 while the ASID provides the tag (still to be decided).
39 def __init__(self
, tag_size
, data_size
, set_count
, way_count
, lfsr
=False):
41 * tag_size (bits): The bit count of the tag
42 * data_size (bits): The bit count of the data to be stored
43 * set_count (number): The number of sets/entries in the cache
44 * way_count (number): The number of slots a data can be stored
46 * lfsr: if set, use an LFSR for (pseudo-randomly) selecting
47 set/entry to write to. otherwise, use a PLRU
51 self
.way_count
= way_count
# The number of slots in one set
52 self
.tag_size
= tag_size
# The bit count of the tag
53 self
.data_size
= data_size
# The bit count of the data to be stored
56 self
.mem_array
= Array() # memory array
57 for i
in range(way_count
):
58 ms
= MemorySet(data_size
, tag_size
, set_count
, active
=0)
59 self
.mem_array
.append(ms
)
62 self
.encoder
= AddressEncoder(way_count
)
67 self
.lfsr
= LFSR(LFSR_POLY_24
)
70 # One block to handle plru calculations
71 self
.plru
= PLRU(way_count
)
72 self
.plru_array
= Array() # PLRU data on each set
73 for i
in range(set_count
):
75 self
.plru_array
.append(Signal(self
.plru
.TLBSZ
, name
=name
))
78 self
.enable
= Signal(1) # Whether the cache is enabled
79 self
.command
= Signal(2) # 00=None, 01=Read, 10=Write (see SA_XX)
80 self
.cset
= Signal(range(set_count
)) # The set to be checked
81 self
.tag
= Signal(tag_size
) # The tag to find
82 self
.data_i
= Signal(data_size
) # The input data
85 self
.ready
= Signal(1) # 0 => Processing 1 => Ready for commands
86 self
.hit
= Signal(1) # Tag matched one way in the given set
87 # Tag matched many ways in the given set
88 self
.multiple_hit
= Signal(1)
89 self
.data_o
= Signal(data_size
) # The data linked to the matched tag
91 def check_tags(self
, m
):
92 """ Validate the tags in the selected set. If one and only one
93 tag matches set its state to zero and increment all others
94 by one. We only advance to next state if a single hit is found.
96 # Vector to store way valid results
97 # A zero denotes a way is invalid
99 # Loop through memory to prep read/write ports and set valid_vector
100 for i
in range(self
.way_count
):
101 valid_vector
.append(self
.mem_array
[i
].valid
)
103 # Pass encoder the valid vector
104 m
.d
.comb
+= self
.encoder
.i
.eq(Cat(*valid_vector
))
106 # Only one entry should be marked
107 # This is due to already verifying the tags
108 # matched and the valid bit is high
110 m
.next
= "FINISHED_READ"
111 # Pull out data from the read port
112 data
= self
.mem_array
[self
.encoder
.o
].data_o
113 m
.d
.comb
+= self
.data_o
.eq(data
)
114 if not self
.lfsr_mode
:
117 # Oh no! Seal the gates! Multiple tags matched?!? kasd;ljkafdsj;k
118 with m
.Elif(self
.multiple_hit
):
119 # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
120 m
.d
.comb
+= self
.data_o
.eq(0)
122 # No tag matches means no data
124 # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
125 m
.d
.comb
+= self
.data_o
.eq(0)
127 def access_plru(self
, m
):
128 """ An entry was accessed and the plru tree must now be updated
130 # Pull out the set's entry being edited
131 plru_entry
= self
.plru_array
[self
.cset
]
133 # Set the plru data to the current state
134 self
.plru
.plru_tree
.eq(plru_entry
),
135 # Set that the cache was accessed
136 self
.plru
.lu_access_i
.eq(1)
140 """ Go through the read process of the cache.
141 This takes two cycles to complete. First it checks for a valid tag
142 and secondly it updates the LRU values.
144 with m
.FSM() as fsm_read
:
145 with m
.State("READY"):
146 m
.d
.comb
+= self
.ready
.eq(0)
147 # check_tags will set the state if the conditions are met
149 with m
.State("FINISHED_READ"):
151 m
.d
.comb
+= self
.ready
.eq(1)
152 if not self
.lfsr_mode
:
153 plru_tree_o
= self
.plru
.plru_tree_o
154 m
.d
.sync
+= self
.plru_array
[self
.cset
].eq(plru_tree_o
)
156 def write_entry(self
, m
):
157 if not self
.lfsr_mode
:
158 m
.d
.comb
+= [ # set cset (mem address) into PLRU
159 self
.plru
.plru_tree
.eq(self
.plru_array
[self
.cset
]),
160 # and connect plru to encoder for write
161 self
.encoder
.i
.eq(self
.plru
.replace_en_o
)
163 write_port
= self
.mem_array
[self
.encoder
.o
].w
165 # use the LFSR to generate a random(ish) one of the mem array
166 lfsr_output
= Signal(range(self
.way_count
))
167 lfsr_random
= Signal(range(self
.way_count
))
168 m
.d
.comb
+= lfsr_output
.eq(self
.lfsr
.state
) # lose some bits
169 # address too big, limit to range of array
170 m
.d
.comb
+= lfsr_random
.eq(Mux(lfsr_output
> self
.way_count
,
171 lfsr_output
- self
.way_count
,
173 write_port
= self
.mem_array
[lfsr_random
].w
175 # then if there is a match from the encoder, enable the selected write
176 with m
.If(self
.encoder
.single_match
):
177 m
.d
.comb
+= write_port
.en
.eq(1)
180 """ Go through the write process of the cache.
181 This takes two cycles to complete. First it writes the entry,
182 and secondly it updates the PLRU (in plru mode)
184 with m
.FSM() as fsm_write
:
185 with m
.State("READY"):
186 m
.d
.comb
+= self
.ready
.eq(0)
188 m
.next
= "FINISHED_WRITE"
189 with m
.State("FINISHED_WRITE"):
190 m
.d
.comb
+= self
.ready
.eq(1)
191 if not self
.lfsr_mode
:
192 plru_entry
= self
.plru_array
[self
.cset
]
193 m
.d
.sync
+= plru_entry
.eq(self
.plru
.plru_tree_o
)
196 def elaborate(self
, platform
=None):
200 # set up Modules: AddressEncoder, LFSR/PLRU, Mem Array
203 m
.submodules
.AddressEncoder
= self
.encoder
205 m
.submodules
.LFSR
= self
.lfsr
207 m
.submodules
.PLRU
= self
.plru
209 for i
, mem
in enumerate(self
.mem_array
):
210 setattr(m
.submodules
, "mem%d" % i
, mem
)
213 # select mode: PLRU connect to encoder, LFSR do... something
216 if not self
.lfsr_mode
:
217 # Set what entry was hit
218 m
.d
.comb
+= self
.plru
.lu_hit
.eq(self
.encoder
.o
)
221 m
.d
.comb
+= self
.lfsr
.enable
.eq(self
.enable
)
224 # connect hit/multiple hit to encoder output
228 self
.hit
.eq(self
.encoder
.single_match
),
229 self
.multiple_hit
.eq(self
.encoder
.multiple_match
),
233 # connect incoming data/tag/cset(addr) to mem_array
236 for mem
in self
.mem_array
:
238 m
.d
.comb
+= [mem
.cset
.eq(self
.cset
),
239 mem
.tag
.eq(self
.tag
),
240 mem
.data_i
.eq(self
.data_i
),
241 write_port
.en
.eq(0), # default: disable write
244 # Commands: READ/WRITE/TODO
247 with m
.If(self
.enable
):
248 with m
.Switch(self
.command
):
249 # Search all sets at a particular tag
254 # Maybe catch multiple tags write here?
256 # TODO: invalidate/flush, flush-all?
261 return [self
.enable
, self
.command
, self
.cset
, self
.tag
, self
.data_i
,
262 self
.ready
, self
.hit
, self
.multiple_hit
, self
.data_o
]
265 if __name__
== '__main__':
266 sac
= SetAssociativeCache(4, 8, 4, 6)
267 vl
= rtlil
.convert(sac
, ports
=sac
.ports())
268 with
open("SetAssociativeCache.il", "w") as f
:
271 sac_lfsr
= SetAssociativeCache(4, 8, 4, 6, True)
272 vl
= rtlil
.convert(sac_lfsr
, ports
=sac_lfsr
.ports())
273 with
open("SetAssociativeCacheLFSR.il", "w") as f
: