[CS61C FA20] Lecture 15.3 - State, State Machines: Accumulator revisited — Transcript

Full transcript

1. 0:00and welcome back now let's take a deeper
2. 0:03look at the accumulator we tried to do a
3. 0:04couple of lectures ago
4. 0:06now that we know what a register is and
5. 0:07a flip-flop is and actually how to
6. 0:09think about some of the timing issues
7. 0:10that are accompanying
8. 0:12uh the registered details so there's
9. 0:14only two slides in this this lecture
10. 0:17but it's a complicated one so let's
11. 0:18actually dig deeper on this make sure we
12. 0:19make sure we're at the same with the
13. 0:21understanding what's happening
14. 0:24here's my clock my clock is going to
15. 0:26have
16. 0:27rising edges and things are going to
17. 0:29happen as those rising edges hit
18. 0:32i'm going to indicate the adder
19. 0:34propagation delay with
20. 0:35tau sub add there's another way we think
21. 0:37about it and
22. 0:39the clock to q delay half of that let's
23. 0:42just think about that
24. 0:44and you're going to see this is
25. 0:46complicated we're kind of turning this
26. 0:47on the side to kind of show it a little
27. 0:48bit better
28. 0:49so x of i is going to be changing here's
29. 0:51my x of i having different values
30. 0:53starts at 0 here's of x x 0 x 1 x 2 etc
31. 0:57okay
32. 0:59here's the hard part this register it's
33. 1:01got a reset button the most important
34. 1:03thing on this slide i think is that the
35. 1:04reset
36. 1:05if the register gets up you know
37. 1:09clocks up so rising edge turns around
38. 1:12and
39. 1:12there's an input d but also the register
40. 1:15line is
41. 1:16asserted or high i'm going to ignore my
42. 1:18d and reset myself
43. 1:20so kind of the idea is the reset takes
44. 1:22priority over the d
45. 1:23so i can't i can't care what the d is
46. 1:25for my job is to reset myself so that's
47. 1:27really important
48. 1:29here's another thing that's confusing to
49. 1:30many students i've got an
50. 1:32s of i here and i've got an s of i minus
51. 1:351 here
52. 1:36and you're going to say well shouldn't
53. 1:38shouldn't s of i shouldn't this be
54. 1:39survived
55. 1:40plus one isn't that isn't that right
56. 1:41does that make more sense well let's
57. 1:42think about it
58. 1:43let's say we're at the s of i minus
59. 1:44first iteration i went back and grabbed
60. 1:47it okay
61. 1:48rising edge of the clock presets low d
62. 1:50asserted
63. 1:51and now uh i'm now going to
64. 1:54grab s of i minus 1 and show s of i
65. 1:56minus 1. so now i'm holding it stable
66. 1:59so f of y minus 1 is being stable on the
67. 2:01s of y minus first iteration
68. 2:02it comes around instantaneously and then
69. 2:05x of i
70. 2:07changes to the next value of r the last
71. 2:10value of i
72. 2:11and so this is the final output
73. 2:15whatever that is this is s minus this is
74. 2:16like all but the last number let's say
75. 2:18that's what i mean okay let's say that's
76. 2:20the n
77. 2:20minus one maybe maybe n minus two here
78. 2:22but it's all but the last number
79. 2:24this then can change to the last number
80. 2:26and then this holds
81. 2:28the sum so really you're right that this
82. 2:30is s of i because as that last number
83. 2:32comes in
84. 2:33i'm holding all but the last number on
85. 2:34my s of i minus 1
86. 2:36x of i as the last number that would be
87. 2:38x of n minus 1.
88. 2:39and then boom this is now the final
89. 2:42value so that makes sense that this is s
90. 2:44of i
91. 2:44and this is s of i minus 1.
92. 2:47we want to think about the circuit
93. 2:49timing if we could take a look at this
94. 2:50you know as you see this
95. 2:52watch what happens it takes a little bit
96. 2:54of time this
97. 2:55s of i to s of i minus 1 is always going
98. 2:58to be
99. 2:59s of r minus s of i is sampled s of i is
100. 3:02sampled and that value
101. 3:06is then shown there always sampled
102. 3:10shown there sampled and shown there okay
103. 3:13so that's
104. 3:14that's pretty clear what that does then
105. 3:17there's going to be an adder delay okay
106. 3:20x is going to change we don't actually
107. 3:21know
108. 3:22whether x is synchronous or async x is
109. 3:24like basically hopefully a rhythmic
110. 3:26number but who knows where it is regard
111. 3:28to
112. 3:29the actual rising edges of the clock x
113. 3:31could be shifted all around there
114. 3:33so only after watch this x is going to
115. 3:36change okay i happen to draw this really
116. 3:38nicely let me clear this up
117. 3:40that i've got a new value of x just as
118. 3:43what's this
119. 3:43what's this device this this has s of i
120. 3:46minus 1 here
121. 3:49and x of i so i'm looking at this is the
122. 3:51adder between these two values
123. 3:53s of y minus 1 and x of i so when this
124. 3:57n and thankfully they both change at
125. 3:59exactly the same time
126. 4:00so now i have to wait t add before
127. 4:03that is seen on the output get it
128. 4:06x of i x of i as x is 0 x 1
129. 4:09this is now x of 0 plus x of 1 okay
130. 4:13and this is the output so that the
131. 4:15output is stable here
132. 4:16that's pretty cool now let's actually go
133. 4:18one more level of detail into this
134. 4:20let's actually really look at this and
135. 4:22this is fun to to do so
136. 4:23please feel free to do this on your own
137. 4:25grab the slides mark them up i encourage
138. 4:26you to do this you'll learn a lot
139. 4:28by the process i'm now including the
140. 4:30reset value
141. 4:31i'm including that i have no idea what s
142. 4:33of i minus one was
143. 4:35before i don't know what this what was
144. 4:36locked in hook i buy a register from
145. 4:39you know from fry's electronics who
146. 4:40knows what was stored into it i don't
147. 4:42even know
148. 4:42you know rented apartment who knows what
149. 4:44the condition of your apartment is going
150. 4:45to be when you before you open the first
151. 4:46door then you clean it up you reset it
152. 4:48now you've got a nice apartment it's
153. 4:49yours but when you get some used thing
154. 4:51who knows what was in there before
155. 4:52so i'm going to draw that as i don't
156. 4:54know what was here before okay
157. 4:56all right again we're gonna do the same
158. 4:58thing we did before but really slowly
159. 5:00okay so first let's put some numbers in
160. 5:02here here one two three four
161. 5:04all right my reset signal is shown let's
162. 5:07go
163. 5:07really slowly make sure we understand
164. 5:09what's happening okay
165. 5:11in practice x may not arrive to the
166. 5:14adder at the same time of s
167. 5:15minus one before a slide before like ah
168. 5:17let's make the ideal case they both
169. 5:18arrive at the same time
170. 5:20that adder may see it offset you don't
171. 5:21know when x comes in x is an
172. 5:23asynchronous
173. 5:24number so now by drawing them different
174. 5:26watch what happens this is the fun thing
175. 5:28here we go first thing ready who knows
176. 5:31what happened in the past who knows
177. 5:33where the register who knows the
178. 5:34condition i register
179. 5:35but i do know that at that first clock
180. 5:37what do i get
181. 5:38reset is high i'm going to ignore the
182. 5:40input s of i so i ignore that for that
183. 5:42time
184. 5:43and i reset it so boom i wait t clock to
185. 5:47q
186. 5:47and who is my output s of i minus 1
187. 5:50therefore
188. 5:51this reset controls that number and it's
189. 5:54reset to zero
190. 5:55okay so that's the first i got the first
191. 5:56there now it's stable at zero
192. 5:58so now what what's the next thing to
193. 6:01happen
194. 6:02well that's a zero and now
195. 6:06x i what's the next device this adder
196. 6:10has s of i minus one so s of r minus one
197. 6:13and x of i and this is the adders the
198. 6:14same place so these guys are going to
199. 6:16control oops
200. 6:18these guys are going to control what
201. 6:21happens
202. 6:21here so both of these control what
203. 6:24happens
204. 6:24there at the sovi output okay so
205. 6:29here is my zero here is my
206. 6:33this was a zero before okay so that i
207. 6:35have to wait t
208. 6:36add t add and i go and that value
209. 6:40after t add is available here zero zero
210. 6:43i'm going to right here but again i
211. 6:47don't know what this is this is zero who
212. 6:48knows
213. 6:48and now here's the key only at the next
214. 6:52time
215. 6:53right here there's my line
216. 6:57only at that time do i have a stable s
217. 6:59of i at zero a stable
218. 7:00new value of x of i and in a way i kind
219. 7:03of didn't care what was here
220. 7:05now i've got a stable x of 0 right there
221. 7:09after t add that's the time i have that
222. 7:11x of
223. 7:120 set on s of i so now
224. 7:15and by the way i hope that that has
225. 7:18stable
226. 7:19from t set up before the clock
227. 7:22through t hold after that's the
228. 7:24important thing and we're going to see
229. 7:24that a little bit more detail
230. 7:26and it happens to be in this picture why
231. 7:29do i care about that being stable
232. 7:30because this
233. 7:32this is being sampled right there
234. 7:36and that output is going right there
235. 7:38when is it going after clock to queue
236. 7:40okay so it's often useful to do this on
237. 7:42a graph paper where you can
238. 7:44and make it you know make like t clock
239. 7:45to queue one box as it's done here
240. 7:48t adders two boxes kind of play with it
241. 7:50a little bit and maybe make the clock
242. 7:52eight boxes or something so you can see
243. 7:53that's
244. 7:53really useful to draw this on a big
245. 7:55white board or graph paper okay so now
246. 7:58i've got a stable x zero now here's the
247. 8:00front here's the part that's really
248. 8:01interesting
249. 8:03there's my first value of s of i minus
250. 8:07one
251. 8:08x of i happens to be not synchronized
252. 8:11with
253. 8:11s of i minus one so now watch this this
254. 8:15is crazy
255. 8:17right here at this time right oops i'll
256. 8:20try to
257. 8:21i'll try to zoom in here so right there
258. 8:26i have what's on the input the input
259. 8:28this is the outer
260. 8:29the input of the adder folks is x is
261. 8:31zero and x is zero
262. 8:34i should never have two x's zeros in my
263. 8:36output and so watch what happens
264. 8:38after after right there
265. 8:41t add in this window that value
266. 8:45is x zero plus x zero a wrong value
267. 8:49my accumulator should never have that
268. 8:50should i have zero x is zero
269. 8:52x is 0 plus x of 1 x 0 plus x of 2
270. 8:54should never have x 0 plus x 0 but it
271. 8:56does for that exact window of time
272. 8:59okay because of this x
273. 9:02s of i is temporarily wrong
274. 9:05but because this circuit stabilizes
275. 9:08before it gets
276. 9:10sampled at the clock period it's on it's
277. 9:12temporary wrong for this window of time
278. 9:15those inputs are x zero plus x is zero
279. 9:18but at this time
280. 9:22now they're right now i've got an x 0
281. 9:24plus x of 1. and so
282. 9:26then that's the right value
283. 9:29okay and now
284. 9:32hopefully if the circuit is built right
285. 9:34what happens
286. 9:36that stable t set up before this
287. 9:40and stable t hold after and now i've got
288. 9:43x is zero plus x sub 1
289. 9:44and the right thing happens
290. 9:48so ask yourself what
291. 9:51happens if you ever overclock a system
292. 9:54overclocking system means you turn the
293. 9:56clock frequency up turn the clock
294. 9:58frequency up means you
295. 9:59shrink the period what starts to fail
296. 10:02well let's look at this circuit
297. 10:03as this i turn my clock frequency up as
298. 10:06my
299. 10:07yellow lines might start to shrink what
300. 10:10happens
301. 10:11well all of a sudden i'm starting to
302. 10:14violate something what's getting
303. 10:15violated why
304. 10:16why would this ever be in kind of a why
305. 10:19would they have a break this is going to
306. 10:20work perfectly as long as i have a nice
307. 10:22slow clock
308. 10:23clock frequency big all long period i'm
309. 10:25fine
310. 10:26this starts to fail when all of a sudden
311. 10:31that delay where it's stable here look
312. 10:34boom right here
313. 10:35s of i is stable but what if
314. 10:39this is the line for and it's a little
315. 10:41wiggly
316. 10:42for t setup well it's still good it's
317. 10:45stable before t setup
318. 10:47and all of a sudden as i'm making the
319. 10:49clock
320. 10:50period smaller and smaller now t setup
321. 10:52is getting closer and closer to when it
322. 10:54is stable
323. 10:55and when it just crosses that that's at
324. 10:58my problem point
325. 10:59so it turns out that it's the set up and
326. 11:01hold issue that causes
327. 11:03circuits to be wonky the circuit's not
328. 11:07to be stable um so that's the issue
329. 11:10it is that you start to infringe on my
330. 11:13setup to hold that was a rule we agreed
331. 11:15that's the rule you bought it it said
332. 11:16look
333. 11:17if you don't have a stable value on the
334. 11:19input of this flip flop
335. 11:21between setup setup time before the
336. 11:23clock rising edge of the clock
337. 11:24and whole time after i can't guarantee
338. 11:26what i'm going to do i may go into a
339. 11:28wheat i may have a
340. 11:29value of a half or whatever that means
341. 11:30whatever that means for the voltage is
342. 11:32there
343. 11:32i made wobble i may go into you know
344. 11:35defibrillated heart attack up and down
345. 11:37who knows i may
346. 11:38i may start ignoring my input and just
347. 11:40be i'll just hold this forever
348. 11:42who knows where the flip-flop is going
349. 11:43to break that starts to happen if you
350. 11:45ever have a changing value between
351. 11:47setup and hold and that's what starts to
352. 11:49happen as i turn this clock
353. 11:51cycle up and these yellow lines get
354. 11:52closer all of a sudden the delay before
355. 11:55it's stable before
356. 11:56i sample it now it's not stable anymore
357. 11:58i'm sampling a change value all of a
358. 11:59sudden flip-flop goes into a bad
359. 12:01situation that's exactly what happens
360. 12:03see so in good circuits
361. 12:06instability never happens around the
362. 12:08rising edge of clock time before
363. 12:10time after in bad circuits it does so
364. 12:12that's what starts to break as you
365. 12:14overclock systems you have this and by
366. 12:16the way it's okay
367. 12:17and in real life it's okay to have you
368. 12:19know the input to some
369. 12:20his register the input is registered be
370. 12:23some crazy
371. 12:24value but i don't care as long as it's
372. 12:26the right value
373. 12:27between set up and hold i've said the
374. 12:28same thing multiple times but i really
375. 12:29want to make sure i emphasize that
376. 12:30the critical thing is it's stable
377. 12:32between set up and hold and then i'm
378. 12:33good i don't care if it's actually
379. 12:35bad between it's all right to have x be
380. 12:36totally asynchronous in fact you can
381. 12:38even play with this
382. 12:39and how far can you move x to be
383. 12:40asynchronous be changing
384. 12:42until this stops working so all those
385. 12:44things are interesting thing we have
386. 12:45drawn in a way that it actually does
387. 12:46work but if i slide it the wrong way so
388. 12:47it
389. 12:48just is changing exactly right at the
390. 12:50wrong time if it's changing just so that
391. 12:52the adder by the time the adder delay
392. 12:54gets factored in all of a sudden it's
393. 12:56changing in there or how about this
394. 12:58then i would have trouble or if i turn
395. 13:00up t add if i make t
396. 13:01add bigger i turn it'll knob on t add i
397. 13:03buy a cheaper ti was
398. 13:05discount to the discount bin to get to
399. 13:07get the adder well now t add is bigger
400. 13:09because of that now that pushes in to
401. 13:10start impinging on my setup and whole
402. 13:11time so all those things affect this
403. 13:13circuit
404. 13:14but you could either turn this clock
405. 13:15cycle 2 up up too high
406. 13:17or have t add too high or even clock to
407. 13:19queue
408. 13:20clock to queue could have i mean
409. 13:21collector queue affects it as well so if
410. 13:22i make talk to q really big
411. 13:24it can start to impinge on its own the
412. 13:26clock to queue is part of the flip flop
413. 13:28it could impinge on its own set up and
414. 13:29hold as well as well depending how you
415. 13:31built those circuits
416. 13:32okay boy good stuff right good stuff all
417. 13:35right
418. 13:35that's the end of this lecture we'll see
419. 13:37the next one