YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 20.3 - Single-Cycle CPU Control: Instruction Timing

[CS61C FA20] Lecture 20.3 - Single-Cycle CPU Control: Instruction Timing — Transcript

by CS 61C Departmental · 3,009 words · 545 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01[Music]
0:09hello
0:10and welcome back to the rest 5 cpu
0:12design module
0:13we have designed a configurable data
0:15path and
0:16we have outlined the logic control logic
0:20that sets up the data path to execute
0:22pretty much every instruction that we
0:24have in the rp32i
0:26base instruction set in that process we
0:29have
0:29figured out that there is a lot of stuff
0:32that happens concurrently
0:33in both data path and the logic for
0:37example
0:37while we are retrieving an operand from
0:40the register file
0:42we are generating the immediate as well
0:46concurrently we've also
0:49gotten some sense for the timing timing
0:52is
0:53very important um obviously these
0:57this logic that implements the data path
0:59and the control
1:00takes some time to complete
1:04and that critical path the longest time
1:08that it takes us to execute
1:09an instruction in a data path sets how
1:12frequently we can
1:16operate around the clock on this
1:18processor and sets how many instructions
1:20we can
1:20run per second we have gotten
1:24only qualitative sense for timing so far
1:28so we're going to try to make it a bit
1:31more quantitative
1:33in this section so to do that
1:36let's examine our well-known data path
1:38that we've had before so this is the
1:40same pictures
1:41as we have had before along with the
1:44control
1:44module below it and we'll execute
1:48a very familiar instruction which is a
1:51register based ad
1:54this instruction runs like every single
1:56one every
1:57single one that we have already seen
2:00running on this data path
2:02it starts the execution on the rising
2:04edge of a clock
2:06that's when we update the program
2:07counter the new value of the program
2:09counter appears
2:10at its output and there are two things
2:13that happen concurrently
2:15we add four to it and we fetch
2:18the instruction from the instruction
2:20memory those two processes
2:22are will take about a comparable amount
2:26of time i wouldn't say
2:27the same amount of time which one is
2:30going to be longer
2:31it really depends on the technology that
2:33we implement
2:34this in
2:38so we are going to have
2:41a new value of pc plus 4 ready
2:44at the input of this multiplexer but the
2:47correct value is not going to be
2:49present in front of the pc until we have
2:52the value
2:53of pc cell settled
2:56so concurrently with that we will fetch
2:58the instruction from the instruction
3:00memory and when that signal
3:02appears we have completed the phase
3:04first phase of this
3:05execution which is the instruction fetch
3:08now at that moment two other things are
3:12going to happen concurrently
3:14we will start the process of
3:17retrieving the values of the source
3:19registers rs1 and rs2 from the register
3:21file
3:22and we will start decoding the
3:26instruction
3:26as we decode the instruction we'll
3:28figure out that it's an add
3:30that add will tell us that
3:33we should set the pc cell to pick the
3:36top
3:37input from this multiplexer right there
3:40that the immediate select
3:44control should be a donk here because we
3:47don't have an immediate in this
3:48instruction register write enable
3:51should be set to one because we do have
3:52to write the value
3:54of the addition back into the
3:56destination register of a register file
3:59all branch signals are donkeyers a
4:02select and b select are both zeros
4:03because we are selecting the outputs of
4:06the outputs of the register file
4:10alu select is set to add memory read
4:12write is set
4:13to read because we are not writing to
4:15the memory and right back select is set
4:17to one such that we will be writing back
4:19the alu value
4:20as soon as the signal pc cell settles
4:24we will have a valid output
4:28of that multiplexer set at the input of
4:31the program counter but the new value
4:32into a program counter is not going to
4:34be written
4:35until we
4:39complete the cycle and set up the next
4:44rising edge of the clock
4:47what you see here is that this path is
4:50shorter than the one that is going to
4:54happen concurrently there is way more
4:56blocks
4:57downstream let's see what is happening
4:58downstream
5:00so we are still in the instruction
5:02decode phase it will complete at the
5:04moment when we get the valid outputs
5:07of the register file from the register
5:09file
5:10so the register file read completes the
5:14instruction decode
5:16phase of execution then we proceed with
5:19the execute phase during that we will
5:22go through these two multiplexers there
5:25are two multiplexers but
5:27both propagation delays are happening
5:29concurrently
5:30so we only count for one propagation
5:32delay they there
5:33and then we go through the alu delay
5:36and we have completed the execute phase
5:40so three phases are done there is no
5:42memory access phase
5:43when we are doing register based ad so
5:45we are proceeding to complete
5:47the write back right back doesn't have
5:49much here
5:51there is only one multiplexer in the
5:53path and
5:55we have data ready to be written back
5:58into the destination register
6:01it will be written on the next rising
6:04edge of a clock
6:05but keep in mind that this input
6:08into the register rd has to be stable
6:12setup time before the rising edge of the
6:14clock
6:15so that has to be accounted for into the
6:17delay
6:19so on the next rising edge of a clock
6:21we'll update both the destination
6:22register and the program counter let's
6:24take a look at the timing diagrams
6:26that describe this in a bit more detail
6:28and describe more of this concurrency
6:30of operations that are happening during
6:32the execution of the instruction
6:34so this is the same data path that we
6:36have seen before we are just
6:37annotating signals and the timing
6:41clock signal has its high and low values
6:45each one clock cycle corresponds to
6:48the time from one rising edge of a clock
6:50to the next rising edge of a clock so we
6:52have
6:53a total of two clock cycles in
6:56this diagram two complete clock cycles
6:58in this diagram
7:00um we are going to show what we have
7:04at the output of a program counter at
7:06the output of a program counter
7:08we have a bundle of 32 wires we are not
7:11going to show these
7:1232 wires individually like we haven't
7:16we're going to use a shorthand notation
7:17that we've introduced before
7:19we're going to show them as a bundle and
7:22we are going to associate a hexadecimal
7:24value with that bundle
7:26in this case let's say the program
7:27counter has a value
7:29of one zero zero zero hex
7:33the value
7:37at
7:40the output of the program counter
7:45is valid after the propagation delay
7:48that is equal to t
7:50clock to q
7:54and all 32 outputs of that
7:57program counter are valid at the same
7:59time
8:00now two things are happening
8:02concurrently we're
8:04fetching an instruction from the memory
8:06and the
8:08we're updating the program counter
8:12incrementing the program counter the
8:14value of pc plus 4
8:16gets stable gets updated after
8:19a propagation delay through that adder
8:22but there is one important difference
8:24here while
8:26when we are updating pc on the rising
8:29edge of a clock
8:30all of those outputs
8:33changed at the same time after clock to
8:35output delay
8:36because all of them go through the same
8:39type of
8:39flip-flops or the same flavor of a
8:42flip-flop
8:44these pc plus four outputs are
8:47not going to show up all at the same
8:50time
8:51the least significant bits of addition
8:54become
8:55stable sooner than the more significant
8:59bits
8:59so we're going to have multiple of these
9:01crosses in these diagrams we're always
9:03showing the last transition
9:05which is the one that is going to be in
9:07the critical path
9:09so after the propagation delay of the
9:13most significant bit the pc plus 4
9:16is the new value and at the same time
9:19we are proceeding with fetching the
9:21instruction
9:23the instruction is going to show up at
9:26the output of the instruction memory
9:28and it's also going to have 32 bits here
9:31we are using annotation where we
9:34this uh assemble that instruction and
9:37find out that it is an ad instead of
9:39showing 32 bits here we show it's an ad
9:41that adds extra contents of x2 and x3
9:44and stores it in x1
9:46propagation delays are comparable to
9:50the other delays now control logic
9:54is going to follow that at this moment
9:57when the
9:57instruction has been read from the
10:00memory we have finished the instruction
10:02fetch
10:04phase of execution so this is our
10:08instruction fetch we are proceeding with
10:12the next phase
10:13which is instruction decode control
10:16logic
10:17does a part of that and sets the
10:20control bits you know reading
10:23the registers register values takes
10:27usually
10:27longer time than that and when they
10:31those outputs are stable
10:33we have completed the sixth second phase
10:37of execution which is
10:40instruction decode
10:43then we perform the alu operation
10:48and at that point we have completed
10:51the execute phase finally
10:55we are ready to write
10:59the result back into the register file
11:05there is a short delay between the alu
11:07and
11:09and the point when the write back signal
11:11is stable that corresponds to
11:13this final multiplexer delay but one
11:16thing
11:16that we have to keep in mind we cannot
11:20have the next rising edge of a clock too
11:23early otherwise we will be violating the
11:25setup time
11:25so we have to respect the setup time
11:28before this
11:29rising edge of our clock tsu
11:33so this last transition
11:36out of the from the right back signal
11:41cannot come after the setup time of
11:45the register in the register file so
11:51we are going to write the correct value
11:53into the register so register one
11:55gets a new value that is the sum of the
11:58contents of register two
11:59and register three and notice that both
12:04program counter and the register file
12:08are updated at the same time
12:11clock to queue delay after the rising
12:14edge of a clock
12:16hopefully this was clear
12:19let's take a look at you know if we can
12:21quantify this
12:23timing what we said there are
12:26two things that are happening
12:28concurrently and
12:29we are assuming here that the control
12:32logic definitely takes
12:34shorter time than the time that it takes
12:37us
12:38to retrieve the data from the register
12:40file
12:41so there are two loops that set the
12:43timing
12:44one that involves the propagation delay
12:47from the program counter
12:48through the other and the multiplexer
12:50and comes back to that program counter
12:53that that delay path equals to clock to
12:55output delay of the program counter
12:58plus time to add time to propagate
13:01through the multiplexer and then has to
13:02meet the setup time
13:04of that program counter
13:08the other path is clearly longer it's
13:10the yellow one
13:11in the yellow path we go through the
13:14clocked output delay of the program
13:15counter
13:17access time for the instruction memory
13:19access time for the register file
13:23multiplexer alu delay another
13:26multiplexer and then we again have to
13:28meet the setup time but
13:29not of the program counter the setup
13:31time of the
13:33register file so we can write correctly
13:36the value into the
13:40rd so those two if you just
13:44compare these two terms these two
13:46equations
13:47it turns out that the max of these two
13:50is always going to be um i
13:54i t i mem t reg t max t
13:58l u plus another t max so
14:01the critical path here is the pathways
14:05execution
14:06not update of the program counter
14:12okay this instruction had only four
14:15phases of execution let's take
14:17a look at an instruction that has five
14:19phases of
14:20five phases of execution which is load
14:23word
14:23or lw so in that case it works
14:28exactly the same way that the extraction
14:31is executed as all the others
14:33on the rising edge of a clock we update
14:34the program counter
14:38and the new value appears at the output
14:40of a program counter
14:41then we have two simultaneous
14:44paths that get exercised we go through
14:47the other
14:48and update the value of a program
14:50counter and fetch a new instruction
14:52then we start decoding that instruction
14:55we set the control bits appropriately
14:57pc plus 4 is
15:00what is bc cell set to immediate select
15:05is set to
15:08be of a type of i immediate because
15:12loads are of immediate of uh i types
15:16register write enable is set to one
15:18because we're going to write
15:19back the result um from the that we
15:23retrieve from the memory uh all branches
15:25are set
15:26to don't cares a select is zero
15:29to take rs1 and b select the set
15:32to one to take the immediate alu adds
15:35those two together
15:37memory read write is set to read because
15:39we're actually this time reading
15:40the memory and right back select is set
15:43to zero
15:44such that we send the memory
15:47output to be written back into the
15:49destination register
15:51we proceed with executing this
15:53instruction so since
15:56the pc 4 is ready
15:59early on as soon as pc cell signal is
16:03ready
16:04we'll write a new value into the program
16:06counter
16:09now two other things happen concurrently
16:12and they start while we are decoding the
16:15instruction
16:16first the output
16:19we read we access the register file
16:23and we get the rs2 rs1 at its output
16:27simultaneously we also generate the
16:30immediate
16:31it is not clear which one of these two
16:33is going to take longer time
16:35because if you remember the immediate
16:37generation depends
16:38on the coding of the instructions so we
16:40need to know that this is an i type of
16:42intermediate in order to
16:43generate the correct correct immediate
16:46so that delay tends to be
16:48comparable to the delay of retrieving
16:50the data
16:51from the register so then the rest is
16:55similar to what we have seen before this
16:58completes the instruction fetch
17:02instruction decode phase instruction
17:04fetch was completed with the
17:05access of to the instruction memory this
17:08completes the
17:09instruction the code phase
17:12then we go into the execute phase that
17:15one is completed
17:16when the output of the alu is valid with
17:19the address that points to the memory
17:21we go through the memory access phase
17:24and
17:24finally we write back the result of that
17:28into the destination register
17:31now we have three possible parts that
17:34uh could be critical one is this one
17:36that we have already figured out that
17:38this short
17:38this uh um founders
17:41rock is the name of this color it's a
17:43berkeley color
17:46is definitely a shorter path than either
17:48one of these two and these two other
17:50parts
17:51are almost the same they just differ in
17:54the delay
17:55of the register file axis versus the
17:57immediate generation
17:58delay so in both of those cases
18:02we go through the instruction memory
18:07then either the immediate generation
18:12or the register file followed by a mux
18:15alu data memory and another multiplexer
18:19we have to add clock to queue delay of
18:22the program counter that launched the
18:23instruction
18:24and the setup time of the register file
18:28that needs to be met in order to
18:29correctly write back the result
18:33when that is done we can write back
18:36right complete this instruction right
18:38back into the
18:39register and update the program counter
18:43a little bit more conceptual timing
18:45shows what we have seen
18:47already in the previous few slides here
18:50is
18:51showing what is happening during one
18:53clock cycle
18:54pc gets updated and
18:58instruction fetch completes
19:01the first phase of execution the time
19:04that it takes here
19:05is some time that corresponds to
19:07instruction fetch
19:09then valid outputs
19:13at the output of the register file
19:15complete the instruction decode phase
19:17of execution then alu stabili output
19:22finishes the execute phase
19:25stable memory
19:28output completes the memory access phase
19:34there is very little logic that is
19:37in the right back phase so we have to go
19:40through that
19:42by piece of logic and make sure that we
19:46meet the setup time of whatever we are
19:49writing back into
19:51before the next rising edge of the clock
19:55if we put some numbers to it instruction
19:58fetch say takes
20:00200 picoseconds until we get
20:03the results out of the instruction
20:04memory and that then
20:06takes another 100 picoseconds to read
20:08the registers
20:09to complete the instruction decode alu
20:12say takes 200 picoseconds and completes
20:14the execute phase
20:16data memory say takes 200 picoseconds to
20:19get the data and complete the memory
20:21access phase
20:22and finally write back says takes a 100
20:25picoseconds that includes that setup
20:27time
20:28the total time is 800 picoseconds
20:32to execute this instruction
20:36one thing that is worth noting
20:40is that not all the instructions go
20:42through every single phase so some of
20:43them are going to be done sooner some of
20:45them are going to be done later
20:46we always have to take the worst case in
20:48this case the worst case is
20:51load word add only goes through four
20:54phases as we have seen before
20:56instruction fetch instruction decode alu
20:59or
21:00execute and write back so that takes
21:03only 600 picoseconds
21:04branch of equal goes only through three
21:06phases
21:08and so on um load word is the longest
21:11one takes 800 picoseconds
21:13how fast we can clock that well we can
21:16clock it
21:17at maximum clock frequency
21:21that is 1.25 gigahertz
21:27should be noted that we were if we're
21:31somehow able to clock this data path so
21:35we can execute
21:36just one piece of it we
21:40would have been able to run this at
21:44the frequency that corresponds to the
21:48longest delay of each execution units
21:51of each of the units that are in the
21:53data path so perhaps we could run this
21:55at five gigahertz we can't do that
22:00because we can't just execute some
22:02instructions and not the others
22:04or just perform the addition and neglect
22:06everything else
22:07but we are going to see how we can
22:08benefit from that a bit later i'll
22:12take a quick break now and be back in a
22:15second

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 20.3 - Single-Cycle CPU Control: Instruction Timing by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 3,009 words across 545 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.