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).
38 def __init__(self
, tag_size
, data_size
, set_count
, way_count
, lfsr
=False):
40 * tag_size (bits): The bit count of the tag
41 * data_size (bits): The bit count of the data to be stored
42 * set_count (number): The number of sets/entries in the cache
43 * way_count (number): The number of slots a data can be stored
45 * lfsr: if set, use an LFSR for (pseudo-randomly) selecting
46 set/entry to write to. otherwise, use a PLRU
50 self
.way_count
= way_count
# The number of slots in one set
51 self
.tag_size
= tag_size
# The bit count of the tag
52 self
.data_size
= data_size
# The bit count of the data to be stored
55 self
.mem_array
= Array() # memory array
56 for i
in range(way_count
):
57 ms
= MemorySet(data_size
, tag_size
, set_count
, active
=0)
58 self
.mem_array
.append(ms
)
61 self
.encoder
= AddressEncoder(way_count
)
66 self
.lfsr
= LFSR(LFSR_POLY_24
)
69 self
.plru
= PLRU(way_count
) # One block to handle plru calculations
70 self
.plru_array
= Array() # PLRU data on each set
71 for i
in range(set_count
):
73 self
.plru_array
.append(Signal(self
.plru
.TLBSZ
, name
=name
))
76 self
.enable
= Signal(1) # Whether the cache is enabled
77 self
.command
= Signal(2) # 00=None, 01=Read, 10=Write (see SA_XX)
78 self
.cset
= Signal(max=set_count
) # The set to be checked
79 self
.tag
= Signal(tag_size
) # The tag to find
80 self
.data_i
= Signal(data_size
) # The input data
83 self
.ready
= Signal(1) # 0 => Processing 1 => Ready for commands
84 self
.hit
= Signal(1) # Tag matched one way in the given set
85 self
.multiple_hit
= Signal(1) # Tag matched many ways in the given set
86 self
.data_o
= Signal(data_size
) # The data linked to the matched tag
88 def check_tags(self
, m
):
89 """ Validate the tags in the selected set. If one and only one
90 tag matches set its state to zero and increment all others
91 by one. We only advance to next state if a single hit is found.
93 # Vector to store way valid results
94 # A zero denotes a way is invalid
96 # Loop through memory to prep read/write ports and set valid_vector
97 for i
in range(self
.way_count
):
98 valid_vector
.append(self
.mem_array
[i
].valid
)
100 # Pass encoder the valid vector
101 m
.d
.comb
+= self
.encoder
.i
.eq(Cat(*valid_vector
))
103 # Only one entry should be marked
104 # This is due to already verifying the tags
105 # matched and the valid bit is high
107 m
.next
= "FINISHED_READ"
108 # Pull out data from the read port
109 data
= self
.mem_array
[self
.encoder
.o
].data_o
110 m
.d
.comb
+= self
.data_o
.eq(data
)
111 if not self
.lfsr_mode
:
114 # Oh no! Seal the gates! Multiple tags matched?!? kasd;ljkafdsj;k
115 with m
.Elif(self
.multiple_hit
):
116 # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
117 m
.d
.comb
+= self
.data_o
.eq(0)
119 # No tag matches means no data
121 # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
122 m
.d
.comb
+= self
.data_o
.eq(0)
124 def access_plru(self
, m
):
125 """ An entry was accessed and the plru tree must now be updated
127 # Pull out the set's entry being edited
128 plru_entry
= self
.plru_array
[self
.cset
]
130 # Set the plru data to the current state
131 self
.plru
.plru_tree
.eq(plru_entry
),
132 # Set that the cache was accessed
133 self
.plru
.lu_access_i
.eq(1)
137 """ Go through the read process of the cache.
138 This takes two cycles to complete. First it checks for a valid tag
139 and secondly it updates the LRU values.
141 with m
.FSM() as fsm_read
:
142 with m
.State("READY"):
143 m
.d
.comb
+= self
.ready
.eq(0)
144 # check_tags will set the state if the conditions are met
146 with m
.State("FINISHED_READ"):
148 m
.d
.comb
+= self
.ready
.eq(1)
149 if not self
.lfsr_mode
:
150 plru_tree_o
= self
.plru
.plru_tree_o
151 m
.d
.sync
+= self
.plru_array
[self
.cset
].eq(plru_tree_o
)
153 def write_entry(self
, m
):
154 if not self
.lfsr_mode
:
155 m
.d
.comb
+= [# set cset (mem address) into PLRU
156 self
.plru
.plru_tree
.eq(self
.plru_array
[self
.cset
]),
157 # and connect plru to encoder for write
158 self
.encoder
.i
.eq(self
.plru
.replace_en_o
)
160 write_port
= self
.mem_array
[self
.encoder
.o
].w
162 # use the LFSR to generate a random(ish) one of the mem array
163 lfsr_output
= Signal(max=self
.way_count
)
164 lfsr_random
= Signal(max=self
.way_count
)
165 m
.d
.comb
+= lfsr_output
.eq(self
.lfsr
.state
) # lose some bits
166 # address too big, limit to range of array
167 m
.d
.comb
+= lfsr_random
.eq(Mux(lfsr_output
> self
.way_count
,
168 lfsr_output
- self
.way_count
,
170 write_port
= self
.mem_array
[lfsr_random
].w
172 # then if there is a match from the encoder, enable the selected write
173 with m
.If(self
.encoder
.single_match
):
174 m
.d
.comb
+= write_port
.en
.eq(1)
177 """ Go through the write process of the cache.
178 This takes two cycles to complete. First it writes the entry,
179 and secondly it updates the PLRU (in plru mode)
181 with m
.FSM() as fsm_write
:
182 with m
.State("READY"):
183 m
.d
.comb
+= self
.ready
.eq(0)
185 m
.next
="FINISHED_WRITE"
186 with m
.State("FINISHED_WRITE"):
187 m
.d
.comb
+= self
.ready
.eq(1)
188 if not self
.lfsr_mode
:
189 plru_entry
= self
.plru_array
[self
.cset
]
190 m
.d
.sync
+= plru_entry
.eq(self
.plru
.plru_tree_o
)
194 def elaborate(self
, platform
=None):
198 # set up Modules: AddressEncoder, LFSR/PLRU, Mem Array
201 m
.submodules
.AddressEncoder
= self
.encoder
203 m
.submodules
.LFSR
= self
.lfsr
205 m
.submodules
.PLRU
= self
.plru
207 for i
, mem
in enumerate(self
.mem_array
):
208 setattr(m
.submodules
, "mem%d" % i
, mem
)
211 # select mode: PLRU connect to encoder, LFSR do... something
214 if not self
.lfsr_mode
:
215 # Set what entry was hit
216 m
.d
.comb
+= self
.plru
.lu_hit
.eq(self
.encoder
.o
)
219 m
.d
.comb
+= self
.lfsr
.enable
.eq(self
.enable
)
222 # connect hit/multiple hit to encoder output
226 self
.hit
.eq(self
.encoder
.single_match
),
227 self
.multiple_hit
.eq(self
.encoder
.multiple_match
),
231 # connect incoming data/tag/cset(addr) to mem_array
234 for mem
in self
.mem_array
:
236 m
.d
.comb
+= [mem
.cset
.eq(self
.cset
),
237 mem
.tag
.eq(self
.tag
),
238 mem
.data_i
.eq(self
.data_i
),
239 write_port
.en
.eq(0), # default: disable write
242 # Commands: READ/WRITE/TODO
245 with m
.If(self
.enable
):
246 with m
.Switch(self
.command
):
247 # Search all sets at a particular tag
252 # Maybe catch multiple tags write here?
254 # TODO: invalidate/flush, flush-all?
259 return [self
.enable
, self
.command
, self
.cset
, self
.tag
, self
.data_i
,
260 self
.ready
, self
.hit
, self
.multiple_hit
, self
.data_o
]
263 if __name__
== '__main__':
264 sac
= SetAssociativeCache(4, 8, 4, 6)
265 vl
= rtlil
.convert(sac
, ports
=sac
.ports())
266 with
open("SetAssociativeCache.il", "w") as f
:
269 sac_lfsr
= SetAssociativeCache(4, 8, 4, 6, True)
270 vl
= rtlil
.convert(sac_lfsr
, ports
=sac_lfsr
.ports())
271 with
open("SetAssociativeCacheLFSR.il", "w") as f
: