DOC PREVIEW
U of I CS 232 - Stalls and flushes

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

October 17, 2007 ©2003 Craig Zilles (derived fromslides by Howard Huang)1Stalls and flushes Last time, we discussed data hazards that can occur in pipelined CPUs ifsome instructions depend upon others that are still executing.— Many hazards can be resolved by forwarding data from the pipelineregisters, instead of waiting for the writeback stage.— The pipeline continues running at full speed, with one instructionbeginning on every clock cycle. Today we’ll see some real limitations of pipelining.— Forwarding may not work for data hazards from load instructions.— Branches affect the instruction fetch for the next clock cycle. In both of these cases we may need to slow down, or stall, the pipeline.October 17, 2007 Stalls and flushes 2Data hazard review A data hazard arises if one instruction needs data that isn’t ready yet.— Below, the AND and OR both need to read register $2.— But $2 isn’t updated by SUB until the fifth clock cycle. Dependency arrows that point backwards indicate hazards. DM Reg RegIM DM Reg RegIM DM Reg RegIMsub $2, $1, $3and $12, $2, $5or $13, $6, $2Clock cycle1 2 3 4 5 6 7October 17, 2007 Stalls and flushes 3Forwarding to the rescue! The desired value ($1 - $3) has actually already been computed—it justhasn’t been written to the registers yet. Forwarding allows other instructions to read ALU results directly from thepipeline registers, without going through the register file. DM Reg RegIM DM Reg RegIM DM Reg RegIMsub $2, $1, $3and $12, $2, $5or $13, $6, $2Clock cycle1 2 3 4 5 6 7October 17, 2007 Stalls and flushes 4What about loads? Imagine if the first instruction in the example was LW instead of SUB.— How does this change the data hazard? DM Reg RegIM DM Reg RegIMlw $2, 20($3)and $12, $2, $5Clock cycle1 2 3 4 5 6October 17, 2007 Stalls and flushes 5What about loads? Imagine if the first instruction in the example was LW instead of SUB.— The load data doesn’t come from memory until the end of cycle 4.— But the AND needs that value at the beginning of the same cycle! This is a “true” data hazard—the data is not available when we need it. DM Reg RegIM DM Reg RegIMlw $2, 20($3)and $12, $2, $5Clock cycle1 2 3 4 5 6October 17, 2007 Stalls and flushes 6Stalling The easiest solution is to stall the pipeline. We could delay the AND instruction by introducing a one-cycle delay intothe pipeline, sometimes called a bubble. Notice that we’re still using forwarding in cycle 5, to get data from theMEM/WB pipeline register to the ALU. DM Reg RegIM DM Reg RegIMlw $2, 20($3)and $12, $2, $5Clock cycle1 2 3 4 5 6 7October 17, 2007 Stalls and flushes 7Stalling and forwarding Without forwarding, we’d have to stall for two cycles to wait for the LWinstruction’s writeback stage. In general, you can always stall to avoid hazards—but dependencies arevery common in real code, and stalling often can reduce performance bya significant amount. DM Reg RegIM DM Reg RegIMlw $2, 20($3)and $12, $2, $5Clock cycle1 2 3 4 5 6 7 8October 17, 2007 Stalls and flushes 8Stalling delays the entire pipeline If we delay the second instruction, we’ll have to delay the third one too.— Why? (two reasons) DM Reg RegIM DM Reg RegIM DMReg RegIMlw $2, 20($3)and $12, $2, $5or $13, $12, $2Clock cycle1 2 3 4 5 6 7 8October 17, 2007 Stalls and flushes 9Stalling delays the entire pipeline If we delay the second instruction, we’ll have to delay the third one too.— This is necessary to make forwarding work between AND and OR.— It also prevents problems such as two instructions trying to write tothe same register in the same cycle. DM Reg RegIM DM Reg RegIM DMReg RegIMlw $2, 20($3)and $12, $2, $5or $13, $12, $2Clock cycle1 2 3 4 5 6 7 8October 17, 2007 Stalls and flushes 10 One way to implement a stall is to force the two instructions after LW topause and remain in their ID and IF stages for one extra cycle. This is easily accomplished.— Don’t update the PC, so the current IF stage is repeated.— Don’t update the IF/ID register, so the ID stage is also repeated.RegImplementing stalls DM Reg RegIM RegIMIMlw $2, 20($3)and $12, $2, $5or $13, $12, $2 DMReg RegIM DM RegClock cycle1 2 3 4 5 6 7 8October 17, 2007 Stalls and flushes 11 But what about the ALU during cycle 4, the data memory in cycle 5, andthe register file write in cycle 6? Those units aren’t used in those cycles because of the stall, so we can setthe EX, MEM and WB control signals to all 0s.RegWhat about EXE, MEM, WB DM Reg RegIM RegIMIMlw $2, 20($3)and $12, $2, $5or $13, $12, $2 DMReg RegIM DM RegClock cycle1 2 3 4 5 6 7 8October 17, 2007 Stalls and flushes 12Stall = Nop conversion The effect of a load stall is to insert an empty or nop instruction into thepipeline DM Reg RegIM RegIMIMlw $2, 20($3)and -> nopand $12, $2, $5or $13, $12, $2 DMReg RegIM DMReg RegClock cycle1 2 3 4 5 6 7 8 DM RegOctober 17, 2007 Stalls and flushes 13Stall = Nop conversion The effect of a load stall is to insert an empty or nop (“no operation”)instruction into the pipeline DM Reg RegIM RegIMIMlw $2, 20($3)and -> nopand $12, $2, $5or $13, $12, $2 DMReg RegIM DMReg RegClock cycle1 2 3 4 5 6 7 8 DM RegOctober 17, 2007 Stalls and flushes 14Detecting stalls Detecting stall is much like detecting data hazards. Recall the format of hazard detection equations:if (EX/MEM.RegWrite = 1and EX/MEM.RegisterRd = ID/EX.RegisterRs)then Bypass Rs from EX/MEM stage latch DM Reg RegIM DM Reg RegIMsub $2, $1, $3and $12, $2, $5id/exif/idex/memmem\wbid/exif/idex/memmem\wbOctober 17, 2007 Stalls and flushes 15Detecting Stalls, cont. When should stalls be detected?Reg DM Reg RegIM RegIMlw $2, 20($3)and $12, $2, $5 DM Regid/exif/idex/memmem\wbid/exif/idex/memmem\wbif/id What is the stall condition?if ()then stallOctober 17, 2007 Stalls and flushes 16Detecting stalls We can detect a load hazard between the current instruction in its IDstage and the previous instruction in the EX stage just like we detecteddata hazards. A hazard occurs if the previous instruction was LW...ID/EX.MemRead = 1...and the LW destination is one of the current source registers.ID/EX.RegisterRt = IF/ID.RegisterRsorID/EX.RegisterRt = IF/ID.RegisterRt The complete test for stalling is the conjunction of


View Full Document

U of I CS 232 - Stalls and flushes

Documents in this Course
Goal

Goal

2 pages

Exam 1

Exam 1

5 pages

Exam 1

Exam 1

6 pages

Exam 2

Exam 2

6 pages

Exam 1

Exam 1

5 pages

Load more
Download Stalls and flushes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Stalls and flushes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Stalls and flushes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?