KEMBAR78
Data Dependency Graph | PDF | Computers | Technology & Engineering
Scribd
Upload
144 views4 pages

Data Dependency Graph

This document discusses data dependency graphs (DDG), which represent data dependencies using acyclic graphs with instructions as nodes. DDGs differ from data flow graphs in that they do not include control structures. DDGs are normally represented using tree data structures that examine instruction pairs for dependencies and construct the graph accordingly. An example DDG is given for 5 instructions showing their dependencies.

Uploaded by

Vishal Sindhnoor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
144 views4 pages

Data Dependency Graph

This document discusses data dependency graphs (DDG), which represent data dependencies using acyclic graphs with instructions as nodes. DDGs differ from data flow graphs in that they do not include control structures. DDGs are normally represented using tree data structures that examine instruction pairs for dependencies and construct the graph accordingly. An example DDG is given for 5 instructions showing their dependencies.

Uploaded by

Vishal Sindhnoor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 4

DATA DEPENDENCY GRAPH

• This is a method of representation of data


dependecies using acyclic graphs.
• Here instruction are symbolised by nodes in
the graph .
• This is normally used for straight line code in
our syllabus.
• This is also called as DAG dependency , DAG
code.
UNIQUENESS OF DDG
• DDG differs from data flow graph(DFG) as it
doesn’t comprises control structures.
• Also unlike DDG ,DFG indicates raw
dependencies because of single assignment
data flow model as shown.
• Ex :
i1 i2

• instruction i2 is dependent on i1
REPRESENTING DDG
• This is normally represented by tree data
structures as the name itself indicates.
• The basic principle behind this is to examine
all the possible instruction pair for
dependencies.
• If dependencies exists accordingly then
construct the graph accordingly as explained
below.
Ex

• i1 :load r1,a; i1 i2

• i2 :load r2,b;
• i3 :add r3, r1,r2;
i3
• i4 : mul r1,r2,r4;
• i5 :div r1,r2,r4; i4

i5

You might also like