Conditions of Parallelism : Data Dependence

In Parallel or Sequential Execution of programs there are some concepts of dependence that we need to understand. These dependencies are known as Data,Control and Resource Dependence.


Here I will be focusing on Data dependence.


Data Dependence :


It can be explained as the ordering relationship between statements. There are five kinds of data dependence :

1. Flow Dependence : A statement S2 is flow-dependent on the statement S1 if an execution path exists from S1 to S2 and if at least one output of S1 feeds input to S2, i.e. if the output of statement S1 is same as the input of statement S2. It is denoted as S1 ----> S2.
2. Anti Dependence :  A statement S2 is anti-dependent on statement S1 if S2 follows S1 in the program order i.e. if the output of S2 overlaps with the input of S1.It is denoted as S1 -|--> S2. 
3. Output Dependence : A statement S2 is output-dependent on statement S1 if the output of S2 overlaps with the output of S1.It is denoted as S1 -o--> S2.   
4. I/O Dependence : Read and Write are I/O statements. I/O dependence occurs not because the same variable is involved but because the same file is referenced.
5. Unknown Dependence : When the dependence relation cannot be determined between two statements then it is known as unknown-dependence.

The dependence are shown with the help of a dependence graph. The nodes correspond to the program statement (instructions), and the directed edges with different labels show the relationship.

Example :

Text File (5tH.txt):

S1: Load R1,A

S2: Add R2,R1

S3: Move R1,R3

S4: Store B,R1

Java Program : 

package aca;
import java.io.*;

public class DataDependence {

    public static String s[] = new String[6];
    public static String opt[] = new String[6];
    public static String opt1[] = new String[6];
    public static String str="";
    public static int i=0;
    public static int flw=0,ant=0,out=0,tot=0;
    
    public static void main(String[] args) {

        try{
            File f=new File("5tH.txt");
            FileReader fl=new FileReader(f);
            BufferedReader bf=new BufferedReader(fl);
            while((str=bf.readLine())!=null){
                s[i]=str.substring(0, str.indexOf(':'));
                opt[i]=str.substring(str.lastIndexOf(' '), 

                str.lastIndexOf(',')).trim();
                opt1[i]=str.substring(str.lastIndexOf(',')+1,

                str.length()).trim();
                i++;
            }
            Flow(s,opt,opt1);
            Output(s,opt,opt1);
            Anti(s,opt,opt1);
        }catch(Exception e){
            System.out.println("Error : " );
            e.printStackTrace();
        }
    }
    
    public static void Flow(String[] s, String[] opt, String[] opt1){
        int p=0;
        System.out.println("Flow Dependence : ");
        while(p!=s.length-1){
            if(opt[p]==null&&opt1[p]==null&&s[p]==null){
                opt[p]=" ";
                opt1[p]=" ";
                s[p]=" ";
            }
                for(int j=p+1;j<s.length;j++){
                    if(opt[p].equalsIgnoreCase(opt1[j])){
                        System.out.println("FLOW :" + s[p] + " ----> " +s[j]);
                        flw++;
                    }
                }
                p++;
                }
    }
    
    public static void Output(String[] s, String[] opt, String[] opt1){
        int p=0;
        System.out.println("\nOutput Dependence : ");
        while(p!=s.length-1){
            if(opt[p]==null&&opt1[p]==null&&s[p]==null){
                opt[p]=" ";
                opt1[p]=" ";
                s[p]=" ";
            }
        
        for(int j=p+1;j<s.length;j++){
            if(opt[p].equalsIgnoreCase(opt[j])){
                System.out.println("OUTPUT : " + s[p] + " -o--> " +s[j]);
                out++;
            }
        }
        p++;
        }

    }

    public static void Anti(String[] s, String[] opt, String[] opt1){
        int p=0;
        System.out.println("\nAnti Dependence : ");
        while(p!=s.length-1){
            if(opt[p]==null&&opt1[p]==null&&s[p]==null){
                opt[p]=" ";
                opt1[p]=" ";
                s[p]=" ";
            }
        
        for(int j=p+1;j<s.length;j++){
            if(opt1[p].equalsIgnoreCase(opt[j])){
                System.out.println("ANTI : " + s[p] + " -|--> " +s[j]);
                ant++;
            }
        }
        p++;
        }

    }

}

OUTPUT :




Flow Dependence :
FLOW : S1 ----> S2
FLOW : S1 ----> S4
FLOW : S3 ----> S4


Output Dependence :
OUTPUT : S1 -o--> S3


Anti Dependence :
ANTI : S2 -|--> S3