Consider the pipelined implementation (without forwarding and/or stalling) of th
ID: 641763 • Letter: C
Question
Consider the pipelined implementation (without forwarding and/or stalling) of the MIPS microprocessor.
(a) Explain how this pipelined implementation deals with I-type conditional branch instructions in the case the branch is not taken and in the case the branch is taken.
(b) Explain why data dependency hazards may occur in this implementation.
(c) List all possible instruction sequences that may exhibit data dependency hazards.
(d) For each sequence in (c), give a software equivalent that does not suffer from the data dependency limitation
Explanation / Answer
(a) Branch instructions are those that tell the processor to make a decision about what the next instruction to be executed should be based on the results of another instruction. Branch instructions can be troublesome in a pipeline if a branch is conditional on the results of an instruction which has not yet finished its path through the pipeline.
For example:
Loop :
add $r3, $r2, $r1
sub $r6, $r5, $r4
beq $r3, $r6, Loop
The example above instructs the processor to add r1 and r2 and put the result in r3, then subtract r4 from r5, storing the difference in r6. In the third instruction, beq stands for branch if equal. If the contents of r3 and r6 are equal, the processor should execute the instruction labeled "Loop." Otherwise, it should continue to the next instruction. In this example, the processor cannot make a decision about which branch to take because neither the value of r3 or r6 have been written into the registers yet.
The processor could stall, but a more sophisticated method of dealing with branch instructions is branch prediction. The processor makes a guess about which path to take - if the guess is wrong, anything written into the registers must be cleared, and the pipeline must be started again with the correct instruction. Some methods of branch prediction depend on stereotypical behavior. Branches pointing backward are taken about 90% of the time since backward-pointing branches are often found at the bottom of loops. On the other hand, branches pointing forward, are only taken approximately 50% of the time. Thus, it would be logical for processors to always follow the branch when it points backward, but not when it points forward. Other methods of branch prediction are less static: processors that use dynamic prediction keep a history for each branch and uses it to predict future branches. These processors are correct in their predictions 90% of the time.
(b) In the domain of central processing unit (CPU) design, hazards are problems with the instruction pipeline in CPU microarchitectures when the next instruction cannot execute in the following clock cycle, and can potentially lead to incorrect computation results.Here as the CPU takes time to decide, it can result into hazards.
(c)
Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions(sometimes known as race hazards). There are three situations in which a data hazard can occur:
Consider two instructions i1 and i2, with i1 occurring before i2 in program order.
Read After Write (RAW)
(i2 tries to read a source before i1 writes to it) A read after write (RAW) data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a previous instruction, the previous instruction has not been completely processed through the pipeline.
Example
For example:
i1. R2 <- R1 + R3
i2. R4 <- R2 + R3
The first instruction is calculating a value to be saved in register R2, and the second is going to use this value to compute a result for register R4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the first will not yet have been saved, and hence we have a data dependency.
We say that there is a data dependency with instruction i2, as it is dependent on the completion of instruction i1.
Write After Read (WAR)
(i2 tries to write a destination before it is read by i1) A write after read (WAR) data hazard represents a problem with concurrent execution.
Example
For example:
i1. R4 <- R1 + R5
i2. R5 <- R1 + R2
If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register R5before i1 has had a chance to fetch the operands.
Write After Write (WAW)
(i2 tries to write an operand before it is written by i1) A write after write (WAW) data hazard may occur in a concurrent execution environment.
Example
For example:
i1. R2 <- R4 + R7
i2. R2 <- R1 + R3
We must delay the WB (Write Back) of i2 until the execution of i1.
For example:
Loop :
add $r3, $r2, $r1
sub $r6, $r5, $r4
beq $r3, $r6, Loop
The example above instructs the processor to add r1 and r2 and put the result in r3, then subtract r4 from r5, storing the difference in r6. In the third instruction, beq stands for branch if equal. If the contents of r3 and r6 are equal, the processor should execute the instruction labeled "Loop." Otherwise, it should continue to the next instruction. In this example, the processor cannot make a decision about which branch to take because neither the value of r3 or r6 have been written into the registers yet.
The processor could stall, but a more sophisticated method of dealing with branch instructions is branch prediction. The processor makes a guess about which path to take - if the guess is wrong, anything written into the registers must be cleared, and the pipeline must be started again with the correct instruction. Some methods of branch prediction depend on stereotypical behavior. Branches pointing backward are taken about 90% of the time since backward-pointing branches are often found at the bottom of loops. On the other hand, branches pointing forward, are only taken approximately 50% of the time. Thus, it would be logical for processors to always follow the branch when it points backward, but not when it points forward. Other methods of branch prediction are less static: processors that use dynamic prediction keep a history for each branch and uses it to predict future branches. These processors are correct in their predictions 90% of the time.
(b) In the domain of central processing unit (CPU) design, hazards are problems with the instruction pipeline in CPU microarchitectures when the next instruction cannot execute in the following clock cycle, and can potentially lead to incorrect computation results.Here as the CPU takes time to decide, it can result into hazards.
(c)
Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions(sometimes known as race hazards). 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
Consider two instructions i1 and i2, with i1 occurring before i2 in program order.
Read After Write (RAW)
(i2 tries to read a source before i1 writes to it) A read after write (RAW) data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a previous instruction, the previous instruction has not been completely processed through the pipeline.
Example
For example:
i1. R2 <- R1 + R3
i2. R4 <- R2 + R3
The first instruction is calculating a value to be saved in register R2, and the second is going to use this value to compute a result for register R4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the first will not yet have been saved, and hence we have a data dependency.
We say that there is a data dependency with instruction i2, as it is dependent on the completion of instruction i1.
Write After Read (WAR)
(i2 tries to write a destination before it is read by i1) A write after read (WAR) data hazard represents a problem with concurrent execution.
Example
For example:
i1. R4 <- R1 + R5
i2. R5 <- R1 + R2
If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register R5before i1 has had a chance to fetch the operands.
Write After Write (WAW)
(i2 tries to write an operand before it is written by i1) A write after write (WAW) data hazard may occur in a concurrent execution environment.
Example
For example:
i1. R2 <- R4 + R7
i2. R2 <- R1 + R3
We must delay the WB (Write Back) of i2 until the execution of i1.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.