YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 22.4 - Pipelining II: Data Hazards

[CS61C FA20] Lecture 22.4 - Pipelining II: Data Hazards — Transcript

by CS 61C Departmental · 2,149 words · 385 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01[Music]
0:11hello and welcome back to our pipelining
0:13module
0:14we are continuing to talk about hazards
0:17we have
0:18identified three types of hazards
0:21namely structural hazards data hazards
0:24and control hazards we have talked about
0:26structural hazards
0:28which are generally addressed by the
0:30data path design
0:32that identifies all the needs
0:36that that the isa presents
0:40so the data path is provisioned to
0:42support
0:43efficient pipelining
0:47data hazards are a little bit different
0:49and
0:50let's try to first understand them and
0:53then
0:54figure out how do we address them
0:59so we have talked about a structural
1:01hazard or
1:02of having to address the memory
1:06for both instructions and data
1:11there is a hazard also that affects the
1:13register file access
1:15so in there there may be instructions
1:18like this one add or there are
1:20definitely instructions like the add
1:22that writes the value into
1:26the register t0 that is going to happen
1:29during the write-back phase here when
1:31the register file
1:32is accessed so a register file
1:37well during the write-back phase is
1:38going to be
1:40accessed for writing that's why it is
1:42shaded
1:43on the left hand side now at some point
1:47an instruction like this one store word
1:51will be in the pipeline in the
1:54instruction decode phase
1:55when it will also
1:59wish to read the register file so the
2:02register file is going to be
2:04accessed for both reading
2:07and writing
2:11and it will happen that a ad
2:15instruction is going to be writing a
2:17value of t0
2:18while store would also like to
2:22read the t0 so will star instruction end
2:26up reading
2:27the the old value that is in there or
2:30should it read the new value as it's
2:32supposed to
2:34the answer to that is
2:37that the register files are designed to
2:39support single cycle
2:41read write operation what does that mean
2:45that means that the add instruction
2:49that we have here is going to write
2:52during the first phase of this cycle
2:54right back in complete
2:56writing in 100 picoseconds as
2:59we said before then in the remaining 100
3:03picoseconds of a 200
3:04picosecond clock cycle
3:08store word is going to read t0 out of
3:10the register file
3:15so this is very much dependent on the
3:17implementation
3:18on circuit and logic implementation of a
3:20register file that needs to support
3:22writing and reading in the same cycle
3:25that avoids this data hazard that
3:28happens
3:29during the register update so if that is
3:31true
3:32um right back we'll up the stage will
3:34update
3:35the value in the register and the next
3:37instruction that is accessing it during
3:39the instruction decode
3:40is going to get the new value and that
3:44that will be indicated in this diagram
3:47where we have the right backs the
3:51right back phase of the add shading the
3:54first part of the the left hand part of
3:57the register
3:59access and then the stored word shades
4:02the right hand side
4:03now keep in mind that this is certainly
4:06true for most of
4:08standard five stage pipelines but may
4:10not be true for some
4:11more complicated higher frequency
4:13pipelines
4:16we're not touching those for now they
4:19may be a subject of
4:20152 if you take that class but for now
4:24um just make sure that you clearly read
4:26the assumptions that are stated in any
4:28exam or midterm questions that you see
4:31do they permit
4:32simultaneous read and write in one cycle
4:34simultaneous
4:35meaning in this say case consecutive
4:38that the rate is completed
4:39before we want to read from the register
4:43all right but let's take a look at a
4:46little bit more
4:47complex data hazard and here it is
4:52let's say that the add instruction
4:55this time writes its result into the
4:58destination register as zero
5:00then we have this kind of a crazy code
5:02down here that
5:04perhaps doesn't make any sense i haven't
5:05really checked if it does anything
5:06useful
5:07but every subsequent instruction would
5:09like to use
5:10that as 0 as the source so the sub use
5:13it as a source this or use it as a
5:15source this xor uses the source
5:17and stored word uses the source so all
5:20these
5:22instructions depend on add 0 completing
5:26what it's doing and writing back the
5:28value into
5:30the register file but let's take a look
5:32at what is happening here
5:34let's say that the value of 0 you know
5:36starting
5:37when this ad the instruction started its
5:40execution was five
5:42and it stays five and at this point the
5:45alu result
5:46is nine and this nine is supposed to be
5:48written back into a register file
5:49but that doesn't happen until
5:53mid through the right backstage of add
5:57so we still have five during the
5:59execution stage of the ad
6:02and the memory access stage of the ad
6:04instruction
6:05and for the first half of the
6:08right back stage so if the next
6:11instruction would like to use that
6:13when it goes to the register fetch
6:16stage to the register um
6:19to retrieve the values from the
6:21registers during the instruction decode
6:23stage what is it going to find
6:24five that's the wrong value that
6:28is not going to be good what is the or
6:31instruction going to find in the
6:33register file also five
6:35that's a problem now this xor is going
6:39to do better
6:40because nine is going to be available
6:43in the second five phase of
6:47the instruction decode
6:50when it is going to be read correctly
6:52and store word is also going to find the
6:54correct value
6:55now what are we going to do with these
6:57sub and or they are going to get
6:59incorrect values
7:01from the register file
7:05we need to do something otherwise we are
7:07executing an incorrect problem
7:09incorrect program so the first solution
7:12is so-called stalling what installing is
7:14like when you have an old car and you
7:16know you
7:17you you drive a lot and you stall and
7:20then you start again
7:21and you drive a little bit and stall
7:25so that's how your program would
7:26actually execute with the stalling
7:28um when the result of
7:33when the next instruction
7:36depends on the result of the previous
7:38instruction we cannot start its
7:40execution until the result is written
7:41back
7:42so if the sub follows the add
7:46the sub execution needs to be delayed by
7:48two cycles by inserting
7:50two bubbles in between these bubbles are
7:54essentially knobs
7:55that are going to correctly help
7:57correctly align
7:59the register right back stage with the
8:02register read
8:05the bubbles are perhaps
8:08not the most useful thing that is out
8:12there
8:13because during that time processor is
8:15doing nothing
8:17um although the reason you know we
8:19accomplished the main thing
8:21to get the right result the correct
8:23execution of a program
8:25what may happen is that we are going to
8:28lose performance
8:29now compilers generally try to do
8:31something to avoid that
8:33so you'll go through our list of
8:35instructions that are following that ad
8:37and try to find something some
8:38instruction it is not dependent on the
8:40result of that ad
8:41and it is going to try to swap that sub
8:44with the instruction that does not
8:45depend on the result of the ad
8:47so that way we are not going to lose any
8:49cycles
8:50but in case it can't find any
8:54instructions
8:55we have to install insert these knobs
8:57which will cause stalls
8:59such that we can correctly align the
9:03register read with the register right
9:06this knob is anything that writes into
9:09the x0
9:10by convention in risk 5 assembly
9:14knob is add immediate x 0 x 0 0.
9:20all right the second solution is
9:23a hardware solution that we need to
9:26implement
9:27by modifying the data path here is the
9:30thing
9:32when this ad instruction is
9:35at the end of its execute phase we have
9:37the value somewhere in the pipeline
9:39that is correct that is a correct value
9:41that should be read
9:43by the register files by by
9:46instructions sub and or from the
9:48register file
9:49but that value is not in the register
9:52file yet
9:52it is somewhere in the pipeline but it's
9:54not in the register file
9:56so the idea here is to take that value
10:00from the alu or a cycle later
10:04from the memory access
10:08stage and forward it to the appropriate
10:13input port of the alu so we'll take
10:17this output of the alu and
10:21essentially fast forward it to the input
10:23of the alu for the sub instruction
10:25and then sub is going to perform
10:27correctly sub is executing in the next
10:29cycle
10:29and we just need to make sure that this
10:31shows up straight at its input
10:34similarly um that result is going to
10:37propagate in the next cycle to the
10:39output of the
10:40uh to the end of the memory access phase
10:42and we would need to forward it
10:44to the input of the alu to correctly
10:46execute the or
10:48all right so we need to have these
10:50forwarding or so
10:52called bypass paths in our data path
10:55to enable data to be forwarded to the
10:58right place
10:59without being written to register file
11:01it's going to get
11:02written in the register file but this is
11:04just for the
11:05subsequent instructions to use use the
11:08result immediate
11:09immediately so
11:12um you know this is basically outlining
11:16what we need to do
11:17we need to basically have a short
11:19circuit a sort of a short circuit
11:21between the output of the alu here and
11:24the input
11:25of the alu
11:29that is something
11:32that is relatively straightforward to
11:36implement you you guess that there will
11:38be a multiplexer another multiplexer
11:40that is going to be sitting in front of
11:42the
11:46or together with the cell a operand
11:50by the way the forwarding here is just
11:51shown for the operand a to the alu we
11:54also need to forward
11:55the operand b
11:59now what do we need to control this
12:02forwarding this there will be a
12:03multiplexer and we need to somehow
12:04control that multiplexer so what kind of
12:06information do we have
12:08that is going to help us with that
12:09remember we
12:11our data path saves the instructions
12:13that are currently in flight so we'll
12:15know which registers are being accessed
12:17by the two consecutive instructions so
12:18what we need to do here
12:20is we need to take a look at
12:23the instruction that is the destination
12:26of this instruction that that is in the
12:28execute stage
12:30and compare it with the instruction that
12:33is
12:33in the instruction decode stage if
12:36they're the same
12:37and not take zero then we have a hazard
12:40we have a data hazard and we should
12:43forward
12:45right so we just compare those two and
12:47that is going to select our multiplexer
12:51uh forwarding multiplexer we are going
12:53to have the same comparison
12:55between this alu and between this
12:58alu and the right and memory access
13:01stage
13:02to allow us to forward again there so
13:05what we are seeing here the the
13:07multiplexer that selects the operand a
13:09is going to have its two standard values
13:12you know pc
13:13and the register file output and then
13:15they're going it is going to have two
13:16more forwarding paths
13:19um let's take a look at how this
13:22is this implemented in the data path
13:24this is our pipelined
13:25rv32i data path all the registers are
13:29where they're supposed to be
13:30so what we are what we did here we added
13:33these two
13:34forwarding paths the forwarding paths
13:36are not really in this picture
13:38uh shown that they're going forward they
13:40look like they're going backward
13:41but actually the they're going forward
13:44to the the execution of the next
13:46instruction they're bypassing in
13:48for the in in for the next instruction
13:51in this case
13:52from the output alu back to the input
13:55of the alu after one cycle delay
13:58and then after two cycle delays from the
14:02right back
14:02right back stage back to the input of
14:04the aldu
14:06and that is it all what we need to do is
14:08to implement the forwarding control
14:10logic
14:10this one is shown to be working only
14:13just
14:14on this multiplexer forwarding
14:17um you know comparing the the
14:21the registers that are being used in
14:23these two instructions that are in
14:25flight
14:25that are in the instruction decode in
14:27the execute stage we would need to make
14:30we need to control uh to figure out what
14:32is in instruction decode
14:34and the memory access and repeat all of
14:36that
14:37for the operand b as well and that is it
14:41that is the story of the forwarding the
14:44best thing here is to
14:45look at a few code examples and see
14:49when the forwarding is needed and
14:51implementation is
14:52relatively straightforward we're going
14:56to break here
14:56we are going to return to the control
14:59hazards
15:00after the break see you then

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 22.4 - Pipelining II: Data Hazards by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,149 words across 385 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.