Question

Use the following code fragment:

1       sub x4,x4,x0

     2       add x3,x4,x0

     3       sub x6,x3,x2

     4       mul x1,x6,x7

     5       add x2,x5,x9

     6       div x5,x9,x2

     7       add x8,x1,x4

Draw the dependency graph among the instructions and indicate the type of data hazards (such as RAW, WAW, etc.) on each edge.

Answer 1

Answer : There are 3 types of hazards in Data Dependencies :

Let there be two instructions I and J, such that J follow I. Then,

1. RAW hazard(Read After Write): It occurs when instruction J tries to read data before instruction I writes it.
Eg:
I: R2 <- R1 + R3
J: R4 <- R2 + R3

2. WAR hazard(Write After Read): It occurs when instruction J tries to write data before instruction I reads it.
Eg:
I: R2 <- R1 + R3
J: R3 <- R4 + R5

3. WAW hazard (Write After Write): It occurs when instruction J tries to write output before instruction I writes it.
Eg:
I: R2 <- R1 + R3
J: R2 <- R4 + R5

Now in the given question instruction sequences are as follows:

I1 : sub x4,x4,x0

I2 : add x3,x4,x0

I3 : sub x6,x3,x2

I4 : mul x1,x6,x7

I5: add x2,x5,x9

I6: div x5,x9,x2

I7: add x8,x1,x4

From the above we can easily say that

Instructions I1,I2

I2,I3

I3,I4

I5,I6

I4,I7

are causing RAW Hazard

and instruction I3,I5 are causing WAR hazard

and there is no WAW hazard in the given set of instructions

So the dependency graph will be as follows :

In the above graph , Instruction I1, I2, I3 will exceute one after the other in the given order and then we can execute any of the instruction I5 and I4 as they have no dependency among them .

Depending upon instruction executed we will be executing remaining instruction as per given graph.