The RAW, WAW and WAR hazards we discussed in previous posts are with respect to registers. For memory accesses, there exists subtle data dependencies that are barely mentioned. These data dependencies include RAW, WAW and WAR as well. Note,

  1. Memory data dependencies only exist for accesses to the same memory address; for memory accesses to different addresses, load and store can be safely done out of order
  2. In MIPS 5-stage pipeline, all memory accesses are performed in MEM stage and thus are serialized, so these data dependencies will not happen in MIPS 5-stage pipeline. In this post, we will focus on CPU out-of-order scheduling.

RAW Data Dependency

An example is shown below. The value in R1 is stored in some memory address, and later on R2 is loaded from the same memory address.

Mem[Addr] <- R1 (store)
R2 <- Mem[Addr] (load)

If store and load are allowed to execute out of order, the load may get a staled value and a RAW data dependency may occur.

WAW Data Dependency

An example is shown below. The value in R1 is stored in some memory address, and later on R2 is stored to the same memory address.

Mem[Addr] <- R1 (store)
Mem[Addr] <- R2 (store)

If both stores are allowed to execute out of order, the memory address may store value of R1 instead of R2 and a WAW data dependency may occur.

WAR Data Dependency

An example is shown below. The value in R1 is loaded from some memory address, and later on R2 is stored to the same memory address.

R1 <- Mem[Addr] (load)
Mem[Addr] <- R2 (store)

If load and store are allowed to execute out of order, the load may get a “updated” value and a WAR data dependency may occur.

Conclusion

To determine if a load can be executed, we should check all uncompleted store that precedes the load in program order sharing the same data memory address.

Similarly, a store must wait until no uncompleted load or store that is earlier in program order and shares the same data memory address.

In next post, we will discuss how to handle data dependencies through memory in detail.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.