Data Flow Graphs And Their Linearization

this report is to investigate the representation of algorithms as data flow graphs and the linearization of these graphs. N 1. 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, whenev..