Computer Architecture Control Hazards + Branch Prediction Prof. Sagnik Nath CSE 120 Contents 2 Control hazards strategies comparison Control Hazard Wrap up Structural Hazards Pipeline summary Comparing Control Hazard Strategies 3 Control point Branch strategy Clock cycle penalty Strategy 1:MEM Stall pipeline till branch resolved (unconditional stall) Pipeline always stalled for 2 extra cycles Strategy 2: ID Stall pipeline till branch resolved; (unconditional stall) Pipeline always stalled for 1 extra cycle Strategy 3: ID Predict not taken Pipeline stalled for 1 extra cycle if branch indeed taken, else no stall if branch taken Strategy 1: Branch decision available in MEM stage => requires 2 NOPs after each xBranch computed here 4 xBranch decision available here 5 Strategy 3: Most efficient for Static Branch prediction! Only 1 NOP introduced in pipeline and that too if branch turns out to be indeed taken; else pipeline flows as is ! 6 Comparing Control Hazard Strategies 9 15% branch frequency, 65% branches are taken Assume CPI=1 for non branch instructions Control point Branch strategy Clock cycle penalty Global CPI Strategy 1:MEM Stall pipeline till branch resolved (unconditional stall) Pipeline always stalled for 2 extra cycles 0.85 * 1 + 0.15 * (2+1) =1.3 Strategy 2: ID Stall pipeline till branch resolved; (unconditional stall) Pipeline always stalled for 1 extra cycle 0.85 * 1 + 0.15 * (1+1) =1.15 Strategy 3: ID Predict not taken Pipeline stalled for 1 extra cycle if branch indeed taken, else no stall if branch taken 0.85 * 1 + 0.15 *0.65* (1+1) + 0.15 * 0.35 * 1=1.098 Brief Idea of Structural Hazards 8 Occurs when we try to read and write to the same resource at the same time Memory Access: In our processor design, we have different physical memory for Instructions and Data. No structural hazard possible. Will be an issue for processors with common physical memory (beyond scope of this course) Register file: For reading and writing to same register at the same time, this could be an issue. Already covered in lecture on Data forwarding . If you have fast register file (Write and read on different clock edge), this control hazard is resolved. Pipeline Timing Diagram Summary 9 Pipeline Timing Diagram Summary Compact way to represent state of pipeline over time Time is horizontal axis (1 column per cycle) Program order is vertical axis (1 row per instruction) Recommend having Datapath handy to visualize actual constraints For given example, assume forwarding available with datahazard stall and fast register file 12 Instruction Clock Cycle => 0 1 2 3 4 5 6 7 8 9 ld x1, 0(x2) F D X M W sub x4, x1, x3 and x6, x1, x7 or x8, x1, x9 Pipeline Timing Diagram Summary Compact way to represent state of pipeline over time Time is horizontal axis (1 column per cycle) Program order is vertical axis (1 row per instruction) Recommend having Datapath handy to visualize actual constraints For given example, assume forwarding available with datahazard stall and fast register file 12 Instruction Clock Cycle => 0 1 2 3 4 5 6 7 8 9 ld x1, 0(x2) F D X M W sub x4, x1, x3 F D D X M W and x6, x1, x7 F F D X M W or x8, x1, x9 F D X M W Pipeline Timing Diagram Summary Compact way to represent state of pipeline over time Time is horizontal axis (1 column per cycle) Program order is vertical axis (1 row per instruction) Recommend having Datapath handy to visualize actual constraints For given example, assume forwarding available with datahazard stall and fast register file 12 Instruction Clock Cycle => stall available 0 1 2 3 4 5 6 7 8 9 ld x1, 0(x2) F D X M W sub x4, x1, x3 F F D D D D X D M X W M W and x6, x1, x7 F F D X M W F F F D X M W or x8, x1, x9 F D F X D M X W M W * Assume no forwarding; but fast register file and data hazard 13 END OF COVERAGE FOR MIDTERM Midterm Preparation: Study all lecture videos and corresponding slides till this mark Go through HW 1,2,3,4
