Data Flow Graphs And Their Linearization
Edith A. Lawson
r. Lawrence Coon
epartment of Computer Science
ySchool of Computer Science and Information Technolog
Rochester Institute of Technology
Rochester, New York 14623
ataflow provides a mechanism to identify the parallelism inherent in a program
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.
Data flow is a functional approach to programming that is based on the concept of data flowing from one
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
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
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
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
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
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.
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
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.