STRUCTURED DATA FLOW: A QUASI-SYNCHRONOUS INTERPRETATION OF DATA DRIVEN COMPUTATIONS.
Item
-
Title
-
STRUCTURED DATA FLOW: A QUASI-SYNCHRONOUS INTERPRETATION OF DATA DRIVEN COMPUTATIONS.
-
Identifier
-
AAI8611347
-
identifier
-
8611347
-
Creator
-
GOTTLIEB, ISRAEL.
-
Contributor
-
Jacob Roolenberg
-
Date
-
1986
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
This thesis develops an interpretation of data flow graphs which imposes an additional level of execution disciplines on the usual data flow mechanism. A data flow graph is first partitioned into computation paths in such a way that every node belongs to exactly one path. As in data flow, a node becomes enabled when all of its data have arrived. However, the scheduled activity which results is not restricted to the individual node. The assigned processor may continue to execute the successors of that node along the computation path to which it belongs. This execution proceeds in a sequential fashion much as it does in a conventional von Neumann processor. In order for the nodes encountered in the course of such sequential execution to be executable, any operands they require must be available. If this is found not to be the case, the execution sequence is suspended via a form of exception handling.;A set of basic programming constructs based on this approach is developed and an operational semantics is defined for them. Determinacy and liveness in a modified form are demonstrated for computations expressed in this system.;The question of what constitutes an optimal partition of data flow graphs, under the SDF execution discipline, is addressed. An optimality criteria for static programs is defined and an algorithm for achieving it is given.;A preliminary design of an architecture for implementing the SDF execution discipline is presented. The performance improvement over conventional data flow which can be expected from SDF is discussed.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
-
Program
-
Computer Science
