[CS61C FA20] Lecture 25.3 - Caches II: Cache Terminology — Transcript

Full transcript

1. 0:00and welcome back now let's talk about
2. 0:02some of the terminology as we
3. 0:04start we've seen some examples with
4. 0:05caches we understand direct map caches
5. 0:07we think about how to think about them
6. 0:08how to draw them
7. 0:09but there's a lot of new words caches
8. 0:11boy caches have probably
9. 0:12i feel like 20 words you may have never
10. 0:14used before so or maybe using different
11. 0:16context so let's make sure we understand
12. 0:18all the words that people use when they
13. 0:19talk about different caches
14. 0:20so when i read memory sometimes it's
15. 0:23there
16. 0:24sometimes it isn't or sometimes it's
17. 0:26there but the tags don't match those
18. 0:27three cases we call a cache hit
19. 0:31that's the best situation it means i
20. 0:33loaded it before
21. 0:34into the cache spot and the cache block
22. 0:37and
23. 0:37when i want some data it's there the
24. 0:39tags match
25. 0:41best situation well there's
26. 0:44the there's a not so great situation
27. 0:46which is i go there
28. 0:48i go to see the cash it's in the i go to
29. 0:50the cover the cupboard's bare i went to
30. 0:52the cash
31. 0:52the cash wasn't there and we call that a
32. 0:55cash miss if i don't successfully get it
33. 0:57if i look it up
34. 0:58and either it wasn't there because i
35. 0:59never loaded that that particular block
36. 1:01or the block isn't there it's going to
37. 1:02be a miss so both of those cases i
38. 1:04kind of walk away unhappy is a cache
39. 1:06miss i probably got to go to sacramento
40. 1:08to memory to do that
41. 1:10now there's a situation where what if i
42. 1:13went there and it was loaded by somebody
43. 1:15else it's almost like goldilocks wait
44. 1:16who's in my bed
45. 1:17i went to that block and there was
46. 1:19somebody in my right what do you do
47. 1:20there
48. 1:21and so that's a situation where you have
49. 1:22a cache missed with block replacement
50. 1:24i went there someone was already loaded
51. 1:27into that into that row
52. 1:28into that block but it's not the one i
53. 1:30wanted so that's a replacement that's
54. 1:32got to be replaced out
55. 1:34and the new one has to be loaded in
56. 1:35there so that's an issue okay
57. 1:38cache is always a copy now here's an
58. 1:40interesting i i i made this slide this
59. 1:42is a brand new slide for this year and i
60. 1:44wanted to add that because i've heard
61. 1:45people who talk about caches use these
62. 1:47words but we never actually formally
63. 1:49share with students so i want to share
64. 1:50some of the these are kind of informal
65. 1:52words we use about the cache
66. 1:54are temperatures you can look at a cache
67. 1:56and assign a
68. 1:57temperature to it well what does that
69. 2:00mean
70. 2:00well when the cache is empty we actually
71. 2:02call it a cold cache
72. 2:04it means there's nothing there we think
73. 2:06of the heat as how full
74. 2:08and successful the cache might be to be
75. 2:09able to respond to a future request
76. 2:11so as i start to chug through my the
77. 2:14beginning of my for loop
78. 2:15it's cold if you don't have every code
79. 2:16it's always cold because i you know you
80. 2:18don't preload their cache the cache
81. 2:19always starts empty so
82. 2:20it's there by the way you could in other
83. 2:22situations pre-load a cache but in kind
84. 2:23of normal the computer science
85. 2:25the memory hierarchy we don't pre-load
86. 2:27caches
87. 2:29then i have to warm it up as i start
88. 2:32exercising my for loop and as i'm going
89. 2:34to memory and bring it in and having a
90. 2:36lot of misses we saw that
91. 2:37as i misses all of a sudden i'm filling
92. 2:39it up and maybe i'm
93. 2:40walking across here and maybe i'm
94. 2:42filling the rows and blocked okay got
95. 2:44that i've got
96. 2:45okay i've got it here we go it's warming
97. 2:46up it's warming up and now i'm starting
98. 2:48to have him hits
99. 2:49and now i'm starting to have that good
100. 2:51that good warm fuzzy feeling
101. 2:52that i'm actually getting back the
102. 2:54reason i had a catch in the first place
103. 2:55that i'm actually getting some cash hits
104. 2:57so i love that so when it's warm
105. 3:00they say that cash is now warm when the
106. 3:02catch is warm it means it's doing its
107. 3:03job
108. 3:04it's filled up with you know it's not
109. 3:05gonna be perfect every time but it's
110. 3:06filled up with
111. 3:07probably some recent guys and i'm
112. 3:09hitting them i'm hitting some fraction
113. 3:10of them
114. 3:11now i've also heard hot which means i'm
115. 3:14stuck on a tight loop and i'm everything
116. 3:16as a hit when i get to the point where
117. 3:18basically a high percentage is
118. 3:19maybe here and then whoop i jumped over
119. 3:21here but mostly it's hits that cash is
120. 3:23hot
121. 3:23so that kind of temperature is a way to
122. 3:25think about it's really fun way to think
123. 3:27about
124. 3:27um how successful my cash is to be able
125. 3:30to respond with more
126. 3:32cache hits in the future it always
127. 3:33starts cold it warms its way up and when
128. 3:36if you're really lucky in a tight loop
129. 3:37it gets really hot can it not it doesn't
130. 3:39mean that the silicon gets hot it means
131. 3:40that the idea that you're just
132. 3:42hot means a high chance of a successful
133. 3:43hit in the future some more cash terms
134. 3:46let's make sure we go through all of
135. 3:47them
136. 3:49as i'm getting more hits know what a hit
137. 3:50is obviously a cash hit means i
138. 3:52successfully got there so as i get a
139. 3:54cash hit
140. 3:57there's a fraction of all the total
141. 3:59requests i had how many of them were
142. 4:00hits
143. 4:01we called that the hit rate so that's
144. 4:03just a fraction that's a unitless number
145. 4:05it's a fraction of the of the hits that
146. 4:07actually were successful
147. 4:08the fraction of my requests that were
148. 4:10hits i'll say it again it's a fraction
149. 4:12of requests
150. 4:12that were hits the miss rate
151. 4:15is the opposite it's the it's the the
152. 4:18complement of that number so
153. 4:19they both add to one uh the one minus
154. 4:22the hit rate
155. 4:23is the miss rate so if i have a eighty
156. 4:25percent hit rate whoo
157. 4:27you know four out of five requests or
158. 4:28hits probably a 20
159. 4:30miss rate because you're either hit or
160. 4:31miss okay
161. 4:35xor or inclusive or
162. 4:38you're either a hit x or a miss you're
163. 4:41never
164. 4:42both see how i fix war with them okay
165. 4:46miss penalty miss penalty is
166. 4:49the time to replace the block when i
167. 4:51have a miss
168. 4:52you know you gotta miss what's your
169. 4:54penalty you know okay you caught me with
170. 4:56my hand in the cookie jar where's my
171. 4:57penalty
172. 4:58you know it's some wallops on my butt or
173. 4:59i have to go i'm on time out for
174. 5:01you know i stand in the corner that's
175. 5:03the penalty for
176. 5:04for having this myth so um the time to
177. 5:07replace a block from the lower level is
178. 5:08my miss
179. 5:09by the way this is true for any cache
180. 5:10it's true for any cache to the guys
181. 5:12below any cache that's caching the lower
182. 5:14element at any level
183. 5:16this is you have this miss penalty how
184. 5:18how long does it take to get to the
185. 5:20level below to bring it back into
186. 5:22the level above because you always want
187. 5:23to bring that back in and the hit
188. 5:25time is what time is it to access the
189. 5:28cache memory so this is just great and
190. 5:30by the way this
191. 5:31counts the tag time i do the tag
192. 5:33comparison blah blah blah
193. 5:35a lot of these are hardware so they're
194. 5:36fast because they're parallel but that's
195. 5:38a factor as well you gotta factor in the
196. 5:39hit time as well
197. 5:40and by the way this is an interesting
198. 5:42thing we actually use a dollar sign for
199. 5:44cash
200. 5:45so kind of like you know the whole the
201. 5:46whole kind of that
202. 5:48i know what this means this means i'm
203. 5:49hitting my hands i know what this means
204. 5:50but
205. 5:51cash money people so think of a dollar
206. 5:53sign for
207. 5:54a berkeley innovation we may as far as i
208. 5:57know
209. 5:57my predecessors invented that they use a
210. 5:59dollar sign for cashes
211. 6:01there's one more piece of information we
212. 6:03need which is
213. 6:06i mentioned this earlier do we have a
214. 6:08sentinel value
215. 6:09that the cache can never have to know
216. 6:11when it's remember we need to know
217. 6:13whether
218. 6:13am i cold am i warming up how do i know
219. 6:16when it's
220. 6:16garbage data so do i have to re i write
221. 6:19zeros to everywhere
222. 6:20i can't just write zeros everywhere
223. 6:21because you could have a tag of zero and
224. 6:23a data of zero and that doesn't make any
225. 6:25sense so
226. 6:25am i gonna let's reserve a spot that can
227. 6:28never be in the well that doesn't i
228. 6:29don't like that either
229. 6:30so what we're gonna do and this is a
230. 6:33clever design decision you may have come
231. 6:34up with this on your own
232. 6:35is have a bit just call it a valid bit
233. 6:38and when that bit is zero
234. 6:40it's not valid and when bit is one now
235. 6:43it means i have good data there
236. 6:44so by having a single bit it saves me
237. 6:46from having to kind of
238. 6:48write to my cache to erase it putting
239. 6:50the sentinel value in
240. 6:51just have a single bit once i set those
241. 6:53all the zeros
242. 6:54that the cache is is is is cold and has
243. 6:57garbage values in there
244. 6:58so we're going to use what's called a
245. 6:59valid bit to store it which is nice and
246. 7:01this tells me whether that tag is valid
247. 7:03because the tag can be anything
248. 7:05the tag is my cache number that's from
249. 7:07zero to the maximum number of
250. 7:10cache copies i could have in memory
251. 7:11that's it that's all i've got
252. 7:13so there's no bad value there so we
253. 7:15don't you want to think about having a
254. 7:17sentinel and borrowing one of those guys
255. 7:19we want to be able to access anything
256. 7:20any part of memory should be able to be
257. 7:22in my cache which means any tag whatever
258. 7:25however
259. 7:25wide bits wide my tag is that could be
260. 7:28any bit pattern i don't want to use up
261. 7:29one of those bit patterns i don't like
262. 7:30that idea it's not a good design
263. 7:31i don't like that from a computer
264. 7:32engineering point from an engineer
265. 7:33period i get the computer i don't think
266. 7:35from an engineering printer to waste
267. 7:36something because i can't think of
268. 7:38having another bit
269. 7:38now i do you know ain't no free lunch i
270. 7:42need to borrow some space to store that
271. 7:44vial but anyway but it's better than
272. 7:45having to steal
273. 7:46some memory that i can't access anymore
274. 7:48it could never be in the cache i don't
275. 7:49like that model i like to battle a bit
276. 7:50better
277. 7:51so that's it zero is there so
278. 7:54zero is like when i go to request it if
279. 7:57it's zero it's always gonna be a miss
280. 7:59a cold cache has all zeros in the valid
281. 8:01bit it means there's nothing there
282. 8:03it has bits there but they're garbage
283. 8:04all the tags are garbage you can't trust
284. 8:06them you can't trust them
285. 8:07i'm telling you give them some money
286. 8:08they'll never return it can't trust it
287. 8:10can't trust those tags if the valid if
288. 8:12the valid bit is set to zero
289. 8:13if you can't if there's one then you can
290. 8:15trust it this idea
291. 8:16so here is a picture here's a beautiful
292. 8:18picture a 16 kibi byte
293. 8:20how many bits why how many total bits
294. 8:22for my
295. 8:24for my i and my oh 16kb come on 16 kb
296. 8:2716 14 bits
297. 8:302 to the 14 is 16 kb bytes
298. 8:33okay so 14 bits for total amount
299. 8:37and i have here look at this oh look 0
300. 8:39through well
301. 8:40i'll i'll do with the other numbers
302. 8:41later oh say here we go 16 by blocks
303. 8:43in my head i'm already doing 16 byte
304. 8:46blocks
305. 8:47okay well 16 kibi byte total 16 by
306. 8:51blocks that means the width of 16 bytes
307. 8:52how many rows
308. 8:541k 1k times 16 is 16k
309. 8:57that's not that hard okay so how many
310. 8:59bits for 1k
311. 9:0110 10 bits of index how many bits to
312. 9:03tell me what byte it is for 16
313. 9:054 four bits four here ten there
314. 9:09that's 14 bits there's my total area to
315. 9:11the 14 to 16 kb it just works
316. 9:14and there's my valid bit and there's my
317. 9:16tag
318. 9:17so my valid bit is set and we're going
319. 9:19to reset it to make it all zeros
320. 9:22this looks like a real cache i'm feeling
321. 9:23pretty warm this is pretty i'm feeling
322. 9:25pretty good about this this is a nice
323. 9:27model this is a picture that we might
324. 9:28use
325. 9:30this is the end of this lecture i'm
326. 9:31pretty excited we're already kind of
327. 9:32half this is it there's a halfway point
328. 9:34we're downhill from here we're going to
329. 9:35see a really nice example very detailed
330. 9:37example as we play with this and
331. 9:39expand more of the parameters of how to
332. 9:41expand our cache
333. 9:42we're going to show you a cache and say
334. 9:43well it doesn't work in this way and
335. 9:45we'll add this feature
336. 9:46it doesn't work in this way we'll add
337. 9:47these features and we haven't talked
338. 9:48about rights yet we've only talked about
339. 9:49reading bytes for now so we'll talk
340. 9:51about
341. 9:51a more general thing in the cache as
342. 9:53well but in conclusion
343. 9:54in these lectures you've learned the
344. 9:56operation of a direct map cache the
345. 9:58simplest kind it comes from
346. 10:00i hope you understood and appreciated
347. 10:02the tio
348. 10:03and the kind of where to think about
349. 10:04that i did in the last lecture i thought
350. 10:06that was useful
351. 10:07we talked about a mechanism for moving
352. 10:08data back and forth in the memory
353. 10:10hierarchy which is kind of neat
354. 10:11there's address and value bindings from
355. 10:13the point of view of the program i don't
356. 10:15even know whether it's a cache or not it
357. 10:16just is faster when it does
358. 10:18have a cache so i don't have to change
359. 10:19anything now if i did change something
360. 10:21that'd be great because i could optimize
361. 10:22for the cache and that would be
362. 10:23something we could talk about later
363. 10:25we got to compare our address with the
364. 10:26tag and we got to be able to handle the
365. 10:28hit or miss
366. 10:29that's the idea and when it's missed we
367. 10:31gotta load the new block and reset it
368. 10:32and bind it up on a miss
369. 10:34okay that's it we're done with this
370. 10:35lecture we're done with we're at the
371. 10:37halfway point
372. 10:38we will see the next set of lectures
373. 10:40cache is part three take care