Pipeline hazards | Structural Hazard, Data Hazard & Control Hazard

Audio Version available in YouTube Link : https://www.youtube.com/AKSHARAM?sub_confirmation=1
subscribe the channel

Computer Architecture and Organization
V semester
Anna University
By
Babu M, Assistant Professor
Department of ECE
RMK College of Engineering and Technology
Chennai

1. PIPELINE Hazards The events which leads to Pipeline stall by preventing the next instruction to execute are known as Hazards. Structural Hazard Data Hazard Control Hazard

2. Pipelined Data Path with Control Signals

3. Structural Hazard IF ID EX MEM WB IF ID EX MEM WB lw $10,20($1) IF ID EX MEM WB IF ID EX MEM WB 1 2 3 4 5 6 7 8 9 CLOCK CYCLES PROGRAM INSTRUCTIONS Instruction 1 IF ID EX MEM WB IF ID EX MEM WB Instruction 2 Instruction 3 Instruction 4 sub $11,$2,$3 add $12,$ 3 ,$ 4 lw $13,24($1) add $14,$5,$6

4. Pipeline Stall

5. Von Neumann Vs Harvard Architecture Pipeline Hardware Resouces

6. DATA HAZARD Data hazards occur when the pipeline get stalled because one step must wait for another to complete. Data Dependency IF ID EX MEM WB IF ID EX MEM WB 1 2 3 4 5 6 7 8 add $s0, $t0, $ t1 sub $t2, $s0, $t3

7. Types of Data Hazard There are three situations in which a data hazard can occur Read After Write (RAW ) a  true dependency Write After Read ( WAR) an  anti-dependency write after write ( WAW) an  output dependency add $s0, $t0, $ t1 sub $t2, $s0, $t3 add $ s1, $ t2, $ t1 sub $t2, $s0, $t3 add $ s1, $ t2, $ t1 sub $s1, $s0 , $ t3

8. How is to overcome Data Hazard? 1. Forwarding / Bypassing

9. Forwarding Unit to overcome pipeline stall

10. Load-use Data hazard lw $s0 , 20($t1) sub $t2, $s0 , $t3 IF ID EX MEM WB IF ID EX MEM WB 1 2 3 4 5 6 7 8 2 . Pipeline Stall / Bubble lw $s0 , 20($t1) NOP sub $t2, $s0 , $t3 NOP

11. 3. Re-ordering the code a = b + e; c = b + f; lw $t1, 0($t0) lw $t2, 4($t0) add $t3, $t1,$t2 sw $t3, 12($t0) lw $t4, 8($t0) add $t5, $t1,$t4 sw $t5, 16($t0) lw $t1, 0($t0) lw $t2, 4($t0) add $t3, $t1,$t2 sw $t3, 12($t0) lw $t4, 8($t0) add $t5, $t1,$t4 sw $t5, 16($t0) lw $t1, 0($t0) lw $t2, 4($t0 ) lw $t4, 8($t0 ) add $t3, $t1,$t2 sw $t3, 12($t0) add $t5, $t1,$t4 sw $t5, 16($t0)

12. Computer Organization and Design by David A Patterson – Page no. 361 I1: or r1,r2,r3 I2: or r2,r1,r4 I3: or r1,r1,r2 1. Indicate dependences and their type Comparing I1 & I2 a . RAW on r1 – True Dependency b. WAR on r2 – Anti - Dependency

13. Computer Organization and Design by David A Patterson – Page no. 361 I1: or r1,r2,r3 I2: or r2,r1,r4 I3: or r1,r1,r2 1. Indicate dependences and their type Comparing I1 & I3 a. RAW on r1 – True Dependency b. WAW on r1 – Output Dependency

14. Computer Organization and Design by David A Patterson – Page no. 361 I1: or r1,r2,r3 I2: or r2,r1,r4 I3: or r1,r1,r2 1. Indicate dependences and their type Comparing I2 & I3 a. RAW on r2 – True Dependency b. WAR on r1 – Anti- Dependency

15. Computer Organization and Design by David A Patterson – Page no. 361 I1: or r1,r2,r3 I2: or r2,r1,r4 I3: or r1,r1,r2 2 . Assume there is no forwarding in this pipelined processor. Indicate hazards and add NOP instructions to eliminate them. or r1,r2,r3 NOP NOP or r2,r1,r4 NOP NOP NOP NOP or r1,r1,r2 IF ID EX MEM WB IF ID EX MEM WB 1 2 3 4 5 6 7 8 9 10 11 IF ID EX MEM WB

16. Computer Organization and Design by David A Patterson – Page no. 361 I1: or r1,r2,r3 I2: or r2,r1,r4 I3: or r1,r1,r2 3. Assume there is full forwarding. Indicate hazards and add NOP instructions to eliminate them. or r1,r2,r3 or r2,r1,r4 or r1,r1,r2 IF ID EX MEM WB IF ID EX MEM WB 1 2 3 4 5 6 7 IF ID EX MEM WB

17. Control Hazard / Branch Hazard control hazard arising from the need to make a decision based on the results of one instruction while others are executing beq $6,$ 7,7 sub $11,$2,$ 3 add $12,$3,$ 4 IF ID EX MEM WB IF ID EX MEM 1 2 3 4 5 6 7 IF ID EX

18. Control Hazard / Branch Hazard control hazard arising from the need to make a decision based on the results of one instruction while others are executing A control hazard is when we need to find destination of a branch, and can’t fetch any new instruction until we know that destination A branch is either Taken : PC + 4 + Immediate address * 4 Not Taken : PC + 4

19. Penalty is 3 Clock Cycle

20. How to overcome Control Hazard? 1. Stall – Stop loading the instructions until the branch target is available 2 . Prediction – Assume whether branch is taken or not and continue fetching the instructions (Static Branch and Dynamic Branch Prediction) 3. Delayed Branch

21. Assume Branch is Not Taken Static Prediction FLUSH

22. Reducing the Delay of Branches sub $11,$2,$ 3 beq $6,$7,7 add $12,$3,$ 4 IF ID EX MEM WB IF ID EX MEM 1 2 3 4 5 6 7 IF ID EX WB MEM WB Complication Factors New forwarding unit is required Data dependency from previous instruction

23. Dynamic Branch Prediction Prediction of branches at run time using run time information 1-bit Prediction scheme 2-bit Prediction scheme

24. Dynamic Branch Prediction 1-bit Prediction scheme Branch Prediction Buffer / Branch History Table (BHT) - A small memory indexed by the lower portion of the address of the branch instruction Prediction Bit 1 if Branch is taken previously if Branch is not taken previously

25. Dynamic Branch Prediction Disadvantage of 1-bit Prediction scheme Even if a branch is almost taken always, there is a possibility to predict it incorrectly twice, when the branch is not taken

26. Dynamic Branch Prediction 2 -bit Prediction scheme The prediction is changed iff the branch is wrongly predicted twice

27. Advanced Prediction Schemes Correlation Predictor Tournament Predictor A branch predictor that combines local behavior of a particular branch and global information about the behavior of some recent number of executed branches. A branch predictor with multiple predictions for each branch and a selection mechanism that chooses which predictor to enable for a given branch