ON CHOOSING A PLAN FOR THE EKECUTION OF 
DATA FLOW PROGRAM GRAPH 
INFORIVIATICA3/86 
Borut Robič, Jurij Šile 
Jožef Štefan Institute, Ljubljana 
UDK: 681.519,7 
ABSTRACT - In the paper ue present a generalized analisy5 af static data 
<low progran graphs. These graphs are allowed to have nodes that use more 
than one unit of tioe for their execution. Such graphs are more realisti.c 
then graphs with nodes that execute in one itnit of tirne. Ue restrict our 
consideration to graphs uith Integer execution times of thelr nodes. In the 
paper ue first briefly describe the data flow concept of computation. Next 
ue describe the baslc data flow architecture and a comnon way of the 
BKecutlon of a graph on it. Ue shou that this way of the eKecution has a 
drauback. In the next sections we introduce the notion of a static data 
flou prograa graph and describe the state of the execution of such graph. 
The State consiste of a few tirne depending sets of nodes. Ue define a plan 
for the execution of a program graph uhich is the result of the analysis 
of the graph nade before its execution. There are tuo special plans for the 
eKecution. Infornation, obtained by these tuo plans is used for defining 
the third special plan, uhich ue call the heuristic plan for the graph 
execution. The execution of a graph according to this plan iiidy nlniinize 
the nuober of processors needed, uithout lengthenlng the total e«ecution 
ti«e of the graph. Finally, ue informally describe the algorithm for 
obtaining plans for the execution. 
O IZBIRANJU NAflRTA ZA IZVRŠEVANJE PODATKOVNO PRETOKOVNIH GRAFOV - V delu je 
podana posplošena analiza statiCnih podatkovno pretokovnih grafov. Tofike 
taksnih programskih grafov se lahko izvrSujejo poljubna celo Število 
Časovnih enot. Uvodoma je opisan koncept podatkovno pretokovnega računanja. 
Sledi opis znafiilne podatkovno pretokovne arhitekture ter enega izmed 
oolfnih izvrševanj podatkovno pretokovnega grafa na njej. Prikazana je 
slabost taksnega naiiina izvrSevanJa. Po opisu statičnega programskega grafa 
sledijo definicije onoZic toflk, ki sestavljajo stanje izvrševanja grafa. 
Definiran Je naCrt izvrSevanJa programskega grafa, ki Je rezultat njegove 
predhodne analize. V sploSnem obstaja vefi naCrtov za izvrševanje. IzvrStve, 
ki ustrezajo posaaezni« naCrtom, se razlikujejo po uporabljenem Številu 
procesnih elementov in ne podaljšujejo minimalnega Časa, potrebnega za 
izvršitev programskega grafa, v kolikor Je na voljo dovolj procesnih 
elementov. Obstajata dva posebna naCrta za t.i. takojSnJe in leno 
izvrševanje, ki v sploSnea ne ninimizirata Števila potrebnih procesnih 
elementov. Ker sistematično pregledovanje vseh možnih naCrtov vodi v 
kosbinantorieno eksplozijo, Je v delu predlagan hevristlCni postopek za 
izbiro naCrta IzvrSevanJa, ki teži k mininizaciji Števila procesnih 
elementov. 
1. INTRODUCTION 
A data flou systBo oomprises a user-oriented 
high-level l_anguage, a low-level base langua-
ge, and a hi9hly-parallel computer architec­
ture. User programs are uritten in the high-
level language and , are translated into 
corresponding programs in the base language. 
A base language program is a graph oomposed 
of nodes interconnected via directed arcs. 
Eaoh internal node is an operation and re-
presents a separate processing elemet oapable 
of accepting, processing and emitting value 
tokens travelling along the graph arcs. Each 
operation e»ecutes only uhen ali tokens, oar-
rying operands required by that operation 
have arrived. At that point the operands are 
consumed by the node and neu tokens, carry-
ing results, are placed on the output aros 
CC0M82D. This fundaaiental princLple permits 
the graph to be napped onto a computer archi­
tecture conslsting of a very large nunber of 
independent processing elements and suitches, 
able to connect any tuo processing elements, 
making a data path betueen them. Separate 
data paths can cross the suitch simultaneous-
ly CKF6S8«]. For example see Fig.1. 
2. SIHULATION OF DATA FLOU ARCHITECTURE 
In general not ali operations ( nodes of a 
graph ) need to be assigned to processing 
elements at the same. moment since not ali 
operations have avallable ali input operands 
at that moment. To make the data flou concept 
possible even uithout a very large number of 
processing elements data flou computers are 

•J^.?^ 
Fig.1: In the switch lattice the squares re-
present processing eletnents, circles repre-
sent suitches, lines represent data paths. 
PROCESSrNG 
UNIT 
. PEp 
t 
•. o 
N 
ftRV I 
SECONDAHV 
IX 
y 
Fig.2: The model of data flou machine. 
usually based on a packet communication 
machine organizatlon, consisting oj a circu-
lar instruction exeoution pipeline ol resour-
oes. The resources are meiiiory, arbitration, 
processing and distributlon unlt. The «eoiory 
unit is divlded into the primary and seoon-
dary part, the lormer beeing faster. The pro­
cessing unit consists of a number of proces­
sing elements (Fig,2). 
Nodes, having none of their input operands 
arrived reside in the seoondary ine«iory. These 
are nonoreated nodes. At the moment uhen the 
first input operand has arrived the node is 
oreated, i.e. moved to the primary memory to 
wait for the other input operands. A created 
node becomes executable at the moment when 
the last input operand has arrived. 
Exeoutable node is ready for the execution 
and may be transferred (fired) to the proces­
sing unit uhere a processing element čtarts 
to execute it. It is the arbitration unit 
that deoides which of the nodes are e^ecuta-
ble and vhich processing elements are to be 
allocated to. The plaoe in the memory unit 
uhich uas occupied by that node is now set 
free. While the node is beeing exeouted the 
distribution unit finds out uhere the nodes 
uaiting for the result are. When the result 
is produced, the distribution unit send;, it 
to ali nodes uaiting for it, creating iome of 
them if neocessary. The node that has been 
eKBCuted is now deleted. 
Such exeoution raay need more processing ele­
ments than there are in the processing unit. 
The problem where there are more sKecutable 
nodes than processing elements must be solved 
during the exeoution of a graph. Ali these 
nodes are exeouted in several steps implying 
the lengthening the total minimum exec;utiuti 
tirne of a graph. Note that after each such 
step again the same problem may appear. 
An anaysis of the graph before its executian 
may prevent the problem discussed above. The 
basio observation is that in general not ali 
executable nodes have to be fired immedi-
ately, since some of tfiem may wail a pe.riod 
of tirne in the memory uithout lengthening 
the total iginimum execution tirne of a graph. 
Analysing the graph we obtain severa! plani. 
for its eKBCution, each execution having its 
oun characteristic. Information oblainded b> 
the plan is used by the architecture com-
ponents during the actual ext!Culion of a 
graph in deciding uhich executable nodes 
should be retained. The execution according 
to a properly chosen plan may result in roini-
nization of some resources needed, such as 
the number of processing elements. Ue point 
out three special plans for the executiQn. 
Execution according to the first of them is 
esBentially the immediate execution, des-
oribed ahove. The execution according to the 
second plan is the opposite of the immediate 
execution, uhile the executian according to 
the third plan often ušes minimum number of 
processing elements. Executing graphs accor­
ding to this plan we may avoid the problema 
discussed above. 
STATIC DATA FLOW PROGRAM GRAPH 
There are two uays of envisaging a data ilaw 
program: as a static or as a dynamic data 
flow program graph. Ue limit our discussion 
to static graphs. In short, static data flow 
program graphs are acyclio, uhile the dynamic 
are not. 

13 
We define a static data fSow program gi-aph 
6 = ( V,A ), in further discussion program 
graph, ta be a directed, acyc\ic, and simple 
(no inultiple arcs ol the same direction bet-
ween two nodes) gL'aph. The sst V ol noJes is 
partitioned into three disjoint sets Vj ,V| , 
Vp ol starting, internal and final nodes, 
respectively. The starting nodes have no 
input archs uhile the (inal nodes have no 
output archs. Furtherinore, there oiust always 
eyist a path to any internal or final node 
{rosi some starting node and, similarly, a 
path troB any starting or internal node to 
soae final node. Starting nodes are used to 
carry the input values uhile the final nodes 
store the results. Internal nodes carry ope-
rations CRQfi863. The tirne of the eKScution of 
a node n is t„, uhere t„ = 1 (or ali starting 
and (inal nodes n. 
K node n is beeing eKtouted at the 
moment j we define l'<n,Vf l to be the 
sum o( tbe length o( the longest path Irom 
the 5et of its sons to the set o( the (inal 
nodes and, the tirne neccessary (or the node n 
ta finish its evecution. 
4. THE STATE OF THE GRAPH EXECUTION 
The Etdte of the eKecution of a graph at the 
»oment j Is the quintuple Oj =(Nj , C, ,Ej ,fj , Dj ) 
uhere Nj , Cj ,Ej ,Fi and D, are the sets of non-
created, created, executable, eMecuting and 
deleted nodes at the monent J, respectively. 
There are also (ew other sets used for com-
puting the sets mentioned. The sets are des-
crlbed bellou: 
.'•V:i7'!, 
.-v 
2 1 
i n+1 '• • n + i '; 
1 
k 1 
V 
fn+r+i; 
^-. 
/-r 
•2n+l j 
i' 
Hlaz, Mheu 
Fig.3: Static data (lov program gcaph. 
The. length o( a path is defined to be the sum 
o(,the execution tiities of the nodes along the 
path. The path Irom a set o( nodes A te a set 
o( nodes E is de(ined to be any path that 
starts at some node o( the set A and ends at 
soae node o( the set B. The longest path (rom 
the set A" to the set B is a path that has 
among ali the paths from the set A to the Siil 
B saKioal length. The length o{ the longest 
path (rom the set A to the set B is described 
by 1<A,B). When the set consists o( only 
one element ue substitute the set by its 
element. For example, l(n,Vp) is the length 
of the longest path from the node n to ' the 
set of the final nod = s. Note that sinot; the 
program graph as acyolic by assumption, the 
lengths l(«i,nJ for any pair of nodes can 
easily be computed using one of well knawn 
algorithms CLaw743. The evaluation of 1(A,B) 
is then trivial for any two disjoint sets of 
nodes A and B. 
I • 
^l 
(enecuted nodes) is the set of ali the 
nodes fired before the moment j that 
have finished their-execution at the 
moment j and put their results on ali 
output arcs, 
(neu created nodes) is the set" jf ali 
those nodes that received at ' the 
moment j the first input oper and, 
(old created nodes) is the set of al! 
those nodes that had been created at 
any of the moments before the moment j 
yet did not fire until the moment j-1 
including, 
(created nodes) is the union of old 
and new created nodes, 
(new ejtecutable nodes) is the set a( 
ali those nodes that have received the 
last input operand at the moment j, 
(old executable nodes) is the set D( 
ali those nodes that had become eKecu-
table before the moment j but have not 
fired until the moment j-1 including, 
(enecutable nodes) is the union of the 
old and neu eKecutable nodes, 
(unoonditionaIly executdbifr nodes) is 
the set o( ali those executable node-i 
that must be fired at the moment j so 
as not to lengthen the total ekeoutior-
tinej 
(oonditionally executable nodesi is 
the set of ali those executable nodes 
that are fired at the moment j 
although they oould be fired later 
uithot lengthening the total execution 
tirne of a graph, 
(neu executing nodes) is the set of 
ali the nodes that started executing 
at the moment j, 
(old executing nodes) is the set of 
ali those nodes that had been fired 
before the moment j yet have not fini­
shed their excution till the moment j 
including, 
(executing nodes) is the union of the 
old and neu executing nodes, 
(noncreated nodes) is the set of ali 
those nodes that have not created till 
the moment j including, 
(deleted nodes) is the set of ali 
those nodes that executed till the mo­
ment j including, 
(crltical nodes) is the set oi ali 
those nodes.that alluays become uncon-
dltionally enecutable at the same 
monent j regardless of the plan of the 
execution. 
5. THE PLAN FOR THE EXECUTION 
The plan of the exeoution is a supervisor 
that Controls the eKecution of a program 
Ef 

graph. Conae()uent 1> , the plan Impl/es a 
certain degree of control flou in data flow 
architeoture and is realized by a time 
control vector associated to each node o( a 
program graph. 
The plan lor the eKeoution o( a graph is de-
terained by the rule whloh selects the sets 
Ej. There are two trivial plans for the ene­
cution of a graph. These are a plan for inne-
diate and a plan for lazy eKeoution, The plan 
for iamediate eKecution is determined by 
choosing E] to consists of ali those enecuta-
ble nodes at the moment j Ihat could be fl-
red even later. The plan for the lazy enecu­
tion is determined by forcing Ej to be eaipty 
at ali ooinents j. Consequently, the inimediate 
e«ecution fires the nodes as soon as possible 
while the la2y eKecution defers firing to 
the last possible moment. In gener.al, none of 
these tuo eKecutions minimizes the number of 
prooessing elements needed. The plan for the 
eKecution that ušes minimum number of proces-
sing elements could be found by sistematic 
eKaminatiun of ali possible rules for the 
choosinc) tne sets E' . Sinoe ue want to avoid 
the co»t)indt.ori 3! explosion we try to find a 
heuristic rule sucn tnat the eKecution accor-
ding to the associated heuristic plan wouId 
use the number of processing elements as 
close as possible to the theoretical louei-
bound. For eKample, enecution of the graph on 
Fig.3 according to the immediate plan needs 
n+1 processing eleoients, since at the moment 
j = 1 the node 1 is fired simultaneousIy uith 
the nodes n + i, 14iin. Similarly, the la2y 
plan implies the execution that tnvolves n+1 
processing elements, too. Namely, at the last 
step the node n is fired together uith the 
nodes n + i, 1iiin. On the other hand, the 
heuristic plan offers ar\ eKecution uith only 
twa processing elements for at each step only 
the pair of nodes k, and r\*k are beeing exe-
cuted. 
The plan for the heuristic eKecution uill be 
discussed belou. 
6. THE TIME CONTROL VECTOR 
Every node n is associated uith a time con­
trol VeCtor T„ = ( Tc„ , tE.„ , Tfn ) . 
^Cn t 'E.n ^""^ V.n ^^^ the iiioments uhen the 
node n becomes created, eKecutable and fired. 
Time control vectors are camputed for each 
node uhile the plan for the execution is bee­
ing constructed. Sinoe ali the sets described 
above are affected by the rule for choosing 
the set Ej , the time control vectors depend 
on 3 plan constructed. Every plan for the 
eKecution has its oun set of time control 
vectors. To point out that the time control 
vector of a node n is coraputed according to 
the plan for immediate or lazy eKecution we 
ti"* urite Ti(™"or ti?'", respectively. 
7. THE PLAN FOR HEURISTIC EXECUTION 
7.1. CRITICAL NODES 
and tl,"i = <t||"» ,i'^'„' .T^"^" ) time control vec­
tors of a node n according to lazy eKecuti­
on. Then ue Bay that an internal node n is 
crltical if TJ!;;'" = T|?^» 
THEOREH 1. 
'F.n 
Every oritlcal node n is fired at the 
noaent T^'„ , regardless of the plan of 
the eKecution. 
PROOF; tp"^ is the first possible moment uhen 
the node'n can be fired, regardless oi the 
plan of the execution of a program graph. On 
the other hand, T|?^» is the last moment uhen 
the node can be fired uithout lengthening the 
total eKecution time, taken over a\\ possible 
plane of the execution. Consequently, if n is 
a critical node, then T'J TS' uhich 
means, that the moment T^/„ is the only moment 
uhen the node n can be fired in ali possible 
plans of the eKecutions. O.E.O. 
LEMMA 1. 
There Is at least one crltical node in 
the program graph. 
PROOF: Let be p the longest path from the set 
of starting nodes to the set of flnal nodes. 
Then, in any plan of the execution the son of 
starting node on the path p must be fired at 
the moment j=I so as not to lengther the 
total eKecution tirne. Consequently, the son 
of the starting node is critical. Q.E.D. 
THEOREM 2. 
A node is critical If and only if it Is 
on a longest path from the set of star­
ting nodes to the set of flnal nodes. 
PROOF 1 Let p be some longest path from the 
to the set Ve By Lemma 1 the son of 
™ ) be time control 
vectors of "a nod'e n according to immediate 
sat 
the starting node on the path p is critical. 
Nou suppose that ali flrst k > D internal 
nodes n, , n2 i. .., n,, on the path p are criti­
cal. Consec|uently, the flrst moment at uhich 
the node nj,^, can be fired Is the moment 
l + E-L, tn.. Slnce the node njj^^ is on the longest 
path' from the set V^ to the set Vp this is 
also the last moment, uhen it can be fired, 
so as not to lengthen the total eKecution 
time of the graph lmplylng that the node n,,^, 
is critical. Canversely, suppose a node n 
is .critical. Conslder the longest path p of 
the ali paths from V^ to Vp , passlng the node 
n. Ue dedne the subpath p' of the path p tu 
be the path consistlng of ali the nodes from 
Vg to the father of the node n. Simllarly, 
the subpath p" of the path p consists of ali 
the nodes from the son of the node n to the 
set Vp . Ue deflne l(p') and Up") to be the 
lengthfi of the paths p' and p", respectively. 
Note, that slnce p is the longest path from 
Vg to Vf through the node n, the path p' must 
b« the longest of the paths from V^ to the 
tet of fathers of n. Similarly, the path p" 
oust be the longest path from the set of sons 
of the node n to the Vp . Suppose the relation 
Hp')+tn+l<p") < KVg.Vp) holds. Then there 
must be some node oi on the path p, that can 
be fired at at least tuo different moments. 
The node m must be either on the path p' or 
on the path p", slnce the node n is criti­
cal, by assumptlon. Uere the node m on the 
path p' the node n could be fired at 

it least two different itioments contradic-
ting the assumption that it is critical. If 
the node « were on the path p", a similar 
argument would result. Consequently, relation 
1 (p')+tn+ 1 (p" ' = HVsjVp) is true, implyincj 
that the path p is one of the longest paths 
fr(i« Vs to Vp Q.E.D. 
Let Ej be the set ol ali critical internal 
nodes at the mooient j. We call the value 
5 = na« I E'' I, whtre lij^t* the mdxi»al ci^i-
tical parallelisn of a program graph, uhere 
t*= KVs ,Vf )-1 . 
Constructing the longest paths from Vs to Vf 
LLavlbl and considering their nodes, the cri­
tical internal nodes are easil/ computed. 
Ue could deternine the critical nodes also 
by coaputing the tirne control vectors associ-
ated to the plan for the immediate and lazy 
e«ecution and oomparing their third compo-
nents, for each internal node. 
7.3. THE PLAN FOR HEURISTIC EXECUTION 
Since the lower bound on the aiinlnuin number 
of processing units needed is given by a, ue 
choose the sets E* in such a way, that the 
nunber IFj - Vp I is on each step j, Mjit", as 
close as possible to a. To do this we first 
of consider the number c = I Ej^ - Vf I + 1 F"'" 
the processors that are already needed at the 
noment J. If this number is gceater than or 
equal to o, nothing is put into the set Ef . 
On the other hand, if o < a, we consider the 
executable nodes, that need not to be fired 
i.e. at the moment j 
are at most m = m - c 
of them into the set Ej , Houever, if 
are more than m such nodes n, we choose 
them, having the highest values l(n,Vf), and 
put the« into the set E* (Fig.A). 
the set Ej -E* . If there 
such nodesi we put ali 
there 
«1 of 
7.2. UPPER ANO LOUER BOUNOS ON ji„i„ 
Let us define Pminto be the minimum numbar of 
processing elements needed for the execution 
of a program graph, taken over ali possible 
plans of the executian. Me want to bound Pmin 
as much as possible. 
'-^' Cimm ^"'^ •'ia/y deoote the number of piroces-
sing elements needed in the immediate ana 
lazy GKecution of a program graph, respec-
tively. Ue define the average paral lel isiu of 
a program graph to be n 
*'Seq 
/t*, wherfc 
^&eq 
= rtn , ne V| , and maximal paral lel ism 
to be Tnl' . We also define o = max<rnT,C>,' 
and p = oin<pimm , >iia2y >• Then the following 
theorea illustrates the upper and lower 
bounds on p„i„ . 
eise Choose m nodes n from Ej - E* having 
the longest values l(n,Vp) and put 
them into the set E' ; 
end; 
THEORE« 3. 
Minioal number of processing elements 
needed is bounded by ct ^ ^i^in - ?•. 
PHOOFi In čase of ? 
since there exist5 
^ critical nodes mus 
that 5<rit1 . Let m , 
number of internal e 
ž ril the proof is evident 
a moment j uhen at least 
t be fired. Suppose nQw 
j = 1,2,...,t' denote the 
xecuting nodes at the mo-
Fig.^!-Heurlstic choosing the sets Ej 
8. ALGORITMU FOR OBTAINING EXECUTION PLANS 
»ent j. Then 
(ij < ». 
''Seq 
for 
<. 
ali j 
. rt* 
Pj = tse, . Suppose that 
= 1,2,...,t* . Then ue have 
•-Pi = t 
seq 
a contradic-
tion. ConsequentIy, 
Since the number p 
have Pj- i TitT , and 
right side of the 
dent. O.E.D. 
pj- ia, for some j', lijit. 
j. is an integer, we also 
a fortiorl Pmjn- 1^"^ • The 
nonei^uation is also evi-
In this section we desoribe the algorithm for 
obtaining a plan of the execution. Different 
plans may be obtaind according to the rule by 
uhich the subsets E' are chosen (see step 15). 
At the moment j 
Fj , and Fj"*" are 
starting nodes. 
the set V - V„ . 
Q the sets 
-I ' 
initialized to the set Vj of 
The set Nj is initialized to 
AU the other sets are empty. 
If ue • get a = p then at least one of the 
plans for immediate or lazy execution is also 
ar\ optiaal one. If o < p, uhich is much more 
possible, ue oan try to push the upper bnund 
3 doun by additional coinputations uhere 
ue chose another plan of the program 
graph execution. For example, ue may try to 
choose the sets E* on each step in such a 
way, that IF - Vp I , Ižjsf, is as close as 
possible to a. The details are discussad in 
next section. 
" TrT is the louest integer, greater or equal 
to r. 
The plans for immediate and for lazy execution 
are computed by choosing Ej" := Ej - E* and 
E' := 0, respeotively, on each step (15). The 
plan for the heuristlc execution is obtaind by 
choosing the sets E" on each step (15) accor­
ding to the sequence desoribed on Fig.^. 
The algorithm is implemented on LSI-11/23 Com­
puter under RT-11 operating system and tested 
on several program graphs. The Fig.7 describes 
an analysed program graph and the resulting 
tirne control vectors obtained. 

16 
(1) Evaluate l(iD,n) lor ali nodes m,n by coniputing the transitive 
closure of the program graph ; 
(2) initialize sets ; j := 0; 
(3) while Dj * V do 
beoin 
J := j + 1 i 
Fj t = < n I n linished enecution at the moment j } (5) 
(6) 
(7) 
(fi) 
(9) 
i\0) 
(11) 
(12) 
(13) 
(U) 
(15) 
(16) 
(17) 
(18) 
(19) 
(20) 
,new 
i 
o Id 
i 
C 
C 
E 
E; 
l'(Fi 
= C,., 
•^i-i 
< n 1 n reoeived at the moment J its fii-st iiiput operand } 
= cr 
U cr 
= E, 
i-1 
= < n I n reoeived at the moment j its last input operand ) 
_ pold 
= F|-, 
old 
U Ej"' 
, Vp) := fflax l'(n,VF), uhere n e Fj 
:= { n e E: I Kn.Vp ) = 1 (E, ,VF ) l'(F° ,Vp ) > U (Ej n Vp ) i 
Choose a subset E; of the set E 
:= E' U E' 
old 
:= Dj.i 
U FP 
U Fi* 
V - ( Ci U F, U Di ) 
Adjust the components of tirne control vectors for the nodes 
in c;"" , E™"" and Fj""" ; 
Fig.5: Algorithm for ohtaining execution plans of a program graph. 
CONCLUSION 
Uhat 
on F 
is O 
of 
ali 
plEX 
sine 
each 
coiop 
tiae 
IS O 
is the tiin 
ig.5? The t 
( IVl^ ) , sin 
the comput 
nodes in a 
ity of the 
e the loop 
of the ste 
lEKitv 0( I V 
COAplBKit 
( IVt^ ) . 
e coalexity at the algorithm 
ime coaplexit/ of the step (1) 
ce this is the tirne complexity 
ing the longest paths between 
graph CLaw7fc3. The tirne com-
steps (2) to (20) is 0( IVI^ ) , 
(3) is entered O(IVI) times, 
ps (A) to (20) having tirne 
I). Consequently, the overall 
y of the algorithm on Fig.5 is 
The 
gener 
nodes 
was o 
than 
botn 
of ca 
risti 
optim 
proce 
o, a 
this 
very 
cuted 
resul 
algorithm w 
ated progra 
. In only O 
btained. In 
or equal to 
immediate a 
ses. Furthe 
C execution 
al, since th 
ssing elemen 
s uas the ca 
number is 
probably gr 
using only 
ts are depic 
as tested 
m Qi'aphs 
Sy. of ana 
ali other 
Heuri 
nd lazy e 
r m • r e , m a 
s were 
e associ 
ts needed 
se on the 
pesimisti 
aphs tha 
a proces 
ted on Fi 
on 
uit 
lysed 
čase 
Stic 
xecut 
ny (5 
also 
ated 
equa 
Fig 
C si 
t cou 
sing 
g.6. 
'iOO randomIy 
h at most ti 
graphs >Jhou >& 
s fj^ou uas less 
plan inprovsd 
ion in SC1.2S7. 
5.75'/.) of heu-
proved to be 
numbers of the 
led the values 
7. Note, that 
nce thure uere 
Id not be exe-
elements. The 
It is to point out that the algorithm on 
Fig.5 oan be used for minimiiation of some 
other resources suoh as the number of primary 
meaory locations needed . 
Mheu > P 
(O.SQX> 
^-,:;:.i^|f|ip^ 
I T-i] 
I I 
Mhou = p 
('.9.25X) 
Mheu < e 
(50.25X) 
Mheu « « 
(55.751) 
Flg.6i The behavior of the heuristic plan. 

1 v I Ti"«" 1 T'i'y I TJ«" I 
F. v ^.v r.v 
+ + + + + 
I a K O, O, 0)I( O, Q, 0)I( O, 0. 0)I 
+ + + + • + 
I b I C Q, Q, 0) I( O, O, 0) I ( O, O, 0)I 
+ + + + • + 
I C K O, O, 0)I( O, O, 0)I( O, O, 0)I 
+ + • • + 
I d I C 1, 1, 1)I( 1, 1, 6)I( 1 , 1 , 1)1 
+ + + + . + 
I e 1( 1, 1, 1)I( 1, 1, 1)I( 1 , 1 , 1)1 
+ + + • • 
1 I K 1 , 1 , 1) I ( 1 , 1 ,10) I C -1, 1 , *) I 
+ + + + • 
I g K 1, 1, 1) I ( 1 , 1 , 9) I ( 1 , 1 , 1)1 
+ + + • + • 
I h K 2, 7, 7)I( 7, 7, 7)I( 2, 7, 7)1 
+ + + . + f 
I i K 1, 1, 1)I C 1, 1 ,19) 1 ( 1, 1 , 9)1 
+ + 4 .• + 4 
I j K 1, 1, 1)I( 1, 1 ,10) I ( 1 , 1 , 2) I 
+ + + + + 
1 k K 1, 1, 1)I( 1, 1,18)1 ( 1, 1 , 6) I 
+ • + + + 
I 1 K 1 , 1 , 1) I ( 1 , 1 ,1',) I ( 1 , 1 , 4) I 
+ + + + * 
I a K 3,12,12)I(12,12,12) I C A,12,12)1 
•. + + 1 + 
1 n K 1, 1, 1)I< 1, 1 ,15) K 1; 1 , 6) I 
t-..^^ + + 1 
I o M 3,1A,1',) I (1<,,16,16) I ( 6,1',,U)I 
+ + + 1 1 
I p K 1,1',,1'i)l( 1,1'i,1'>)l( 1,H,U)I 
• *--• + + • 
I q I (16,16,16)I(16,16,16)I(16,16,16)I 
+ + + •-- + + 
I r K 5,19,19)1(19,19,19)1(10,19,19)1 
+ + + + 1 
I s K 3,21,21)I(19,21 ,21) 1 ( 9,21,21)1 
+ + + .__ + _• + 
I t 1(22,22,22)1(22,22,22)1(22,22,22)1 
. M imm ~ ' 
? = 1 
Mheu 
In thls čase the heuristic 
plan is also optiaal1 
Fig.7: Plans (or immediate, la2y and heuristic execution 
of a given program graph. 
10. LITERATURE 
CC0MB23 
COMPUTER, Soecial Issue On OataflGw 
SvBlems, Vol.15, No.2, Feb.1982 
CKFSSa^D Kapauan A 
L.Snyder 
J.T.Field, O.B.Gannoni 
The Pringle Parallel 
Computer', Proč. 11th Int'1 S/op. 
Conp. Arch., IEEE Press, New York, 
198'., pp.12-20 
CRaSfi6] RobiC B., J.Silo : 'Analyeis o( 
Static Data Flow Program Graphs' , 
to be published in Elektrotehniški 
vestnik, (in Slovene) 
CTJSS3] Tokoro M., J.R,Jagannathan, H.Suna-
hara: 'On the Uorking Set Concept 
for Data-llow Machines', Proč. 10th 
Int'1 Syiiip. Computer Architecture, 
IEEE Press, New Vork, 1983, pp.90-
97 
CLaw76: Lauler E.: Combinatorial Optimiza-
tioni Networks and Matroids, Holt, 
RinehartiWinston, New Vork, 1976 
CSiRasa Silo J., B.RobiC : 'Basic .Princip-
les ol Data Flou Systeiiis' , Infor-
matica 2/85, pp.10-15 (in Slovene)