[Solved]: Does register renaming remove all kinds of WAR hazard?

Problem Detail: 

For the following two instruction

[Note: MOV Destination, Source ]  i1 : MOV R1, R2 i2 : ADD R2, R3 

Since i1 is reading from R2 and i2 is writing to R2 there is a WAR data dependency and by register renaming like below we can remove this hazard

i1 : MOV R1, R2 i2 : ADD R4, R3 

What are the other possible situations where such WAR hazard can occur ? and does register renaming solve all kinds of WAR hazard ?

Asked By : vikkyhacks

Answered By : Wandering Logic

Write-after-read (WAR) hazards are pervasive throughout all of computer systems, although different subfields call it different things. Renaming of one kind or another (and called one thing or another) is the most general method I can think of for working around these kinds of problems.

Register renaming is the form of renaming used in CPUs that want to expose more instruction-level parallelism. It can be made relatively efficient because the number of programmer-visible register names on most architectures is bounded and small.

From a computer architecture point of view, an additional problem for write-after-read hazards is dealing with load and store operations to main memory. Register renaming won't help with this problem, because the space of visible memory locations is enormous compared to the number of available registers. For this problem a different kind of "renaming" is done where store operations are buffered in a store queue for a period of time. The store queue can be made relatively small because on most CPUs the number of stores that we want to have "in-flight" simultaneously is relatively small. Thus the store-queue can be relatively small and we can afford to have every load operation perform an associative search of the store queue.

But the renaming concept is fundamental outside of computer architecture too. An analogous situation occurs in the implementation of any programming language with automatic local variables (which is most programming languages.) You can view the locally declared variables in the source code as analogous to register names and activation records (stack frames) as analogous to renamings of the registers. This concept is leveraged in several parallel programming languages, for example in the Id programming language (one of the precursors to Haskell) and the Cilk programming language (an extension to C) the fact that each procedure writes its local variables in a different activation record is used to allow procedure calls to execute in parallel.

In transaction processing systems used in large databases multiversion concurrency control is analogous to renaming. Each transaction sees, and modifies, its own "snapshot" of the entire memory and the snapshots are committed atomically. The snapshots are generally implemented using techniques that are more similar to store queues than to register renaming.

Renaming is also a fundamental technique used in non-blocking synchronization. Suppose you have some container data type (like a map) where you have a unique pointer to the root of the implementation. You can implement lock-free atomic operations by copying the pointer, allocating a new data structure, copying the entire data structure from the old copy to the new, modifying the new version and then trying to compare-and-swap the pointer to the new copy for the pointer to the old copy. Copying an entire data structure would be ridiculously expensive, so in general if you want to do this you would use purely functional data structures.

If you couldn't already tell, this is my favorite topic, and I could go on for hours. So I'll stop here since I've probably written way more than you wanted.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30108

 Ask a Question

 Download Related Notes/Documents