UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Termination and storage requirements in a model for parallel computations Schnapp, Ivan 1970

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1970_A7 S39_4.pdf [ 2.5MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0102044.json
JSON-LD: 1.0102044+ld.json
RDF/XML (Pretty): 1.0102044.xml
RDF/JSON: 1.0102044+rdf.json
Turtle: 1.0102044+rdf-turtle.txt
N-Triples: 1.0102044+rdf-ntriples.txt
Original Record: 1.0102044 +original-record.json
Full Text
1.0102044.txt
Citation
1.0102044.ris

Full Text

TERMINATION AND STORAGE REQUIREMENTS IN A MODEL FOR PARALLEL COMPUTATIONS  by  IVAN 3CHNAPP D i p l . I n g . , Czech T e c h n i c a l U n i v e r s i t y , Prague, 1966  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF .  MASTER OF APPLIED SCIENCE  i n the Department of Electrical  We accept t h i s  Engineering  t h e s i s as conforming to the  required  standard  Research Supervisor Members of the Committee  A c t i n g Head of the Department  Members of the Department of E l e c t r i c a l  Engineering  THE UNIVERSITY OF BRITISH COLUMBIA June, 1970  In  presenting  this  an a d v a n c e d d e g r e e the L i b r a r y I  further  for  of  this  written  at  agree  freely  that permission  for  It  financial  of  Columbia,  British  by  for  gain  Columbia  shall  the  requirements  reference copying  of  I agree and this  that  not  copying  or  for  that  study. thesis  t h e Head o f my D e p a r t m e n t  is understood  Department  Date  of  for extensive  permission.  The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8, Canada  fulfilment  available  p u r p o s e s may be g r a n t e d  representatives. thesis  in p a r t i a l  the U n i v e r s i t y  s h a l l make i t  scholarly  by h i s  thesis  or  publication  be a l l o w e d w i t h o u t  my  ABSTRACT  This paper deals with a grajjh-theoret i c model f o r p a r a l l e l computations  as formulated-by  and a s u f f i c i e n t  Karp and M i l l e r . A necessary c o n d i t i o n  c o n d i t i o n f o r s e l f - t e r m i n a t i o n of loops with u n i t  loop g a i n are presented. For the s p e c i a l case that W=U and  sufficient  c o n d i t i o n i s d e r i v e d . A d i r e c t procedure  t e r m i n a t i o n p r o p e r t i e s of s t r o n g l y connected  the necessary for testing  graphs i s presented.  A method due to R e i t e r , f o r determining the rua ximura storage r e q u i r e d f o r a computation case.  graph,  i s extended  to cover the general  TABLE OF CONTENTS  ABSTRACT  i  TABLE OP CONTENTS  i i  LIST OF ILLUSTRATIONS  i i i  ACKNOWLEDGMENT 1.  iv  INTRODUCTION.  1  1.1  1  The K a r p - M i l l e r model  1 . 2 Research connected w i t h p a r a l l e l computation models 2. TERMINATION PROPERTIES OF COMPUTATION GRAPHS 2 . 1 The K a r p - M i l l e r a l g o r i t h m  6 9 9  2.2 Some n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s f o r s e l f - t e r m i n a t i o n of loops  1 7  2.3 A d i r e c t method of t e s t i n g t e r m i n a t i o n p r o p e r t i e s of s t r o n g components  25  3 . STORAGE REQUIREMENTS  4.  28  3 . 1 Maximum s t o r a g e requirement - s p e c i a l case  28  3.2 Maximum s t o r a g e requirement - g e n e r a l case  33  CONCLUSIONS  .40  REFERENCES  42  ii  L I S T OP  ILLUSTRATIONS  Figure  Page  1  Computation graph  f o r Laguerre  2  Dependence o f t h e amount o f d a t a on t h e l o o p g a i n  18-19  3  Termination of loops  24  iii  polynomials  ...5  ACKNOWLEDGMENT  I wish to express my gratitude to Dr. E . L. Sigurdson for his guidance and encouragement  in carrying out this research, and  to Dr. G. F . Schrack for reading the manuscript. I also wish to acknowledge the f i n a n c i a l support of the National Research Council.  iv  CHAPTER 1 INTRODUCTION  As s i g n a l p r o p a g a t i o n speeds r e p r e s e n t a s e r i o u s b a r r i e r to  i n c r e a s i n g the speed of s t r i c t l y s e q u e n t i a l computers more  a t t e n t i o n has been p a i d i n r e c e n t y e a r s t o ' t h e use of the ism i n t r i n s i c  to most c o m p u t a t i o n a l  parallel-  a l g o r i t h m s . A number of  de-  s i g n s have appeared which u t i l i z e a number of p r o c e s s o r s which s i m u l t a n e o u s l y execute  s e v e r a l steps of the computation  may  (/l/-/5/),  r a t h e r than o v e r l a p p i n g of s u b f u n c t i o n s i n s e q u e n t i a l p r o c e s s i n g . In g e n e r a l , v a l u e s to be u s e d . i n a computation r e s u l t s of p r e v i o u s computation  s t e p are the  steps. This e s t a b l i s h e s c e r t a i n  precedence c o n s t r a i n t s upon the computation  steps.  A model of such a system, s a t i s f y i n g a p a r t i c u l a r c l a s s of precedence c o n s t r a i n t s , lias been f o r m u l a t e d by Karp and M i l l e r  /6/.  T h i s t h e s i s s t u d i e s some problems a r i s i n g i n c o n n e c t i o n w i t h t h i s model, i n p a r t i c u l a r t e r m i n a t i o n p r o p e r t i e s (Chapter 2) s t o r a g e requirements  (Chapter  and  3).  In t h i s chapter we p r e s e n t the model and the r e s u l t s of p r e v i o u s r e s e a r c h , and compare i t w i t h o t h e r approaches to the  parallel  processing.  1.1 The  K a r p - M i l l e r Model The model r e p r e s e n t s the sequencing  of a p a r a l l e l  computation  by a f i n i t e d i r e c t e d graph. Each node of the graph corresponds an o p e r a t i o n i n the computation  to  (or to a p r o c e s s o r a s s i g n e d to per-  form t h a t o p e r a t i o n ) . Each branch  1  represents a f i r s t - i n f i r s t - o u t  2 queue data  of  data  d i r e c t e d from  transformation  single-valued inputs. ed  by  The  the  of  the queues  to  each  a  computation  computation  on  of  an  branches  i s represented  graph  which  a  set of  nodes  (ii)  a  set of  branches  ( i i i )  Here,  by  i s given  ing 0-. J Ch  A^  outputs  operation directed  i s  a  on  determin-  into i t s  added  a  d i r e c t e d graph  to  terminates;  gives  the  queue  d^,..d^, a  where  specified  i n i t i a l  number  associated  t h e queue V<T  G  any  node  n^  given to  a  branch  d^  specified  n •,  first-out  of  with  d  gives  whenever  the  t h e number  P  data ; U  gives  P  operation  of words  words  Ch  where  i n the the  number  associated  remove;: f r o m  the  of  with queue  o p e r a t i o n 0- i s i n i t i a t e d ; and T i s a threshold g i v . J P t h e minimum queue l e n g t l i o f d^ w h i c h p e r m i t s t h e i n i t i a t i o n o f  Upon are  the  i n i t i a t i o n  of  0. J  the  The  0. a s s o c i a t e d w i t h J i f and only i f , f o r each  number  o f words  t o T^.  removed  from  i n t h e queue  After each  Ch  P  of  the  T  P  operands f o r 1  queue.  operation  the  W  f i r s t  from  equal  the  only  removed  i n i t i a t i o n  are  of  f o u r n o n n e g a t i v e i n t e g e r s A ,U ,¥ a n d T , • ° ° P P P P T > ¥ , a s s o c i a t e d with each branch d . P P P  for  or  i s associated  by:  1  whenever  describe  n ^ n ^ , ..  d i r e c t e d from  node  n^  node  To  node.  is  words  another.  the dependence  f o r initiation  (i)  f i r s t - i n  with  function determining  lengths  Thus a  processor  processors,  e l i g i b i l i t y  associated  called  by  one  becomes  branch  d  a  given  branch  associated eligible  d  n. i s e l i g i b l e J directed into n., J  P  with  d  i s greater  f o r i n i t i a t i o n ,  directed into P  node  n.. J  The  ¥  than  words  operation  0. J  3  i s then performed. Vhen Ch t e r m i n a t e s , branch d  words are p l a c e d on each  d i r e c t e d out from n.. The times r e q u i r e d to perform the  steps mentioned  above are l e f t u n s p e c i f i e d by the o r i g i n a l  model as  presented i n /6/. These itions  c o n s t r a i n t s on i n i t i a t i o n lead to the f o l l o w i n g  of the p o s s i b l e sequences  given computation graph Let  T  of i n i t i a t i o n s a s s o c i a t e d with a  G.  E be a sequence  t h a t each set S^  defin-  of nonempty sets  i s a subset o f £ l , 2 , . . ,  ,S,j > • . >S^, . . , such r  whore X i s the number of  nodes i n G. Let of  x ( j , 0 ) - 0, and, f o r N > 0 ,  sets S , l < m < N , of which '  in'  The sequence the  i i s an  0  l e t x(j,N) denote the number element,  E i s an execution of G i f and only i f f o r a l l N,  following conditions hold: (i)  i f j C S ,. and G has a branch d d i r e c t e d from n. to N+l p l n., then A + U x ( i , N ) - W x ( j , N ) > T : v  J  (ii)  i f E i s f i n i t e and of length R, then f o r each j there e x i s t s a node n. and a branch d d i r e c t e d from n. to l p l n. such that A + U x ( i , R ) - W x ( j , R ) < T j p p ' ' p ' ' p v  An execution E of G i s c a l l e d ing  xJ  .  a proper execution i f the f o l l o w -  implication holds: (iii)  i f , f o r a l l n. and f o r every branch d d i r e c t e d from l p n. to n., A + U x(i,N) - W x ( j , N ) > T , then j € S„ l j p p ' p ' p' li J  J  for  some R > N.  The sequence temporal sequence formance  J  E may  be i n t e r p r e t e d as g i v i n g a p o s s i b l e  of i n i t i a t i o n s  of the p a r a l l e l  of operations throughout the per-  computation  s p e c i f i e d by G; the occurence  4  of S.. denotes  the simultaneous  i n i t i a t i o n of 0. f o r a l l }€. S,-.  C o n d i t i o n ( i ) s t a t e s that i n order f o r node n_. to i n i t i a t e J f o r the x ( j , N + l ) - t h time, the queue lengths on i t s input branches must be g r e a t e r than, or equal, to the r e s p e c t i v e branch t h r e s h o l d s . Condition  ( i i ) d e f i n e s the circumstance under which an execution  terminates, i . e . under which the computation T h i s computation  d e f i n e d by G h a l t s .  terminates when every node of G i s unable to  i n i t i a t e . C o n d i t i o n ( i i i ) r e q u i r e s that a node, i f able to i n i t i a t e , a c t u a l l y w i l l do so a f t e r some f i n i t e number of i n i t i a t i o n s of other nodes. The f o l l o w i n g example i l l u s t r a t e s these i d e a s : Example 1.1 Consider the Laguerre polynomials d e f i n e d by the recurrence relation L ^-.(x) = (2n + 1 - x)L (x) - n L ,(x) n+l ' n ' n-1 ' 2  v  v  with i n i t i a l c o n d i t i o n s L (x) - 1 Q  L (x) = 1 - x x  We want to compute the values of L ( x ) f o r n = 2,3,..,N and f o r a n  given x. A computation  graph f o r t h i s c a l c u l a t i o n i s i n F i g . l . For  each branch the intermediate r e s u l t i s shown. Branch  coefficients  are assumed to be A=0, U=Vi =T=l unless otherwise shown. Brandies :  (n^,n^)' ( i . e . the branch d i r e c t e d from n^ to n^ ) and (n2>n ) serve 9  as counters; the computation  i s terminated by the d e p l e t i o n of queues  a s s o c i a t e d with these branches. Node n^ produces  2n and n", and  p l a c e s them on (n,,n~) and (n, ,n-j), r e s p e c t i v e l y . Node n„ takes  5  A=N-1  A=N-  U=0  U=0 2n  (2n+l-x)  n  n.  L  n-l  ( x  >  Computation graph f o r Laguerre polynomials Fig.  1  6  ( l - x ) from the branch ^ 2 ^ 2 ) and adds i t t o the o t h e r i n p u t 2 n ; the result  ( 2 n + l - x ) i s p l a c e d on ( i ^ j n ^ ) . Node n^ forms the p r o d u c t of  ( 2 n + l - x ) and L ( x ) and p l a c e s the r e s u l t on ( n ^ , n ^ ) . Node n^ m u l t i n  2  p l i e s L _-^(x) by n n  and p l a c e s the r e s u l t on ( n ^ , n _ ) . F i n a l l y ,  n^  produces the d e s i r e d p o l y n o m i a l s L ^ x ) , L ^ ( x ) , . . , L^,(x) and p l a c e s them on (n^,n^) and LQ(X)=1,  L^(X)=1-X  ( n ^ , n ^ ) . The i n i t i a l d a t a queue on (n^,n^) i s and on ( n ^ , n ) i t i s L ^ ( x ) = l - x . 4  1.2 Research connected w i t h p a r a l l e l computation models Karp and M i l l e r fbf  show t h a t f o r every p r o p e r e x e c u t i o n the  sequence of d a t a words o c c u r i n g on any branch of G i s always the same thus e n s u r i n g the same c o m p u t a t i o n a l r e s u l t . T h i s p r o p e r t y i s r e f e r r e d to as the determinaoy  of a computation graph. A l s o , they  g i v e an a l g o r i t h m t o determine whether a computation t e r m i n a t e s , and a procedure f o r f i n d i n g the number of performances of each o p e r a t i o n i n G. F i n a l l y , they g i v e n e c e s s a r y and s u f f i c i e n t  con-  d i t i o n s f o r the l e n g t h s of d a t a queues to remain bounded. R e i t e r i n h i s Ph.D.  t h e s i s fjf  addresses h i m s e l f to the  problems of s t o r a g e , s c h e d u l i n g , and optimum assignment of o p e r a t i o n s to p r o c e s s i n g u n i t s . He g i v e s an i n t e g e r l i n e a r program f o r the d e t e r m i n a t i o n of the maximum s t o r a g e r e q u i r e d by a computation graph G. He i n t r o d u c e s a concept of an a d m i s s i b l e schedule d e f i n i n g  valid  node i n i t i a t i o n times and c h a r a c t e r i z e s the c l a s s of a l l a d m i s s i b l e s c h e d u l e s i n the case W =T =1, U -0 or 1. He f u r t h e r shows t h a t i n P P P t h i s case i t i s p o s s i b l e to f i n d a p e r i o d i c a d m i s s i b l e schedule which a c h i e v e s the maximum computation r a t e ( a l s o see / 8 / ) . He  also  d e f i n e s the c o s t of an assignment of node f u n c t i o n s to p r o c e s s o r s  7 and g i v e s a method f o r d e t e r m i n i n g f e a s i b l e s o l u t i o n s when the maximum comjmtation r a t e has a lower bound. F i n a l l y , he extends the model t o i n c o r p o r a t e a r e s t r i c t e d form of data dependency w i t h o u t l o s i n g i t s detcrminacy. A d i f f e r e n t approach t o the g r a p h i c a l r e p r e s e n t a t i o n o f a computation i s t a k e n by M a r t i n / 9 / . He a l l o w s two types of node i n put c o n t r o l . I n the case of c o n j u n c t i v e i n p u t c o n t r o l a node can i n i t i a t e o n l y i f each branch d i r e c t e d i n t o t h e node c o n t a i n s a t l e a s t one data word. In the case of d i s j u n c t i v e i n p u t c o n t r o l a node can i n i t i a t e  only i f at least one branch directed into the node  c o n t a i n s a t l e a s t one data word.  Similarly,  conjunctive output  c o n t r o l p l a c e s one word on each branch d i r e c t e d out from the node and d i s j u n c t i v e output c o n t r o l p l a c e s one word on a branch d i r e c t e d out from t h e node a c c o r d i n g t o an a p r i o r i p r o b a b i l i t y . The l a t t e r r e p r e s e n t s a c o n d i t i o n a l t r a n s f e r which i s d e t e r m i n i s t i c every time i t o c c u r s but over many p o s s i b l e d a t a s e t s may be modelled p r o b a b i l istically. Note t h a t the c o n j u n c t i v e i n p u t c o n t r o l and c o n j u n c t i v e o u t put c o n t r o l correspond to the T=vr=l case and U=l case i n t h e Karp - M i l l e r model, r e s p e c t i v e l y . A l s o n o t e , t h a t because of c o n d i t i o n a l t r a n s f e r s , t h i s model i s not d e t e r m i n a t e . In h i s work M a r t i n s t u d i e s the assignment of node computa t i o n s t o p r o c e s s o r s and t r i e s t o minimize the average  computation  t i m e . F u r t h e r r e s e a r c h of t h i s model can be found i n / l O / , where an a p p r o x i m a t i v e method f o r c a l c u l a t i n g the average computation time ± given, and /ll/, where procedures.are Riven.to determine a lower and an upper bound on the number of p r o c e s s o r s r e q u i r e d f o r maximum  s  8  parallelism. An balancing  application problems  of  results  i s given  in  of /12/.  these  studies  to  assembly-line  CHAPTER 2 TERMINATION PROPERTIES OF COMPUTATION GRAPHS P a r t 2.1 o f t h i s c h a p t e r i s devoted t o a p r e s e n t a t i o n o f t h e Karp-Miller algorithm.  The a l g o r i t h m i s used t o d e t e r m i n e whether  the c o m p u t a t i o n s p e c i f i e d by a g i v e n c o m p u t a t i o n graph t e r m i n a t e s , and t o f i n d t h e number o f performances o f each o p e r a t i o n i n case t h e computation terminates. S e v e r a l theorems a r e g i v e n i n p a r t s 2.2 and 2.3 t o improve the e f f i c i e n c y of the a l g o r i t h m .  2.1  The K a r p - M i l l e r A l g o r i t h m Theorems and Lemmas o f s e c t i o n 2.1 a r e p r o v e d i n /6/. S i n c e t h e  number o f performances o f an o p e r a t i o n 0  i s independent o f t h e e x e c u -  t i o n c o n s i d e r e d o n l y i f t h i s e x c u t i o n i s p r o p e r , Karp and M i l l e r r e s t r i c t t h e i r a t t e n t i o n to proper executions. A node n_. o f a c o m p u t a t i o n graph i s s a i d t o t e r m i n a t e i f and o n l y i f ( i n t h e f o l l o w i n g i f f ) j o c c u r s i n o n l y a f i n i t e number o f the s e t s  o f a p r o p e r e x e c u t i o n o f G.  N a t u r a l l y , t h i s number i s  the same f o r a l l p r o p e r e x e c u t i o n s o f G. To f u r t h e r s t u d y t h e t e r m i n a t i o n o f p r o p e r t i e s o f c o m p u t a t i o n graphs we need t o i n t r o d u c e a few c o n c e p t s from graph t h e o r y . A d i r e c t e d graph i s c a l l e d s t r o n g l y c o n n e c t e d i f f g i v e n any p a i r o f nodes n. and n. t h e r e e x i s t s a d i r e c t e d p a t h from n. t o n.. s p e c i a l case o f a s t r o n g l y c o n n e c t e d graph i s t h e t r i v i a l graph w h i c h has o n l y one node and no b r a n c h e s . F o r any d i r e c t e d graph t h e r e e x i s t s a unique p a r t i t i o n o f  9  A  10  i t s nodes i n t o e q u i v a l e n c e c l a s s e s as f o l l o w s : Two nodes n. and n. a r e i n t h e same c l a s s i f t h e r e e x i s t s a d i r e c t e d path from n^ t o n^ , and a d i r e c t e d path from n^ t o n^. A subgraph c o n s i s t i n g of t h e nodes of an e q u i v a l e n c e c l a s s and t h e branches o f t h e o r i g i n a l graph c o n n e c t i n g these nodes i s then a s t r o n g l y connected graph. The subgraphs c o r r e s p o n d i n g to t h e node e q u i v a l e n c e c l a s s e s a r e maximal  s t r o n g l y connected  subgraphs  of t h e o r i g i n a l graph and a r e c a l l e d t h e s t r o n g components of t h e graph. These s t r o n g components p l a y a c r u c i a l r o l e i n t h e KarpMiller  algorithm. Lemma 2.I L e t G' be a s t r o n g l y connected subgraph of a computation graph G.'Then e i t h e r every node of G' t e r m i n a t e s o r nonedoes.  We say t h a t 0' t e r m i n a t e s i f every node of G' t e r m i n a t e s . D i v i d e a l l the nodes of a computation graph G i n t o two c l a s s e s a c c o r d i n g t o whether they t e r m i n a t e o r n o t . Then by Lemma 2.1 t h e s e t S of t e r m i n a t i n g nodes i s a u n i o n of s e t s of nodes of some s t r o n g components of G. The s t r o n g l y connected subgraph G' which would t e r m i n a t e i f i t were i s o l a t e d from t h e r e s t of G i s c a l l e d  self-terminating.  L e t us examine when a s t r o n g component i s s e l f - t e r m i n a t i n g .  Lemma 2.2 Let d^=(n^,iij) be a branch of a computation graph. Then n^ t e r m i n a t e s i f n. t e r m i n a t e s . l  11  r  s and G' -be  This loads to the f o l l o w i n g concepts: Let G strong components of G. Then define G such nodes n - 6 G  r  >_ G  S  i f either G . = G or there exist r  S  s and n.€ G that there i s a d i r e c t e d path from n.  1  to  r  1  j  n . i n G.  J Theorem 2.3 s A strong component G r iff  there e x i s t s G  G>  G .  r  Thus G  s  of a computation graph G terminates r such that G  i s s e l f - t e r m i n a t i n g and  s  r terminates i f f i t i s s e l f - t e r m i n a t i n g or some G i s s e l f -  t e r m i n a t i n g and there i s a d i r e c t e d path from some n . 6 G  to some  n - £ G . Therefore to determine the set S we examine strong comb  r  s  r  ponents f o r s e l f - t e r m i n a t i o n i n such order that i f G >. G , then G is  examined  first.  Now the problem i s how to determine 'whether a s t r o n g l y connected subgraph G' i s s e l f - t e r m i n a t i n g . For t h i s purpose Karp and M i l l e r use p r o p e r t i e s of the  1OO|JS  contained i n G'.  A computation graph L i s c a l l e d a loop i f i t c o n s i s t s of d i s t i n c t nodes  ,n ,.,"and  d i r e c t e d from  to ^ _  to  0  n  +1  branches d^,d2,..,d£ such that d^ i s  > k=l, 2, . . , / , - l ,  and d^ i s d i r e c t e d from n^  n^ . Here we note that any s t r o n g l y connected subgraph G' except  the  trivial  graph c o n t a i n s at l e a s t one loop.  Theorem 2.4 A s t r o n g l y connected subgraph G  1  i s s e l f - t e r m i n a t i n g i f f G'  12  contains a s e l f - t e r m i n a t i n g  loop.  G i v e n t h i s theorem the o n l y problem i s how to e s t a b l i s h t h a t a p a r t i c u l a r loop i s s e l f - t e r m i n a t i n g . Let L be a loop w i t h branches d, ,d,,, . . ,d«. The it  product  U .  g= TT rr^ i s c a l l e d the g a i n of the l o o p . There are 3 cases: g ^ l , i =l i g=l, and g >1. Loops w i t h g < 1  2.5  Theorem  Any loop L f o r which g < l i s s e l f - t e r m i n a t i n g .  Loops w i t l i g=I  2.6.  Theorem Let  r~  1  1  v  l  u  = Y  'l  , i  ''2  h-l  'l  Vl h-l  I  V,  i  V l V i  h P  '"l  U  V h-l  U  h hh h "1 T.I  1  '  I  '  1  V i  W  l l  U  2  W  2  h h  u  w  u  h j  i. I  i i  i  13  *1 fo  where  /3  l{  A  =  k-i" k-i y— T  + 1  k=2 , 3 ,. .  k-1 3 A  and  /3i  i- x T  + 1  =  ft  Then the necessary c o n d i t i o n f o r s e l f - t e r m i n a t i o n of a loop with g=l i s P  /3  <  0  Karp and M i l l e r give a necessary and s u f f i c i e n t termination  i n the f o l l o w i n g s p e c i a l case:  Theorem  2.7  If,  for  l£k^X,,  k=l  "  iff  condition for s e l f -  Vi'. = U , =1,  (i.e. Z  k=l  then the loop L i s s e l f - t e r m i n a t i n g  A < Z k  k=l  ( T , - l ) ). k  In case that Theorems 2.6 -and 2.7 cannot be a p p l i e d Karp and M i l l e r derive  an upper bound on the numbers of x^erformances of nodes of a  self-terminating  Theorem  loop.  2.8  Let L be a s e l f - t e r m i n a t i n g  loop with g=l. Let X* be a p o s i t i v e  i n t e g e r s o l u t i o n of the system  OC^  = a  14  U  1  OC = - i 2 M  a  a  1  U  l  U  u ry,  2  u  - _  U  —£  a  whore a i s an a r b i t r a r y parameter. L e t  x  n  X =  X,  where X^ i s the number of performances  of node n^, k = l , 2 , . . ,  Then a t l e a s t one component of X i s l e s s than the c o r r e s p o n d i n g component of X*.  Loops w i t h g >1 Theorem 2.6 i s v a l i d a l s o f o r t h i s  case.  I f L i s s e l f - t e r m i n a t i n g then we get the f o l l o w i n g  upper  bound: X < y i - P fi 1-g 'Having o b t a i n e d an upper bound f o r X we can t e s t  self-termination  of a loop by a p p l y i n g a procedure g i v e n i n the f o l l o w i n g  theorem.  15  Theorem 2.9 # For a l l nodes n.€S the f o l l o w i n g i t e r a t i o n scheme  J  converges  i n a f i n i t e number of steps t o X;  * <;>=° (0)  x^  n + 1  r  ^ ( j ) = max J  _ x ^ ( j ) ,  Ik -T +1+U  (i,p)6Z.j, i € S \  („) , x {iT Ka,  %  H e r e ^ j i s the s e t of o r d e r e d p a i r s ( i , p ) such t h a t d^ i s a brancli from node n. t o node n..  The r e s u l t s g i v e n so f a r may be o r g a n i z e d i n t o an a l g o r i t h m f o r d e t e r m i n i n g which nodes of a computation graph G t e r m i n a t e and, f o r the t e r m i n a t i n g nodes n.. , computing the number of performances  x(j).  T h i s a l g o r i t h m may be o u t l i n e d /6/ as f o l l o w s :  Step 1. From among the s t r o n g components of the computation graph b e i n g c o n s i d e r e d ( i n i t i a l l y t h i s graph i s G ) , s e l e c t one which i s not covered by any o t h e r subgraph. C a l l i t G'. Step 2. By a p p l y i n g Steps 2A,...,2D g i v e n below, t e s t whether G' i s s e l f - t e r m i n a t i n g and, when i t i s , determine x ( j ) f o r each n.£G'. Step 3. Form a new computation graph as f o l l o w s : I f G' i s not s e l f t e r m i n a t i n g , remove G' and a l l branches i n c i d e n t w i t h nodes of G'. I f G' i s s e l f - t e r m i n a t i n g , r e p l a c e each branch d  from n ^ G ' t o  n ^ G ' by an " e q u i v a l e n t " branch d^, from n^ t o n^ , having U^,=0, A ,=A +U x ( i ) , T ,=T , and W , =V, . Then remove G' . P P p p p p p T  Step 4. I f the new computation graph i s nonempty, r e t u r n t o Step 1. Otherwise the a n a l y s i s of t e r m i n a t i o n i s complete. 4 The symbol f x ! denotes " l e a s t i n t e g e r g r e a t e r than or equal t o x."  16  The d e t a i l s of Step 2 a r e now d e s c r i b e d . Step 2k. I f G' c o n t a i n s a branch d^ w i t h U =0, go t o Step 2D. I f n o t , determine whether G' c o n t a i n s a l o o p w i t h g < l . T h i s i s e q u i v a l e n t t o d e t e r m i n i n g whether t h e r e i s a loop L sucli t h a t  Z  d € L P  l o g (U / V ) < 0 .  P  P  T h i s d e t e r m i n a t i o n can be c a r r i e d out by a s h o r t e s t - r o u t e a l g o r i t h m g i v e n i n /13/. Enumeration of loops i s not r e q u i r e d i n t h i s p r o cedure. I f a loop w i t h g < l e x i s t s , go t o Step 2D; o t h e r w i s e , go to Step 2E. Step 2B. Every l o o p of G' has .g > 1. Determine whether t h e r e i s a l o o p not p r e v i o u s l y c o n s i d e r e d such t h a t 0> Pyg. I f no such loop e x i s t s , G' i s not s e l f - t e r m i n a t i n g ; r e t u r n t o Step 3. I f such a loop L i s found, determine upper bounds on the q u a n t i t i e s x ^ ( k ) by the methods g i v e n above. These bounds h o l d , of c o u r s e , o n l y i f L i s self-terminating. Step 2C. Continue a p p l y i n g t h e i t e r a t i o n scheme of Theorem 2.9, t a k i n g S t o be s e t of nodes of G', u n t i l  either  (a) i t t e r m i n a t e s , e s t a b l i s h i n g t h a t G' i s s e l f - t e r m i n a t i n g , and g i v i n g x ( j ) f o r each n.£G', or J  (b) f o r some n and some k, x ^ ^ ( k ) exceeds the upper bound on x ^ ( k ) , n  e s t a b l i s h i n g t h a t L i s not s e l f - t e r m i n a t i n g . Return t o Step 2B. Step 2D. G' i s s e l f - t e r m i n a t i n g . Apply the i t e r a t i o n scheme of Theorem 2.9, t a k i n g S t o be the s e t of nodes of G', t o o b t a i n x ( j ) f o r each n.£G'.. R e t u r n to Step 3.  17  2.2 Some necessary and s u f f i c i e n t  conditions  f o r .self-termination  of 1o o ps As  shown above, the K a r p - M i l l e r algorithm is.based on termin-  ation properties  of loops.  Consequently i t s e f f i c i e n c y depends main-  l y on the means a v a i l a b l e f o r t e s t i n g s e l f - t e r m i n a t i o n of loops. In the f o l l o w i n g we s h a l l d e r i v e  some theorems t e s t i n g these proper-  ties.  Theorem 2.10  '  I f , f o r l^k<L,£, p— = 1, then the loop L i s s e l f - t e r m i n a t i n g k b  I  1X1 £ k=l Z  o  PROOF; By Theorem 6 of /6/ the necessary and s u f f i c i e n t for  s e l f - t e r m i n a t i o n of a loop i s the existence  i n t e g e r s o l u t i o n of the f o l l o w i n g , , x(l)>  v  of a nonnegative  system of i n e q u a l i t i e s :  A^-Tjt+l+lixU) g  A -T^+1+U,,x(k) x(k+l)>——\-. k 1r  This  condition  'for k = l , 2 , . . j e - l  system reduces to  x ( l ) > /3 +x(i) £  x(k+l)>/3 +x(k) k  Since a l l x's are i n t e g e r s , we have  f o r k-1, 2 , . . , i - l  18  x(k+l) >  f/3j+x(k)  for  k=l,2 ..,1-1 f  By summing l e f t and r i g h t - h a n d sides of the above i n e q u a l i t i e s , r e s p e c t i v e l y , we get the necessary c o n d i t i o n  To prove that i t i s a l s o a s u f f i c i e n t c o n d i t i o n we if  -ban.-, show that  i t i s s a t i s f i e d the system  x(l)=C k=l,2,..,1-1  x(k+l)=x(k)+ f / 3 ] k  where C i s a s u f f i c i e n t l y large i n t e g e r i s a nonnegative s o l u t i o n of the above  integer  inequalities.  Consider the f o l l o w i n g examples Example 2 . 1  A-0 U=l \V=T=2 A=2  Here g = l / 2 . The data d i s t r i b u t i o n a f t e r each node performes once i s A'=0  U=l  T=Vf=l  W=T=2  U=l A'=l Fig. 2  19  Example  2.2 A=0  A=l  Here g=2. The data d i s t r i b u t i o n a f t e r each node performs once i s A'=0 T=W=1  A'=2  Example  2.3  A=l.  Here g-l. The data d i s t r i b u t i o n a f t e r each node performs once i s  A'=0 T=Vf=l  A'=l  Dependence  of tlie amount of data on the loop g a i n Fig.2  20  These examples i n d i c a t e that "amount of data"  (roughly speaking) f o r g > l  i n c r e a s e s , f o r g<1  remains constant.  The  i t decreases,  and  the  f o r g=l i t  f o l l o w i n g theorem gives t h i s f a c t a p r e c i s e  form.  Theorem 2.11  „  I L be a loop with gain g -  Let  initial  and  u  II ^— . Let A. and A^ be i =l i  the  current number of words on the i - t h branch,  r e s p e c t i v e l y , f o r i = l,2,..,j£. Then JL I if g < l Z i i < 21 c.A^ i=l i=l c  A  L i f g=l  5L  Z c.A. = Z c.A . , l i • , I l i=l i=l  '  0  t  Z .  i f g> 1 FA  Z. L  ,  1=1  c. A. > I  I  where  c^ - 1  and  c. 4 TT  .  ,  i=l  Tf-* — 1  I  I  c.A  for i=2,3,..,i.  PROOF; Suppose that W . words are taken from the j - t h branch (j'^;C),  J and L j _ ^ words are placed on the T  that  ( j + l ) - t h branch. Taking  c d+i . , = c j. u .  the change i n the sum ^  F c.A. i s . , I l i =l  + 1  i n t o account  21 W . c. ,U. , - c.V. = c. rr-L- U. , - C.W. = 0 0+1 J+l J J J J+l J J  Now  suppose that W^ words are taken from the j2-th branch and U  words are placed  on the 1-st branch. We have  C  c  and  l  z  2  h.  V i  !i!2 =u u  u  3  z  = e w^  the change i n the sum  c  i i - A = i - i*x u  C  U  u  W  =V  1  " i>  i s p o s i t i v e f o r g > l , negative f o r g < 1, and zero f o r g=l. As a c o r o l l a r y we get a necessary c o n d i t i o n i n a t i o n of a loop,  Corollary  which i s e s s e n t i a l l y equivalent  to Theorem 2.6.  2.12  A necessary c o n d i t i o n g>l  for self-term-  and i n i t i a l  for self-termination  number  of a loop with  of words on the i - t h branch A?,  i = l , 2 , . . , L i s that  T  c.A°< J" c. ( T . - l )  1=1  PROOF:  1=1  I f the loop i s s e l f - t e r m i n a t i n g ,  of performances we must have  then a f t e r a f i n i t e  number  22  A. < T . - l i - i  f o r i=l,2,..,1 ' ' '  and T c.A.< i i .> , cI . ( T I. - l ) i=l i=l x  X  x  By Theorem 2.11 I  I  I  I , c.A°< . I l — f c.A. I l —< f c.I ( Tl. - l') i=l i=l i=l A  A  x  x  Now we s h a l l d e r i v e a s u f f i c i e n t c o n d i t i o n f o r loops w i t h g=l  Lemma 2.13 Let L be a loop w i t h g = l , and W\=T^  f o r i = l , 2 , . . , L e t A?  be the i n i t i a l number of data words on t h e i - t h branch f o r i=l,2,..,£. I f  Z c.A. < max c .V .  i=l  1  1  I<j<l  J  J  then t h e loop i s s e l f - t e r m i n a t i n g ,  PROOF:  L e t k be such number t h a t  max c -V . = c, Vf, Tli en  JL  c t— n .*—, c, i=l k Since  i 1  ^ k  23  I  c.A° =  I c.A.  where A. i s the current number of words on the i - t h branch we have l X* c X c A, < 5" — A. = 7 — A ° < W , = T, k c, l c, l k k i=l k i=l k  Thus the number of words on the k-th branch w i l l never reach the t h r e s h o l d and the number of performances of node iij. i s zero. By Lemma 2.2 every node of the loop terminates. Hence the theorem.  Theorem 2.14 Let  L be a loop with g=l. Let A? be the i n i t i a l  number of  data words on the i - t h branch, i = l , 2 , . . , X . A s u f f i c i e n t c o n d i t i o n f o r s e l f - t e r m i n a t i o n of L i s that  0  1  y c.A < y c. (T.-W.) + i=i  PROOF;  1  1  i i i  1  1  1  max c.V .  i*gjt  JJ  Suppose t h a t L does not terminate. Then a f t e r each node  performed  at l e a s t once,  A  i ^  W  i , e  -  A  i  =  (VV  +  A  i  where A[> 0  for i=l,2,..  I f we r e p l a c e A^ and T^ by A| and T^=Vr_^, r e s p e c t i v e l y , the r e s u l t i n g loop L' w i l l not  have the same t e r m i n a t i o n p r o p e r t i e s as L, i . e . w i l l  terminate. . Then by Lemma 2.13  24  2_ c'A!  i=l  1  > max c'.W. J J l£j*Jt  1  Since c!=c f o r i=1.2,*.,£  f  iTi  c . A = f c.A. = ? c. (T.-YT. ) + [ c.A! 0  1  1  iti  1  1  1  1  T c(T.-W.) +  itl  1  1  1  i=i  1  1  i=i  1  1  = £ c. (T.-V. ) + J_ c!A!> 1  i=l  1  1  max c'.W. = T c.(T.-W.) +  l<j<Z  J  J  i=l  1  1  1  l*j£  ~  x  max c .W.  J  J  which i s a c o n t r a d i c t i o n .  To i l l u s t r a t e how strong the c o n d i t i o n s of C o r o l l a r y 2.12 and Theorem 2.14 are consider the f o l l o w i n g two simple  examples;  Example 2.4 4 W=T=2 * U=2 n  Here  W=T=1  c^=c-j=l c =c =2 2  U=l  Ic.A  i i  and  4  = 2 =Ic.(T.-l)  0  *~ l  the l o o p  x  terminates  Example 2.5  Here c^=c =l and 2  max c.W.=1 l<j£2 J  A=0  Termination Fig.3  J  7c.A?=l= Zc•(T.-W.)+raax c.W. l<g£2 J and the loop does not terminate 1  of loops  1  1  1  1  l  J  25  2•3 A d i r e c t method of t e s t i n g t e r m i n a t i o n p r o p e r t i e s of strong components• As noted  i n /6/, the K a r p - M i l l e r a l g o r i t h m r e q u i r e s the inspec-  t i o n of each loop of a strong component G' when G' i s not s e l f - t e r m i n a t i n g . I f G' contains many loops a more d i r e c t way i s d e s i r a b l e . Consider  the s h o r t e s t - r o u t e a l g o r i t h m given i n / l 3 / . I t i s  used i n Step 2A of the K a r p - M i l l e r a l g o r i t h m f o r t e s t i n g t e r m i a t i o n properties  (see p a r t 2 . 1 ) . I f we use m u l t i p l i c a t i o n and a s s o c i a t e  U p/A p with branch dp ,'rather than a d d i t i o n and log(U ° p'A p'), ' then,' i n• r  the absence of loops with g < l , the algorithm r e s u l t s i n a s s i g n i n g a r a t i o n a l number to each node of G'. On m u l t i p l y i n g these numbers by the l e a s t common product of t h e i r denominators each node n. w i l l have an i n t e g e r OC . assigned. l ° l ° If d =(n.,n.) i s a branch of a loop L with g=l, then 06. /oi. =\j A . p i ' j o > j ' i p ' p 1  I f L has g > 1, then f o r one and only one branch do we haveOc^/<X< <U  P  A  ; f o r other branches of L OC./CX.^U A • P' J/ i P P Consider  now an a r b i t r a r y loop L of G' with g=l. I f L i s s e l f -  t e r m i n a t i n g then by Theorem 2.8 the number of performances i s f o r at l e a s t one node n.€ L l e s s t h a n O C . . We  shall  J  J  show that the same i s v a l i d f o r loops with g>l.  Theorem 2.15 I f L i s a s e l f - t e r m i n a t i n g loop with g> 1, then at l e a s t one component of X i s l e s s than the corresponding here  X =  X,  a  X,  oc  X,  x*=  component of X?  a  l 0  OC,,  a(U A ) 1  1  a(u A )(u A )-(fiV i-i ;  1  1  2  2  )  26  where a i s an a r b i t r a r y parameter  and X^ i s the number of  jierf ormances of node n^, i=l,2,..,X.  PROOF;  By Theorem 4 of /6/, X i s the minimum nonnegative (E-A)X>/3  of  0  0  1  0  ,  , i.e.  .  0  x  0  •  •  V  l  x  u.  0  solution  2  ^2  >  •  •  •  •  •  0  0  where  /3-,  uJt-1  0  =  W  V l 1  A  and  fc.  i-1- i-1 T  + 1  i  i  V l  —  2 , 3 , . . ,/£  Then 0  U.  (E-A)X* =  0  0  0  a  0  0  l  tf  0  0  0  u'l-l l-l  W  2  ^1^2 W  l  V l W l  27  1-g 0  (E-A)X* =  a  ^  0  0  0  Now  consider the v e c t o r  X-X*.  (E-A)(X-X*) = (E-A)X - (E-A)X* > /3  I f no  component of X i s l e s s than the corresponding  component of  then (X-X*) i s a smaller nonnegative i n t e g e r s o l u t i o n of  X*,  (E-A)X>/|  than X, which i s a c o n t r a d i c t i o n .  Theorems 2.15, for  2.8,  and  2.4  serve as a b a s i s f o r a procedure  t e s t i n g t e r m i n a t i o n p r o p e r t i e s of strong components, which  may  be o u t l i n e d as f o l l o w s : Step 1.  Apply the s h o r t e s t - r o u t e algorithm modified  I f a loop with g<1  i s found go to Step 2; otherwise  each node n. of the strong component i s assigned l  Step 2. the  continue  strong component G  1  until  until  a constant^. .  °  Apply the i t e r a t i o n  scheme of Theorem 2.9  l  to the nodes of  either  a) the scheme terminates, terminating  as shown above.  e s t a b l i s h i n g t h a t G'  is self-  and g i v i n g the number of performances x ( j ) f o r each  n . € G , or 1  3  b) f o r some n and C*  k  some k, x  on x ( k ) , e s t a b l i s h i n g t h a t G'  (k) exceeds the upper bound  i s not s e l f - t e r m i n a t i n g .  - CHAPTER 3 ;  STORAGE  REQUIREMENTS  In the K a r p - M i l l e r model each branch d^=(n^,nj) r e p r e s e n t s a queue of data words which may i a t e d with node n^ and which may  be an output of o p e r a t i o n 0^ a s s o c serve as an input f o r o p e r a t i o n 0j  a s s o c i a t e d with node n^. Each data word has to be s t o r e d i n a memory l o c a t i o n of a computer performing the computation, and the maximum number of memory l o c a t i o n s r e q u i r e d becomes of i n t e r e s t . Chapter 3 i s devoted to t h i s  problem.  3•1 Maximum storage requirement - s p e c i a l case In t h i s part we present the r e s u l t s of / i f . Let us introduce a branch parameter tr > 0: I f d =(n..n.),X p p i J p r  i s the f i x e d time r e q u i r e d by node n^ to f e t c h i t s input data from storage, process these data, and place outputs i n t o memory l o c a t i o n s a s s o c i a t e d with the queue on branch d . Thus i f n. i n i t i a t e s at time p l t , i t places U data words upon branch d at time t+tT . Another P parameter we introduce i s PT^=max^TJ^| where the maxim um P i s taken over a l l branches d  d i r e c t e d out from node n.. P i ,( A schedule i s a set 4-{^-^ ' * * ->t} each w  n  e  r  e  i s a funct-  ion 6. such that f o r  : {l,2,..,X.} -» R  l<k<r£X. l  ^(kKd.U)  Here R i s the set of r e a l numbers and X^ i s the number of i n i t i a t i o n s  28  29  of node n^ f o r any proper execution of G. I f X^=0, With each  we a s s o c i a t e a f u n c t i o n x  : R-{o,l,2,..,X.}  i  x.(t)=0 1  i f f e i t h e r X.=0 1 iff 6  x  l<k<X ,  x (t)=k  For  X. > 1 ,  x.(t)=X. i f f <S-(X.)<t. i i i i  I  '  t  or X . i l and l  (k) ^ t < 6  For  i  i s undefined.  t<4.(l). l  (k+l)  v  For every branch d =(n.,n.) d e f i n e P i j b ( t ) = A +U x . ( t - T )-W ( x . ( t ) - E . ( t ) ) p P p i p p J J d  where £.(t)=l i f there e x i s t s k,  l^k^X.  such that  6.(k)=t  £..(t)=0 otherwise. A schedule  i s c a l l e d an a d m i s s i b l e schedule i f , f o r  j=l,2,..,X  <S.(k)=t b (t)> T j P P f o r a l l branches d i n t o n.. and f o r a l l k, 1 £ k £ X . . 6  P  J  J  A schedule <o i s s e q u e n t i a l i f f o r no nodes n., n., with i ' j do we have 1  n . . i J  6 . ( k ) < d . ( r ) < 6 . (k)+T. J  I  ,forl£k£X., i  I  I  l£r<X.. J  These d e f i n i t i o n s are to be i n t e r p r e t e d as f o l l o w s : <^(k)=t means that node n^ begins i t s k-th i n i t i a t i o n at time t under the schedule (J. x ^ ( t ) i s the number of i n i t i a t i o n s of node I K , up to and  including  time t , under the schedule <i. b ^ ( t ) i s the number of data words on branch d^ at time t . The  quant-  i t y £.(t) i s i n t r o d u c e d f o r the f o l l o w i n g reason: A l l data t r a n s m i t J  ted to node n^ by node n^ v i a the branch (n^,n^) must f i r s t  pass  30  through s t o r a g e . Then i f t i s a time at which n. does not  initiate,  the storage requirement at time t i s b ( t ) = A +U x . ( t - f )-W x . ( t ) . P P P i • P P J 6  I f n^ i n i t i a t e s at time t , the number of data words i n storage at time t i s b ( t ) = A +U x . ( t - r )-V ( x . ( t ) - l ) P P P i P P j 6  An a d m i s s i b l e schedule s p e c i f i e s those node i n i t i a t i o n times c o r responding to a proper e x e c u t i o n . Thus a node n^ i n i t i a t e s at time t (d>.(k)=t f o r some l < k < X .I )' only i f each branch dp d i r e c t e d i n t o J l v  v  n. contains at l e a s t T data words at time t . ( b ^ ( t ) > T ). F i n a l l y , l p ' p p a s e q u e n t i a l schedule i s a schedule under which no node i n i t i a t e s at the same time that some other node i s e x e c u t i n g . For any a d m i s s i b l e s c h e d u l e d , d e f i n e  A> = max t  C  6  T  b (t) p P 6  jkJ^ thus d e f i n e s the maximum amount of storage r e q u i r e d by the admissible schedule 6.  Lemma 3.1 Let 6 be an a d m i s s i b l e schedule f o r a computation graph G. Then there e x i s t s an a d m i s s i b l e s e q u e n t i a l schedule (a.s.s.) 6 such that  ^6' *  <^6  This Lemma shows that i n general a p a r a l l e l system i s more economi c a l than a s e q u e n t i a l system i n the sense that i t needs fewer storage  locations.  31  Let ^U/ = max ^ i s  6 i  s  &  n  admissible s c h e d u l e ^ .  the maximum number of memory l o c a t i o n s that a  computation  graph G can r e q u i r e .  i_,  C o r o l l a r y 3.2  £M = oax( ^/<?  For any admissible schedule  i s an a.s.s.)  define  <* = {t/t£ (6.(10,4. (kJ+'E) T  for 0 < k £ X . ,  i = l,2,..,/}.  are those times during which no node of G i s executing under the schedule 6 ;  however, nodes of G may  ing under 6 at some of the times t€ We  j u s t be i n i t i a t i n g or t e r m i n a t T^.  then have the f o l l o w i n g r e s u l t :  Corollary  3.3 (Ms- wax  6  Write b. f °  r  ^  n e  max { ^ ( " t ) / C J i s an a.s.s. and t 6 T^} t  .  column v e c t o r with p-th component A , W f o r the  column v e c t o r with p-th component W , T f o r the column v e c t o r with p-th component T , and,  f o r any admissible schedule  to be the column v e c t o r with p-th component b ^ ( t ) ,  <$> d e f i n e _b^(t) p=l,2,..,t.  Define a tXj£, matrix A with elements a a a a  PJ PJ PJ PJ  .=\V  i f branch d  P  . =-U  .=0  J  i f brancli d  P P  J  i f branch d  P  otherwise.  n..  i s d i r e c t e d out from n. but not a l s o into  P  . =Vr - U P  i s d i r e c t e d into n. but not a l s o out from  P  i s d i r e c t e d out from n. i n t o J  n.. J  J  n.. J  32  F i n a l l y , l e t X be a column v e c t o r with i - t h component X^, i = l , 2 , . . ,  Theorem 3.4 # Let G s a t i s f y b.>T-W. Then  i s determined by the f o l l o w i n g  i n t e g e r l i n e a r program: |b| - m i n U ^ I subject to 0 <y_< X  where each y^, i=l,2,..£, i s an i n t e g e r .  Theorem 3.4 enables us to determine r e q u i r e d f o r a given computation  the maximum amount of storage  graph, provided b>T_-W. What i f  t h i s i s not s a t i s f i e d ? We quote from /l/: "In those cases where t h i s i n e q u a l i t y i s v i o l a t e d , the program /of Theorem 3.4/ i s i n a p p l i c a b l e . Under such contingency one poss i b l e course of a c t i o n i s to simulate a l l p o s s i b l e a d m i s s i b l e schedules f o r G u n t i l a d i s t r i b u t i o n of data i s obtained which s a t i s f i e s the above i n e q a l i t y , and then apply the program /of Theorem 3.4/ to t h i s data d i s t r i b u t i o n . Then the maximum storage requirement  i s e i t h e r that obtained through the s i m u l a t i o n phase,  or that obtained by the program, whichever  i s the g r e a t e r . In  g e n e r a l , however, such a scheme would be i m p r a c t i c a l due to the p o t e n t i a l l y large number of p o s s i b l e d i f f e r e n t s i m u l a t i o n s i n volved. "  #  n I f ii i s a n-dimensional v e c t o r , then define |x[ = T, x. . ~~  i=l  1  33  3.2 Maximum storage requirement - general case A node n^ of a computation graph can i n i t i a t e  only i f f o r  every branch d^ d i r e c t e d i n t o n^ the number of data words associ a t e d with t h i s branch i s not l e s s than the corresponding t h r e s h o l d T . Consequently, the number of data words on t h i s branch a f t e r the i n i t i a t i o n i s not l e s s than T -V .  P  P  Consider a computation graph Cr which does not s a t i s f y b> T-W, i.e.  there e x i s t s at l e a s t one branch d^=(n^,n..), d^ £ G such that  A < T -Vi . Let us assume that G contains only one node t e r m i n a l to p p p r  such a branch. Later we s h a l l show how to extend the r e s u l t s to the case of more nodes t e r m i n a l to such branches. C l e a r l y , the data d i s t r i b u t i o n w i l l b >T-W  a f t e r the f i r s t  s a t i s f y the requirement  i n i t i a t i o n of n.. In the f o l l o w i n g we d e r i v e J  a method f o r f i n d i n g the maximum storage r e q u i r e d p r i o r to the f i r s t i n i t i a t i o n of n.. Then we apply methods of part 3.1 to determine the maximum storage r e q u i r e d a f t e r the f i r s t  initiation  of n.. J  Given a computation graph G modify i t as f o l l o w s : For  the node n^ jmt V .=T -=0 U • .=0 J  all all  s  Note that the data d i s t r i b u t i o n of the modified graph G' i s not a f f e c t e d by i n i t i a t i o n s of n.. In the f o l l o w i n g parameters  of G'  w i l l be primed. Lemma 3.5 Let  <o = (6L  where  x  ^ i ^ ,  (k. ), d>. (k. ), . . ,<J. (k. )} l l 2 2 m m x  r  i ,.., 2  1  x  be a schedule,  x  i } - I C { l , 2 , . . , j - 1 , j + 1,., l) m  and  34  x  l  x  l  i  x  x  2  x  2  x  2  x  di  2  x  2  (k  moreover  PROOF:  By  b*.(t)=b*(t)  3  x  3  £  m-1  Then 6 i s a d m i s s i b l e f o r G'  x  m-1  m-1  < <£. (k. ) . m ra  i f f i t i s admissible f o r G;  for  0<t£c?.  (k. ). m m  definition x.(t)=o i f f t ^ 6 . ( i ) x ( t ) = k i f f t >6\(k) and t£<S\ (k+l) i  Therefore  x.(t)=x!(t) l  and Also  for  and  0<t<d. ~-  x. (t)=x! (t)=0 i i  for  £ ( t ) = £j(t)  for  £. (t) = 6! (t)=0  i  i € l  x  i  and Let  l  i / l and i€I i/l  for  i  /  0<t<6. i  0<t<6-  d  and (ii) Here  r € I, s € I U =U , W =V» P P P P b ( t ) = A +U x ( t - t )-\f (x (t)-£ ( t ) ) = l j ( t ) p p p r p p s s p 1  6  6  U  and (iv) Here and  x  x  s^I  = p»  x (t)=x^(t)=0,  U  p  g  £ (t)=£^(t)=0 g  b*(t)=A +U x (t-r )=b'J(t) p  ( i i i ) r £ I, e  v  r e l ,  and  H re  M  v  V  p  = V  i  r  p  s6 I p»  x (t)=x^.(t)=0 r  b (t )=A -W ( x ( t ) - £ ( t ) )=b'J( t ) p  r£l,  p  p  s  s  s£l  x (t )=x^.( t )=x (t )=x^ (t ) = £ (t ) = £, (t )=0 f  s  b (t)=A =b {t) P P P 6  6  m  rn  i  for  (k.  m  i  ).  m d =(n p r  cases depending on whether r and s are  elements of I or not. (i) Here  (k. ). i m (1^ ),  i  and  lm  m  0 < t < d>  and  us examine b ( t ) = A +U x (t-V )-V (x (t)-£ ( t ) ) p p p r p p s s  There are four d i f f e r e n t  (k. )  I in  g  35  We  have thus e s t a b l i s h e d that  b£(t)  = b£,(t)  for  0 * t < 6 . (k. ). ni  Moreover, f o r a l l d =(n ,n ), s € I 'we ' p r' s ' v  have T'=T p p  m  and  b (t)>T 6  P P b'<Ht)>T'  iff.  p  A  r  for  p  This proves that 6 i s admissible  Lemma The  0 < t £ 6 . '(k. ). 1  1  ram  f o r G i f f i t i s admissible  for  G'.  3.6  maximum storage  S' r e q u i r e d f o r the modified graph G' max i s the same as the maximum storage S required for G p r i o r max to the f i r s t i n i t i a t i o n 6 • (1) of n.. J  PROOF: The  By C o r o l l a r y 3.2  proof  we  J  need only consider  sequential  schedules.  w i l l c o n s i s t s of 3 p a r t s .  Every s e q u e n t i a l s chedul e d> = i 6>. (k. ), < • > . (k. ) , . . , ( i . (k. ) , . . 1 1 2 2 mm can be d i v i d e d i n t o time i n t e r v a l s (i)  <o,6.  (k X  l  ) ) , <<3. (k l  X  l  X  1  l  ),6 X  (k  2  1  )),..,<d  2  1  From the d e f i n i t i o n of b ^ ( t ) and £^(t)  if  S(t)<S(<S. (k. in  where  m  ))  Sa+l  i t follows  S ( t ) < S(0) and  m  ) , L  (k 1  ra  if  t<6m  )),.. ^m+l  that  (k. )  1 1 (k. ) < t < d m  i  m+1  (k.  m+1  )  3(t)=|b (t)| 6  Thus to get S  i t i s s u f f i c i e n t to examine S ( t ) at t=0, <£. (k. ), max l ^ ^" 1' (>• (k. ), d>. (k. ),..; i n other words i t i s s u f f i c i e n t to examine the 2 2 3 3 i n t e g e r sequence S where S =S(<S. (k. ). m m . (ii) Here we s h a l l show that'S' is infinite i f f S is infinite. max max 1  x  x  x  (  ]ii  v  Let N be an a r b i t r a r y i n t e g e r . I f S'  i s i n f i n i t e , then there e x i s t s  36  a schedule («> and i n t e g e r M' such that S  Take the i n i t i a l  M • >  N  part of d> up to d> .  Hi'  (k. X  ) and omit a l l i n i t i a t i o n s  M'  of n.. Then by Lemma 3.5 we get an admissible  schedule 6 f o r G which  J  r e q u i r e s the same storage  as C>'.  Thus f o r some M<M'  we have S  M  = S  M«  >  N  "  In the same f a s h i o n we can show that S' is infinite i fS is max max infinite. (iii) v  Now suppose that S' max  ed by S J  1  max  and there  S' m  are bound-  part of 6 up to 6. (k. ) and omit a l l l^p l^j,  t  initiations  x  e x i s t s such a schedule d' and i n t e g e r M' that  S^ =S' . Take the i n i t i a l M max the  i s f i n i t e . Then sequences  1 1  of n.. This by Lemma 3.5 w i l l give us an a.s.s. f o r  G with the same storage  requirements as 6 . Thus S ' =S' i —S., £v£> max iM' M max V  (  On the other hand, since S i s f i n i t e , there ' max ' and i n t e g e r N such that N The i n i t i a l  part of t h i s  max  schedule up to O. (k. ) i s an a.s.s. o' f o r N • \\ requirements as o* This gives X  G' with the same storage  s From t h i s and S' < S max max  e x i s t s a schedule Q >  T  =s5=s'£^ S'  max N N we obtain S  =S  max  1  max" max C o r o l l a r y 3.7 Let a l l branches of G s a t i s f y A > T -Yi with a p o s s i b l e exp- p p 1  c e p t i o n of branch (n.,n.). Modify G as f o l l o w s : Put  all  V .=T .=0, rj  r;  a l l U =0 jg  37  Then the maximum storage S  ^ r e q u i r e d f o r G p r i o r t o the  f i r s t i n i t i a t i o n of n. i s determined by the f o l l o w i n g i n t e g e r l i n e a r program: max —' 1  1  -'  d  subject to  o<y <x^.  k/j  k  0 < y • < oo • A'vib-T'+W' where A', T', W', X' a r e parameters of the m o d i f i e d graph G'.  PROOF:  P r o o f f o l l o w s from Lemma 3.6 and Theorem 3.4.  Lemma 3.8 Let G be a computation graph whose a l l branches s a t i s f y Ap >T p- V ip' w i t h a p o s s i b l e e x c e p t i o n of a branch ( in .', n .j, ) ." 1  Let X.> 0. Then £=b^(t), where _c i s defined belov/, for some a . s . s . <S and some t € T^, t > <S. (1) i f f there e x i s t such i n t e g e r s y^ , i = l , 2 , . . ,J& which  PROOF:  satisfy  (i)  °-yk- k  (ii)  1< y• < X . J J £=P_- X^1-1L  X  k  ^  A  Analogous to t h a t of Theorem 2.4 of /l/.  C o r o l l a r y 3.9 Let G be a computation graph whose a l l branches  satisfy  Ap > T p-Vp w i t h a p o s s i b l e e x c e*p t i o n of a branch  (i n . ,Jn . ) .  1  38  Let X.>0. Then the maximum storage j °  S^ max  r e q u i r e d a f t e r the 1  first  i n i t i a t i o n of n. i s determined by the f o l l o w i n g i n t e g e r J l i n e a r program: S"*" =1 b I -inin j Ay I max ' — 1  J  1  subject to  o<y <\  k^j  k  Ay_<b - T + ¥ where ea.ch y  k  i s integer.  Theorem 3.10 Let G be a computation graph whose a l l brandies  satisfy  A  (n.,n.). J  >T -YY with a p o s s i b l e exception P P P Let X^ > 0. Then the maximum storage  of a branch  1  required i s  M/ = max(3 , ) < max' max  PROOF:  I.  a)  Suppose 1 1  S ^S max max 1  There e x i s t s an a.s.s. f o r the modified  graph G' which r e q u i r e s S ^ m  of storage. By Lemma 3.5 t h i s schedule i s admissible t h e r e f o r e i s an i n i t i a l  part of some a.s.s.  a l s o f o r G and  f o r G. Thus  A/> S >3 max C max and XC>max(S ,3"^ ) C — max' max b) Now suppose S >S max— max By C o r o l l a r y 3.9 S ^ = I b | -1 Ay_°l 1  1 1  ax  whor e subject to  | Ay_°| = m i n | Ay_ | 0^y <X k  k  k^j  x  39  Then by Lemma 3.8 S  =|b (t)|- f o r some a.s»s.» and  1  6  niax  /W/^S >s C max— max Xt/>raax(S ,3^" ) <• max' max Let (•> be an a r b i t r a r y schedule f o r G. Then 1  i.e. II.  |b (t)|<S — " max  for t<d.(l) j  6  1  and  x  I b (t )| ^ 3 for t>6.(l) — max j ii/<iraax(S , ) Cr — max' max r e s u l t s of I . and I I . give M/= raax(S , S"^ ), q.e.d. < max' max ' ^ d  1  Thus The  1  1  —  b  Theorem 3.10 and C o r o l l a r i e s  3.7 and 3.9 thus provide means  f o r f i n d i n g the maximum storage f o r graphs  where one and only one node  i s t e r m i n a l to a branch which does not s a t i s f v A > T -W . p- p p In case there are' r such nodes, we take a subset of these nodes { n. ,n. ,..,n. , where 0 < s r . For a l l branches d i r e c t e d ^ l 2 s i n t o the nodes of the subset we put Yi =T=0, and f o r a l l branches X  X  r  directed  out from the nodes of the subset we put U=0. Then to t h i s  m o d i f i e d graph we apply the f o l l o w i n g i n t e g e r l i n e a r program: Smax =jbl-min|Ay I — I J. i 1  1  s u b j e c t to 0<y <X k  k  Mn  ,n 1 2  ,..,n. s  l £ y • £ x. i l 1 < y • < X. x  x  16 y • £ X . i i s s r r Since there are 2 sucli subsets we have 2 l i n e a r J  The maximum r e q u i r e d storage i s the maximum of the 2 storage  requirements.  programs.  p a r t i a l maximum  CHAPTER 4 CONCLUSIONS  The  Karp-Miller algorithm f o r t e s t i n g termination properties  of computation graphs i s based on the t e r m i n a t i o n p r o p e r t i e s of loops. I t i s , t h e r e f o r e , d e s i r a b l e to have means f o r t e s t i n g  loops.  A q u a n t i t y r e l a t e d to the number of data words i n a loop i s i n t r o d u c e d , which decreases f o r g < l , constant it  f o r g=l,  i n the course  p o s s i b l e to d e r i v e a simple  increases for g > l ,  sufficient  i n t u i t i v e l y more s a t i s f y i n g proof  case that \V=U,  due  the necessary  c o n d i t i o n (Theorem  is invalid simple  has  i n the general  sufficient a simple  l o c a l character case, one  and  and  necessary special  c o n d i t i o n i s given form due  to the  fact  i n t h i s case. Since  probably  form of the general necessary The  of  to Karp and M i l l e r . In the and  2.14)  to give a s h o r t e r  ( C o r o l l a r y 2.12)  (Theorem 2.10). This c o n d i t i o n has t h a t data propagation  remains  of computation. This concept makes  f o r s e l f - t e r m i n a t i o n of loops with g=l, and  c o n d i t i o n of Theorem 2.6  and  this  cannot hoj)e f o r a  sufficient condition.  K a r p - M i l l e r algorithm i s not w e l l s u i t e d f o r computation  graphs with many loops. Therefore,  i n part 2.3  of Chapter 2 a d i r e c t  procedure f o r t e s t i n g t e r m i n a t i o n p r o p e r t i e s of s t r o n g l y connected graphs i s d e r i v e d . The every  procedure does not r e q u i r e i n s p e c t i o n of  loop as i n the K a r p - M i l l e r a l g o r i t h m . However, i t a l s o uses  the i t e r a t i o n scheme of Theorem 2.9, too  which f o r l a r g e graphs may  be  lengthy. R e i t e r i n /l/  gives a l i n e a r i n t e g e r program f o r  the maximum amount of storage  determining  r e q u i r e d i n the s p e c i a l case that 40  41  b>T-W. P a r t 3.2 of c h a p t e r 3 extends h i s method t o cover the g e n e r a l case. The number of l i n e a r as 2  1  programs r e q u i r e d i n our method  increases  where i i s the number of nodes t e r m i n a l t o b r a n d i e s which do  not s a t i s f y A^ > ^p""^*p»  o u  ^  -"-^ appears t o be more e f f i c i e n t  than  s i m u l a t i o n of a l l p o s s i b l e schedules /7/, e s p e c i a l l y f o r h i g h l y parallel  computations.  REFERENCES  flf  Gregory J . and McReynolds R., "The SOLOMON computer", IEEE T r a n s , on E l e c t r o n i c Computers, v o l . EC-12, pp.774-781, Dec. 1963.  /2/  Schwartz J . , "Large p a r a l l e l pp.25-32, Jan.1966.  /3/  S l o t n i c k D.L. et al.,"The ILLIAC IV computer", IEEE T r a n s , on Computers, v o l . C-17, No.8, pp.746-757, Aug.1968.  /A/  Thurber K . J . and Myrna J.W., "System d e s i g n of a c e l l u l a r APL computer", IEEE T r a n s , on Computers, v o l . C-19, No.4, pp.291-303, A p r i l 1970.  /5/  K o c z e l a L . J . and Yvang G.Y., "The d e s i g n of a h i g h l y p a r a l l e l computer o r g a n i s a t i o n " , IEEE T r a n s , on Computers, v o l . C - 1 8 , No.6, pp.520-529, June 1969.  /6/  Karp R.M. and M i l l e r R.E., " P r o p e r t i e s of a model f o r p a r a l l e l computations: deterrninacy, t e r m i n a t i o n , q u e u i n g " , SIAM J . A p p l . Math., vol'.14, No.6, pp. 1390-1411, Nov.1966.  flf  R e i t e r R., "A study of a model f o r p a r a l l e l c o m p u t a t i o n s " , Techn. Report No. RADC-TR-6S-350, Rome A i r Development C e n t e r , Nov.1968.  /8/  R e i t e r R., " S c h e d u l i n g p a r a l l e l No.4, pp.590-599, Oct.1968.  /9/  Mart i n D.F., "The automatic assignment and sequencing of computa t i o n s on p a r a l l e l p r o c e s s o r systems", -Ph.D. T h e s i s , Dept. of Eng., UCLA, Jan.1966.  computers", J.ACM, v o l . 1 3 , No. 1,  c o m p u t a t i o n s " , J.ACM, v o l . 1 5 ,  /lO/  M a r t i n D.F. and E s t r i n G., "Path l e n g t h on graph models of computations", IEEE T r a n s , on Computers, v o l . C - 1 8 , No.6, pp.530-536, June 1969.  /ll/  Baer J.L.E. and E s t r i n G., "Bounds f o r maximum p a r a l l e l i s m i n a b i l o g i c graph model of c o m p u t a t i o n s " , IEEE T r a n s , on Comp., v o l . C - 1 8 , No.11,.pp.1012-1014, Nov.1969.  /12/  R e i t e r R., "On a s s e m b l y - l i n e b a l a n c i n g problems", O p e r a t i o n s Research, v o l . 1 7 , No.4, pp.685-700, July-Aug.1969.  /13/  Ford L.R. and F u l k e r s o n D.P., Flows i n networks, P r i n c e t o n U n i v e r s i t y P r e s s , P r i n c e t o n , 1962, pp.130-134.  42  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 29 27
United States 7 0
Russia 3 0
Japan 1 0
City Views Downloads
Beijing 23 0
Unknown 6 2
Shenzhen 6 27
Ashburn 3 0
Saint Petersburg 1 0
Tokyo 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0102044/manifest

Comment

Related Items