Content deleted Content added
Added {{More citations needed}} tag |
For clarity, added reminder that the RAW dependency cannot be removed. |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 1:
{{Short description|Programming situation where an instruction refers to a prior instruction's data}}
{{More citations needed|date=September 2024}}
A '''data dependency''' in [[computer science]] is a situation in which a [[program statement]] (instruction) refers to the data of a preceding statement. In [[compiler theory]], the technique used to discover data dependencies among statements (or instructions) is called [[dependence analysis]].
Line 23 ⟶ 24:
== Types ==
=== Data hazards ===
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 condition|race conditions]] (also termed 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''
# read after read (RAR), a false dependency
Read after read (RAR) is not a hazard case.
Consider two instructions {{Mono|i1}} and {{Mono|i2}}, with {{Mono|i1}} occurring before {{Mono|i2}} in program order.
==== Read after write (RAW) ====
({{Mono|i2}} tries to read a source before {{Mono|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 prior instruction, the prior instruction has been processed only partly through the pipeline.
===== Example =====
For example:
i1. '''R2''' <- R5 + R8
i2. R4 <- '''R2''' + R8
The first instruction is calculating a value to be saved in register {{Mono|R2}}, and the second is going to use this value to compute a result for register {{Mono|R4}}. However, in a [[Pipeline (computing)|pipeline]], when operands are fetched for the 2nd operation, the results from the first have not yet been saved, and hence a data dependency occurs.
A data dependency occurs with instruction {{Mono|i2}}, as it is dependent on the completion of instruction {{Mono|i1}}.
==== Write after read (WAR) ====
({{Mono|i2}} tries to write a destination before it is read by {{Mono|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
In any situation with a chance that {{Mono|i2}} may finish before {{Mono|i1}} (i.e., with concurrent execution), it must be ensured that the result of register {{Mono|R5}} is not stored before {{Mono|i1}} has had a chance to fetch the operands.
==== Write after write (WAW) ====
({{Mono|i2}} tries to write an operand before it is written by {{Mono|i1}}) A write after write (WAW) data hazard may occur in a [[Concurrent computing|concurrent execution]] environment.
===== Example =====
For example:
i1. '''R5''' <- R4 + R7
i2. '''R5''' <- R1 + R3
The write back (WB) of {{Mono|i2}} must be delayed until {{Mono|i1}} finishes executing.
=== True dependency (read-after-write) ===
Line 58 ⟶ 99:
3. B = 7
A new variable, B2, has been declared as a copy of B in a new instruction, instruction N. The anti-dependency between 2 and 3 has been removed, meaning that these instructions may now be executed in parallel.
Note === Output dependency (write-after-write) ===
| |||