On choosing a plan for the execution of data flow program graph
B. Robič, J. Šilc
Informatica, 1986, 10(3): 11-17
In the paper we present a generalized analisys of static data flow program graphs. These graphs are allowed to have nodes that use more than one unit of time for their execution. Such graphs are more realistic than graphs with nodes that execute in one unit of time. We restrict our consideration to graphs with integer execution times of their nodes. In the paper we first briefly describe the data flow concept of computation. Next we describe the basic data flow architecture and common way of the execution of a graph on it. We show that this way of the execution has a drawback. In the next sections we introduce the notion of a static data flow program graph and describe the state of the execution of such graph. The state consists of a few time depending sets of nodes. We define a plan for the execution of a program graph which is the result of the analysis of the graph made before its execution. There are two special plans for the execution. Information, obtained by these two plans is used for defining the third special plan, which we call the heuristic plan for the graph execution. The execution of a graph according to this plan may minimize the number of processors needed, without lengthening the total execution time of the graph. Finally, we informally describe the algorithm for obtaining plans for the execution.
BIBTEX copied to Clipboard