YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 23.1 - Pipelining III: Load Data Hazard

[CS61C FA20] Lecture 23.1 - Pipelining III: Load Data Hazard — Transcript

by CS 61C Departmental · 1,998 words · 373 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01[Music]
0:12hello
0:13and welcome back to our pipelining
0:14module
0:16so far we have studied the principles of
0:19pipelining
0:21and then moved on to analyze hazards we
0:24have seen
0:24that we generally deal with the
0:27structural hazards by adding enough
0:30hardware such that we can
0:31execute multiple instructions in the
0:34pipeline
0:37then we moved on to study the data
0:41hazards
0:42that stem from the
0:45fact that the or the condition that
0:49the following instruction depends on the
0:52results
0:52of the previous instruction that is in
0:54the pipeline
0:57let's take a look look at that you know
0:59let's
1:00revisit that such that we understand how
1:02we dealt with that
1:03by using forwarding so in this case we
1:06had the instruction
1:07add that was in the pipeline already and
1:10then there was a sub
1:11instruction that was following it and
1:14used
1:15the result that was stored in a
1:18destination register as 0
1:20as the source for that
1:23following instruction and then
1:27the instruction after that also used as
1:30zero
1:31as the source register
1:35so as the ad instruction is
1:38traveling through a pipeline so it's
1:39five stages of pipeline
1:42although the result of the
1:45execution of this edition is known um at
1:48the end
1:49of the execute stage it is not written
1:52back
1:52into the register file until
1:56two stages later until halfway through
1:59the right backstage
2:01so the value of s0 still is the old
2:05value
2:05of 5 in this case it gets updated to a
2:08new value
2:09that is 9 in the first
2:13phase of the write-back phase
2:16so if the sub-instruction that follows
2:20the add instruction
2:21reads the value from the register when
2:23it's supposed to be
2:25during the instruction decode phase it
2:28would
2:28read the wrong value which is 5
2:31the old value instead
2:35we deal with that by forwarding
2:39the new value and this is something that
2:42is possible because
2:43we already know that the new value is 9
2:46it is just not written back in the
2:48register file but it is handy it is
2:51sitting
2:51right there at the output of the alu
2:55in in the register that separates the
2:59the execute phase with the memory access
3:02phase
3:04so what we need to do is to widen the
3:07multiplexer
3:09that feeds the alu with the operand in
3:12this case
3:13ra and it's there
3:17it is just gonna show up at the input of
3:19the alu
3:21similarly for the subsequent instruction
3:24or
3:25we would forward the
3:28result of this addition before it gets
3:31retained register file
3:32from the pipeline register that divides
3:36the memory access phase and the right
3:39back face
3:39because we have it handy it is it still
3:42traveled a little bit deeper in the
3:43pipeline
3:44so it is nicely aligned with this
3:46instruction
3:48with the input of the instruction or
3:52okay so we learn how to deal
3:56with these data hazards by using
4:00hardware forwarding
4:01without hard forwarding we would have
4:03had
4:04to stall the pipeline meaning
4:07we would have to insert knobs and
4:11don't do something during particular
4:13cycles
4:15there is no such easy way out
4:18in another case of data hazard which
4:22are the data hazards associated with
4:24loads
4:25so here is a sequence of instructions
4:27that starts with the load
4:29this load takes the
4:33data from the memory and stores in the
4:36destination register s2
4:38and then subsequent instructions would
4:40like to use that value
4:43from s2 as the source operand
4:47so here is what happens our load word
4:53goes addresses the memory and this data
4:56is available
4:57at the end of the memory access phase
5:02that is one cycle later than what we
5:04have had
5:05in the r type instructions where it was
5:08available at the end of the execute
5:10phase so this new data
5:13is going to be written just one cycle
5:15after that
5:16but the subsequent instruction here is
5:19looking
5:20at the values that are in the register
5:22file
5:23they're stale they're old so
5:28data from the memory is there but it is
5:31needed
5:32one cycle earlier we can go back
5:35we cannot jump time
5:39here
5:43there is no forwarding solution it is
5:45going to fix
5:46this here we can forwarding basically
5:49helps us
5:50go kind of forward in the pipeline there
5:53is no solution that allows us to go
5:55back in the pipeline what can we do
6:01we need to stall there is no practical
6:04way
6:05we don't have a time machine yet here
6:08not in compute hardware or anywhere else
6:13so um this end instruction that
6:17needs s2 as it's its source operand
6:20cannot proceed until it becomes valid
6:23until
6:24it is there
6:28we can forward from here but that
6:30forwarding
6:31would make it only into the
6:34into the instruction that is delayed by
6:36one it would make it in time
6:39for or but and can do it
6:42so we will stall and forward
6:46and then all the instructions that are
6:48down the stream
6:49would not be affected so
6:53in a quick summary here load instruction
6:56all types of load instructions require
7:00one cycle pipeline stall let's see how
7:02does that pipeline stall look like
7:05so our data is here
7:08in the pipeline register that follows
7:10the memory access stage
7:13and it needs to be there it can happen
7:16so we need to stall the processor
7:19in order to slow down the execution
7:23delay the execution of this end
7:26so instead we convert this end
7:29into a knob and move all the
7:32instructions
7:34by one cycle
7:37down the down the stream
7:40okay so um
7:44how do we convert in flight this end
7:47that
7:47is uh that that is an and to a knob
7:51i mean it's already there it is in the
7:53pipeline by the time
7:55we have figured out that this is a load
7:57at the end of this cycle we have already
7:59fetched the end we have within
8:01fetch something else so we have an end
8:03on our hand that we are executing
8:07so we have to have a hardware mechanism
8:09that basically cancels this end
8:11invalidates the end and
8:15repeats it in the next cycle
8:20so how do we do that what does the end
8:22do well it does
8:23flip some bits but
8:26if it doesn't write them back if it
8:28doesn't change the state of a processor
8:31it's like it did not exist so that's a
8:34clue
8:35all what you need to do quickly when we
8:38find out that we are we have a load
8:40on our hands here right in this
8:43instruction decode phase
8:45immediately after that turn off set all
8:49the control signals
8:51that are associated with writing the the
8:53state the new state
8:55into the processor to being disabled
8:59so we are not writing back into a
9:00register file
9:02we are not writing into the memory and
9:05we are not updating the program counter
9:08so if there is no state update the next
9:11instruction
9:12is going to be the same one it's going
9:14to be our end and we just proceed
9:16with executing that end
9:20and it's as simple as that so
9:23we need a mechanism here
9:27a piece of logic that is going to detect
9:29that we are dealing with
9:31a load and that
9:34destination of that load is
9:37the source for the next instruction that
9:41requires us to stall and this is a
9:43mechanism to stall we basically make the
9:46latch and that door do nothing we
9:49disable
9:50the control signals and run that
9:53following instruction again
9:56when we run this and again
9:59when we repeat the end we are able to
10:02forward
10:03this using very similar principles that
10:06what we have seen before actually
10:08exactly same mechanism as we have seen
10:10before in the
10:11in mitigating data hazards
10:16so it becomes available at the input of
10:18the alu
10:20so we are going to repeat this and with
10:22the forwarding
10:26so in a quick summary here
10:30in order to handle the load hazard slow
10:33data hazards
10:34we have to have one cycle pipeline stall
10:37implemented in hardware
10:39that prevents completion of the
10:41instruction
10:42does not update the processor state and
10:45forces re-execution of the following and
10:48satisfaction
10:50okay
10:54so this is a very important concept in
10:56pipelines
10:58it happens fairly frequently so that
11:00instruction
11:02that is sitting after the load word
11:06is called the load delay slot
11:10if that instruction uses the result of
11:12the load then the hardware
11:14has to to stall for one cycle
11:17so what do we do um
11:19[Music]
11:20with that well you know that's like
11:22inserting a knob in the slot
11:24but you know knobs can be inserted
11:27during compilations
11:29phase um and result in a in a
11:33code bloat and performance loss
11:36so the key idea here is something that
11:38we mentioned before
11:40let's go through the list of instruction
11:42that we would like to execute and we can
11:44find one that does not where
11:46whose operands do not depend on the
11:48result of the load
11:50then just put it into that delay slot
11:55all right so that's the idea and there
11:58is no performance loss
11:59so the burden of doing that is generally
12:02put
12:03on the compiler
12:07let's see how does that work so here is
12:09a piece of
12:10risk 5 assembly code that does
12:14two additions
12:18by using data that is in the memory
12:21so a3 sums a not
12:25an a1 and a4 sums a not
12:28an a2 so let's see a sample
12:32risk 5 assembly code so here is the
12:35original order
12:36of that code we're gonna go ahead um
12:39load you know t zero points to the
12:41zeroth element of the array a
12:44um and we're going to go get uh
12:48the first element of the array store it
12:51in t1
12:52get the second element of the array
12:54store it in t2
12:55and immediately proceed with the
12:57addition
12:59see the problem here we
13:02proceeded by executing two loads they do
13:05not block
13:06each other there you know there is no
13:07dependency between the source of the
13:10of the second load with the destination
13:12of the first load but look at this
13:14one over here t2 here t2 there
13:18so there is a dependency there um
13:21so this is going to cause a stall so we
13:25have to stall
13:26this add execution until
13:29we can forward from the the
13:32load pipeline into the add instruction
13:36and then we're okay we proceed and then
13:38we find out there is another hazard here
13:41we see t4 here
13:42and t4 there that's a hazard we have to
13:46stall again
13:47when we insert that one extra cycle we
13:50continue
13:52how can we do better than this
13:55can we reorder this and that's typically
13:57a java
13:59for a compiler so here is an alternative
14:03schedule of instructions we are going to
14:06go ahead
14:07and load all three of them
14:10three operands here that we need a
14:12naught a1 and a2
14:14in three consecutive load cycles that
14:16enabled us to
14:18insert this load instruction between
14:21the load of a0 of a2
14:24of a1 of a1
14:28and the consumption of a1 in
14:31this addition here
14:35so we are using in the delay slot
14:40load delay slot we are putting another
14:42independent load
14:44so we proceed with that and
14:47these two
14:51you know the the storing t2 in the
14:55register file and the consumption of the
14:58data from
14:59the register file are now separated by
15:01one cycle and that's plenty enough for
15:03our hardware and
15:05forwarding in hardware to to help us
15:08avoid
15:10stalling then
15:14the other one is also resolved because
15:17you know t4 loading into t4 and using
15:21the data from t4 are now separated by
15:24two instructions
15:25and that is plenty enough it's not even
15:27activating
15:28the forwarding so instead of
15:32nine cycles that we used initially for
15:34executing these
15:35uh seven instructions we can execute all
15:38seven instructions
15:39in seven cycles so this is all what we
15:43had about the
15:44load delays
15:47slot and load data hazard
15:51we're going to move on to the control
15:53hazards right after a quick break

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 23.1 - Pipelining III: Load Data Hazard by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 1,998 words across 373 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.