A TRANSPUTER-BASED ARCHITECTURE TO EXPLOIT THE

RESTRICTED-AND- PARALLELISM OF PROLOG

Jose J. RUZ, Fernando SBenz, and Lourdes Araujo
Dept. Informatica y Automatica, Fac. Ciencias Fisicas,
Universidad Complutense, Madrid, Spain

ABSTRACT The RAP model is easier to implement than

Thia paper present8 8 ayatem for a general graph-based scheme such as
exploiting Roatricted-And- Parallelism Conery's E51 because CGEs have a linear
(RAP) in logic program on a diatributod form and the goals are collected into
(nonaharud memory) architecture. Tho groups for scheduling. Hennenegildo [31
syaterm uaea global collppilation tochni- has extended the WAM (Warren Abstract
que8 and it ia &aignod having tho n o w Machine) [21 to support RAP; this machine
generation of transputor8 (Rl/Cl04) in is known as PWAM. However, most of the
mind. & t e n l l y the ayat- behave8 88 8 current work attempts to exploit RAP
sequential ono, that ia, the solution. model at level of parallel processes
are alwaya produced according to the executing on shared-memory MIMD multi-
processor architectures. The number of
depth-firat atrategy. Pirat, we perfoan
processors in this approach is limited
a mode analyaia of the aource program in
by the bandwidth of the shared-memory.
order to determine which mode8 might
occur in each aubgoal, and then we create In this paper we describe an execution
a n e w veraion of the procedure for oach system for exploiting Restricted-And-
auch mode. Second, wo obtain the Condi- Parallelism on an distributed architec-
tional Graph Expreaaions (CGL) for each ture. The parallelism is exploited in an
clauao in the t r a n a f o d program uaing user transparent way, i.e. without ad-
the mode infoxmation. Third, tho CGEs aro ding new constructs to the standard
compiled to P u instructional an erten- language. The program goes through a
aion of the WAM propoaed by Hermenegildo . series of transformations before its
execution. First, a mode analysis of the
Finally, the Pwlw program ia oxecuted on
a transputer-basod architecture, that source program in order to determine
which modes might occur in each subgoal
is, a multiprocessor in which each is performed. Then a new version of the
processor is connected by means of procedure for each such mode is created.
point-to-point real o virtual links, and Second, the Prolog program is analyzed
where information exchange8 between in order to obtain the CGEs. We have
proceasora aro accampliahed only by developed this stage in the framework
mesaage paaaing. proposed by Jacobs 171 taking advantage
of mode information about the arguments
1 Introduction of the goals. Third, the CGEs are
DeGroot [l] has developed the compiled to PWAM code. The three previous
Restricted And-Parallelism (RAP) execu- stages have been implemented using BIM-
tion model for logic programming which Prolog. Finally, the PWAM code is loaded
combines compile-time analysis with run- into every processor of the network and
time checking. In this model programs the execution is started in the specific
must be first compiled into special processor holding the initial goal.
control expressions, called Conditional
Graph Expressions (CGEs), capable of 2 Compilation
expressing potential AND-parallelism. already mentioned, the compilation
As
The runtime overhead to detect variables of a Prolog program into PWAM code is
binding conflicts is greatly reduced by carried out in three steps: mode
only checking the conditions of a CGE.

CH29645/91/0000-1081$0100 01991 IEEE 1081

-~ - -~
-7r- 7
~~

7 7-- 7- ~ -~ ~~
analysis, CGE obtaining and code genera- Ir ( a m r r x a x i , U), ammi,...,m)
r.Im. ..,-I
tion. CONDITION is a conjunction of basic
tests about variables. Two kinds of basic
2.1 %oda Analysis tests are provided: Ixx is true if X and
For a given goal, the mode analysis Y are independent, and Gx is true if X
[ 8 ] will give information about which is ground. An IF expression executes El
arguments in the goal will be instan- or E2 depending on whether CONDITION is
tiated into ground tenns when the goal true or false; a SEQ expression executes
is executed for a specific query. We have ..
El, . ,En sequentially; a PAR expression
developed this analysis in the framework executes El, ...,En in parallel.
of abstract interpretation [ 9 1 on a We obtain the CGEs in the framework
domain with two elements: (+), which
proposed by Jacobs [ 7 ] , that is, trans-
stand for arguments which are known to forming a graph-based computational
be bound to ground terms, and ( - ) , which form, obtained directly from the clause
stand for arguments about which nothing and called Conditional Dependency Graph
is known. (CDG), by two rewrite rules (Split and
The program is transformed into If). Our approach uses mode informations
another program by determining, for each (call and success patterns) to create
goal in the program, which modes might the initial context, that is, the set of
occur in that goal, and then creating a facts known about basic tests in the DCG.
new version of the procedure for each Three strategies are possible in our
such mode. For example, the program: system in order to select the rule to be
:- &(t,i,-).
applied to the CDG:
P(X,Y,S) :- ..
.,q(xl,Yl,Il), ... , q ( l a , r z , 121,. .. (I)
q(X,r,w :- ... (2) a) Maximum Parallelism. This strategy
if the abstract interpretation infers apply the "If" rule to CDG edges until
the call patterns q(+,+,-) and q(-,-,+) the basic tests have been removed. Then
for the first and second occurrences uses the "Split" rule on each pair of
respectevily of the goal q/3 in the unconnected sub-CDGs, generating in this
clause (1), the one clause procedure (2) way PAR subexpressions. Finally, the
would be transformed into the following "Split" rule is again applied in order
two procedures: to remove the edges with false valued
:- rodr q-wd(t.i.-). basic conditions, appearing this time
:- wad8 e*(-,-.+). SEQ subexpressions.
qJgd(X.Y.1) :- ... Let us consider the following clause:
.+aq(X,Y,I) :- ... a(X.Y) :- p ( X ) . q ( L ) . r W ) . = ( 1 , a .
where we have distinguished the two with the call and success patterns:
versions of q/3 by adding a suffix to a(-,-) :- P ( - ) , q ( - ) , r ( - ) , B ( - , - ) .
their names which gives their respective The maximum parallelism strategy will
modes as a sequence of g (for ground) and obtain the following CGE:
d (for don't know). Each version will Iru
exhibit different conditions of paral- Ir o.
(P. q, r r s)
Q.I
lelism and will be transformed into
different CGEs. QAR (P. r. UP(q, =)I
I r 01
we will also consider the (i) mode for QY( U P (P, I), P m (9, s)1
arguments don't known but independent QAR (nQ(P. = I r U P h. a))
from other ones in the head of the clause. b) Minimum Basic-Tests. In this
The transmission of (i) mode is local strategy, while there are pairs of
into the clause. sub-CDGs with no edges between them, it
will be applied the "Split" rule to such
2 . 2 Conditional Graph Expressions (CGE) pairs in order to generate PAR expres-
Each clause in the new version of the sions. Then the "Split" rule will be
program is converted into its suitable applied to remaining pairs, producing in
CGE. The CGEs are capable of expressing this way SEQ expressions. The resultant
the And-parallelism of a clause on the CGE will express the strict parallelism
basis of tests about its variables. The of the clause and it will not contain any
CGEs are defined inductively as follow. condition. For the above clause with the
Every subgoal is a CGE; if El, .. . ,En are same patterns, it will be produced the
CGEs, the following are CGEs: following CGE:
Q.I ( U P (P, r), np (q, s))

1082
 c ) Hybrid S t r a t e g y . The t h i r d s t r a t e g y 3.1 Scbdulrr P r o e m .
c o n s i d e r s t h a t f i n f a c t , it i s f a s t e r One of t h e t r a n s p u t e r s u p p o r t s t h e
r e s o l v e ground tests t h a n independence Scheduler P r o c e s s (SP), whose aim i s
tests. Consequently, t h i s s t r a t e g y w i l l c o n t r o l t h e planning of t h e goals proved
g e n e r a t e CGEs with o n l y ground tests. T o t o be independent i n runtime. The SP has
do it, t h e " I f " r u l e w i l l be a p p l i e d t o a v a i l a b l e a l l information r e g a r d i n g i d l e
t h e edges with ground tests. The remain- t r a n s p u t e r s and pending g o a l s i n busy
i n g sub-CDGs w i l l be computed using t h e t r a n s p u t e r s . I n o r d e r t o decide where a
minimum b a s i c - t e s t s s t r a t e g y . I n t h i s
c a s e t h e CGE w i l l be:
mea
.Am (W g. e r .Am (q. *I)
.= (aq (P. e. ag (qt .I)
2.3 Code Generation
The CGEs a r e t r a n s l a t e d t o code of PWAM
(an e x t e n s i o n of t h e WAM t o a p a r a l l e l
environment proposed by Hermenegildo
[ 3 ] ) . The i n s t r u c t i o n s set of PWAM & ..........&
i n c l u d e s a l l W A M i n s t r u c t i o n s and
s e v e r a l new ones which are r e l a t e d t o FWl *.m*chl.oan

p a r a l l e l e x e c u t i o n : Check i n s t r u c t i o n s
pending g o a l i s executed, t h e SP must
(check-me-else, check-ground and check
f u l f i l l two c o n s t r a i n t s :
independent) used t o encode t h e
CONDITIONS i n a CGE; Goal scheduling 1. Planning f o r p a r a l l e l e x e c u t i o n t h e
i n s t r u c t i o n s (push-call and p o p g e n d - f i r s t g o a l of t h e t r a n s p u t e r with
ing-goal) used f o r pushing g o a l s with t h e g r e a t e s t number of pending g o a l s .
arguments o n t o t h e g o a l s t a c k ( a new d a t a 2. Do n o t a s s i g n a g o a l on a t r a n s p u t e r
a r e a ) and f o r p i c k i n g up t h e s e g o a l s i n which has a l r e a d y executed a preced-
t h e l o c a l p r o c e s s o r ; and Control i n - i n g g o a l with pending c h o i c e s . The
s t r u c t i o n s ( a l l o c a t e g c a l l , check-ready precedence Order is t h e usual i n
and wait-on-siblings) f o r t h e forking t h e s e a r c h tree of s t a n d a r d Prolog. This
and j o i n i n g i n p a r a l l e l c a l l s . c o n d i t i o n i s n e c e s s a r y t o p r e s e r v e space
r e t r i e v a l on backtracking. The b a s i c
3 System Architecture mechanism of SP p r o c e s s c a n b e
The p a r a l l e l e x e c u t i o n i s supported by d e s c r i b e d by t h e following OCCAM-like
a transputer-based a r c h i t e c t u r e ( f i g u r e program :
up
l ) , t h a t i s , a c o l l e c t i o n of t r a n s p u t e r s ?Am
with p o i n t - t o - p o i n t virtual or real prOaaul(. . .)
i n t e r c o n n e c t i o n , where t h e r e a r e not proau2( ...)
assumptions about t h e network topology,
because w e have had t h e new g e n e r a t i o n
of t r a n s p u t e r s (HI-C104) i n mind. The H 1
t r a n s p u t e r [4] s t i l l w i l l i n c o r p o r a t e
o n l y f o u r communications l i n k s , b u t it
w i l l s u p p o r t many v i r t u a l channels by
d i v i d i n g messages i n t o p a c k e t s and i n -
t e r l e a v i n g p a c k e t s from s e v e r a l messages
down a s i n g l e l i n k . To f u l l y e x p l o i t t h e
v i r t u a l - c h a n n e l concept it i s n e e d e d t h e
C104 r o u t i n g switch, a 32 x 32 c r o s s b a r
switch capable t o connect any of i t s
l i n k s t o any o t h e r l a s w e l l a s some l o g i c
f o r d e c i d i n g t h e i n t e n d e d d e s t i n a t i o n of
each r e c e i v e d message. Two p r o c e s s e s
anywhere i n a network can use a named
s o f t w a r e channel t o communicate, and t h e
hardware w i l l s o r t o u t t h e message
r o u t i n g . Consequently, programs can be
independent of t h e network topology.

1083
 ... goal is .rrDad of tb +mg 40.1 In this paper a system for exploiting
tal..
Restricted-And-Parallelism on a
TIDL
transputer-based architecture has been
m?
That is, after creating PWAM processes presented. The system supports compila-
tion of CGEs and uses mode inference to
.
(processl, . . ) , the SP manage the mes-
generate these CGEs. The network ar-
sage traffic from/to the transputers in chitecture of the system is easily
order to get information about pending expandable to any scale so avoiding the
goals and schedule them onto idle limitation in the number of processors
transputers.
in shared-memory models. However, the
3.2 P W Processes communication overhead caused by shared
structures of Prolog can reduce the
The remaining transputers in the sys- performance if the system does not
tem supports PWAM processes. A PWAM considers program granularity. The
process consists of a simulator of data authors are investigating this topic
structures and instruction set of the using abstract interpretation andmaking
PWAM (PWAM SIMULATION), and a message heuristic measures.
service module (PWAM MESSAGES). A OCCAM-
like program for this process could be
the following: 5 References
spoc pa.&(...) [l] DeGroot, D., "Restricted and-
?AR parallelism", Proc. Int. Conf. Fifth
-- .1w S P Q I L U X W Gen. Comp. Sys., ICOT, (1984), 471-478.
WE
XU tpm
[ 2 ] Warren, D.H.D., "An Abstract
Ir
Prolog Instruction Set", Tech. Note
mo? lmit1-a
... tb. follouirq .IPYiastrrr&ion i n u-
309, SRI International, (1983).
atad [31 Hermenegildo,M., "An Abstract
I? Machine Based Execution Model for
p.ndi-a3O=l Computer Architecture Design and
... 8 --MAL mu+ i. .at t o tb. Efficient Implementation of Logic
Mh0dUl.r
.MO.. Am -I god
Programs in Parallel". PhD thesis, U. of
... S W C U U u s u g . i. -rat Texas at Austin (1986).
fAi1 M -1 (41 Pountain, D. "Virtual Channels:
... TAIL u u q a is sat The Next Generation of Transputers" BYTE
T" April 1990, pp. ECW 3-12.
SKI?
-- S l W ~ S A U S
[SI Conery,J., "Parallel Execution of
IWU T P m
Logic Programs", Kluwer Academic
Publisher, (1987).
mm
... muugm i n nitd [ 6 1 Chang,J.-H., Despain,A., and De-
Groot ,D.,
xr
uag.-tgp. UWuT -
... HIIt tb firmt pndha -1
programs based on
"AND-parallelism of logic
a static depend-
ency analysis", Proc. Spring
unug.-typ .OCCU. -
... r u d fh. i&.ntiatioM of tho war&-
pcon, IEEE, (1985), 218-225.
com-

a.
.
DUuo.-tYp. OQLt - [7] Jacob,D. and Langen,A. "Compila-
tion of Logic
... god infoxmation is pat In tho SYlLy Restricted
Programs for

y...g.-tYp. 1111.
... fa11 1s h8ndl.d
- 284-297.
And-Parallelism",
European Symposium on Programing (1988)

Rm
[ E ] Debray, SK. and Warren, D . S . ,
SKI? "Automatic mode inferencing of Prolog
PWAM instructions are executed until programs" Proc. 1986 Logic Programing
the goal is solved. If the goal was remote Symposium, pp. 78-86.
the result is returned to father process. [9] Bruynooghe, M. , Janssens,G., Cal-
If there are not pending goals a request lebant,A . and Demoen, B. "Abstract In-
is sent to SP. terpretation: towards the global
optimization of Prolog program", Proc.
4 Conclusions Logic Programming Symposium, pp. 192-
204.

1084

I I I 1
I I ii I r -