Data Flow Graphs And Their Linearization

D

Edith A. Lawson

r. Lawrence Coon

D

Carol Torsone

epartment of Computer Science

ySchool of Computer Science and Information Technolog

Rochester Institute of Technology

Rochester, New York 14623

USA

t

D

Abstrac

ataflow provides a mechanism to identify the parallelism inherent in a program
r
p
thereby providing a visualization that suggests a natural partitioning of the code fo
lacement on the nodes of a transputer. The intent of this report is to investigate the
representation of algorithms as data flow graphs and the linearization of these graphs.

N1. INTRODUCTIO

Data flow is a functional approach to programming that is based on the concept of data flowing from one a
m
entity to another. Rather than marching to the count of a program counter and manipulating the contents of emory cell, data flows between operators much like a truck that is carrying merchandise between two points: it

c
loads its cargo at point a; then travels across a highway linking it to its destination (point b) where it unloads its ontents. If another point c also wants the same merchandise, another truck is loaded with copies of the items and that truck travels across a different route to deliver its load.

This view of data flowing between points allows us to represent programs by graphs. The nodes represent

d
instructions (or operators) and the arcs represent the links over which data flows. Thus the arcs depict the data ependencies and highlight the parallel processing possible within an algorithm. Since instructions can execute s
a
as soon as their operands arrive, nodes that are not linked to one another can execute simultaneously as long a ll their inputs are available. The data dependencies determine the sequencing in a program, not a program counter.

Not only does this eliminate the need for the program counter, but also the concept of an updatable -
d
memory cell. Instructions do not reference memory, but rather process the data coming in on their arcs and pro uce results that are placed on their output arcs. If more than one operator needs the output of another, then y
a
that value is duplicated and each destination gets its own copy. There is never a wait for constant values, the re immediately available, whenever needed, to their destination nodes.

d
d

There are two basic types of data flow architecture that have been developed; data driven and deman riven. In the data-driven model inputs are evaluated without regard to their need. In other words, a node is

o
executed when it has received all of its inputs without checking the destination node(s) to see if they need the utput. The demand driven model is a form of lazy evaluation; arguments are not evaluated until they are needed. We will concentrate our discussion in this paper on the data driven model.

page 1