Instruction Pipelining

Instruction Pipelining

1. Afjal Hossain | Emran Hossain Raihan Mahmud| Rejuanul Haque Toriqul Islam Department of Software Engineering Instruction Pipelining SWE-311

2. Pipelining A technique used in advanced microprocessors where the microprocessor begins executing a second instruction before the first has been completed. 2

3. Two Stage Instruction Pipeline 3

4. Six Stage Instruction Pipeline 4

5. Six Stage Instruction Pipeline Fetch Instruction (FI) : Read the next expected introduction into a buffer Decode Instruction (DI) : Determine the opcode and the operand specifiers Calculate Operands (CO) : Calculate the effective address of each source operand. This may involve displacement, register indirect, indirect or other forms of address calculations. Fetch Operands (FO) : Fetch each operand from memory. Operands in register need not be fetched. Execute Instruction (EI) : Perform the indicated operation and store the result, if any, in the specified destination operand location. Write Operand (WO) : Store result in memory 5

6. Types of hazards 6 Resource Data Control HAZARD

7. Resource Hazards Two (or more) instructions in pipeline need same resource Executed in serial rather than parallel for part of pipeline Also called structural hazard E.g. Assume simplified five-stage pipeline Each stage takes one clock cycle Ideal case is new instruction enters pipeline each clock cycle Assume main memory has single ports 7

8. Data Hazards Attempt to use item before it is ready Instruction depends on result of prior instruction still in the pipeline 8

9. Types of Data Hazard 9 RAW WAR WAW DATA HAZARD

10. Read After Write (RAW) It is also known as True dependency An instruction modifies a register or memory location Hazard if read takes place before write complete B tries to read a register before   A has written it and gets the old value 10

11. Write After Read (WAR) It is also known as Anti dependency An instruction reads a register or memory location Hazard if write completes before read takes place B tries to write a register before   A has read it In this case, A uses the new (incorrect) value 11

12. Write After Write (WAW) It is also known as O utput dependency Two instructions both write to same location Hazard if writes take place in reverse of order intended sequence B tries to write an operand before   A has written it After instruction B has executed, the value of the register should be B's result, but A's result is stored instead 12

13. Control Hazard Instructions that disrupt the sequential flow of control present problems for pipelines. Also known as branch hazard Control hazards occur because the PC following a control instruction is not known until control instruction computes if branch should be taken or not. 13

14. 14

15. Types of Control hazards Unconditional branches Conditional branches Indirect branches Procedure calls Procedure returns 15

16. Dealing with Branches Multiple Streams Prefetch Branch Target Loop buffer Branch prediction Delayed branching 16

17. Solutions for Control Hazards Pipeline stall cycles Branch delay slots Branch prediction Indirect branch prediction Return address stack (RAS) 17

18. Multiple Streams Have two pipelines Prefetch each branch into a separate pipeline Use appropriate pipeline Leads to bus & register contention Multiple branches lead to further pipelines being needed 18

19. Prefetch Branch Target Target of branch is prefetched in addition to instructions following branch Keep target until branch is executed Used by IBM 360/91 19

20. Loop Buffer Very fast memory Maintained by fetch stage of pipeline Check buffer before fetching from memory Very good for small loops or jumps Used by CRAY-1 20

21. Loop Buffer Diagram 21

22. Prediction Easy to fetch multiple (consecutive) instructions per cycle Essentially speculating on sequential flow Jump : unconditional change of control flow Always taken Branch: conditional change of control flow Taken typically ~50% of the time in applications Backward: 30% of the Branch  80% taken = ~24% Forward: 70% of the Branch  40% taken = ~28% 22

23. What is Branch Prediction In a computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch. Will go before this is known definitively. The purpose of the branch predictor is to improve the flow in the instruction pipeline. 23

24. Branch Prediction Techniques Static Branch Prediction Some branch instructions predicted as taken and others as not taken End or program loop Beginning of program loop Hardware or compiler Dynamic Branch Prediction Bitmap for Lower bits of PC address Says whether or not branch taken last time If Instr is Branch, predict and update the table 24

25. Predict by Opcode Some instructions are more likely to result in a jump than theirs Can get up to 75% success Taken/Not taken switch Based on previous history Good for loops Refined by two-level or correlation-based branch history 25

26. Branch Prediction Flowchart 26

27. 27 Thank You !!! Any Questions ???