New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Adele Schaden MD


Adele Schaden MD
GPA 3.88


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 13 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 203A at University of California Riverside taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231745/cs-203a-university-of-california-riverside in ComputerScienence at University of California Riverside.

Similar to CS 203A at UCR

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
CS 203A Advanced Comgter Architecture Lecture 3 Pipeline Hazards Pipeline Hazards Hazards are caused by conflicts between Instructions Will lead to incorrect behaVIor if not fixed Three types Structural two instructions use same hw in the same c cle resource conflicts eg one memory port unpipelined divider etc Data two instructions use same data storage registermemory dependent instructions Control one instruction affects which instruction is next PC modifying instruction changes control flow of program Handling Hazards Force sTalls or bubbles in The pipeline STop some younger insTrucTions in The sTage when hazard happen Make younger insTr WaiT for older ones To compleTe Flush pipeline Blow insTrucTions ouT of The pipeline RefeTch new insTrucTions laTer solving conTrol hazar s ImplemenTaTion asserT clear signals on pipeline regisTers Dealing wiTh STrucTural Hazards STall simple low cosT in hw Decrease IPC ReplicaTe The resource good for performance Increase hw and area E Used for cheap resources Duml DI good for performance CompleXiTy eg RAM Useful for mulTicycle resources Pipeline The resource m Single Memory is a STr ucTur al Hazard Time clock cycles n 5 Load t nstr1 r nstr2 r nstr3 d nstr4 e r Can t read same memory twice in same clock cycle Fixing STr ucTur al Hazards Using STaIIs S rall Pipeline 1 2 3 4 5 6 7 8 9 10 Load f d x m w ins rl f d x m w ins rZ f d x m w ins r3 f d x m w ins r4 f d x w Duplica re Resource Separa re IM and DM IOU Speed Up Equafion for39 Pipelining Speedup from pipelining Ave Instr Time unpipelin d Ave Instr Time pipelined CPI x Clock C cle d CPIpipelined x ClOCk cyClepipelined CPIunpipelined x ClOCk cyCleunpipelined CPIpipelined ClOCk cyClepipelined Ideal CPI CPIunpipeunedPipeline depth Speedup Ideal CPI x Pipeline depth Clock Cycle x CPIpipelined Clock Cyclepipeuned Speed Up EquaTion for Pipelining CPIpipelimd Ideal CPI Pipeline sfall clock cycles per insfn Ideal CPI x Pipeline depfh CIOCk eyeleunpipelined Speedup X Ideal CPI Pipeline sfall CPI Clock Cyclepipelined Pipeline depfh x Clock Cycleunpipelimd Speedup 1 Pipeline sfall CPI Clock Cyclepipelimd lgt 1709 Example DualporT vs Singlepom Machine A Dual por red memory achine B Single por red memory bu r has a 105 rimes as rer clock ra e Ideal CPI 1 for bo rh Loads are 40 of ins rruc rions execu red SpeedUpA Pipeline Dep rhl O x clockunPiPeclockpipe Pipeline Dep rh SpeedUpB Pipeline Dep rhl 04 x clockunPiPeclockunpipe 105 Pipeline DepTh14 x 105 075 x Pipeline Dep rh SpeedUpA SpeedUpB Pipeline Dep rhO75 x Pipeline Dep rh 133 Machine A is 133 rimes fas rer Da ia Hazards Two differen r ins rruc rions use The same s rorage loca rion If mus r appear as if They execu red in sequen rial order add R1 R2 R3 add R132 R3 add R1 R2 R3 sub R2 R4 R1 sub R2 R4 R1 sub R4 R1 or R1 R6 R3 or R1 R6 R3 or R1 R6 R3 readafferwri re wriTeafferread wri reafferwri re RAW WAR WAW True dependence an ri dependence oufpuf dependence real ar rificial ar rificial I01 Reducing RAW Hazards Bypassing Da ra available a r The end of EX s rage why wai r un ril WB stage Bypass forward da ra direc rly To inpu r of EX Reducesavoids s ralls in a big way Large fracTion of input operands are bypassed Complex Impor ran r does no r relieve you from having To perform WB 1 2 3 4 5 6 7 8 9 add R1 R2 R3 1 d X m w 5 Sub R2 R4 R1 1 d X m w Can bypass from MEM also useful in case of a load Minimizing Da ra Hazard S ralls by Forwarding Time in clock cycles 7 DADD R1R2 R3 e Fug i C t I o z I I l l39 I I 392 DSUB R4 R1 R5 9 AND R6 R1 R7 XOR R10 R1 R11 ALU U H 2003 Elsevier Science USA All rights reserved l0 Bu r Even wi rh bypassing no r all RAWs s ralls can be avoided Load To an ALU immedia rely affer Can be elimina red wi rh compiler scheduling IwRLiaRa h sub R2 R4 R1 Compiler Scheduling Compiler moves ins rruc rions around To reduce s rol Is Eg code Sequence a bo d ef before scheduling Iw Rb b Iw RC 0 add Ra Rb Ro sta sw Ra a Iw Re e Iw Rf f sub Rd Re Rf sta sw Rd d affer scheduling Iw Rb b Iw RC 0 Iw Re e add Ra Rb Relno stall Iw Rf f sw Ra a sub Rd Re Rflno stall sw Rd d 1709 l WAR Hazards Recall WAR add R1 R2 R3 sub R2 R4 R1 or R1 R6 R3 Problem swap means introducing false RAW hazards Artificial can be removed if sub used a different destination register Can39t happen in inorder pipeline since reads happen in ID but writes happen in WB Can happen in outoforder execution WAW Hazards add R1 R2 R3 sub R2 R4 R1 or R1 R6 R3 Problem scheduling would leave wrong value in R1 for the sub Artificial using different destination register would solve Can39t happen in inorder pipeline in which every instruction takes same cycles since writes are inorder Can happen in the presence of muticyce operations ie outoforder writes I0 Compiler b03ed Regisrer Renaming Program order RAW WAR WAW and RAW I quot Flow Ami Output depen dencedependence dependencm also ow dependence 11 Load R1A RIG MemoryA 12 Add R2 R1 R2 R2R1 13 Add R3 R4 R3 R3R4 I4 Mul R4 R5 R4 R4R5 15 Comp R6 R6 N0tR6 I6 Mul R6 R7 R6 R6R7 Compiler b03ed Regisrer Renaming Rewri re The previous progr0m 0s I1 R1 6 Memory A I2 R2 6 R2 R1 I3 R3 6 R3 R40 I4 R4b 6 R40 R50 I5 R60 6 R60 I6 R6b 6 R60 R7 Alloc0 re more regis rers 0nd ren0me rhe regis rers Th0 r re0y do no r h0ve flow dependency The WAR h0z0rd be rween I3 0nd I4 0nd WAW h0z0rd be rween I5 0nd I6 h0ve heen removed These rwo h0z0rds 0so c0ed N0me dependencies Control Hazards Branch problem branches are resolved in EX stage gt 2 cycles penalty on taken branches Ideal CPI 1 Assuming 2 cycles for all branches and 32 branch instructions gt new CPI 1 O322 164 Solutions Reduce branch penalty change the datapath new adder needed in ID stage Fill branch delay slots with a useful instruction Fixed branch prediction Static branch prediction Dynamic branch prediction Control Hazards Reducing branch penalty Compute branch condition and target address in the ID stage Still left with 1 cycle stall Branch delay slot filling Move an instruction into the slot right after the branch Always fetch this instruction for execution Fetch dependent upon branch outcome is delayed by one cycle Example Nondelayed vs Delayed Branch Nondelayed Branch Delayed Branch or M8 M9 M10 add M1 M2M3 add M1 M2M3 sub M4 M5M6 sub M4 M5M6 beq M1 M4 Exit beq M1 M4 Exit or M8 M9 M10 xor M10 M1M11 xor M10 M1M11 Exit Exit Control Hazards Branch Prediction Idea doing something is better than waiting around doing nothing 0 Guess branch target start executing at guessed position 0 Execute branch verify check your guess minimize penalty if guess is right to zero May increase penalty for wrong guesses o Heavily researched area in the last 20 years Fixed branch prediction Each of these strategies must be applied to all branch instructions indiscriminately Predict I39IO l39 taken 47 actually not taken continue to fetch instruction without stalling do not change any state no register write if branch is taken turn the fetched instruction into no op restart fetch at target address 1 cycle penalty Confrol Hazards Branch Prediction Predict Taken 53 more difficul r mus r know Targef before branch is decoded no advanfage in our simple 5 s rage pipeline S ra ric branch prediction Opcodebased predicfion based on opcode ifself and rela red condi139ion Examples MC 88110 PowerPC 601603 Displacemen r based predic rion if d lt 0 predicf Taken if d gt 0 predicf n01 Taken Examples Alpha 21064 as opfion PowerPC 601603 for regular condi rional branches Com ilerdirec red predic rion com iler se139s or clears a pre ic r bi r in The insfrucfion ifsel Examples A 9210 Hobbif PowerPC 601603 predic r bi r reverses opcode or displacemenf predicfions HP PA 8000 as op rion Confrol Hazards Branch PredicTion Dynamic branch prediction La rer 1709 MIPS R4000 pipeline Integer unit EX LJ FPinteger multiply 3 l IF ID MEM WB FP adder A1 FPinteger divider DI 2003 Elsevier Science USA All rights reserved 25 MIPS FP Pipe Stages FP Instr 1 2 3 4 5 6 7 8 Add Subtract U SA AR RS Multiply U EM M M M N NA R Digde U A R D28 DA DR DR DA DR A Square r39oot U E AR108 A R Negate U 5 Absolute value U S FP compare U A R Stages M First stage of multiplier A Mantissa ADD Stage N Second stage of multiplier D Divide pipeline stage P Rounding stage E Exception test stage 5 Operand shift stage U Unpack FP numbers 26


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.