[Computer Architecture] Data Hazard
This is a summary of what I’ve learned about data hazard. If there’s anything wrong, please let me know!
What is Data Hazard?
Pipelines are used to improve the performance of a process. The operating frequency of a process is adjusted to the operating frequency of the circuit with the slowest operating frequency, so the pipeline allows the longest-running operation to be broken down into small pieces and operated quickly. Pipelined processes may improve performance, but problems may arise as a result. These are called hazards. Let’s learn about data hazards among various hazards. Data hazards can be divided into three types.
RAW(read after write)
Assume that it uses a 5-stage pipeline that have instruction-fetch, decode, execute, memory, and write-back stages.
What happens if you execute the following command in a structure with such a pipeline?
R2 ← R1 + R3
R4 ← R2 + R3
R5 ← R4 + R7Basically, in the pipeline, the results performed in the Execute stage are stored in the register in the Write Back stage. Therefore, the following problems occur.
Step EX of Pipeline 2 requires R2 before Pipeline 1 ends. It also requires R4 in Step EX of Pipeline 3 before Pipeline 2 is terminated. In this case, R2 and R4 of commands 2 and 3 will be entered with an odd value (trash value) or the result of the previous pipeline, respectively. Therefore, there is a problem that the desired value cannot be obtained properly.
This situation is referred to as a situation in which dependency occurs between commands, which means that the previous and subsequent commands affect the execution of the next command
WAR(write after read)
Unlike RAW, WAR and WAW occur during parallel operations.
R2 ← R1 + R7
R7 ← R1 + R3Assuming that the following command is executed, if two threads execute the above command simultaneously, two results will be produced.
One is when the thread of command 1 ends first, and the other is when the thread of command 2 ends first. That is, in parallel computing, the value can change depending on which of the threads that perform the operation ends first. Such a case is called WAR Hazard.
WAW(write after wirte)
What values are in R2 after the two commands are finished?
R2 ← R1 + R7
R7 ← R1 + R3like WAR, no one knows. If command 1 ends first, the result value will be overridden with the result of command 2. However, if command number 2 ends first, the result value is overridden with the result of command number 1, which then affects the operation of the command.
How to avoid Data Hazard?
Stall
Before explaining Stall, let’s look at the cause of data hazard.
In the first ADD operation, the value of $2 + $3 is stored in $1, and then the stored value of $1 is used in the next sub operation.
However, in this process, if steps 1 and 2 are executed before the Write back process where the add calculation is completed and the value is stored, the calculation will be performed with an incorrect value that was not added, so it must be updated through the Write back step like step 3 and then executed.
Therefore, the only way to avoid data hazards is to delay the instruction that follows. Stall is used to temporarily freeze the instruction that follows so that it is not executed. However, this slows down the overall processing speed because 2 cycles do nothing and delay the processing of the instruction.
In conclusion, although Stall can somewhat reduce performance, it is an important technique for maintaining data consistency and accuracy.
Forwarding
Forwarding is based on observation that you don’t have to wait until the command is over before trying to resolve the data hazard.
Because the result of command execution is passed directly to the next command before being written to the register file, commands can be executed quickly without stalling. It usually solve RAW hazard.
EX stage forwarding
: Directly transfer the value to the next command before the command writes the value to the register
MEM stage forwarding
: Make the following instructions available after memory access before saving the value to the register
Out-of-Order Execution (OoOE)
Which is more effective?
The basic idea of out-of-order execution is to improve efficiency by prioritizing processing of only prepared instructions. A command window is used to perform out-of-order execution.
Scoreboard
The CDC 6600 computer released in 1964, by Seymour Cray. The scoreboard was first implemented to allow non-sequential execution.
4 stages of scoreboard control
What is unique is that the decode step is divided into two parts: the issue and the read operand. This is one of the biggest features of out-of-order execution.
Get yuheun’s stories in your inbox
Join Medium for free to get updates from this writer.
Issue (ID1) : Decode instructions, check for structural hazard. Instructions are issued in program order. If there are no structural hazards or data dependencies, they are issued
Read operand (ID2) : Wait until no data hazards, then read operands, no forwarding
Execution (EX) : Operate on operands. When the operation unit receives an operand, the execution of the instruction begins. When the execution is completed, a completion signal is sent to the scoreboard
Write result (WB) : Finish execution. To avoid data collisions (WAR), write the result only if the previous instruction did not read the result register
3 parts of scoreboard
Instruction status : ID1, ID2, EX, WB
Functional unit status :
Register result status : Which functional unit will write register, if one exist.
Walk Through
Let’s take a look at an example to see how the scoreboard processes commands for each cycle.
In cycle 1, LD F6 34 R2 is issued. At this time, FU is not busy, and the result register is not written to another instruction, so it is issued. After the issue, FU is marked as busy, the operation to be performed is recorded in Op, and the source register and destination register are also recorded respectively.
The Rk flag is not related to whether the value of the register was actually read, but only indicates whether the required data is already prepared, so it is marked as ‘yes’. Since the F6 register is to store the result by the Integer FU, an integer is written to the register result status.
In cycle 2, the first LD instruction was issued in cycle 1 and is ready to read the source register, so it starts reading the memory value from R2.
At this time, the second LD instruction is not issued because the Integer Functional Unit is already processing the first LD instruction.
Let’s see cycle 3. In the functional unit state, the Rk flag corresponding to Fk is marked as “no”. This means that the corresponding register (Fk = R2) has already read the required value. In MULTD F0, F2, F4, the source register f2 is not ready because the second LD instruction has not been issued yet. Therefore, it is not issued.
Since the first LD instruction is completed, we mark the corresponding functional unit as not busy and record the result in the F6 register.
Now that the Integer function unit is finally free, the second LD instruction is issued. As in the first cycle, it writes the appropriate values to the function unit state.
In cycle 6, the LD instruction reads the operand, and MULTD is issued.
Among the operands of MULTD, F2 is loaded by the LD instruction, so it records in Qj that it comes from the Integer functional unit.
Since F2 has not been written result yet, we can see that ‘no’ is written in Rj. It is also recorded in the register result status that the destination register is written by the Mult1 functional unit.
The LD instruction has been executed. However, it is not yet the write result step that writes the value to the F2 register. Because F2, one of the operands of the MULTD instruction, is not ready yet, MULTD does not read the operand and waits. SUBD is also issued, and we can see that it uses the functional unit Add. The source register of SUBD F2 is also prepared by the integer functional unit, ‘no’ is written in Rk.
Now that the second LD instruction has been executed, the values of all source registers are ready, so in the next cycle, both MULTD and SUBD will perform read operands. DIVD instruction is also issued. The source register of DIVD, F0, is prepared by Mult1, but since Mult1 has not yet completed its execution, ‘no’ is written to the value of Rj.
We can see that both MULTD and SUBD are read operands in cycle 9.
Let’s skip a few cycles and see a situation where a WAR hazard can occur.
The ADD F6, F8, F2 instructions are trying to write the result to F6.
The DIVD F10, F0, F6 instructions need to read F6 as an operand, but if the ADD instruction writes the result to F6 at this point, a WAR hazard can occur where DIVD reads the wrong value. The scoreboard resolves the WAR hazard by waiting for the write result of add until the divide reads the operand.
Reference
Out-of-order scheduling — John Kubiatowicz, Electrical Engineering and Computer Sciences, University of California, Berkeley
https://cyber0946.tistory.com/90
https://namu.wiki/w/Scoreboarding#rfn-3
https://deep-math.tistory.com/33
https://wongsingfo.github.io/comp-sys/docs/arch/ooe/#details
https://slideplayer.com/slide/7009035/
https://www.techtarget.com/whatis/definition/speculative-execution
https://www.extremetech.com/computing/261792-what-is-speculative-execution
https://csg.csail.mit.edu/6.823S15/lectures/L12.pdf
https://wh00300.tistory.com/84
https://velog.io/@apphia39/%EC%9E%84%EB%B2%A0%EB%94%94%EB%93%9C-Instruction-Level-ParallelismILP
