Dependency relations

Determine the dependency relations among the following instructions:

I1: a=b+c;

I2: b=a+d;

I3: e=a/f;

Then, Read Sets & Write Sets of given Instruction

For I1,                         R1= {b, c}       W1= {a}

For I2,             R2= {a, d}       W2= {b}

For I3,             R3= {a, f}        W3= {e}

For Instructions I1 & I2

R1 ^ W2 = {b}            ; Anti Dependence

R2 ^ W1 = {a}            ; Flow Dependence

W1 ^ W2 = {}            

Therefore I1 & I2 are both Flow Dependent and Anti Dependent.

For Instruction I2 & I3

R2 ^ W3 = {}

R3 ^ W2 = {}

W2 ^ W3 = {}

Therefore instructions I2 & I3 are independent of each other, and can be run in parallel.

For Instruction I1 & I3

R1 ^ W3 = {}

R3 ^ W1 = {a}            ; Flow Dependence

W1 ^ W3 = {}

Therefore instructions I1 & I3 are Flow Dependent.