[CS61C FA20] Lecture 25.2 - Caches II: Direct Mapped Example — Transcript

Full transcript

1. 0:00and welcome back now let's work on a
2. 0:02problem let's work on an
3. 0:03actual problem where we learn about
4. 0:05direct map caches
5. 0:06with some actual numbers and some actual
6. 0:08problems so here we go
7. 0:09i got eight bytes of data in a direct
8. 0:12map cache with two byte blocks
9. 0:14okay oh eight bytes of data overall area
10. 0:18of the problem you might have seen this
11. 0:19before there eight bytes of my total guy
12. 0:22two by blocks okay two bytes across i
13. 0:25got that
14. 0:26okay now we're gonna ask you some
15. 0:27questions how big is the tag
16. 0:29index and offset fields if we're doing a
17. 0:3132-bit architecture
18. 0:33okay so that's usually the setup so
19. 0:35let's figure out the offset first let's
20. 0:36do the offset first
21. 0:37well the offset is the number of total
22. 0:40bits i need
23. 0:42to if i'm looking at how am i dividing
24. 0:43up that set of bits
25. 0:45how am i his 32-bit address sum's got to
26. 0:48be some of those 32-bits is going to be
27. 0:49the t and the i and the o
28. 0:51so let's do the o first well the o tells
29. 0:54me
30. 0:54which column i'm in that's the first
31. 0:55thing we do so how many columns do i
32. 0:57have how many bytes
33. 0:58it's always in bytes how many bytes do i
34. 1:00have in a block
35. 1:02i figured it out it said it it says two
36. 1:04by blocks well
37. 1:05so two to the what two to the number of
38. 1:07bits is that total number of bytes
39. 1:10in that block well two to the blank is
40. 1:13two so blank is one so i need one bit
41. 1:16for my
42. 1:16and that's what we saw before one bit to
43. 1:19determine my offset
44. 1:21what's my index well it's the same idea
45. 1:24i just did this before kind of when i
46. 1:26was talking about the the
47. 1:28larger cash problem here we go total
48. 1:30cash is what's the area
49. 1:32well i told you eight two to the three
50. 1:35what's a block a block is two to the one
51. 1:38bytes two to the three over two to the
52. 1:41one is three minus two is one
53. 1:43therefore two to the two blocks per
54. 1:46cache
55. 1:46therefore i need two bits to specify
56. 1:49that number of blocks
57. 1:50so then i go to my tag tag is everybody
58. 1:54else
59. 1:55that basically said three bits are
60. 1:56needed to access
61. 1:58a cache i could by the way i could have
62. 2:00told you the tag size already
63. 2:01because you told me the cache size
64. 2:02that's three because sorry you told me
65. 2:04the cache is eight bytes
66. 2:05that's three bits to access eight bytes
67. 2:07so therefore three can be borrowed
68. 2:09for whatever if i'm even if i'm confused
69. 2:11some of them are indexed some of them
70. 2:13are
71. 2:13offset i don't know which is which i do
72. 2:15know that three of them are to tell me
73. 2:16about the
74. 2:17place it inside the cache well the three
75. 2:20are for there
76. 2:20the rest of them 29 are my tag and
77. 2:23that's it so i need a 29 bit tag
78. 2:26and three bits to tell me which row the
79. 2:29left two bits
80. 2:30of that the left two bits are the index
81. 2:33that tells me what row and one bit is my
82. 2:35offset which is what column
83. 2:36that's it again why not the first full
84. 2:3932 bits for the tag
85. 2:40well why waste those those rightmost
86. 2:43three bits are never used they're always
87. 2:45you know they're always going to be
88. 2:46uh uh uh redundant so we don't want to
89. 2:48have them in that system
90. 2:51so let's do this now a big picture this
91. 2:54is a really big picture idea
92. 2:56taking a computer without a cache and
93. 2:58then adding a cache
94. 2:59doesn't change the process it changes
95. 3:01the process doesn't change the value
96. 3:03doesn't change the program i told you
97. 3:05you should take the same code
98. 3:06with or without cash it does the same
99. 3:08thing now it may not be it may be faster
100. 3:10if you
101. 3:11knew that there were cash there but the
102. 3:12same thing should happen effectively
103. 3:14so i want to load a word i got some
104. 3:17memory
105. 3:19t1 is a pointer to memory i want to load
106. 3:21that and store it into t0
107. 3:23clobber whatever t0 was and put that
108. 3:25memory in there and let's say t1
109. 3:27contains
110. 3:28uh one zero two two okay 1022
111. 3:31is the is the pointer say and what's in
112. 3:34that address
113. 3:3599. so what happens those are the steps
114. 3:38without the case just the days without a
115. 3:39cash
116. 3:39back in the days the simple the simple
117. 3:42halcyon days before caches
118. 3:46processor issues an address 1022 to
119. 3:48memory it says i want to get you know
120. 3:49what is that what is lw
121. 3:51t0 0 t1 where t1 is 10 22 it says
122. 3:54look can you please go to memory at
123. 3:57address 2 10 22 and get something there
124. 3:59yeah sure i can get you that how much
125. 4:00you're asking for oh it's the lw it's a
126. 4:02word all right please i'll get you back
127. 4:03no problem okay here's 99.
128. 4:07the memory reads it returns 99. remember
129. 4:10he sends it back to the processor and
130. 4:11the processor then
131. 4:12loads that into the register and by the
132. 4:14way at this point you know how the whole
133. 4:15thing works
134. 4:16you know that how the data you
135. 4:20you i could ask you for a data path of
136. 4:21what what lights up and how it actually
137. 4:23does it and you can even show me the
138. 4:24control lines to make it work at this
139. 4:26stage in the course
140. 4:27you can explain everything about how a
141. 4:29load work works it's really very
142. 4:30powerful
143. 4:31to understand how that whole thing works
144. 4:32to run on a risk 5 machine
145. 4:34this lights up this this goes there the
146. 4:36index the offset there's a zero at the
147. 4:38zero uh
148. 4:39uh immediate there that zero gets added
149. 4:41to that memory location
150. 4:42doesn't change it's still 10 22. so
151. 4:44that's an immediate had to be extended
152. 4:46all those things you know how to do and
153. 4:48you know how to route it you know what
154. 4:49turns on you know what muxes turn on
155. 4:50what the signal lines that go to the mux
156. 4:52it's really very cool
157. 4:53at this point your understanding of the
158. 4:55whole system very powerful i hope you
159. 4:57walk a little bit taller now that you
160. 4:58understand how that works
161. 4:59but again this is without a cache what
162. 5:02happens with the cache what's the
163. 5:04algorithm with the cache
164. 5:05again i got my same load word and t once
165. 5:07contains the same thing
166. 5:09well with the cache it's similar to like
167. 5:10what a hash function does
168. 5:12it says well you know i could save time
169. 5:15if it's in my cache then go into memory
170. 5:17okay so first i do is i have to see if
171. 5:20it has a copy
172. 5:21do you have a copy of that data at is
173. 5:24that 99
174. 5:25somehow copied in because i'm remember
175. 5:27i'm only reading for now i'm never
176. 5:28writing i'm only reading for now okay so
177. 5:30is that 99 somewhere in my cache so if
178. 5:33it is
179. 5:34i say it's a hit we got it whoo and i
180. 5:36returned that and
181. 5:37i never had to go to sacramento
182. 5:38sacramento was really far away
183. 5:40is it in my room is that 99 somewhere in
184. 5:42my room well i got to check it if it is
185. 5:44if not oh man well then i got to go to
186. 5:46memory and then here's what i have to do
187. 5:48here's a step forward
188. 5:49i have to memory resident to the address
189. 5:53memory sends it back to the cash so the
190. 5:55cash is in there
191. 5:57when it wasn't there the cash has to
192. 5:59still store it for the next time
193. 6:01so it doesn't well i don't have it sorry
194. 6:02i'm going to sleep don't go to sleep you
195. 6:03got to store it for the next time that's
196. 6:05the whole purpose of the cache is that
197. 6:06right you have the first time you'll
198. 6:07have it for the next time i ask for it
199. 6:09it replaces the spot that word with 99
200. 6:12and then it sends that idea back to it
201. 6:14so it still has to do with storage and
202. 6:15update itself and then it sends it back
203. 6:17and from the process point of view it
204. 6:18didn't didn't know it didn't have to i
205. 6:20just
206. 6:21asked for it and if it was there it was
207. 6:22much faster return value if it's not
208. 6:24magic things happen behind the scenes as
209. 6:27it moves to the right place and updates
210. 6:29update updates and then
211. 6:30finally i just get my 99 and i work with
212. 6:32it and it sets it to
213. 6:33zero so in some sense it's the same
214. 6:35thing from the processor's point of view
215. 6:36abstractly i don't know what happened
216. 6:38below the hood and now the cache is
217. 6:39moving around and putting it here
218. 6:41and doing its thing so that it does the
219. 6:43right thing
220. 6:44this is the last slide on this uh on
221. 6:46this particular uh
222. 6:48mini lecture but i wanted to i want to
223. 6:49show talk more about
224. 6:51how to think about i i created this
225. 6:53because i realized as i was working with
226. 6:55many students in office hours they
227. 6:56weren't
228. 6:57visualizing it right and i'm a visual
229. 6:58guy i got my phd in graphics so
230. 7:00pictures always help me learn and maybe
231. 7:02some others are like that
232. 7:04so i wanted to show you how to solve
233. 7:06cash problems in general
234. 7:08we always as i mentioned before draw our
235. 7:11memory the same width
236. 7:12as the cache okay always the same
237. 7:15however however many
238. 7:16whatever that block size is of my cache
239. 7:19draw your memory
240. 7:20the same size the width of it at least
241. 7:24and now as i have my t i and o
242. 7:27and i have a value all zeros where is
243. 7:30all zeros
244. 7:31in cache well i always start
245. 7:34in the upper right there it is
246. 7:38where is it in memory same spot
247. 7:41like these are these are like mirrors
248. 7:44it's almost like a mirror this is
249. 7:46there's this
250. 7:46wonderful there's this wonderful marx
251. 7:48brothers where they're
252. 7:50kind of like the two brothers are
253. 7:51pretending to be he he walks in and he
254. 7:53thinks he's looking at a mirror but it's
255. 7:54actually his brother his brother goes
256. 7:56like this it's like maybe if i can grab
257. 7:59a copy i'll show you this over here but
258. 8:00it does the hand and the hand in there
259. 8:02it's a mirror
260. 8:03that's what's happening as i'm asking
261. 8:05for the memory the cache is exactly the
262. 8:07same spot so wherever you see this arrow
263. 8:08pointing to memory it's literally the
264. 8:10same spot
265. 8:10in that cache okay next one
266. 8:14of interest oh i just increment that guy
267. 8:17my increment my
268. 8:18binary odometer by one which means all
269. 8:20i'm going to do is change my offset
270. 8:22i move my offset by one what am i doing
271. 8:24i just move over by one
272. 8:26it's the next one over so it's like i'm
273. 8:27starting from the top right and read
274. 8:28across to the left
275. 8:30i'm just increasing the bytes that i'm
276. 8:31going to ask for as i'm asking for my
277. 8:33address i change my one i'm getting the
278. 8:35next byte then the next byte and the
279. 8:36next byte and for now we're just doing
280. 8:37load bytes we're just moving by one okay
281. 8:40the next interesting thing the next kind
282. 8:42of significant number is when it gets to
283. 8:44all ones
284. 8:45i want you to draw think before i give
285. 8:47you the answer where is that
286. 8:48where is that thing if i say all zero
287. 8:49zero zeros all zeros in my tag
288. 8:52all zeros are my index but all ones are
289. 8:54my offset where is that in the picture
290. 8:55of memory circle it
291. 8:57circle i should i'm gonna make an exam
292. 8:59question circle the box where it is in
293. 9:01memory in there
294. 9:02i'll tell you where it is it means i got
295. 9:05to the last spot
296. 9:08before i wrapped into the next index so
297. 9:11it is in the top
298. 9:12left okay got that so as i read it
299. 9:16across
300. 9:17offset continues to move across until i
301. 9:19get to all ones
302. 9:20that's the top left then what happens
303. 9:22then it wraps
304. 9:24to make the index up by one and where is
305. 9:26that
306. 9:28it's the next row it's still in that
307. 9:30it's still in cache zero this is
308. 9:32tag zero or cache number zero
309. 9:36and so again that's here that's the next
310. 9:38row down that's my
311. 9:39okay so start to think about and see
312. 9:41kind of visualize where this thing is
313. 9:43now the next thing is what what's what
314. 9:45happens when that maxes out when that
315. 9:47maxes out
316. 9:48and offset max is out where am i you
317. 9:50probably can guess where i'm going to be
318. 9:52you're exactly right it is in the bottom
319. 9:54left
320. 9:55of the memory the bottom left of your
321. 9:57cache and your bottom left of memory
322. 9:59same exact idea
323. 10:00i hope this is helpful by the way when
324. 10:03that wraps what happens next
325. 10:05well as you might imagine i now go
326. 10:08back to the top left of my cache
327. 10:14top right of my cache but now the tag
328. 10:17has
329. 10:18changed now i'm in the next cache the
330. 10:20cashflow bloop
331. 10:21and because this is the next box this is
332. 10:23the next box this tells me
333. 10:25what my cache number so my tag is now a
334. 10:27one there so
335. 10:29one in all zeros is in the top right of
336. 10:32the next cache size down in memory or if
337. 10:35i my cache i just go back to the top
338. 10:37right
339. 10:37because i basically go across go across
340. 10:39go zigzag and then i just jump back up
341. 10:41there
342. 10:41that's what happens so i've jumped back
343. 10:43up there when i had all zeros
344. 10:44because again in this i only am looking
345. 10:48at these to tell me where i am in here
346. 10:50i'm using this one to tell me which one
347. 10:52of these guys i go to that's all this is
348. 10:55it really isn't that bad
349. 10:57the next thing that's most important is
350. 10:59all ones whoa that's the biggest memory
351. 11:01location of all time
352. 11:04where is it you're exactly right it's
353. 11:06the bottom left
354. 11:07of here and because this maps to that
355. 11:10it'd be the bottom left of that cache
356. 11:13with tag number whatever the maximum
357. 11:15value is
358. 11:16that's it that's the big idea of how to
359. 11:18solve cash problems
360. 11:20take your t ino theoden gracias
361. 11:23thanks to dan for teaching me this the
362. 11:26idea is
363. 11:27you are going to be able to look i could
364. 11:28just tell my
365. 11:30i give you some bits and they look
366. 11:31complicated no make your columns there's
367. 11:33my t
368. 11:34there's my i there's my o if you want if
369. 11:36you're really fancy have three different
370. 11:38colors red green and blue like i use
371. 11:39here
372. 11:40and then start to make use of this
373. 11:43i don't know this kind of visual way to
374. 11:45think about this as you start to have
375. 11:46problems
376. 11:47and as i start to have some piece here's
377. 11:48a piece of code i might give you what's
378. 11:50happening in this loop oh
379. 11:51maybe it's just look at this maybe the
380. 11:53loop is dressed let me let me go maybe
381. 11:54maybe go back
382. 11:55maybe this loop is just in here in the
383. 11:57cache maybe just reading this
384. 11:58oh okay so i can think about that that
385. 12:01means it's running it maybe it keeps
386. 12:02going
387. 12:02it just goes on here right on the right
388. 12:04okay i don't know what my stride is
389. 12:06maybe
390. 12:07read this memory address and then jump
391. 12:09another if it's memory address not the
392. 12:11neighbor
393. 12:11if i'm reading by ones i'll be reading
394. 12:14i'm reading a cross
395. 12:15i'm reading a cross what if i jump by
396. 12:17some stride i'd read this memory and
397. 12:18then i jump to the next one
398. 12:20how big is your stride well what if your
399. 12:22stride is exactly a block size
400. 12:24well that means i start some place and
401. 12:26i'm going down here because i'm jumping
402. 12:28by a block i jump by a whole block which
403. 12:30means i go to the next block
404. 12:32what if i'm my what if my stride is the
405. 12:34cash size
406. 12:35whatever memory address i have i jump
407. 12:37back what what happens if it's not even
408. 12:38on the edge
409. 12:39here's my first access here and i
410. 12:42stride by my cache size what's your next
411. 12:46location there it is because i moved by
412. 12:50a cache size
413. 12:51and by the way if this is the first one
414. 12:53if that's the first one
415. 12:54where's the second one same spot because
416. 12:57if i jump by the cache size
417. 12:59it doesn't move in the cache right it
418. 13:00does this is just a copy of what that
419. 13:02looks like
420. 13:03that's not saying the whole thing is a
421. 13:04copy of the whole thing but i'm just
422. 13:05saying the location in the cache
423. 13:07is parallel to where it is in that box
424. 13:09moved over
425. 13:10so i could stride i can make a memory
426. 13:13access and then stride by some amount
427. 13:15and if i stride by a byte i move across
428. 13:17the top
429. 13:18if i stride by a block size i move down
430. 13:20wherever i start with
431. 13:22wherever i start with i'm moving down
432. 13:23that same row if i stride by a cache
433. 13:26size
434. 13:26i store wherever i start with and i'm
435. 13:28jumping to the next guy the same spot
436. 13:31okay so these are common strides we
437. 13:33might have an example
438. 13:34what if i stride by a little less than a
439. 13:36block oh let's play with that
440. 13:37here we go a little less than a block
441. 13:39i'm here a little less than a block
442. 13:41means
443. 13:42i'm actually going to go this way it's a
444. 13:44little less than a block
445. 13:46what if it's a little more than a block
446. 13:48well then i'm going to go this way
447. 13:50okay what if i'm what if i'm not exactly
448. 13:52a cash
449. 13:53but a little more than a cash what
450. 13:56happens
451. 13:57here and i move over a little bit and i
452. 14:00move
453. 14:01over a little bit what if i'm a little
454. 14:03less than
455. 14:04a cash size i'm here
456. 14:07in the same spot but a little's in here
457. 14:11what if i'm not just a little less than
458. 14:13the cash's what if i'm a whole block
459. 14:14size let's
460. 14:15lessen the cache size starting to hurt
461. 14:18here's my memory
462. 14:19exactly one block size less than the
463. 14:21cache size if i start with this
464. 14:22m that means the next one is b up one
465. 14:26and up one it means i'm going up one i'm
466. 14:28kind of not completely
467. 14:29getting there what if i my stride is
468. 14:32and by the way play this slower and
469. 14:34rewind this to make sure you understand
470. 14:35this what if my stride is
471. 14:36cache size plus a block well i start on
472. 14:39this m
473. 14:40and the next one would be the same m but
474. 14:41down one and the next
475. 14:43m but down two okay so think about as we
476. 14:47give you some code and maybe have a
477. 14:48stride as i'm accessing not just
478. 14:51continuous
479. 14:51version of memory but like a stride and
480. 14:54then another one and another one
481. 14:56how you're moving through this space to
482. 14:58understand
483. 14:59as you're solving these problems what
484. 15:01how many hits do you get how many times
485. 15:03do you get it how many times did you
486. 15:04miss it
487. 15:05all those things about in terms of
488. 15:07performance of a problem
489. 15:08okay phew i hope this was useful i kind
490. 15:10of i really
491. 15:12visually always go here you give me any
492. 15:14problem i say excuse me give me time
493. 15:15hold on
494. 15:16i draw my picture okay now now let me
495. 15:18read the problem and i label it i draw
496. 15:19my p
497. 15:20i draw my this and then i say okay
498. 15:21what's the width of the cache what's the
499. 15:23block size that's the width of both
500. 15:24cache and memory because i've drawn them
501. 15:25the same
502. 15:26and now i start with my here's my t i
503. 15:28drop my t's out my tio
504. 15:29and i drive them out and i understand
505. 15:30that that's i do so
506. 15:33basically just sit down take your time
507. 15:35on these problems and draw the pictures
508. 15:37and you will get them right
509. 15:38okay see the next lecture