YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 19.3 - Single-Cycle CPU Datapath II: Implementing Branches

[CS61C FA20] Lecture 19.3 - Single-Cycle CPU Datapath II: Implementing Branches — Transcript

by CS 61C Departmental · 1,899 words · 346 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01[Music]
0:09welcome back to s5 cpu design
0:11we have designed more than 50
0:14of a data path or much more than 50 of
0:16the data path
0:18so far by adding instructions that we
0:21needed for
0:22our type i type and s-type instructions
0:25now we are going to
0:26add support for the branches which are
0:28slightly different
0:31remember branches what do branches do
0:34they compare the contents of the
0:36registers rs1 and rs2
0:39and depending on the condition of a
0:41branch
0:42update the program counter so if the
0:45branch condition is met
0:46the program counter is updated to a new
0:50address
0:50that is specified by as the offset
0:55immediate to the current
0:58value of the program counter if the
1:00branch condition is not met
1:03then it goes to the next instruction
1:05which is four bytes away
1:08instruction encoding for b types for
1:12b format encoding is similar
1:15to the s format except that the
1:18immediate now
1:19uses those 12 bits to encode
1:22a 13 bit range the last bit is
1:25always zero because we try to use this
1:29range to represent values of minus four
1:32thousand ninety six
1:33to plus four thousand ninety four in
1:36two by ten increments
1:41let's see how does our data path
1:44look like so far so we
1:47have our program counter that so far has
1:50ability only to be updated
1:52to the next instruction which is four
1:54bytes away we'll need to do something to
1:56that
1:56to enable this other update uh based on
1:59the outcome of the branch
2:00we have the instruction memory register
2:02file immediate
2:04computation alu for execution and the
2:08memory
2:10when we are looking at branches we
2:12clearly
2:13don't need to work with the memory so we
2:16will not be
2:16writing or reading anything from the
2:18memory we are also not updating the
2:20register file so
2:22a lot of that part of the data path will
2:25not
2:25be lit up but we need to do two things
2:29simultaneously for which we'll need
2:31resources
2:32we need to perform the branch
2:34computation and
2:36a branch condition evaluation and
2:39computation of the new address
2:42so in order to add branches we need to
2:45look at
2:46what functionality we need to have in
2:48our data path
2:50so the state changes not now by
2:53changing the contents of the registers
2:55or the memory
2:56this change of state is by changing the
2:59program counter
3:00problem counter takes two values after a
3:03completion of a branch
3:04it either is pc plus 4 or it is
3:07pc plus immediate or this immediate is
3:10of a new type
3:11is of the s type there are six different
3:14branch instructions
3:16bq and e blt bg and bgltu bgeu
3:21the last two being unsigned versions
3:24of the blt and bge
3:27that essentially evaluate conditions
3:30whether
3:31the contents of rs1 and rs2 are equal to
3:35each other
3:35not equal to each other less than
3:38greater or equal
3:39and so on so what does our data path
3:43need to do
3:44it needs to evaluate the
3:48the contents the the the contents of
3:51rs01 and rs2
3:54needs to compare them and then needs to
3:56compute
3:57pc plus the immediate but we have only
4:00one alu
4:01that we have been able to use so far uh
4:04so we need to add more hardware now you
4:06may want to think where
4:07which additional hard what should the
4:09additional hardware do
4:11should it be used to calculate pc plus
4:13immediate
4:14or to perform the comparison well we
4:16have a powerful alu that can do all
4:18kinds of things
4:19so let's not mess with that and it is
4:21already wired to
4:23calculate to take on the immediate
4:26so let's not touch that what we
4:29should add is a simpler hardware that is
4:32going to perform
4:34the branch comparison
4:37so let's take a look at how do we modify
4:40the data path
4:42here is our new data path it got a few
4:46new additions most notable one
4:49is that we have a multiplexer in front
4:52of a program counter that enables us
4:54to write either pc plus 4 or
4:57the new address then we have a
5:02a little bit bigger piece of hardware
5:03that does the branch comparison
5:06it takes one input whether the branch is
5:09signed or unsigned
5:11and produces two single bit outputs
5:15is if the values are equal or less than
5:19than each other and then we have one
5:21more multiplexer here in the data path
5:24this multiplexer enables us
5:27to feed to the a port of the alu the top
5:30part of the alu
5:31either the rs1 contents which is what we
5:34did before
5:36or the program counter so we are going
5:39to
5:40use the alu to add
5:43the immediate value to the program
5:47counter
5:48and we are going to take that output and
5:51write it back
5:52into the program counter
5:56there are a few things here additional
5:58things that need to
5:59happen we need to set the immediate
6:03select to
6:04the branch type of intermediate we meet
6:06that means we need to
6:07generate yet another type of an
6:09immediate in addition to ins type of
6:11immediates
6:12then we need to control the branch
6:15comparator
6:16with whether it's signed or unsigned
6:21based on decoding of the instruction and
6:24then we need to
6:25control this multiplexer as well in
6:27front
6:28of the a input to the alu
6:31what is inside the branch comparator
6:33well it is
6:35a piece of logic that compares the
6:37values that are in rs1 and rs2
6:40fairly straightforward and not very
6:43difficult to
6:44implement in logic
6:48notice that we are supporting
6:51six different branches two of them being
6:53variants of each other signed or
6:54unsigned
6:57but we have only two possible outcomes
7:00so
7:00out of these four basic types whether
7:03something is
7:03equal to other or less than we support
7:07the other ones
7:08directly because branch
7:12if greater or equal is exactly
7:15the opposite of branch on
7:18less than so if we just negate the
7:21output of
7:22branch on less than we get
7:26branch or if greater than or equal
7:29so that is it we have therefore
7:33one input single bit control and two
7:36outputs out of a branch comparator
7:41the other uh kind of important thing to
7:45to mention about branches
7:48and in encoding of immediates
7:51in b types is it's
7:55the difference of risk five from some
7:56other isas in other isas
7:59what you will find out is that the
8:01immediate value is
8:04the whole immediate value is shifted by
8:06one bit
8:08in the instruction encoding which
8:12requires us to use a multiplexer
8:15to you know a bunch
8:19a wide multiplexer that shifts
8:22left or right the what we would like to
8:26pick as an immediate from
8:28the instruction so
8:32there are 12 inputs to a multiplexer
8:35that produce 12 outputs but all of them
8:38are occupied
8:39risk five does it a little bit
8:40differently it keeps
8:42most of the immediate values 11 out of
8:4512 immediate values
8:47in the same place as what we have had in
8:50the s format and just moves
8:53one immediate value that's the rationale
8:56that we
8:57you know why we have that kind of an
8:59encoding that looked a little bit
9:00strange
9:01early on but as a result now we just
9:03need
9:04one multiplexer with two inputs
9:07to move that bit to the right position
9:11between the two formats so s immediate
9:14and b immediate are very similar to each
9:16other
9:16all we need to do is to place
9:19the eleventh immediate in the right spot
9:24please just take a look at that and
9:26convince yourself that this is true
9:29so just to recap immediate encoding we
9:32have
9:33seen three types of immediate so far i
9:35type
9:36as type and b type they're very similar
9:39to each other
9:40and when we produce the actual immediate
9:43that is
9:4431 bits 32 bits
9:47wide out of a 12 12-bit
9:50value that is encoded inside the
9:52instruction we
9:54do that in a similar fashion so
9:58we always sign extend the bottom parts
10:02between i immediates and s immediates
10:06are um are different
10:09so it's a one two-way multiplexer that
10:11we have seen before
10:12um and the b immediate shares the same
10:17idea the instructions
10:2030 to 20 firing the instruction bits 30
10:23to 25
10:24are in the same position instruction
10:26bits 11 to 80s are in the same position
10:28we just move the instruction bit 7
10:32to a different position so it's again
10:34one
10:36single bit two-way multiplexer
10:39and we always sign extend based on the
10:42most significant bit
10:46let's just light up the branch path and
10:49that will let us allow us to wrap up the
10:52discussion about the branches
10:54when so here is what happens in
10:58uh in when we're executing a branch
11:00instruction it is a little bit different
11:01than the instructions that we have seen
11:03so far well first fetch an instruction
11:07by pointing the program counter to
11:09instruction
11:10memory then
11:14we will point you know we will
11:18fetch that instruction and instruction
11:19will address appropriate fields
11:21in the register file we only care about
11:24the two source registers
11:26we don't care about the destination
11:27register and therefore
11:30register write enable is going to be
11:32disabled
11:33we also start implement
11:37the immediate generation through
11:40you know sign extension but not is this
11:44we prepare the next value of the program
11:47counter first
11:48we increment it by 4 because we may
11:52take that value or
11:55we send the program counter downstream
11:58to the alu we don't know what is going
12:00to be the outcome of the branch
12:02until we perform the comparison so we
12:05set the control
12:06here to be
12:10to correspond to that branch so
12:12immediate select is a b
12:14register write enable is zero um
12:17we send also a signal
12:20to the branch comparator should we
12:24have um unsigned or signed comparison
12:27um set the appropriate inputs uh
12:31to the to the multiplexers alu is still
12:33going to do the addition
12:35of the this time of a program counter
12:37value
12:38with the immediate and memory is going
12:41to be set to read
12:42we are not going to write to it we don't
12:44want to even accidentally write to it
12:46and we are going to disregard any output
12:49that might come out of that
12:53the next thing in in execution is
12:56we are going to get the outputs of the
13:00two registers rs1 and rs2
13:04we are going to perform branch
13:05comparison the output of a branch
13:07comparison
13:08is going to tell us what to do where
13:11does
13:12the pc go which is the next value of the
13:14pc that we need to
13:15take um alu is going to
13:20add the the immediate
13:23offset to the current value of the
13:25program counter
13:27and bring that over
13:30to the input of the multiplexer that is
13:32sitting in front of the program counter
13:34based on whether the branch is taken or
13:37not
13:38we update the program counter and that
13:40is it
13:41that completes the branch that is the
13:44only state
13:45that is being updated after quite a bit
13:48of lighting up of the data path
13:55this is it that we need to know
13:58about the branches we have added the
14:00data path that supports the branches
14:03and we'll see that we actually
14:06have now a huge majority of what we need
14:09to
14:10implement the rest of the instruction
14:12formats
14:13so we'll do that after a break

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 19.3 - Single-Cycle CPU Datapath II: Implementing Branches by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 1,899 words across 346 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.