This a r t i c l e is concerned with c e r t a i n p r o b l e m s in the application of m u l t i p r o c e s s i n g computation s y s t e m s . It puts f o r w a r d a s y s t e m of equivalent t r a n s f o r m a t i o n s of linear and sequential p r o g r a m s written in a high level language (of the type of ALGOL-60) into p a r a l l e l ones. The c o m p l e t e n e s s of the s y s t e m of equivalent t r a n s f o r m a t i o n s of the linear p r o g r a m s is proved. This article also c o n s i d e r s questions on the 9automatic d e p a r a l l e l i z a t i o n of sequential p r o g r a m s and the r e a l i z a t i o n of the language A L G O P P , which is an e x a m p l e of the extension of ALGOL-60 to d e s c r i b e p a r a l l e l p r o c e s s e s , on the b a s i s of the existing t r a n s l a t o r s f r o m ALGOL-60o 1. E q u i v a l e n t Programs
into
Transformations Parallel
of Sequential
Ones
1.1. Some Definitions and Notation. An ALGOL p r o g r a m is called a sequential p r o g r a m if it does not contain any t r a n s f e r s t a t e m e n t s , and is called a l i n e a r p r o g r a m if it contains n e i t h e r t r a n s f e r n o r loop s t a t e m e n t s . When p r o c e d u r e s t a t e m e n t s a r e p r e s e n t the above r e s t r i c t i o n s a r e extended to the whole. Under the stated conditions, a l i n e a r p r o g r a m is a sequence of input and output s t a t e m e n t s , IF s t a t e m e n t s , a s s i g n m e n t s t a t e m e n t s , p r o c e d u r e s t a t e m e n t s , and empty s t a t e m e n t s ; t h e s e may be joined t o g e t h e r to f o r m compound s t a t e m e n t s and blocks. S t a t e m e n t s will be denoted by the l e t t e r s or the l e t t e r s with indices, unless the c o n t r a r y is explicitly stated. Let us new suppose that the p r o g r a m P c o n s i s t s , besides other s t a t e m e n t s , of n a s s i g n m e n t s t a t e ments: Yl : = L Cxl, x2. . . . . xmt), where i =1, 2, . . . , n; and m i is the n u m b e r of distinct v a r i a b l e s on the right side of the a s s i g n m e n t s t a t e ment, and not ~11 the Yi a n d f i a r e different.~ We will distinguish the following sets of v a r i a b l e s in the p r o g r a m P: C(P) ={yi}; b) the independent v a r i a b l e s R (P} = x l x C
ables V(P) =C(P) U R(P); d) the inputs ! (P)= 0 /Y l Y ~ C (si) & g ~
8) the dependent v a r i a b l e s
T~ , where T~. = {xl, x~. . . . . xm~.}; c) the useful v a r i -
I x [ x E R ( s ~ ) & x f ~ C ( s l , s 2. . . . . s~_~)}; e) the outputs 0 (P) =
C (s,.+~, . . . , s2}~
F o r an input-output s t a t e m e n t s, C ( s ) = ~ , I ( s ) = R(s) =O(s)~ F o r the e m p t y s t a t e m e n t s, I(s)= R(s)= C(s) = o (s)= r We will use the following notations: =V: this will denote i m m e d i a t e s u c c e s s i o n between s t a t e m e n t s , i.e., se--=.~s~+~. =v : this will denote s u c c e s s i o n between s t a t e m e n t s , i.e., st::~st, where i< j. S (si, s i + l , . . . , s i + k) will denote a sequence of s t a t e m e n t s in the p r o g r a m which has the s e n s e of a unit of action and f o r m s a section of the p r o g r a m . Where a p r o c e d u r e s t a t e m e n t is concerned, this section will be taken to be the whole of the p r o c e d u r e . In p a r t i c u l a r c a s e s the section m a y consist of a single s t a t e ment. T r a n s l a t e d f r o m Kibernetika, No. 1, pp. 103-114, J a n u a r y - F e b r u a r y , 1973. Original a r t i c l e s u b mitted N o v e m b e r 26, 1971. 9 1975Plenum Publishing Corporation, 227 West 17th Street, New York, N.Y. 10011. No part of tins publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission o f the publisher. A copy o f this article is available from the publisher for $15.00.
122
~ will denote the e q u i v a l e n c e of the p r o g r a m s P and P ' (P ~ P~). si~ , siz . . . . .
Sik will denote the s i m u l t a n e o u s e x e c u t i o n of the s t a t e m e n t s sil, si2 . . . . .
Sik. T h e s e
s t a t e m e n t s will be c a l l e d p a r a l l e l s t a t e m e n t s o r will be said to be e x e c u t e d in p a r a l l e I . T k e s t a t e m e n t s~ will be said to be d i r e c t l y dependent on the s t a t e m e n t s i (i < j), if t h e r e is at 1east one v a r i a b l e x such thaJt
xEC (sl), xE R (si),
(1o1.1)
and no s t a t e m e n t Sk(i< k < j) such that x E C ( s k ) . T h e s t a t e m e n t sj will be said to be w e a k l y dependent on the s t a t e m e n t s i ( i < j), if e i t h e r it is d i r e c t l y d e p e n d e n t on s i or t h e r e is a n o n e m p t y s e t of s t a t e m e n t s Skl , Sk2 , o o . , Ski such that c ~s,) N R (%) # ~ ,
C%) N R(sk,)#~, ......... C i%_~) N R (Skl) # ~ ,
(1.1.2)
C (%) N R (s~) # | while f o r e a c h v a r i a b l e x E R ( s j ) , if
xEC(s )&xEC(G)&...&xEC%t), then 9max(r, .....
w h e r e i < k~ < k~ < o.. < kl < ]; {rl,G . . . . . q } ~ The statements a)
rt)--I
{k~,k, . . . . . kz}.
s i and sj(i < j) will be said to be w e a k l y independent if
C%)NR%)=2~,
b) C(s) N R ( s ) = ~ , c)
t h e r e is no n o n e m p t y s e t of s t a t e m e n t s S k i ' 81{2 , . . . .
Skl such that
C' (s~,)~ R (%) & C' %,) ~ R (sk,) & . . . &C' ~skl)~ R (st),
(1.1.4)
o r t h e r e is at l e a s t one s t a t e m e n t s k (i < k < j) such that C %) = C ts~),
(1.1.5)
w h e r e s i and s k a r e w e a k l y independent; C' ts,) G C (s~;, C' (sh~ G C (sk) t r = 1,2 . . . . k l
,t) and i < k i < k 2 < . . , <
If j = i+1, then t h e r e is no need f o r (1.1o4) o r (1~176 We will need and u s e the following s t r o n g e r definition of s t a t e m e n t independence~ T h e s t a t e m e n t s s i and s j ( i < j) will be said to be s t r o n g l y independent if e i t h e r a) C(s) N V % ) = Z , b) C (st) N V (sI) = ~ , !
e) t h e r e is no n o n e m p t y s e t of s t a t e m e n t s Ski , Sk2 . . . . .
Skl, f o r which (1.1.4) holds when C (st) _~ U c (%), r=i
o r t h e r e is at l e a s t one s t a t e m e n t s k ( i < k < j) such that (1.1.5) holds w h e r e s i and s k a r e s t r o n g l y i n d e p e n dent. When the c o n t r a r y holds the s t a t e m e n t s s i and sj will be said to be s t r o n g l y dependent. S t r o n g i n d e p e n d e n c e of the s t a t e m e n t s s i and sj g u a r a n t e e s the i n v a r i a n c e of 0 (P) with r e s p e c t to the o r d e r of e x e c u t i o n of t h e s e s t a t e m e n t s , i.e., if y ~ C (s~), y E (-" (sj) and y E A ( s / ) , w h e r e l > j, then the r e s u l t
123
of e x e c u t i n g p r o g r a m P is independent of the o r d e r of execution of the s t a t e m e n t s s i and sj when t h e s e a r e s t r o n g l y independent. F i n a l l y , if we r e s t r i c t o u r s e l v e s to the c a s e of weak i n d e p e n d e n c e , then the i n v a r l a n c e of O(P) with r e s p e c t to the o r d e r of execution of the s t a t e m e n t s s i and sj r e q u i r e s that T s i < T s j hold w h e r e T s i ( T s j ) is the t i m e o f execution of the s t a t e m e n t si(sj). It is obvious that the definition of d i r e c t d e p e n d e n c e , of s t r o n g and weak dependence, and i n d e p e n d e n c e of s t a t e m e n t s can be extended to s e c t i o n s by r e p l a c i n g the w o r d " s t a t e m e n t " and its s y m b o l by the w o r d " s e c t i o n " and its s y m b o l . We shall now u s e the t e r m s " d e p e n d e n c e " and " i n d e p e n d e n c e " f o r s t r o n g dependence and s t r o n g independence, u n l e s s the c o n t r a r y is explicitly s t a t e d . ,
T h e s y m b o l ~ will denote a d i r e c t dependence r e l a t i o n , and ~ will denote a s t r o n g dependence r e l a tion between the s t a t e m e n t s they r e l a t e ; the s y m b o l I ~ will denote s t r o n g independence, and I ~ d i r e c t independence. In a l i n e a r p r o g r a m : is not r e f l e x i v e , s y m m e t r i c o r t r a n s i t i v e ; --* is not r e f l e x i v e o r s y m m e t r i c , but it is t r a n s i t i v e , i.e., if s ~ - ~ s i a n d
s ~ - + sk,
I -T is r e f l e x i v e and s y m m e t r i c , but not t r a n s i t i v e , i.eo, if s~ t - - ~ sr then ~i I- ~ si - - + s ,
then si --~ s~;
si, s~ I--~- s t,
but f r o m
and s j - - - + s k it does not follow that s ~ ] - ~ s k ;
t * is r e f l e x i v e and s y m m e t r i c , but not t r a n s i t i v e , i.e., if st ]--~s~, then s t j - - ~ s t , s t I ~
s, but f r o m
s t ]--~ sj and sj I ~ - s k it does not follow that s~[--~ sk. T h e r e l a t i o n ~ i m p l i e s - - , and I -* i m p l i e s , [ - - , but not c o n v e r s e l y . We note that the s e c t i o n c o n c e p t c o r r e s p o n d s to that of a c o m p l e x of s t a t e m e n t s , I (S) to an input c o r t e g e , and O (S) to an output c o r t e g e in [1]. Suppose that we have a s e c t i o n S with k (S) = {x,, x~. . . . . x,J; 1 (S) = {xq, xt2, . . . . x~}, 0 (S) = {xl~, x~.2. . . . . x~.}, which contains a s s i g n m e n t s t a t e m e n t s g,, : = f, (x~. . . . . x~), re, : = f2 (x, . . . . . xm),
Y.i : = fi ix, . . . . .
x~),
w h e r e t h e r e m a y be fictitious a r g u m e n t s a m o n g the a r g u m e n t s xl, x2, . . . , ....
ft"
F o r p = 1, 2 . . . . .
1. P u t q = t . 2. P u t f p ,
l we execute the following s u b s t i t u t i o n a l g o r i t h m .
Goto2. q=yjq.
Go t o 3 .
3. If q = 0 , then take f p , q f o r f ' 4.
x m of the functions f l , f 2 ,
P u t fq(X l, x 2. . . . .
P
and stop; o r e l s e go to 4.
x m) in f p , q in p l a c e of Yrq. T h e r e s u l t of this substitution is to be t a k e n
f o r f p , q-l" Go to 5. 5.
D e c r e a s e q by unity. Go to 3.
When the a l g o r i t h m has been executed l t i m e s we get a s e q u e n c e of functions:
124
f; (%, ,% . . . . .
x,),
f'2 (x t 1, x~ 2. . . . .
x z),
.
.
,
~
*
~
~
.
f; Cx,,. % ..... ~,). Next we c o m p a r e p a i r s of functions f r o m this sequence and we delete one of each p a i r if they are identical. Hence we obtain a sequence of fimctions:
r, (xq, % ..... x~,),
& (xq, x;2. . . . . x~),
fN (xq, x~2. . . . . x~), which are mutually distinct. F u r t h e r , ff we delete the fictitious arguments f r o m the r e m a i n i n g functions, and if we r e n a m e t h e i r actual arguments as the set of v a r i a b l e s {uil i = 1, 2 . . . . , M} and choose the set { zj I j= 1, 2 . . . . . u 2. . . . .
N} such that {u~} (] {zj} = ~ uM} and O (S')= {zl, z 2. . . . .
, then we can r e w r i t e the section S'(sl, s 2. . . . .
sN) with (S') = {ui,
ZN}, where s~ ts
z, : = fl (ul. % . . . . .
uM,),
The section so obtained is c h a r a c t e r i z e d by the follo~4ng-" 1) t ( S ' ) fl, O(S') = O; 2)
Vv(vEV(S ') ~ v E l (S') V vEO(S'))* ; i.e., any useful variable v is either an input o r an output;
3) the following identity holds for no p a i r k, l (k, t = 1, 2 . . . . . h (u. u 2. . . . .
u~,,) - ~ fl (u. % . . . . .
N and k ~/)
u~).
The section S' is said to be equivalent to the section S and we will denote it by ES . The construction a l g o r i t h m given above for section ES equivalent to "any linear section S is taken f r o m [1], p. 100, and has been t r a n s l a t e d into the notation of t h i s , a r t i c l e . Concepts not defined in Sec. 1 of this article are to be understood in the s e n s e given t h e m in [1]. The t r a n s f o r m a t i o n of a linear section to its equivalent c o r r e s p o n d s exactly to the t r a n s f o r m a tion of a complex to its equivalent in [1]. Now suppose that we have equivalents ES t mad ES 2 f o r the linear sections Si and S2 for which it is kno~11 that O (ES1) and O (ES2) contain the same n u m b e r of variables as do I (ES 1) and I (ES2) , r e s p e c t i v e l y . We shall a s s u m e that for e v e r y value in one of the sets M 1 o r M2 t h e r e is at least one value in the other set which coincides with the f i r s t value in I (ESi) N I (ES2). Each p a i r of such values is a value of a v a r i able in I*, where I* =I(ES1)U I(ES2). The set of all such values will be denoted by M. The sections S1 and S2 will be said to be equivalent (St ~ $2) if the right sides of the a s s i g n m e n t statements of the section ES i are pairwise identical with the right sides of the assignment statements of the section ES2, and the identities a r e in Mo The definition of equivalence also holds for p r o g r a m s since p r o g r a m s can be c o n s i d e r e d to be sections. 1.2. T r a n s f o r m a t i o n of L i n e a r P r o g r a m s into P a r a l l e l P r o g r a m s . Equivalence t r a n s f o r m a t i o n s of linear p r o g r a m s have already been c o n s i d e r e d in [t]. S i m i l a r t r a n s f o r m a t i o n s for p r o g r a m s in a high*Here V means " e i t h e r . . .
or."
125
l e v e l l a n g u a g e (of the t y p e A L G O L - 6 0 ) h a v e b e e n g i v e n in [2]. Such t r a n s f o r m a t i o n s formations) translate linear programs into linear programs.
(called here L-trans-
H e r e we a r e i n t e r e s t e d in t r a n s f o r m a t i o n s which, when a p p l i e d to a s e q u e n t i a l p r o g r a m in a high l e v e l p r o g r a m m i n g l a n g u a g e , would b e a b l e to p r o d u c e a p a r a l l e l p r o g r a m w h i c h would b e t t e r c o r r e s p o n d t o t h e s t r u c t u r e and c o m p o s i t i o n of t h e g i v e n m u l t i p r o c e s s i n g c o m p u t a t i o n s y s t e m . Such t r a n s f o r m a t i o n s (called hereP-transformations)could b e b a s e d on t h e c o n c e p t of s t r o n g i n d e p e n d e n c e and we p r o p o s e s o m e b e l o w , both in t h i s s e c t i o n and in S e c . 1.4. Transformation
1.2.1o I a a r a l l e l i z a t i o n of s e c t i o n s .
If s i and sj a r e i n d e p e n d e n t (i, j = 1, 2 . . . . .
n; i = j), t h e n
S (sl, s 2 . . . . .
T r a n s f o r m a t i o n 1.2.2. R e a r r a n g e m e n t
, i . } = {1, 2 . . . . .
Transformation
1.2.3.
s~, s 2 . . . . .
%
of p a r a l l e l s t a t e m e n t s of s e c t i o n s .
Sl' a2, ....
w h e r e { i , , i, . . . .
s.; ~
s n ~*" Si |, Si~, 9 9 .t Sin,,
n}.
N e s t i n g of p a r a l l e l s e c t i o n s (union of p a r a l l e l s t a t e m e n t s to f o r m s e c t i o n s ) .
"g (s,, s~ ..... s~, st+ , .....
s~+,,, s~+,~+, ..... s,,) .-. ~ (s,, s~ .....
s~,~ (st+ , .....
s~+~), s~+k+ , ..... s.).
T r a n s f o r m a t i o n 1.2.4. I n s e r t i o n of a s t a t e m e n t into a p a r a l l e l s e c t i o n . If a s t a t e m e n t i s p a r a l l e l to a s e c t i o n , t h e n i t s i n d e p e n d e n c e f r o m t h e s t a t e m e n t s of t h e s e c t i o n i m p l i e s t h a t it c a n b e i n s e r t e d into any p o s i t i o n i n t h i s s e c t i o n : s l, s~. . . . . si, S (ql . . . . . qm), sz . . . . . s. N s I. . . . . si_ 1, s~+I . . . . . s~, S (ql . . . . . qk' si, qk+l . . . . . w h e r e j = 1, 2 . . . . . independent.
i, l, i . . . ,
n, k = 1, 2 . . . . .
m; i + m <
l-n;
q.~),st . . . . . sn,
i < l - - m ; m < n, if sj and S a r e m u t u a l l y
D e f i n i t i o n 1.2.1. A s e q u e n c e of s t a t e m e n t s L = s l , s2, . . o, s n o f t h e p r o g r a m P is s a i d to b e a l i n e a r c h a i n if si -~ s~+l (i = 1, 2 . . . . . n - - 1); sl--~tfor
l~i(n
and t E P i r n p l y
tEL;
t - + s t f~
l
and t E P i m p l y
tEL.
(1,2.1)
D e f i n i t i o n 1.2.2. A l i n e a r c h a i n i s s a i d to b e m a x i m a l if it is n o t c o n t a i n e d in any o t h e r l o n g e r l i n e a r c h a i n in t h e p r o g r a m . It i s n o t d i f f i c u l t to v e r i f y t h a t if L t and L 2 a r e two m a x i m a l l i n e a r c h a i n s and L 1 and L 2 E P , t h e n L 1N L 2= 6. S u p p o s e II(s) and Z (s) a r e t h e s e t s , p o s s i b l y e m p t y , o f s t a t e m e n t s f r o m t h e p r o g r a m P on which t h e s t a t e m e n t s i s d i r e c t l y d e p e n d e n t and w h i c h a r e d i r e c t l y d e p e n d e n t on s , r e s p e c t i v e l y . D e f i n i t i o n 1 . 2 . 3 . T h e s e t of s t a t e m e n t s
L = sj, s2. . . . . s
of t h e p r o g r a m P is c a l l e d a p a r a l l e l c h a i n if
Fl(St) = FI(si) and Z (s~.) = Z(s/) for all statements
(1.2.2)
s i and s j , w h e r e 1 - < i , j - - - n and i ~ j .
D e f i n i t i o n 1.2.4. A p a r a l l e l c h a i n is s a i d to b e m a x i m a l i f i t is n o t c o n t a i n e d in any l o n g e r p a r a l l e l chain. I t is o b v i o u s t h a t if LI a n d L 2 a r e two m a x i m a l p a r a l i e l c h a i n s and L 1 a n d L 2 E P , t h e n L1NL 2 = 6 . We s h a l l s a y t h a t t h e s i z e of a c h a i n is t h e n u m b e r of s t a t e m e n t s it c o n t a i n s . D e f i n i t i o n 1.2.5. T h e o r d e r of p a r a 1 I e l i s m of a p r o g r a m i s t h e n u m b e r of s t a t e m e n t s in t h e l a r g e r (by s i z e ) of a l l i t s m a x i m a l p a r a l l e l c h a i n s .
126
Definition 1.2.6. The program P', which is obtained from the program P by distinguishing all its parallel sections and statements and which is equivalent to P, is called the complete parallel form of the program P. Definition 1.2.7. The program P is said to be reducible to complete parallel form (simply "reducible" below) if it can be reduced f~o complete parallel form by replacing maximal linear and parallel chains by linear and parallel sections, respectively. Let Z* (sl)=
{slsi~ s}
be the set of statements
dependent on the statement si,
N, (s,., s~) = Z* (st) f~ Z* (s) and N2 (sl, @ = Z* (st) U Z * ( s i) - - N~ {sf, s).
9T H E O R E M 1.2.1. In o r d e r that a p r o g r a m P = sl, s2, . . . , s n be r e d u e i b l e , it is n e c e s s a r y and s u f ficient that f o r e v e r y p a i r of independent s t a t e m e n t s s i and sj and f o r e v e r y skEN2(si, s j ) t h e following holds: N i ~st, si) ~ Z* (sk). It is obvious that the t h e o r e m holds only if the p r o g r a m P contains ments. Necessity.
(1.2.3) at l e a s t two i n d e p e n d e n t s t a t e -
S u p p o s e the p r o g r a m P is r e d u c i b l e , and that f o r the s t a t e m e n t s s i, s j ~ P we have s i ! - - sj.
It is obvious t h a t e i t h e r s i -~ s k, o r sj -" s k. Now a s s u m e that (1.2.3) is not s a t i s f i e d . T h i s is p o s s i b l e in the following c a s e s :
T h e n e i t h e r Nt (si, si}•Z*(sh)= r o r Z* ( S k ) C N 1 (si, sj)o
1) s i -~ s k and sj -~ s k, which c o n t r a d i c t s the h y p o t h e s i s of the t h e o r e m : s, E N~ (s o s;); 25 s t -:. s~, silL,-s~, , and t h e r e is a s t a t e m e n t s i such that
si-> sz and si--+s t and Z*(sk)N (Z*(s~) U Z*(si)5 = |
T h e n f o r s t a t e m e n t s s i and sj n e i t h e r (1o2.15 n o r (1.2.2) holds. T h i s m e a n s that n e i t h e r of the i n d e p e n d e n t s t a t e m e n t s b e l o n g s to a l i n e a r o r p a r a l l e l chain, which c o n t r a d i c t s the r e d u c i b i l i t y of P . Sufficiency. Suppose (1.2.3) holds. T h e n the s t a t e m e n t s k d e p e n d s on one of the s t a t e m e n t s s i o r sj and f o r m s p a r t of a l i n e a r chain along with it; the s t a t e m e n t s s i and sj e i t h e r both b e l o n g to the one p a r a l l e l c h a i n o r belong to d i f f e r e n t m a x i m a l l i n e a r o r p a r a l l e l chains which can be r e p l a c e d by l i n e a r o r p a r a l l e l s e c t i o n s which r e s p e c t i v e l y belong, in turn, to s o m e p a r a l l e l ehaino Whence it follows that P is r e d u c i b l e . THEOI~IEM 1.2.2o E a c h l i n e a r p r o g r a m P s a t i s f y i n g (1.2.3) has a unique c o m p l e t e p a r a l l e l f o r m . T h e e x i s t e n c e of the c o m p l e t e p a r a l l e l f o r m of the p r o g r a m P s a t i s f y i n g (1.2~
follows f r o m T h e o r e m
1o2olo Definitions 1.2.2 and 1.2.4 imply that one and the same set of statements (sections) cannot form two maximal chains simultaneously. This fact guarantees the uniqueness of the substitution and implies the uniqueness of the complete parallel form for the program P. If at some step several substitutions are made, then the order of their execution does not play any role since the sets of substitution statements have empty intersection and so the resulting substitutions for the section eithe- are independent or belong to independent sets of statements. Definition 1.2.7 and Theorems
1o2ol and 1.2.2 give an algorithm for transforming
the program
to its
complete parallel form. Algorithm I~2.1. i. Replace each maximal parallel chain L by its sectionS. 2. Replace each maximal linear chain L by its section S.
127
3. Repeat steps 1 and 2 until no maximal linear o r parallel chain r e m a i n s . If the p r o g r a m satisfies (1.2.3), A l g o r i t h m 1.2.1, when applied, r e p l a c e s it by a single section which is the complete parallel f o r m of the p r o g r a m . R e m a r k 1.2.1. The irreducibility of the p r o g r a m P means that t h e r e is at least one pair of independent statements (sections) which do not f o r m a parallel chain n o r belong to one. However one need only add the identity statement v : -----v (v ~ I (K) (] V(K)) to this set of independent o p e r a t o r s K in o r d e r to make it satisfy (1.2.3). R e m a r k 1.2.2. The o r d e r in which the maximal linear o r p a r a l l e l chains are replaced by linear or p a r a l l e l sections does not affect the complete parallel f o r m of the p r o g r a m , according to T h e o r e m 1o2.2o However, one can require, for definiteness, that the r e p l a c e m e n t is c a r r i e d out by s t a r t i n g f r o m the leftmost entry of the maximal p a r a l l e l o r linear chain. M o r e o v e r all the maximal parallel chains can be r e placed first, then all the maximal linear chains, and then these p r o c e d u r e s are repeated until the p r o g r a m is reduced to a single section. If a synchronization statement is included in the language, then the dependent sections can be d e p a r a l lelized in o r d e r to make m o r e rational use of the m u l t i p r o c e s s i n g computation s y s t e m instrumentation. T r a n s f o r m a t i o n 1.2.5. Deparallelization of a linear section with dependent s t a t e m e n t s .
If s~ --~ s~,
sk ~ s~ (where s/:~s k ) and s~ ~ s,,, then S (sl, s2. . . . . s ; s~+~. . . . . sn) N S (S1)(sl, s 2 , . . . , Sk) , S2(Sk+ ~, . . . . w(sj), sl .....
Sn)) , where 1 -<- j-< k, k+ 1 - l
-
The synchronization statement stops the execution of the section S2 after the statement s/_l until the final statements of S1 (in this c a s e sj), have been executed; the s t a t e m e n t s I depends on these. This statement is placed in front of each statement of the section S2 which depends on the statement (s) of the section S 1. T h e r e f o r e s e v e r a l synchronization statements can o c c u r in one application of t r a n s f o r m a t i o n 1.2.5. It is c l e a r that t h e r e can be m o r e than two sections on the r i g h t s i d e of the t r a n s f o r m a t i o n . R e m a r k 1.2.3. Application of T r a n s f o r m a t i o n 1.2.5 needs a dynamic approach to the p r o g r a m with due allowance being made for certain constraints on the use of synchronization s t a t e m e n t s . Some of these constraints (even fairly rigid ones) have been considered in [3]. In m u l t i p r o c e s s i n g computation s y s t e m s with partitioned m e m o r y , deparallelization of dependent s t a t e ments makes it n e c e s s a r y to t r a n s m i t information f r o m one parallel branch to anothero The T r a n s f o r m a tion 1.2.6 enables such a p r o c e d u r e to be executed. T r a n s f o r m a t i o n 1.2.6. Deparallelization with information t r a n s m i s s i o n . f o r m a t i o n 1.2.5 hold and C (sI, s2. . . . . sk) n R (sI . . . . , s) r ;~, then
S is,, s~ . . . . . s k. . . . . sl. . . . . s ) ~
If the hypotheses on T r a n s -
S (Sits, ..... ~(st),
t(M),s~ . . . . . s~, S~ ts~+,. 9 w(s~), r (M), sl . . . . . s~)), where w is the synchronization statement, t the t r a n s m i s s i o n statement, r a reception statement, and M is the mass of t r a n s m i t t a b l e (receivable) information (C(s,. . . . . sk) n R (sz. . . . , s~))~_M. We note that T r a n s f o r m a t i o n 1.2.6 can easily be generalized to the c a s e where the n u m b e r of branches is large, where the n u m b e r of dependent statements is large, and when the amount of information to be exchanged is l a r g e r . If C (s, . . . . . sk) ~ R (sz. . . . . sn) = ~3, then t, r, and w(s/) are equivalent to the empty statement and T r a n s formation 1.2.6 reduces to T r a n s f o r m a t i o n 1.2.5. In m u l t i p r o c e s s i n g computation s y s t e m s with c o m m o n m e m o r y there is the problem of a c c e s s to this m e m o r y . One approach to the solution of this p r o b l e m is proposed i n [4, 5]. We now p r e s e n t one m o r e t r a n s f o r m a t i o n which ean be useful in optimizing the p r o g r a m s being considered. This t r a n s f o r m a t i o n helps in extracting statements which are c o m m o n to s e v e r a l parallel branches shortens the p r o g r a m list, and significantly d e c r e a s e s the t r a n s l a t i o n t i m e . 128
T r a n s f o r m a t i o n 1.2.7. Extraction of s i m i l a r statements f r o m p a r a l l e l branches~ Let S I ~ S
2 ~
S m ~
~ll ~ 1~2~ " " "~ Us 9 S i l ~ 812 p ~ 9 ", Sin; I'$1~ gl2' " " ~ US' S]I~ 812' " " " ~ S[n~
UI ~ 122' " " "' Us~ $I 1 ' 812 ~ " " ~~ $ln;
Sin+ l -----sa, s ~ , . . . , spn;
S ~ _- sk,, % . . . . . %
and let Si, $2, o . ~ Sn be mutually independent. Then s ~s,,s2 ..... s~i~
s~(.,,.....,<)s~,
s~, . . . s , ~ - s _1,, +.,, ,..,
Sn) ,
where S~ = s,,, s;2 . . . . . % . S~ = s w si2 . . . . . sin,
*! Sm~--- 811~ Sl 2,
9 , o~ Sln.
Here the set of statements ul, u2, . . . , u s is written down in the initial p r o g r a m and t r a n s l a t e d once, and in the working p r o g r a m it is written ~ each of the sections SI, S89. . . . . S~n(tO the symbol ";"). 1o3_.: A Complete S y s t e m of Fundamental Equivalence T r a n s f o r m a t i o n s for L i n e a r P r o g r a m s . T r a n s formations 1.2.1 through 1.2.6 are the fundamental equivalence t r a n s f o r m a t i o n s which take a linear p r o g r a m to an equivalent parallel one and c o n v e r s e l y . Since the t r a n s f o r m a t i o n s are related to deparallelization and influence only the t e m p o r a l c h a r a c t e r i s t i c s of the p r o g r a m and the state of the m e m o r y , and since they do not change the content of the s t a t e ments n o r the values of the v a r i a b l e s , the equivalent parallel p r o g r a m can be equivalent to the linear p r o g r a m equivalent to it. We shall say that the s y s t e m of fundamental equivalence t r a n s f o r m a t i o n s is complete if e i t h e r of two a r b i t r a r y equivalent sections can be t r a n s f o r m e d into the other with the help of a finite number of the fundamental equivalence t r a n s f o r m a t i o n s . The L - t r a n s f o r m a t i o n s and T r a n s f o r m a t i o n s 1.2.1 through 1.2.6 f o r m a s y s t e m of fundamental equivalence t r a n s f o r m a t i o n s for linear p r o g r a m s . T h e o r e m 1.3.1. The p r o g r a m P can be reduced to its equivalent EP by a finite n u m b e r of fundamental equivalence t r a n s f o r m a t i o n s , and c o n v e r s e l y . The t h e o r e m will be proved if we can establish: a) the reduction of the parallel p r o g r a m to the c o m plete parallel f o r m and c o n v e r s e l y , b ) t h e reduction of the complete parallel f o r m to the linear p r o g r a m and c o n v e r s e l y , and c) the reduction of the l i n e a r p r o g r a m to its equivalent and c o n v e r s e l y . The p a r a l l e l f o r m of the p r o g r a m can differ f r o m its complete parallel f o r m by the p r e s e n c e of s y n chronization s t a t e m e n t s , by r e a r r a n g e m e n t s of p a r a l l e l statements o r sections, and by the o r d e r in which the independent statements o r sections are written. To r e m o v e exchange and s y n c h r o n i z a t i o n statements and to e x t r a c t dependent statements f r o m p a r a l lel sections one needs not m o r e than ( n - 1 ) . 2n t r a n s f o r m a t i o n s of the type of T r a n s f o r m a t i o n 1.2.6 (or not m o r e t h a n ( n - i ) - n / 2 t r a n s f o r m a t i o n s of the type of T r a n s f o r m a t i o n 1.2.5). R e a r r a n g e m e n t of p a r a l l e l s t a t e m e n t s o r sections can be accomplished by T r a n s f o r m a t i o n s 1.2.3 and 1.2.4. No m o r e than n - 2 and n - 2 * of these types of t r a n s f o r m a t i o n a r e n e e d e d , r e s p e c t i v e l y . No m o r e than k . n (or m o r e p r e c i s e l y , no m o r e than n - 2 + n - 2 2 + . . , + n - 2 k*, where k -< log 2 n) of T r a n s f o r m a t i o n s 1.2.2 a r e needed to establish *The notat2on is garbled in the R u s s i a n original text - P u b l i s h e r .
129
the r e q u i r e d o r d e r of the s t a t e m e n t l i s t . As a r e s u l t of t h e s e t r a n s f o r m a t i o n s we get the c o m p l e t e p a r a l l e l f o r m of the p r o g r a m . A c c o r d i n g to T h e o r e m s 1.2.1 and 1.2.2, when we apply T r a n s f o r m a t i o u 1o2ol to this f o r m no m o r e than n - 2 t i m e s , t o g e t h e r with a finite n u m b e r of steps of A l g o r i t h m 1.2.1, and add (or r e m o v e ) a finite n u m b e r of identity s t a t e m e n t s (according to R e m a r k 1.2.15, we get the l i n e a r p r o g r a m equivalent to the given p r o g r a m . Thus a finite n u m b e r of fundamental equivalence t r a n s f o r m a t i o n s r e d u c e s any p a r a l l e l p r o g r a m to a l i n e a r p r o g r a m equivalent to it. The c o n v e r s e t r a n s f o r m a t i o n is s i m i l a r . It is obvious f r o m T h e o r e m 4.2 of [1] that the reduction of the l i n e a r p r o g r a m to its equivalent needs a finite n u m b e r of L - t r a n s f o r m a t i o n s and t h e i r i n v e r s e s , and so o u r t h e o r e m is proved. THEOREM 1.3o2. A p r o g r a m equivalent to one of two equivalent p r o g r a m s can be reduced to a p r o g r a m equivalent to the other by m e a n s of a finite n u m b e r of fundamental equivalence t r a n s f o r m a t i o n s . The proof of this t h e o r e m is s i m i l a r to the proof of T h e o r e m 4.1 in [1]. THEOBEM 1.3.3. The s y s t e m of fundamental equivalence t r a n s f o r m a t i o n s is complete. Suppose Pl ~P2. In o r d e r to reduce the p r o g r a m Pl to the p r o g r a m P2 equivalent to it one need only t r a n s f o r m Pl to EP1, EP 1 to EP2, and EP 2 to P2. T h e o r e m s 1.3.1 and 1o3o2 imply that this needs only a finite n u m b e r of L - t r a n s f o r m a t i o n s and of T r a n s f o r m a t i o n s 1o2.1 through 1.2.6, and, p e r h a p s , the addition o r r e m o v a l of a finite n u m b e r of identity s t a t e m e n t s , and so the t h e o r e m is proved~ 1.4. T r a n s f o r m a t i o n of Loops. L e t us denote a loop by L X (Sl, s 2 . . . . .
where x is the loop p a r a m e t e r and s i ( i = l , 2 . . . . .
snh,
n) a r e the s u b s t a t e m e n t s of the loop.
F o r s i m p l e loops the following t r a n s f o r m a t i o n s a r e well known (also s e e [6], " P u r g i n g Loops"): 15 r e m o v a l of u s e l e s s s t a t e m e n t s ; 25 r e m o v a l of surplus s t a t e m e n t s ; 3) r e a r r a n g e m e n t of v a r i a b l e s ; 45 r e a r r a n g e m e n t of independent s t a t e m e n t s ; 5) e x t r a c t i o n of s t a t e m e n t s f r o m the loop. T h e s e t r a n s f o r m a t i o n s a r e s i m i l a r to the t r a n s f o r m a t i o n s of linear p r o g r a m s with the exception of the following: that the s t a t e m e n t sj follows the s t a t e m e n t s i does not exclude the dependence of s i on sj. Let us now c o n s i d e r two c a s e s of r e m o v i n g s t a t e m e n t s f r o m loops. Suppose we have a loop LX(sl, s 2. . . . .
.... Sn) with O ( P ) = O ( L )
Sn5 whose s e t of input v a r i a b l e s is O(L). L e t P =st, L~ (s2,
and P' =L~(sl, s2,..., Sn_l), sn with O (P')= O (L).
Then L x (s,. . . . , sn) -~ P, if
a) R
(s~SNC (L) =
Z,
a') C (s,)~ R(L), b) 9 =~ x, w h e r e {Y} = C is,),
e) C(st)flO(L)=Z and L x (st, s2,..., sn) N p',
if
d) R(s2NC(L)= o ,
130
(1.4.1)
d'} C sn) s R ( L ) = ~ ,
(1.4.2)
e) C(s2AO(L)= ;g. T h e s t a t e m e n t s sl and s n do not s a t i s f y (1.4.1) e) and (1.4.2) e) r e s p e c t i v e l y , and t h e y cannot be r e m o v e d f r o m the loop s i n c e the r e s u l t depends on the execution o f the s t a t e m e n t z e r o o r m o r e t i m e s . The foilowLng two s t a t e m e n t s g e n e r a l i z e the r e m o v a l of a s t a t e m e n t f r o m the loop and so f a c i l i t a t e ~he p r e p a r a t i o n of loop p r o g r a m s f o r d e p a r a l l e H z a t i o n . T r a n s f o r m a t i o n 1.4.1.
E x t r a c t i o n o f a s t a t e m e n t f r o m a loop ( f o r w a r d ) . sX(sj, s2..... s.) ~sl,
L~(% . . . . . s~_,, s~+,. . . . . sn),
w h e r e s ~.= "if x > 0 then si, if (1.4.1) a), a'), and b) hold f o r s i, 1
T r a n s f o r m a t i o n 1.4.2.
E x t r a c t i o n of a s t a t e m e n t f r o m a loop (baekward)o LX(sp s2. . . . . sn) ~ L~(s 1, s2. . . . . si_i, s~+l. . . . . . . . s~), s~,
w h e r e s ~ = i f . x > 0 then si, if (1.4.2) e) and c') hold f o r si. T h e following t r a n s f o r m a t i o n s a r e d e s i g n e d to d e p a r a I l e l i z e s i m p l e loops. T r a n s f o r m a t i o n 1o4.3. Loop d e p a r a l l e l i z a t i o n L x (s,, s2. . . . . sn) ~ L~(s,, s 2. . . . . s,), L x (s~+, . . . . . Sn) , if
It is obvious that T r a n s f o r m a t i o n 1o4.3 can e a s i l y be g e n e r a l i z e d to the c a s e w h e r e t h e r e a r e m o r e p a r a l l e l loops. T r a n s f o r m a t i o n 1.4.4. D e p a r a l l e l i z a t i o n in a loop. LX(sv s2. . . . . s) -~LX(y~ (s,, s~. . . . . si) ..... Sj (s~/_z+l. . . . . sij), Sj el (sii+l . . . . . sii+ l) . . . . . Sk(si~_l+l . . . . . Sn)), if
15 xCc(sj)uc(sj+ ~) 25 c(sj)nV(sj+t)= 25, 35 c(sj+t)Nv(s j) = ~. T r a n s f o r m a t i o n 1.4.5. D e p a r a l l e l i z a t i o n by loops. :=
Xt
L x (sl, s2. . . . . s) ~ S (L i (sl . . . . .
X m
s.) . . . . . L m (s I . . . .
, snl),
ff
1) o(LX)= o (s) for an i and 1, Xj
3)
.
.
C ( L f i ) n R ( L j 3 ) = Q,
4) C(L J)nR(L[i)=e
(i,]=L2
. . . . . m; ie1
,
w h e r e x k a r e v a l u e s f o r the p a r a m e t e r x (k= 1, 2 . . . . .
m), 131
The loop d e p a r a l l e l i z a t i o n method is based on the T r a n s f o r m a t i o n 1o4.3; the method is based on a partition of the s u b s t a t e m e n t or set of s u b s t a t e m e n t s of the loop into s e v e r a l s u b s t a t e m e n t s o r s e t s of subs t a t e m e n t s , each of which is executed in the loop in p a r a l l e l with r e s p e c t to the o t h e r s . The n u m b e r of repetitions of t h e s e loop is the s a m e as for the original loop. T r a n s f o r m a t i o n 1.4.4 is the b a s i c method f o r d e p a r a l l e l i z a t i o n i n a loop. This method is b a s e d on distinguishing p a r a l l e l sections o r s t a t e m e n t s in the s u b s t a t e m e n t of the loop. We note that this method differs f r o m the l o o p - d e p a r a l l e l i z a t i o n method in that synchronization of the p a r a l l e l sections is n e c e s s a r y h e r e but not in loop deparallelization; this difference is due, in p a r t i c u l a r , to the fact that application of the method in the loop s u b s t a t e m e n t leaves no dependent s e c t i o n s . T r a n s f o r m a t i o n 1.4.5 implies that the method of d e p a r a l l e l i z a t i o n by loops [7] is based on t h e i n d e , pendence of subsequent repetitions of the loop f r o m the previous ones. When T r a n s f o r m a t i o n 1.4:3 is applied to the r e s u l t of T r a n s f o r m a t i o n 1.4.5,we can adapt the p a r a l l e l p r o g r a m to the actual s t r u c t u r e of the m u l t i p r o c e s s i n g computation s y s t e m , and T r a n s f o r m a t i o n 1.4.5 ( T r a n s f o r m a t i o n 1.4.6) allows us to d e p a r a t lelize the p a r t i a l l y dependent loops. We note that it is obvious that the t r a n s f o r m a t i o n of a sequential p r o g r a m to a p a r a l l e l one can be conveniently a c c o m p l i s h e d in the following o r d e r . 1. Apply L - t r a n s f o r m a t i o n s to the loop s u b s t a t e m e n t s , considering t h e m as l i n e a r sections of a p r o g r a m ; in c o m p l i c a t e d loops, s t a r t with the i n n e r m o s t loop. 2. Apply the t r a n s f o r m a t i o n s of T r a n s f o r m a t i o n 1.4 and of T r a n s f o r m a t i o n s 1.4.1 through 1~4.5 to the loop s u b s t a t e m e n t s ; for c o m p l i c a t e d loops, s t a r t with the i n n e r m o s t loop. 3. Apply the t r a n s f o r m a t i o n s of T r a n s f o r m a t i o n 1.4 and take each loop as a single statement; f o r c o m p l i c a t e d loops take the i n n e r m o s t as a single s t a t e m e n t . 4. Apply the T r a n s f o r m a t i o n s 1.2.1 through 1.2.4. 5. Apply the T r a n s f o r m a t i o n s 1.2.4 through 1.2.6 and the i n v e r s e s of the T r a n s f o r m a t i o n s 1.4:1 through 1.4.5. 1.5.
Feasibility
of P-Transformations
At the s t a r t of this a r t i c l e we specifically excluded t r a n s f e r s t a t e m e n t s . However, in many c a s e s they do not f o r m an obstacle to the d e p a r a l l e l i z a t i o n of the p r o g r a m , and they can even be r e m o v e d f r o m the p r o g r a m [8, 9]. An ALGOL p r o g r a m containing t r a n s f e r s t a t e m e n t s m a y be d e p a r a l l e l i z e d as follows, with the help of the t r a n s f o r m a t i o n s given above. 1. Inside a sequential section one m a y use any t r a n s f e r s t a t e m e n t which does not exit outside the limits of the section. 2. Inside a p a r a l l e l section one m a y use any t r a n s f e r s t a t e m e n t which does not exit outside the limits of the section and which does not lead to conflicts with the synchronization of the p a r a l l e l execution. When such a section is d e p a r a l l e l i z e d the t r a n s f e r s between p a r a l l e l s t a t e m e n t s a r e e x p r e s s e d by m e a n s of information exchanges between the p a r a l l e l b r a n c h e s . 3. A t r a n s f e r f r o m a loop to a p a r a l l e l section is p o s s i b l e only at the s t a r t of the section, while a t r a n s f e r to a sequential section is p o s s i b l e at the s t a r t of the section ff this section is a b l o c k , but at any p l a c e if it is not. If the loop is p a r a l l e l , then a t r a n s f e r f r o m it stops the p a r a l l e l execution. 4. A backward t r a n s f e r is always tied to the v e r i f i c a t i o n of s o m e condition and so f o r m s a loop. This loop can be c o n s i d e r e d as a loop with an e l e m e n t which counts ( while loop). M o r e o v e r , in s o m e c a s e s the loop f o r m e d by the t r a n s f e r s t a t e m e n t can be r e p l a c e d by a loop with an e l e m e n t which u s e s an a r i t h m e t i c p r o g r e s s i o n (step - - until loop) o r a t y p e o f a r i t h m e t i c a l e x p r e s s i o n . R e p l a c e m e n t of a loop f o r m e d by a t r a n s f e r s t a t e m e n t by an ALGOL-60 loop needs m o r e detailed investigation. 5. If the section is executed as a task, then t r a n s f e r out of this section is equivalent to completion of the t a s k . 6. R e p l a c e m e n t of t r a n s f e r s t a t e m e n t s in a p r o g r a m by other consiructions, e.g., calling p r o c e d u r e s , loops, etc., m u s t be c a r r i e d out conditionally, under the condition:
132
(~lO~,+~O~i+~O~= kn~l~ ' O~.+h~tO~,=,
//
n
}] ~. 0~ ---e, w h e r e gi' tj, r k, wu a r e t r a n s f e r , t r a n s m i s s i o n , reception, and synchronization s t a t e m e n t s ; n, m, l , v a r e the n u m b e r s of t h e s e s t a t e m e n t s in the p a r a l l e l p r o g r a m ; Og i, Otj, Ork, Owu a r e the r e s p e c tive weights of t h e s e s t a t e m e n t s in the u n i v e r s a l a l g o r i t h m i c c o m p l e x i t y units of [10]; in p a r t i c u l a r , O h is the weight of the c o n s t r u c t i o n which gives a c c e s s to the c o m m o n m e m o r y when the m u l t i p r o c e s s i n g c o m putation s y s t e m has a c o m m o n m e m o r y , and z is the n u m b e r of such constructions in the p r o g r a m ; Ois P is the weight of the s t a t e m e n t Sp which f o r m s p a r t of the construction which r e p l a c e s a t r a n s f e r s t a t e m e n t , and q is the n u m b e r of such s t a t e m e n t s ; and e is the d e p a r a l l e l i z a t i o n efficiency coefficient. 7. If in the conditional s t a t e m e n t if B1 then s l else if B2 then s2 else if B3 then s3; s4 any of the s t a t e m e n t s s l , s2, or s3 is a t r a n s f e r s t a t e m e n t , then it m u s t be one of the types t r e a t e d above. The s t a t e ment i t s e l f belongs e i t h e r to a sequentiai section o r to one of the b r a n c h e s of a p a r a l l e l section. D e p a r a l Ielization is c a r r i e d out as follows: each of the s t a t e m e n t s s l , s2, and s3 is d e p a r a l l e l i z e d and a d i s jtmctive p a r a l l e l section S (slt'\/s21Vs31, sI2Vs2~Vs3~..... sl .... S2m, S3m) is f o r m e d . V e r i f i c a t i o n of the c o n ditions is c a r r i e d out e i t h e r in each b r a n c h of the section o r in the chain to which S belongs and in which the disjunctive t e r m (of this branch) which c o r r e s p o n d s to this condition is executed. The b r a n c h e s m a y contain unequal n u m b e r s of disjunctive t e r m s . This is b e c a u s e the o r d e r of p a r a l l e l i s m of the s t a t e m e n t s s l , s2, and s3 may differ. Thus a f a i r l y wide set of ALGOL p r o g r a m s can be deparallelizedo It is also e s s e n t i a l that the p r o p o s e d t r a n s f o r m a t i o n s not only help us find the c o m p l e t e p a r a l l e l f o r m of a sequential A L G O L - p r o g r a m , i.e., they b r i n g out the n a t u r a l p a r a l l e l i s m of the p r o g r a m , but also help us to r a i s e the d e g r e e of p a r a l l e l i s m by d e p a r a l l e l i z i n g s o m e dependent sections or s t a t e m e n t s . T h e r e f o r e when the p r o p o s e d t r a n s f o r m a t i o n s are applied to a r a t h e r wide ( f r o m the p r a c t i c a l point of view) c l a s s of ALGOL p r o g r a m s one can obtain any p r o g r a m in the family of p r o g r a m s equivalent to the given sequential p r o g r a m . This m e a n s that it is p o s s i b l e to c o n s t r u c t a p r o g r a m which is o p t i m a l in s o m e a p r i o r i stated s e n s e despite the whole f a m i l y of p r o g r a m s equivalent to it. This m e a n s that it is p o s s i b l e to find a v a r i ant of the p a r a l l e l p r o g r a m which is equivalent to the given sequential p r o g r a m and which is optimal f o r the given m u l t i p r o c e s s i n g computation s y s t e m . G e n e r a l l y speaking, the p r o p o s e d t r a n s f o r m a t i o n s can also be applied to p r o g r a m s in o t h e r p r o g r a m ming languages to f o r m u l a t e t h e m in another, m o r e a c c e p t a b l e f o r m . One of the m o s t i m p o r t a n t p r o b l e m s in p r o g r a m m i n g t h e o r y is the d e v e l o p m e n t of the a l g e b r a of a l g o r i t h m i c languages, i.e., the techniques of equivalence t r a n s f o r m a t i o n s in t h e s e languages [11]. The d e v e l o p m e n t of a l g o r i t h m i c languages and the a l g e b r a s of t h e s e languages r e d u c e s to this: e x p r e s s i o n s in t h e s e languages a r e , f r o m the point of view of c u s t o m , clarity, and convenience, at the s a m e level as a n a l ytic e x p r e s s i o n s , which leads to an "equation in laws" of a l g o r i t h m i c methods and analytic ones, and to an invisible extension of the domain of application of the m a t h e m a t i c a l methods. Although the p r o p o s e d t r a n s f o r m a t i o n s a r e not a fundamental contribution they can be c o n s i d e r e d as a step towards the d e v e l o p m e n t of this area~
2.1. A Language for the D e s c r i p t i o n of P a r a l l e l P r o c e s s e s ~ In [3] an a l g o r i t h m i c language for d e s c r i b i n g p a r a l l e l p r o c e s s e s is p r o p o s e d (ALGOPP); this language is an extension o f A L G O L - 6 0 which has f e a t u r e s f o r the following p r o c e s s e s : p a r t s of the p r o g r a m which can be executed in p a r allel can be s e p a r a t e d out; s e v e r a l p a r a l l e l b r a n c h e s of the p r o g r a m can be f o r m e d into a single branch, or c o n v e r s e l y ;
133
TABLE 2.2.2 System staterrlerll:s
do together
STANDARDstatements
Remarks A I is the content o f the first address o f the c o m m a n d in the construction; A2 is the content of the second address of the command in construction; P = --t or 1 ; L2 is the address o f the central transmission for I2 = I.
STANDARD040~, A1, A2) STANDARD (~45,, P, L2)
join
STANDARD(~40~, AI, A2)
task
STANDARD(~44~, el~) STANDARD(~41~, T, K, E, 1)
S T A N D A R D (~42~, X, Y, A, AI, 42)
The number " 1 " is related to the peculiarities o f the translator, T = - 4 6 for the transmission branch, T = --47 for the reception branch, K is the number o f transmittable o f receivable codes, E is the transmittable or receivable mass, and ] = (i - 1) is index of the i4h element from which transmission or reception starts (i = 1, 2, 3, ...), X = 32 or 0 Y is the code for the command transmitted via the OBP*, A = 0 or - 0 , A1 and A2 are the first and second address o f the transmitted command.
transmit
STANDARD (~44~. ~I*) STANDARD (~41~, T, K, E, J)
T = - - 46
receive
STANDARD(r *1,) SIANDARD (g41~, T, K, E, J)
T
expect
S T A N D A R D (~44:P, ~1~)
synchronize
STANDARD(~44.. ~1,)
47
*The significance of this abbreviation is unknown to us - P u b l i s h e r s . p a r a l l e l b r a n c h e s of the p r o g r a m which a r e i n t e r r e l a t e d in s o m e f o r m o r other can be grouped together; i n f o r m a t i o n can be exchanged between branches; p a r a l l e l b r a n c h e s can be nested; execution of p a r a l l e l b r a n c h e s can be synchronized. The following s y s t e m s t a t e m e n t s a r e the m e a n s for r e a l i z i n g t h e s e p r o c e s s e s : 1) 2) ~union statement} :: = join
