[CS61C FA20] Lecture 27.1 - Caches IV: Set-Associative Caches — Transcript

Full transcript

1. 0:00and welcome back in this final series of
2. 0:03lectures
3. 0:03let's learn a little bit about initially
4. 0:06what a set associative cache is
5. 0:08it's the cache that lives somewhere in
6. 0:10the middle between a fully associated
7. 0:11cache where you can sit anywhere
8. 0:13and a direct map cache we have a ticket
9. 0:14for your seat and you sit exactly there
10. 0:16so somewhere in the middle where you
11. 0:17might sit in first class business class
12. 0:19and coach
13. 0:20within those areas you might sit
14. 0:22anywhere but you're kind of set into a
15. 0:24set that's the idea
16. 0:26so an n way set associative cache means
17. 0:29n
18. 0:29means the number of blocks that are in a
19. 0:31set so
20. 0:32you have a tag as before you have an
21. 0:34offset as before offsets the number
22. 0:36what column you're in what byte or what
23. 0:37board you're getting the index now
24. 0:39points to the correct what we call quote
25. 0:41unquote row
26. 0:42or a set so that set has n items so it's
27. 0:45two ways
28. 0:46two way set associated would mean
29. 0:47there's exactly two blocks that live in
30. 0:49that set
31. 0:51that's the idea each set contains
32. 0:53multiple blocks once we're in that set
33. 0:55they're fully associated within a set
34. 0:57and we have to then check
35. 0:59all the tags in some kind of parallel
36. 1:00comparator to do that but
37. 1:02at small scale that's doable at a large
38. 1:03scale that's hard to do hard to build
39. 1:05so the overall size of a cache
40. 1:08is the number of rows what's the rows
41. 1:10now the number of rows is
42. 1:12the number of sets so the index bits
43. 1:15tells you the number of sets
44. 1:16and then times n where n is the number
45. 1:19of blocks per set
46. 1:20you multiply sets times blocks per set
47. 1:22you get blocks that's the number of rows
48. 1:24total right the number of blocks that
49. 1:27times the width which is the offset bits
50. 1:30and the two to the offset bits and
51. 1:31that's your that's your cache size so
52. 1:33very same similar before but just now
53. 1:35each rather than directly going to a
54. 1:37spot
55. 1:38you're going to a set and you're in
56. 1:39you're fully associative within that set
57. 1:42so here's a two-way set associative
58. 1:46cache example notice we have here red
59. 1:49and green and zero one zero you know
60. 1:52zero one two three four there and now if
61. 1:54you watch
62. 1:56any red can go to any one of the two red
63. 1:59positions so if i happen to
64. 2:00want in this exact perfect example the
65. 2:02whole ping-pong effect
66. 2:04in the direct map example when i copied
67. 2:06from zero to four
68. 2:07if you remember zero and four i can grab
69. 2:09my pin here if you remember zero and
70. 2:11four
71. 2:11used to be used to be the same color it
72. 2:14was blue
73. 2:15so if i were copying if i only had let's
74. 2:17say a set that had one block
75. 2:20if i were copying from zero to four i
76. 2:21wouldn't be taking advantage of my cache
77. 2:23at all
78. 2:23because i'd be kicking it out here's
79. 2:25zero and then here's four and then
80. 2:26here's zero and four
81. 2:27and i wouldn't ever be kind of making
82. 2:28use of it if i were walking along let's
83. 2:30say it's a really long block a really
84. 2:32wide block so my cache is
85. 2:34small but wide the aspect ratio was like
86. 2:36that and i were kind of streaming across
87. 2:38copying from one array to the other very
88. 2:39common piece of code copy from this you
89. 2:41know duplicate an array very common
90. 2:42thing to do
91. 2:44i'd be killed if i weren't able to
92. 2:46somehow capture
93. 2:47both the red areas if both of them were
94. 2:49blue i wouldn't be able to have both
95. 2:51blue and my cache at the same time
96. 2:53if you imagine a really big one that's
97. 2:54terrible here even a two-way set
98. 2:57associative solves that problem so
99. 2:59two sets two blocks in the set we're
100. 3:01really happy with this i didn't even say
101. 3:02it this particular doesn't say
102. 3:03picture doesn't say how wide what the
103. 3:05block size is but
104. 3:06we don't care we're just talking about
105. 3:08how how it works
106. 3:10the basic idea again cache is direct map
107. 3:13with respect to the sets the index tells
108. 3:16me exactly what set i'm in
109. 3:17within that i'm fully associative within
110. 3:19the end blocks in that
111. 3:21set for an n-way set associative cache
112. 3:23so again let's do it
113. 3:25find a correct set using the index value
114. 3:27compare the tags with everybody in there
115. 3:28because now
116. 3:29i'm pretending to be fully associative
117. 3:31i'm in here if a match occurs great
118. 3:33otherwise i have a miss um and
119. 3:36finally again as always grab the offset
120. 3:38bits to figure out what word or what
121. 3:39bite i'm requesting
122. 3:40easy so it's great i think i kind of
123. 3:43mentioned this even a two-way set
124. 3:44associative
125. 3:45handles all those conflict misses that
126. 3:47copying from a blue to a blue
127. 3:49is great now in the earlier case copying
128. 3:51from a red to red or green or green i
129. 3:52can fit both reds or both greens there
130. 3:54so that kind of
131. 3:55copy from one to the other really help
132. 3:57even more for two-way even just
133. 3:59moderately allowing for two-way just a
134. 4:00little dribble here's direct mapped
135. 4:03one step over is two-way by the way n
136. 4:05almost universally is a power of two
137. 4:07it's four away eight-way
138. 4:0816-way in general okay and again
139. 4:10hardware isn't that bad only need
140. 4:11n comparators so two comparators which
141. 4:13is great so
142. 4:15sorry i couldn't hear what you said
143. 4:17thank you so much siri
144. 4:18well i said what i'm saying is if it's
145. 4:20direct
146. 4:21it's a one-way set associated just make
147. 4:23sure i tell you that if it's if
148. 4:25if so here's this knob and this knob
149. 4:27says um
150. 4:28if i turn the knob all the way for m for
151. 4:32m
152. 4:32blocks let's say i have m blocks total m
153. 4:34blocks
154. 4:35well one way if i say i'm
155. 4:39one way set associative that really
156. 4:41means direct mapped
157. 4:42so one way set associative is direct
158. 4:44mapped and
159. 4:46m way means that m blocks can occur in
160. 4:49m slots that's fully associative so that
161. 4:52knob really goes if i have total m
162. 4:54the total height of my catch is m when
163. 4:56the knob goes this way it's
164. 4:58one and therefore i'm direct mapped goes
165. 5:00all the other way it's now
166. 5:01m i'm now fully associative that makes
167. 5:03sense and so
168. 5:04these are these are both special cases
169. 5:06of the more general case which is this
170. 5:08so this is actually more general case
171. 5:09which is kind of nice
172. 5:10and this is the dynamic slide this is
173. 5:13the last slide on this
174. 5:14this lecture i love this slide let's do
175. 5:17it together let's walk it through
176. 5:18together i think i did this earlier
177. 5:19but this is great for a four-way set
178. 5:21associative cache here's how that works
179. 5:23how do we start i don't know how to
180. 5:25start divide it up into the fields
181. 5:28tag offset uh uh tag index offset to
182. 5:31don't remember teodan
183. 5:32grab my index and tell me what
184. 5:36set i'm in not what row i'm in in terms
185. 5:38of okay no not one block i'm in
186. 5:40what set i'm in and here i've drawn here
187. 5:42has drawn rather than kind of draw red
188. 5:44red green green
189. 5:45you know whatever i do this way i draw
190. 5:47them across so
191. 5:48this here these four guys
192. 5:51there is my set that's my four in my set
193. 5:55and now this happens in parallel watch
194. 5:58what happens
195. 5:59well let's do our same thing we've seen
196. 6:00this before we've seen our tag
197. 6:02and and valid bit comparison all that's
198. 6:06done
199. 6:06and this is what's really fun about this
200. 6:08if we kind of we can even i think i can
201. 6:09even do this
202. 6:10i can even zoom in let me try that
203. 6:13i can even zoom in look at this on this
204. 6:17and let's see what's happening at the
205. 6:18bottom here this is fun
206. 6:21so what's happening at the bottom is
207. 6:23each of these is did it match
208. 6:24so each of those are comparators did it
209. 6:26match does the tag match and is it valid
210. 6:28because we didn't remember don't forget
211. 6:30the valid bit you could have garbage
212. 6:31there that happens to match the tag
213. 6:32that's that would be really uncool
214. 6:34now do i have a hit sure it's an or
215. 6:37of all four of those lines so that makes
216. 6:40sense
217. 6:41now here's the interesting thing this is
218. 6:42let me zoom back a little bit
219. 6:44this is the actual data if you remember
220. 6:46the data used to go through a mux
221. 6:48being chosen by whatever uh whatever
222. 6:51bits
223. 6:52of the of the whatever
224. 6:55bits of the offset were being used to
225. 6:59grab the particular
226. 7:00the particular um word i think it was
227. 7:03the word i was grabbing at the time do
228. 7:04you remember that
229. 7:05um so that was there in a four it was a
230. 7:07mux that chose those two bits to choose
231. 7:09what word i was grabbing
232. 7:11here this data is coming through
233. 7:14and it goes to a four to one mux but
234. 7:16rather than being driven by
235. 7:17two signals it's going to be driven by
236. 7:21four signals and those four signals
237. 7:23we're going to call let me zoom back
238. 7:24fully
239. 7:25we're going to call that one hot and one
240. 7:28hot is exactly as you might imagine it's
241. 7:30a set of lines
242. 7:31n lines in which i promise you the spec
243. 7:34is on this one hot system
244. 7:36only one of those will ever be one at a
245. 7:38time they'll all be zeros by default
246. 7:40and when when you want to drive the
247. 7:43second one then this would go high but
248. 7:44everyone else would go quiet
249. 7:46so only one is ever hot or one ever
250. 7:49and if that's the case and you by the
251. 7:50way i really encourage you to think
252. 7:52about how you might wire a four to one
253. 7:53comparator
254. 7:54if i did this so rather than having two
255. 7:55bits that select that i have this one
256. 7:58hop model in which whenever
257. 8:02one of those lines goes hot which means
258. 8:04it is both valid
259. 8:05and the tags matched that's what chooses
260. 8:08so let's say it's
261. 8:09the rightmost one let's make this one
262. 8:10here well when that goes high it says
263. 8:13well
264. 8:13probably that came what are that line
265. 8:14frame from that came from the rightmost
266. 8:17guy
267. 8:17that means that matched well then that
268. 8:20means that means
269. 8:21this would get passed through to the
270. 8:24output
271. 8:25okay and similarly for the other four so
272. 8:27the idea of a one hot
273. 8:30signal line for my mux is just another
274. 8:32way to drive the mux
275. 8:33and i do encourage you to be able to sit
276. 8:34back how about it might be on a final
277. 8:36exam
278. 8:37where you might have a situation i want
279. 8:39to show you tell me how to build a one
280. 8:41hot um signal line for uh
281. 8:44two to one mux or four to one mux or
282. 8:46eight to one mux think about how you do
283. 8:48that if i have
284. 8:49a one by the way just in general if i
285. 8:51have a one hot line i have to have the
286. 8:52number of
287. 8:53signal lines at the control lines equal
288. 8:55to the number of input lines
289. 8:57so notice i have four here four to one
290. 8:59and i have
291. 9:00four of these because only one of them
292. 9:01is going to be hot and that one drives
293. 9:03the guy that ends up
294. 9:04driving the the bridge we always talk
295. 9:06about this being a bridge and it's like
296. 9:07four roads converging on one bridge
297. 9:09because the bridge is out or they're
298. 9:10repairing a side of it so
299. 9:11that's the idea okay so that's n-way set
300. 9:15associative in this particular example
301. 9:16for
302. 9:17the hardware the actual circuits of
303. 9:20block diagrams of a four-way set
304. 9:22associative
305. 9:22we'll talk about other set associativity
306. 9:25and other components of caches in the
307. 9:26next lectures see you there