[CS61C FA20] Lecture 26.3 - Caches III: Fully Associative Caches — Transcript

Full transcript

1. 0:00and welcome back we last left our
2. 0:03hero when we were thinking about could
3. 0:06possibly two different
4. 0:07memory requests that were blue end up
5. 0:11being kind of together rather than only
6. 0:13one of them was only one blue spot maybe
7. 0:14there could be two blue spots or more
8. 0:16so the extreme idea is a fully
9. 0:18associative cache
10. 0:20might as well go all the way it's almost
11. 0:21like you're over compensating one says i
12. 0:23know exactly where you go
13. 0:25and the fully associative says maybe you
14. 0:26go anywhere it's like
15. 0:28rather than give you an assigned seat
16. 0:30sit anywhere go crazy
17. 0:32that's kind of what fully associative
18. 0:33caches are like so let's see what that
19. 0:35means
20. 0:36so a fully associated cache what i mean
21. 0:39is
22. 0:39you can literally go anywhere so tag was
23. 0:42before the offset's the same as before
24. 0:45but there's no index the the index would
25. 0:48tell me exactly what row to go to i'm
26. 0:50telling you there's no rows
27. 0:51there's no idea of rows any block goes
28. 0:53anywhere see it anywhere you want go
29. 0:55crazy
30. 0:56and you have to compare all the tags in
31. 0:57the entire cache you see the data is
32. 0:59there
33. 0:59which now means because there's no
34. 1:01remember the tag width
35. 1:03is a function of i and o i is nothing
36. 1:06there's no more i anymore so now there's
37. 1:07only an o
38. 1:08which means the tag got bigger so
39. 1:10remember that the tag has to get bigger
40. 1:11when you have a fully associative cache
41. 1:13to factor it in so here's an example
42. 1:16a 32-byte block that's five
43. 1:19bits to specify through to the two to
44. 1:22the five or 32 different bytes i want
45. 1:24there
46. 1:26well 32 bits wide is my total address
47. 1:30if 5 is here that means 27 is my tag so
48. 1:32remember that that tag would have grown
49. 1:34if i had an index there
50. 1:35then my tag would have grown okay think
51. 1:37about that so i've got my tag my valid
52. 1:39bits my cache data like that
53. 1:41and the key here is i'm going to try to
54. 1:43as it was hardware
55. 1:45i'm going to try to compare my tags in
56. 1:47parallel
57. 1:48that's amazing if i can do that if i can
58. 1:50build circuitry i should show you a
59. 1:52picture in a second
60. 1:53then that's great it means i can compare
61. 1:54tags in parallel and figure out whether
62. 1:56i got it or not if they match
63. 1:58benefits what are the huge benefits are
64. 2:01you kidding me
65. 2:02no more conflict misses the whole idea
66. 2:03that the two blues only one of the two
67. 2:05there's not enough room for this whole
68. 2:07cache for the two of us
69. 2:09that's what that model is only one of
70. 2:11those blues can exist in that blue spot
71. 2:13this is anybody puts their stuff
72. 2:15anywhere just find us find a seat that's
73. 2:17what they're kind of saying
74. 2:18the drawbacks of that again the
75. 2:20drawbacks are just in the hardware point
76. 2:21of view which
77. 2:22is not algorithmic it is it's hard
78. 2:25to build hardware comparators for every
79. 2:28single entry if i have it for two
80. 2:30we can do that if it's not that bad but
81. 2:31for have i mean it's just end up
82. 2:3316 000 comparators which is just too
83. 2:35hard to do this
84. 2:36in a normal in a normal cache so these
85. 2:39are hard to do
86. 2:40a software fully associative cache i
87. 2:42love
88. 2:43but a hardware one is hard to build so
89. 2:45that's the key here
90. 2:47the third kind of miss is called a
91. 2:49capacity miss
92. 2:51and this means this is a miss that if if
93. 2:54i could have
94. 2:55just grown my cash bigger i wouldn't
95. 2:57have had that missed that's what a
96. 2:58capacity misses capacity this is
97. 2:59one that wouldn't have wouldn't have
98. 3:01occurred if i would have had a bigger
99. 3:02cache
100. 3:03um this is kind of a soft idea i'm going
101. 3:05to show you an action algorithm for that
102. 3:06and by the way
103. 3:07this is the kind of misses you get with
104. 3:09fully associated caches you obviously
105. 3:11hit
106. 3:11take a compulsory miss for every time
107. 3:13you ever visit a piece of memory right
108. 3:15every every block of memory
109. 3:17i'm going to take a compulsory miss
110. 3:18because i never visited before but
111. 3:21even if i visit the same one that's one
112. 3:22cache above you fully associative can
113. 3:24handle that i'll take another compulsory
114. 3:26miss to grab it for the first time it's
115. 3:27in there
116. 3:28and the next kind of misses i get once
117. 3:29i'm using these guys is
118. 3:31a capacity one which means i want to fit
119. 3:32more guys in here but i only have a
120. 3:34certain
121. 3:35space for my fully associative cache i
122. 3:37can't fit anymore
123. 3:38so capacity misses what the other set of
124. 3:40misses you're going to see long term
125. 3:42steady state once i've let's say you've
126. 3:44exhausted visited
127. 3:45everybody at least once well it's the
128. 3:47capacity miss that really gets you
129. 3:49because you've already taken the
130. 3:50compulsory hit from every single cache
131. 3:51block
132. 3:52every single memory blocked but it's the
133. 3:54capacity miss that way if i had remember
134. 3:56if i had an
135. 3:57infinite memory i wouldn't have had
136. 3:58those capacity if if my cash
137. 4:00if my cash were infinitely big i
138. 4:02wouldn't have taken those capacity
139. 4:03misses i would have loaded them all in
140. 4:05if i could somehow is a crazy world
141. 4:07storm all my memory in my cache
142. 4:09well once i'm there it's there like
143. 4:12literally it would be i would say a copy
144. 4:14but
145. 4:14it would be a a reordered copy of memory
146. 4:17literally if i had a i think a fully
147. 4:20associative cache
148. 4:21there were 34 gibby bytes 2 to the 32
149. 4:25or more i'll just say more but if
150. 4:26exactly that once all the men and i
151. 4:28visit
152. 4:29i swept through all the memory i can hit
153. 4:31it randomly i could hit an order
154. 4:33once i've loaded them all in they'd be
155. 4:35in my cash and i wouldn't have any more
156. 4:37misses
157. 4:37because they're all there so a capacity
158. 4:41misses the miss that you get because
159. 4:42your cash can't be any bigger and
160. 4:44there's some fixed
161. 4:45cost that you have so here this is a
162. 4:48great
163. 4:48algorithm to think about how to
164. 4:50categorize these misses okay
165. 4:52so first consider like the craziest bit
166. 4:55like almost like what i was telling you
167. 4:56now
168. 4:56a second ago consider the most insanely
169. 4:59sized cache you could ever
170. 5:01infinite size all fully associative
171. 5:04for every miss that occurs it's going to
172. 5:06be a compulsory miss okay because
173. 5:08it's never about a capacity because the
174. 5:10infinite size
175. 5:11it's never about conflict because it's
176. 5:13fully associative
177. 5:15so therefore all those misses that i
178. 5:16have in that world are compulsory misses
179. 5:19okay now consider
180. 5:23i have a finite size cache okay
181. 5:27and now let's start let's have let's
182. 5:28start have let's start actually having a
183. 5:30workload run it so as the first line
184. 5:31says run an address trace
185. 5:33against a set of caches so i have a
186. 5:35particular cache i'm comparing to their
187. 5:36neighbors that's the idea i'm comparing
188. 5:38this design against those designs
189. 5:40wow that's kind of interesting to have
190. 5:4120 designs and see what happens but i
191. 5:43have an address trace
192. 5:44which means i have a list or stream
193. 5:46could be infinite
194. 5:47of address requests and maybe you want
195. 5:50to have
196. 5:50reads and writes in there to play with
197. 5:52that as well to play with as a right
198. 5:53back as a right through all those things
199. 5:55i've got this address trace and i hit r
200. 5:57i hit my cache with that trace
201. 5:59and i hit the neighbor cache with that
202. 6:01trace and i hit that okay and i'm
203. 6:02comparing them all
204. 6:04so when i'm comparing them i'm now
205. 6:07looking at a reasonable you know finite
206. 6:09size cache and
207. 6:10a particular with all the parameters and
208. 6:12now i hit it with this trace
209. 6:14all the misses that are not
210. 6:17in the first category compulsory i count
211. 6:19these as capacity misses
212. 6:21meaning the only thing i changed from
213. 6:23step one to step two was
214. 6:24change it from infinite size to finite
215. 6:26size therefore the ones the new
216. 6:28misses i get must be capacity misses
217. 6:30must be because of the change
218. 6:32kind of logically makes sense and now
219. 6:35here's the piece of it i had it was
220. 6:38fully it was finite but still fully
221. 6:40associative
222. 6:41what if i take it fully associative and
223. 6:42i shrink it down
224. 6:44less associative and kind of make it not
225. 6:47fully associative
226. 6:48you right now you only know of direct
227. 6:49mapped there's something in the middle
228. 6:51i'll mention it
229. 6:52i'll mention a second all the remaining
230. 6:54misses
231. 6:56that um sorry
232. 7:00yes finite associativity so i took away
233. 7:02so i took away first of all it was
234. 7:03infinite took away that
235. 7:04like i take away your power as a
236. 7:06superman oh i can't use the i-beams
237. 7:07anymore i can't fly
238. 7:09okay i took away from being infinite
239. 7:10size made it finite now i take away your
240. 7:13fully associativity and reduce it in
241. 7:14some way either reduce it all the way to
242. 7:16direct mapped or somewhere in the middle
243. 7:18and i'll tell you in a second what that
244. 7:19is
245. 7:19as i do that what are the remaining
246. 7:21misses i have those are conflict misses
247. 7:23those are
248. 7:23those are misses that i wouldn't have
249. 7:24had if you were fully associative
250. 7:26that's the idea so it's a really nice
251. 7:28algorithm to think about how to think
252. 7:29about it is it a comp
253. 7:30compulsory miss capacity miss or
254. 7:32conflict miss
255. 7:33run this run this set of traces on that
256. 7:36to see what would happen
257. 7:37and those three cases will flag be
258. 7:39flagged there's even by the way a fourth
259. 7:41miss we're going to tell you
260. 7:42in about a month ish we're talking about
261. 7:44parallelism so say
262. 7:45remember in your back your head say oh
263. 7:47there's a fourth miss what is it i'm not
264. 7:48gonna tell you yet i'll tell you later
265. 7:51in conclusion this is the end of the
266. 7:53third of the fourth lecture on cast as
267. 7:54we're almost done
268. 7:56we still haven't talked about what the
269. 7:57thing between fully associative and
270. 7:59direct map is
271. 7:59somewhere in the middle that's what
272. 8:01we'll talk about the next lecture and
273. 8:02we'll show an example in demo too
274. 8:05so step here's my algorithm let me make
275. 8:06sure you understand the algorithm
276. 8:08take my i have a memory request now we
277. 8:10know it could be a write also but for
278. 8:12now let's do a read okay
279. 8:14divide into the tio bits go to nxi check
280. 8:17if it's valid if zero
281. 8:19it means it's a compulsory miss set the
282. 8:22valid bis i said that compulsory miss
283. 8:23and use the offset if you turn the right
284. 8:25chunk figure out what what column i'm in
285. 8:27return the right chunk
286. 8:28okay if it's one that means
287. 8:31somebody somebody's there but like
288. 8:33goldilocks it could be somebody fits
289. 8:35exactly in my clothes or
290. 8:36somebody that's wrong oh that's you're
291. 8:38not the same tag you're the wrong person
292. 8:40so check tags okay if it's a match hit
293. 8:43whoo and i use my offset to figure out
294. 8:46which column i want what byte word or
295. 8:47whatever i want from that
296. 8:48maybe it's load double i grab two words
297. 8:50from that
298. 8:52if not then i have a conflict miss i
299. 8:55gotta take that old block
300. 8:57out and here's a part of this it's not
301. 8:59written there
302. 9:00if i have a right through i do nothing i
303. 9:02kick the whole guy out
304. 9:03if it's right back i check the dirty bit
305. 9:05if the dirty blit is
306. 9:07said oh man i gotta write that guy out
307. 9:10send that guy back to memory now the
308. 9:11memory is consistent and now i read the
309. 9:13correct guy in load the tag
310. 9:15turn the dirty bit off and we're back in
311. 9:17business and we and return the value
312. 9:18return the right chunk
313. 9:19so i didn't mention the dirty bit in
314. 9:21here you now know what the dirty bit is
315. 9:22that factors into this
316. 9:23algorithm as well and that's the picture
317. 9:26so
318. 9:26next lecture cash series four we're
319. 9:29going to see an example
320. 9:30a demo and talk about what is that
321. 9:32associativity called
322. 9:33that's not fully associative and not
323. 9:35direct mapped who lives in that kind of
324. 9:38flyover who lives in the flyover area
325. 9:40here you know there's california and the
326. 9:42east coast
327. 9:42who lives in the flyover area that's not
328. 9:44with somewhere between fully associative
329. 9:46and direct but direct mapped
330. 9:48we'll see you next time