High-Le el
Cons uc o s o
Solu ion Sea ching in
O -Pa allel P olog
Sys ems
João And é Ma ins da Sil a
Mes ado In eg ado em Engenha ia de Redes e Sis emas In o má icos
Depa amen o de Ciência de Compu ado es
2014
O ien ado
Rica do Jo ge Gomes Lopes da Rocha, P o esso Auxilia , Faculdade de Ciências
insi a uma igu a alusi a ao ema
Todas as co eções de e minadas
pelo jú i, e só essas, o am e e uadas.
O P esiden e do Jú i,
Po o, ______/______/_________
Jo˜ao And ´e Ma ins da Sil a
High-Le el Cons uc o s o
Solu ion Sea ching in O -Pa allel
P olog Sys ems
Tese subme ida `a Faculdade de Ciˆencias da
Uni e sidade do Po o pa a ob en¸c˜ao do g au de Mes e
em Engenha ia de Redes e Sis emas In o m´a icos
Ad iso : P o . Rica do Jo ge Gomes Lopes da Rocha
Depa amen o de Ciˆencia de Compu ado es
Faculdade de Ciˆencias
Se emb o de 2014

2
Dedicado aos meus pais e i m˜a.
3
4
Abs ac 0
This aim o his wo k is o design and implemen s a egies ha can imp o e he
pe o mance o logic p og ams when sea ching o pa icula solu ions in an O -Pa allel
P olog sys em. P olog is a i s -o de logic p edica e language ha belongs o he
decla a i e amily o p og amming languages, emphasizing da a decla a ion and use.
O -Pa allelism is a o m o implici pa allelism ha can be applied o P olog p og ams,
in o de o allow he pa allel execu ion o se e al clauses ha ma ch a P olog goal.
Wi h he a ailabili y o speci ic s a egies ha can imp o e he sys em’s pe o mance
when sea ching o solu ions in pa allel, we expec o: (i) allow o long- unning
p og ams, such as hose used o simula ions, o ake less ime o execu e; (ii) make i
possible o execu e new p og ams ha deal wi h la ge amoun s o da a, ha would
o he wise be oo slow o un; (iii) gene a e mo e in e es in P olog, which migh lead
o u he esea ch. In pa icula , ou implemen a ion was done on op o he YAP
P olog sys em, a well-known and es ablished sys em which makes i possible o use s
o ge all o hese bene i s.
The s a egies p oposed in his wo k ha e a e y impo an concep a he co e: make
ela i ely small changes o he YAP’s engine codebase in o de o allow hem o be
easily po ed o o he implemen a ions o P olog, and make hem a ailable o he use ,
by using high-le el cons uc o s ha anspa en ly inc ease he speedups ob ained
wi hou o cing he use o make complex sou ce code changes.
5
3 Implemen a ion o Cons uc o s 33
3.1 Me hodology ................................ 33
3.2 Solu ionSea ching ............................. 36
3.2.1 S a egy W - Wai Be o e S a ing . . . . . . . . . . . . . . . . 38
3.2.2 S a egy B - Ge Wo k Below Be o e Taking he Nex Al e na i e 39
3.2.3 S a egy L1 - Ge Wo k o he Le Be o e Taking he Nex
Al e na i e ............................. 40
3.2.4 S a egy L2 - Ge Wo k o he Le , wi h Fallback . . . . . . . . 42
3.2.5 S a egy L3 - Ge Wo k o he Le , in So ed O de . . . . . . 43
3.2.6 S a egy F1 - Descend he T ee, S a Sha ing A e Failing he
Fi s Time.............................. 43
3.2.7 S a egy F2 - Descend he T ee, Sha e Less A e Failing he
Fi s Time.............................. 45
3.2.8 S a egy S - F eeze he O -F ames, Allowing Volun a y Suspension 46
3.2.9 Summa y .............................. 47
4 Expe imen al Resul s 49
5 Conclusions and Fu u e Wo k 55
5.1 MainCon ibu ions............................. 55
5.2 Fu he Wo k ................................ 55
Re e ences 57
A Benchma king Code 59
12

Lis o Tables 0
4.1 Execu ion imes and speedups ob ained wi h 4 wo ke s and p oblem size
30, o alls a egies. .............................. 50
4.2 Execu ion imes and speedups ob ained wi h 8 wo ke s and p oblem size 34. 51
4.3 Execu ion imes and speedups ob ained wi h 12 wo ke s and p oblem size
38......................................... 51
4.4 Execu ion imes and speedups ob ained wi h 16 wo ke s and p oblem size
42......................................... 52
4.5 Execu ion imes and speedups ob ained wi h 20 wo ke s and p oblem size
45......................................... 53
4.6 Execu ion imes and speedups ob ained wi h 24 wo ke s and p oblem size
49......................................... 53
13
14
Lis o Figu es 0
2.1 A P olog example whe e se e al colo - ela ed p edica es a e de ined. . . . . 25
2.2 Implici sea ch ee gene a ed o he que y ?- colo (C). ......... 26
2.3 YAP’s memo y a ea layou . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 The ela ionship be ween choice poin s and O -F ames (cou esy o Rica do
Rocha, om[Roc01]). ............................. 31
3.1 A benchma k ha akes exponen ial ime o ind a lis . . . . . . . . . . . . 34
3.2 A p edica e ha gene a es an unbalanced sea ch ee. . . . . . . . . . . . . 35
3.3 Sea ch ee o a call o ind/2 when gi en a lis o leng h 2. . . . . . . . . 36
3.4 A clause used o gene a e lis s ha p oduce pa hological beha iou . . . . . 36
3.5 YapO sea ch ee a e wo ke 0 sha es wo k wi h wo ke 1. . . . . . . . . 37
3.6 Expec ed YapO wo ke dis ibu ion, using 4 wo ke s. . . . . . . . . . . . . 37
3.7 Expec ed wo ke dis ibu ion wi h s a egy W, using 4 wo ke s. . . . . . . 39
3.8 In e media e wo ke dis ibu ion wi h s a egy B, using 4 wo ke s. . . . . . 40
3.9 Expec ed wo ke dis ibu ion wi h s a egy B, using 4 wo ke s. . . . . . . . 40
3.10 Expec ed wo ke dis ibu ion wi h s a egies L1 o L3, using 4 wo ke s. . . 41
3.11 Wo ke 0, immedia ely be o e ailing..................... 44
3.12 Expec ed wo ke dis ibu ion wi h s a egy F1, using 4 wo ke s. . . . . . . 44
3.13 Expec ed wo ke dis ibu ion wi h s a egy F2, using 4 wo ke s. . . . . . . 45
3.14 Expec ed wo ke dis ibu ion wi h s a egy S, using 4 wo ke s, be o e sus-
pendingwo k................................... 46
3.15 Expec ed wo ke dis ibu ion wi h s a egy S, using 4 wo ke s, a e sus-
pendingwo k................................... 47
4.1 Rela i e speedups ob ained wi h 4 wo ke s. . . . . . . . . . . . . . . . . . . 50
4.2 Rela i e speedups ob ained wi h 8 wo ke s. . . . . . . . . . . . . . . . . . . 51
4.3 Rela i e speedups ob ained wi h 12 wo ke s. . . . . . . . . . . . . . . . . . 52
4.4 Rela i e speedups ob ained wi h 16 wo ke s. . . . . . . . . . . . . . . . . . 52
4.5 Rela i e speedups ob ained wi h 20 wo ke s. . . . . . . . . . . . . . . . . . 53
15
4.6 Rela i e speedups ob ained wi h 24 wo ke s. . . . . . . . . . . . . . . . . . 54
A.1 A es designed o s ess he pa allel ind i s /3 implemen a ion. . . . 59
A.2 Calcula es he speedup o he pa allel execu ion o A.1. . . . . . . . . . . . 60
A.3 A w appe ha calls A.2 o each p oblem size passed as an a gumen . . . 60
16
Lis o Ac onyms 0
CLP Cons ain Logic P og amming.
DCG De ini e Clause G amma .
LP Logic P og amming.
SLD esolu ion Selec i e Linea De ini e clause esolu ion.
WAM Wa en’s Abs ac Machine.
YAP YAP P olog sys em.
17

18
In oduc ion 1
Nowadays, immense amoun s o da a a e gene a ed e e y day. E en hough humans
ha e he abili y o de ec pa e ns, we a e unable o keep up wi h his inc ease o
in o ma ion. We did, howe e , c ea e machines ha a e able o p ocess his da a and
gi e us he big pic u e in a way ha is simple o unde s and. The p oblem is ha
only a ew people ha e he knowledge needed o con ol i s execu ion and de elop new
p og ams e en i hey only pe o m sligh ly di e en asks on iny a ia ions o he
same p oblems.
One ool ha makes his p ocess easie is Logic P og amming (LP). LP belongs o he
class o decla a i e p og amming languages, which means ha p og amme s expose
he p oblem hey a e ying o sol e in a s aigh o wa d manne wi h he added bene i
ha he esul s hey ge back also use he same language. A guably, an impo an
language ha belongs o his class is P olog. This language p esen s ea u es ha make
complex asks such as machine lea ning and language p ocessing easy o p og am due
o i s high-le el decla a i e s yle.
Use s do no simply wan an exp essi e language, hough. They also wan o be able
o pe o m hei asks in a manne ha is as as as possible. Fo a ew yea s now,
being as implies he use o he mul ip ocessing ea u es o mode n CPUs. Explici
pa allelism is, howe e , a oad ha is ull o challenges ha p og amme s used o
w i ing sequen ial p og ams do no wan o hink abou . Once again, P olog simpli ies
he ask o he p og amme : due o i s non-de e minism, asks can be un in a
pa ially a bi a y o de ha can be implici ly pa allelized by he un ime sys em,
wi hou al e ing hei seman ics.
Ano he impo an ad an age o using P olog when compa ed o o he languages is
ha , ha ing deep oo s in ma hema ical concep s, i is possible o p o e he co ec ness
o he p og ams w i en in i .
19
CHAPTER 1. INTRODUCTION 20
1.1 Mo i a ion
Th oughou he las decade mul ico e compu e s became s anda d, wi h hei inclusion
in x86, he mos widely used PC a chi ec u e. Fo his eason, powe ul mul ico e
machines a e widely a ailable and a e becoming inc easingly a o dable. Resea che s
and scien is s make use o hese machines o s udies, expe imen s and de eloping
models in ields ha can go om physics o medicine.
Taking in o accoun he p e iously men ioned ea u es o P olog and he a ailabili y
o powe ul mul ico e compu e s, i was na u al o esea che s o make use o a
combina ion o P olog and mul ico e compu e s. In applica ions wi h e y la ge da a
se s, such as hose ha o en a ise in he p e iously men ioned ields, any dec ease in
he execu ion imes can no only sa e use s ime bu also allow hem o sol e bigge
p oblems.
This hesis’ objec i e is o imp o e pe o mance o he YapO O -Pa allel Engine,
namely by inc easing he speedups o pa allel cons uc o s ha ind speci ic solu ions
o a que y. Ou con ibu ion is a se o s a egies designed o educe he ime
and esou ces used o sol e p oblems in pa allel P olog and hei implemen a ion
in he YAP P olog sys em [CRD12], a s a e-o - he-a implemen a ion o P olog,
including se e al ex ensions and de eloped a he Uni e si y o Po o. We explain
he a ionale o he changes and how hey al e he o e all execu ion o a P olog
p og am, p esen ing he modules whe e hese changes ake place. These s a egies a e
pa icula ly use ul o long- unning p og ams whe e a educ ion o a ew pe cen o
he o e all ime may ansla e in o minu es, hou s o e en days. The implemen a ion
o each o hese s a egies changes a ela i ely small po ion o he sou ce code, on
pu pose, in o de o make hem easy o unde s and and be e-implemen ed in o he
sys ems and also o simpli y he p ocess o combining se e al o hem oge he .
We hope ha his wo k makes LP a mo e iable and a ac i e al e na i e o o he
languages o he p ocessing o asks whe e la ge amoun s o da a mus be p ocessed.
1.2 Thesis Ou line
This documen is s uc u ed in 6 chap e s and a b ie desc ip ion o each is p o ided
nex .
•Chap e 1: In oduc ion. The cu en chap e .
21 1.2. THESIS OUTLINE
•Chap e 2: Backg ound. This chap e p esen s ele an backg ound in o -
ma ion on logic p og amming and he P olog language. Ini ially, we p o ide a
compa ison o LP wi h o he p og amming pa adigms and in oduce he eade
o he P olog p og amming language. The nex sec ions a e dedica ed o he
Wa en’s Abs ac Machine (WAM), a i ual machine used by se e al mode n
P olog implemen a ions, and o he YAAM, YAP’s e sion o he WAM. Finally,
we p esen he YapO O -Pa allel Engine.
•Chap e 3: The Implemen a ion o O -Pa allel Solu ion Sea ching
Cons uc o s. This chap e desc ibes he me hods we used o op imize he
YapO O -Pa allel Engine and desc ibes he se e al s a egies ha we ha e
implemen ed o imp o e he pe o mance o YapO .
•Chap e 4: Expe imen al Resul s. This chap e p esen s measu emen s
made o assess he sys em’s pe o mance and discusses he esul s ob ained.
•Chap e 5: Conclusions and Fu u e Wo k. This chap e concludes he
hesis and p esen s sugges ions o u he wo k.
•Annex A: Benchma king Code. Con ains he code used o benchma king.
CHAPTER 2. BACKGROUND 28
•E, a poin e o he cu en en i onmen ;
•B, a poin e o he mos ecen choice poin ;
•A1, ..., An, he a gumen egis e s;
•X1, ..., Xn, he empo a y a iable egis e s.
2.3.3 Ins uc ions
The WAM de ines an ins uc ions se ha can be di ided in o ou g oups:
•Choice poin ins uc ions which alloca e and dealloca e memo y o choice
poin s, making back acking possible;
•Con ol ins uc ions ha a e esponsible o managing he calls o subgoals
in p edica es and manage he en i onmen s;
•Indexing ins uc ions ha , based on he ype and alue o he i s a gumen
o a call, jump o specialized code o ha call.
•Uni ica ion ins uc ions which pe o m he ma ching and uni ica ion o a i-
ables and o he ypes.
The ins uc ions ha deal wi h P olog da a s uc u es ope a e using he no ion o
modes, o which he e a e wo:
•W i e mode, he mode whe e da a s uc u es ep esen ing P olog e ms a e
c ea ed;
•Read mode, whe e hese da a s uc u es a e ma ched.
2.4 YAAM
The YAAM is YAP’s op imized e sion o he WAM. I is based on many o he same
ideas o WAM’s design, bu makes a conside able numbe o changes, mainly o he
memo y layou o he WAM.
One o he key insigh s made by he YAP de elope s is ha memo y alloca ed on he
heap is long-li ed, which means ha a compac ep esen a ion o e ms is ideal. As
such, he YAAM uses ag bi s o ep esen he i e main ypes o da a p esen ed in

29 2.4. YAAM
[AK91]: in ege s, a oms, applica ions, pai s and e e ences. I addi ionally suppo s
one mo e ype in oduced by YAP: ex ensions, which allow he use o addi ional da a
ypes no p esen in s ic ly-s anda d P olog implemen a ions. Examples o addi ional
da a ypes cu en ly a ailable in YAP a e mul iple-p ecison in ege s and a ays o loa s
and in ege s.
The WAM does no speci y he layou o he memo y a eas. A nai e, bu ob ious, way
would be o alloca e memo y o each a ea independen ly o he o he s, dynamically
adjus ing each one as needed. The YAAM, lea es he code a ea independen bu
comp esses he o he memo y a eas in o he ollowing scheme:
Heap PDLT ail
S ack
Code
Figu e 2.3: YAP’s memo y a ea layou .
This scheme p esen s a some ad an ages:
•Alloca ion o a single la ge memo y a ea, which is as e han he alloca ion o
se e al small memo y a eas;
•The layou allows alloca ion ope a ions o be poin e mo emen s, a he han
ealloca ing and copying memo y as in he nai e way;
•De ec ing o e low o he memo y a eas can be done by a simple poin e com-
pa ison.
A p oblem wi h his scheme is ha , when he memo y needs o be expanded, all o
he memo y a eas mus be copied a he han jus he a ea ha needs mo e memo y.
2.4.1 Jus -in-Time Indexing
T adi ionally, P olog implemen a ions ha make use o he WAM index e ms by he
i s a gumen , making uni ica ion as e by only ying al e na i es whe e he ype o
CHAPTER 2. BACKGROUND 30
he i s a gumen o he que y is compa ible wi h he i s a gumen o he ma ching
p edica e.
Fo e y la ge da ase s, he de elope s o YAP es ed he di e ence in pe o mance
caused by eo de ing he a gumen s and eached he conclusion ha i could change
pe o mance signi ican ly [CRD12].
The solu ion de eloped was a dynamic indexing mechanism, called jus -in- ime index-
ing (o JITI). This mechanism adds an ins uc ion o he WAM, index p ed, ha
pe o ms he ask o indexing he p edica e. Al hough his mechanism may gene a e
a la ge amoun o indexing code, i gene ally does no do so [CRD12].
2.5 The YapO O -Pa allel Engine
Wi h he ad en o mul ico e compu e s, p og ams need o be able o di ide asks in o
smalle sub asks ha a e execu ed by each co e, in pa allel.
The e a e wo main ways in which one can pa allelize he execu ion o a P olog p og am
implici ly. These a e known as And-Pa allelism, whe e se e al subgoals in a clause a e
execu ed simul aneously and he ailu e o any o hem esul s in ailu e o he goal,
and O -Pa allelism, whe e se e al clauses ha ma ch a goal un in pa allel in o de
o ind mul iple solu ions as e .
YapO is an ex ension o he YAP sys em ha enables i o make use o he mul iple
co es ha a e a ailable on cu en CPUs. As he name sugges s, i exploi s he O -
Pa allelism inhe en o P olog p og ams o make solu ion disco e y as e .
Simila ly o he Muse sys em [AK90], he YapO sys em uses en i onmen copying,
whe e a wo ke ha makes a wo k eques copies he en i onmen o he wo ke ha
accep s ha eques . This is done inc emen ally, ha is, he ecei e posi ions i sel
abo e he sende and only copies he po ion o memo y ha is di e en om i s own.
Unlike s anda d Yap, YapO disallows esizing o he memo y a eas, which may be a
p oblem o long- unning applica ions ha use la ge amoun s o memo y. To alle ia e
his p oblem, he use can change he size o he a eas a compile and/o s a up- ime.
Since YapO deals wi h O -Pa allelism, i needs o ack which al e na i es o a choice
poin we e gi en o each wo ke . To do so, each YapO wo ke main ains a linked lis
o O -F ames o s o e ha in o ma ion.
31 2.5. THE YAPOR OR-PARALLEL ENGINE
Sha ing
TR
H
B
CP
ENV
LUB
P & Q
ge wo k
O F _membe s
O F _node
O F _nea es _li enode
O F _nex
ALT O F _al
Unlocked O F _lock
Choice Poin
O -F ame
CP_TR
CP_H
CP_B
CP_CP
CP_ALT
CP_ENV
CP_OR_FR
CP_LUB
TR
H
B
CP
ALT
ENV
---
LUB
Choice Poin
Figu e 2.4: The ela ionship be ween choice poin s and O -F ames (cou esy o Rica do
Rocha, om [Roc01]).
As shown in Figu e 2.4, choice poin s a e coupled wi h O -F ames; choice poin s s o e
in o ma ion ela i e o he di e en al e na i es ha may be aken, mainly in he
CP ALT,CP CP,CP TR,CP H,CP B and CP ENV, while O -F ames main ain in o ma ion
abou he di e en wo ke s ha may sea ch o solu ions wi hin hei associa ed choice
poin , media ing access o he choice poin wi h he O F lock ield and main aining
a bi map o wo ke s, O F membe s. In his manne , he con ol o he choice o he
nex al e na i e o explo e is mo ed om he choice poin , which is p i a e, o he
sha ed O -F ames. O -F ames a e only alloca ed when a wo ke sha es a choice poin
o which he O -F ame hen becomes associa ed. P i a e choice poin s do no ha e
associa ed O -F ames since he e is no need o keep in o ma ion abou o he wo ke s.
An addi ional change made by YapO o he YAP sys em is he in oduc ion o a
new WAM ins uc ion called ge wo k ha implemen s he scheduling s a egy and
is ul ima ely esponsible o he wo k sha ing p ocess [Roc96]. The s a egy can be
summa ized as ollows:
•Ask o wo k o he wo ke ha simul aneously has he highes load and is
nea es .
•When a wo ke sha es wo k, sha e all i s p i a e nodes.
•When unable o ge wo k, back ack o a poin whe e i is able o.
CHAPTER 2. BACKGROUND 32
Mo e p ecisely, when a wo ke back acks o a sha ed choice poin , i i s ies o ge
he nex a ailable al e na i e. Failing ha , i.e. i he e is no wo k le in he sha ed
choice poin , a wo ke will mo e up in he ee un il he e a e o he wo ke s below i
in o de o ask hem o wo k. I , a e his p ocess, no wo k has been sha ed, he
wo ke mo es up o a be e posi ion o be able o ge wo k. The execu ion ends i all
wo ke s each he op oo choice poin and a e unable o ge wo k om each o he .
Implemen a ion o Cons uc o s 3
In his chap e , we p esen he di e en s a egies we es ed o imp o e he execu ion o
O -Pa allel compu a ions in YapO . We i s ly p esen he me hod used o de e mine
wha po ions o YapO would bene i he mos om op imiza ion. Then, we explain
he changes made and he easoning behind each.
3.1 Me hodology
YapO enables a P olog p og amme o use O -Pa allelism wi hin an applica ion in
wo main ways:
•pa allel indall/3, which uns a que y in pa allel, e ie ing a lis o all
solu ions o ha que y
•pa allel ind i s /3, which execu es a que y and s ops a e inding he i s ,
le mos solu ion o ha que y.
Ou goal is o inc ease he speedups we ob ain using hese pa allel p imi i es, ela i e
o he cu en e sion o YapO . In o de o do ha , we mus i s be able o de e mine
whe e he po en ial o imp o emen is. Wi h ha in mind, we c ea ed a simple
syn he ic benchma k o es YapO ’s pa allel indall/3.
The benchma k, p esen ed in Figu e 3.1, ecei es a lis o 0s and 1s as inpu ( i s
a gumen o ind/4), and c ea es all possible lis s o 0s and 1s wi h size smalle o
equal o ha o he inpu lis un il i ec ea es ha lis (second a gumen o ind/4).
This gene a es a balanced sea ch ee, and akes an exponen ially inc easing amoun
o ime as he size o he lis inc eases. The choice o a benchma k ha akes an
exponen ial amoun o ime was made in o de o be able o e y easily es di e en
ime scales, om milliseconds o se e al seconds.
33

CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 34
1append([], X,X).
2append([X|Y], Z, [X|W]) :- append(Y,Z,W).
3
4op ions(0).
5op ions(1).
6
7 ind(In,Ou ):-leng h(In,Len), ind(In, [], Len,Ou ).
8
9 ind(ToFind,SoFa ,Le , [I em|End]) :-
10 Le >0,op ions(I em), append(SoFa , [I em], Nex ),
11 Nex Le is Le -1, ind(ToFind,Nex ,Nex Le ,End).
12 ind(ToFind,ToFind,_, []).
13
14 % A couple o lis examples
15 lis s(Lis ,Len):-mkLis (Len,0,Lis ).
16 lis s([0,0,0|End], Len):-mkLis (Len -3,1,End).
17
18 mkLis (0,_, []) :- !.
19 mkLis (Len,Num, [Num|End]) :- Le is Len -1,mkLis (Le ,Num,End).
20
21 go(Len) :-
22 lis s(Lis ,Len),
23 ime(pa allel_ indall(Va , ind(Lis ,Va ), Solu ions)),
24 ail.
Figu e 3.1: A benchma k ha akes exponen ial ime o ind a lis .
The esul s ob ained wi h ou expe imen s o his benchma k showed ha , on he
24-co e machine we used o hem, YapO wi h 24 wo ke s is able o achie e close o
linea speedups, o app oxima ely 21. These esul s show ha he implemen a ion is
al eady e y op imized and ha in o de o ge be e pe o mance we migh need a
comple ely di e en algo i hm. We he e o e mo ed ou e o s o he implemen a ion
o he pa allel ind i s /3 cons uc o .
By making a small change o his benchma k, consis ing o changing he use o
pa allel indall/3 o pa allel ind i s /3, we es ed he implemen a ion o he
pa allel ind i s /3 cons uc o . Fo an e icien implemen a ion o his p edica e,
we expec ha he execu ion akes an inc easing amoun o ime as he posi ion o he
i s solu ion mo es o he igh in he sea ch ee. This ime should also be p opo -
ional o he numbe o nodes o he sea ch ee ha we mus a e se un il ind he
solu ion. Ou expe imen s o his benchma k, which we pe o med wi h a ying num-
be s o wo ke s, showed ha he exis ing implemen a ion o pa allel ind i s /3
eaches he esul in a as manne - ha is, i is as e han pa allel indall/3
35 3.1. METHODOLOGY
and he execu ion ime does depend on he numbe o nodes a e sed. The ime ha
pa allel ind i s /3 ook o ind a solu ion a he igh mos pa h o he ee was
also simila o ha o pa allel indall/3, as expec ed.
We hus u ned ou a en ion o di e en cases o execu ion. Because o he SLD eso-
lu ion, he ee sea ch is pe o med om le o igh . Addi ionally, as pa allel ind i s /3
s ops a e inding he i s ma ch, a P olog p og amme ha is in e es ed in imp o ing
he pe o mance o a p og am ha makes use o pa allel ind i s /3 will y o
make su e ha whene e a p edica e is execu ed, i s i s al e na i e is he leas
esou ce-in ensi e, hen he second and so on, gene a ing a skewe ed ee ha is hea ie
on he igh . This p oblem has been subjec o esea ch and he e a e algo i hms ha
ha e good pe o mance in his case, such as [MLAP11] and [PA10] bu , because hey
use wo k s ealing a he han wo k sha ing and we wan o make ew changes o YAP,
we didn’ explo e hese op ions. To simula e his use case, we changed he benchma k
p esen ed abo e in a way ha gene a es a ee whe e i s igh hal side is wice as deep
as he le hal , hus we ha e an unbalanced ee o sea ch. This is done by adding
he ollowing p edica e o he benchma k and changing ind/2 as shown nex :
1 ind(In,Ou ):-leng h(In,Len), unbalancedFind(In, [], Len,Ou ).
2
3unbalancedFind(ToFind, [], Le ,End) :-
4op ions(Fi s ), Nex Le is Le *(1+Fi s )-1,
5 ind(ToFind, [Fi s ], Nex Le ,End).
Figu e 3.2: A p edica e ha gene a es an unbalanced sea ch ee.
Due o he exponen ial g ow h o his algo i hm, he di e ence in size be ween he le
and igh hal sides o he ee inc eases quickly, wi h he igh side ha ing he as
majo i y o he sea ch space. This can be easily obse ed e en wi h a small example
such as he one p esen ed in Figu e 3.3.
We hen pe o med some es s wi h his p og am using YapO . Once again, sea ching
he le mos pa h o he ee, whe e he lis s a e composed o ze os only, can no
ob ain any speedup due o he seman ics o P olog, ha equi e mo ing le - o- igh ,
op- o-bo om. Que ies wi h a solu ion on he la ge, igh side o he ee ob ained
easonable speedups, conside ing he la ge numbe o nodes ha mus be sea ched.
Que ies on he le side o he ee, howe e , had small speedups. In pa icula ,
CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 36
[]
[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1][1, 1, 1, 0]
[1, 1, 0]
[1, 1, 0, 1][1, 1, 0, 0]
[1, 0]
[1, 0, 1]
[1, 0, 1, 1][1, 0, 1, 0]
[1, 0, 0]
[1, 0, 0, 1][1, 0, 0, 0]
[0]
[0, 1][0, 0]
Figu e 3.3: Sea ch ee o a call o ind/2 when gi en a lis o leng h 2.
gi en a lis composed o as many ze os as he numbe o YapO wo ke s, ollowed by
ones, p oduces pa hological beha io , in ha YapO achie es speedups ha a e much
smalle han expec ed. Fo hese cases, he speedup eached a maximum o 2 as we
inc eased he numbe o wo ke s up o he numbe o co es o he machine, which is
24 in his case.
In o de o make hese cases easie o ep oduce, we add a new clause o he lis s/1
p edica e ha gene a es lis s ha , gi en he numbe o wo ke s and he size o he
lis , p oduce he pa hological beha io ha we expec :
1lis s(Pa hological,FullLen,Cpus) :-
2Len is FullLen -Cpus,mkLis (Cpus,0,Le ),
3mkLis (Size,1,Righ ), append(Le ,Righ ,Pa hological).
Figu e 3.4: A clause used o gene a e lis s ha p oduce pa hological beha iou .
3.2 Solu ion Sea ching
In o de o imp o e he pe o mance o que ies ha p oduce he pa hological beha io
we ha e p esen ed, we mus i s be able o unde s and why his beha io occu s. When
YapO execu es a p og am in pa allel, each wo ke ge s a wo k slice. The heu is ics
used by YapO y o di ide he a ailable wo k in a way ha :
•I a oids disca ding da a ha he sende / ecei e o wo k ha e in common;
•The wo ke ha makes a eques ecei es a la ge slice o wo k;
•Each wo ke does all he wo k i has be o e making ano he eques .
37 3.2. SOLUTION SEARCHING
Ou expe imen s show ha hese heu is ics wo k e y well o pa allel indall/3
because hey sp ead he wo ke s h oughou he wo k ee, gene a ing a wo k dis i-
bu ion such as he one p esen ed in Figu e 3.6.
Fo simplici y, we assume ha mo ing one om a b anch o ano he , adjacen o i ,
akes one ime uni . Ini ially, only wo ke 0 can sea ch he ee. A e sha ing wo k
wi h wo ke 1, he appea ance o he ee is ha o Figu e 3.5. In he nex ime uni ,
wo ke 0 sha es wo k wi h wo ke 2 and wo ke 1 sha es wo k wi h wo ke 3, esul ing
in he dis ibu ion o Figu e 3.6.
This way, i he ee is balanced, each o he wo ke s akes he same ime, allowing he
P olog compile o achie e linea speedups. I he ee is no balanced, he numbe
o imes ha wo k has o be sha ed is ela i ely small because e e y ime i happens,
he amoun o wo k sha ed is as la ge as possible.
Figu e 3.5: YapO sea ch ee a e wo ke 0 sha es wo k wi h wo ke 1.
Figu e 3.6: Expec ed YapO wo ke dis ibu ion, using 4 wo ke s.
Fo he pa allel ind i s /3 p edica e his s a egy can be imp o ed. Fi s o all,
because we do no need all he solu ions, we should no make he O -Pa allel Engine
sp ead he wo ke s oo much. In his case, we should in ac keep hem as much o
CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 44
The implemen a ion i s c ea es a memo y mapped a iable is wo k sha ing enabled
du ing he ini ializa ion o YapO ha is used o keep ack o whe he o no wo k
sha ing is enabled. Then, once again be ween s eps 1 and 2, e e y wo ke excep o
he i s wai s o he a iable o be ue and keeps yielding he p ocesso in o de
o a oid was ing CPU ime. The i s wo ke s a s execu ion as no mal. When he
a iable becomes ue, a e he i s ail/0, he o he wo ke s s a making wo k
eques s. Using his s a egy he wo ke dis ibu ion p esen s he pa e n shown in
Figu e 3.12. No ice ha wha always happens is ha wo ke 0 ails a he posi ion
shown in Figu e 3.11. A e wa ds, all he wo ke s can s a sha ing wo k, leading
o he somewha andom posi ioning o Figu e 3.12, whe e he wo ke s a e all close
oge he .
Figu e 3.11: Wo ke 0, immedia ely be o e ailing.
Figu e 3.12: Expec ed wo ke dis ibu ion wi h s a egy F1, using 4 wo ke s.
Unlike he p e ious s a egies, his s a egy deals wi h a majo p oblem de ec ed ea ly
on: wo ke s ha s a by mo ing o he igh , become los o e e because hey a e
ne e able o comple e he sea ch o he big sub ee be o e he o he wo ke s comple e
he small one. This s a egy ies o o ce e e y wo ke o s a a he bo om le o
he sea ch ee and hen mo e up and o he igh as needed, minimizing his p oblem.

45 3.2. SOLUTION SEARCHING
This s a egy s ill has a couple o laws - one o hem is ha he wai ing ime be o e
he p ocess o wo k sha ing s a s can be a conside able slice o he o al un ime; he
o he is ha he i s ime ha wo k is sha ed, each wo ke migh copy a huge amoun
o memo y, because i has none in common wi h he sende , which migh be a a e y
deep le el o he ee.
3.2.7 S a egy F2 - Descend he T ee, Sha e Less A e
Failing he Fi s Time
This s a egy in ends o imp o e upon he p e ious one by diminishing he amoun
o wo k ha mus be sha ed o e all du ing he i s ime each wo ke ecei es wo k.
I does no do changes o any addi ional modules o Yap besides he ones changed by
he p e ious s a egy.
We i s change he is wo k sha ing enabled a iable o be an in ege ins ead o
a boolean, changing i s name in he p ocess o maximum sha ing wo ke . When
maximum sha ing wo ke is 0, sha ing is disabled. A e he i s ail/1, he alue is
se o 1 and wo ke 1 ge s wo k om wo ke 0 and hen mo es o 2/3 o he dep h o
wo ke 0, se ing maximum sha ing wo ke o 2. Then wo ke 2 does he same, ela i e
o wo ke 1 and so on un il e e y wo ke has wo k. This s a egy p oduces a di e en
wo ke dis ibu ion om he p e ious s a egy; he expec ed wo ke dis ibu ion is
p esen ed in Figu e 3.13. The di e ence is ha he s a e o Figu e 3.11 is eached, he
wo k sha ing is done sequen ially, wi h each wo ke mo ing up one node, o ming he
dis ibu ion o Figu e 3.13.
Figu e 3.13: Expec ed wo ke dis ibu ion wi h s a egy F2, using 4 wo ke s.
This s a egy would conside ably dec ease he amoun o sha ing and sp ead he
wo ke s enough o a oid ha ing oo many wo k eques s, excep ha in p ac ice,
we obse ed ha his ini ial wo k sha ing p ocess ails mos o he ime, delaying
CHAPTER 3. IMPLEMENTATION OF CONSTRUCTORS 46
conside ably he ini ializa ion o all wo ke s. As discussed in Chap e 4, we can obse e
ha his s a egy is unable o imp o e o e he p e ious one, when implemen ed in
YapO .
3.2.8 S a egy S - F eeze he O -F ames, Allowing
Volun a y Suspension
This s a egy makes use o unc ions o OPTYAP, he O -Pa allel abling engine o
Yap, ha a e capable o eezing and un eezing a comple e execu ion sub-b anch o
he sea ch ee. I should also be he s a egy ha causes he bigges a ia ions in
e ms o execu ion, p oducing he mos nonde e minis ic beha io o all he s a egies
p esen ed. We make changes o he O -F ame da a s uc u e and o he ge wo k
unc ion.
The i s change we ha e done was o add a new ield o he O -F ame, o con inua ion
which keeps a poin e o a ozen O -F ame ha is immedia ely below - o he
con inua ion o - he cu en O -F ame. We also sligh ly al e ed he suspend b anch()
and esume suspension ame() unc ions o eeze and un eeze he O -F ames,
espec i ely. Using he doubly-linked lis o s a egy 3.2.5, we keep ack o he o de
o wo ke s. I he wo ke ha ies o ge wo k is he igh mos , i suspends all
ames ha a e no common o any o he wo ke , essen ially c ea ing a linked lis o
suspended O -F ames, and asks all wo ke s om he le mos o wo k un il i ge s
wo k o , ailing ha , esumes execu ion o he suspended O -F ames. Assuming ha
we ha e he wo ke dis ibu ion p esen ed in Figu e 3.14 and ha wo ke 1 suspends
wo k o mo e o he le , we a i e a he dis ibu ion p esen ed in Figu e 3.15.
Figu e 3.14: Expec ed wo ke dis ibu ion wi h s a egy S, using 4 wo ke s, be o e
suspending wo k.
47 3.2. SOLUTION SEARCHING
Figu e 3.15: Expec ed wo ke dis ibu ion wi h s a egy S, using 4 wo ke s, a e
suspending wo k.
Al hough p elimina y expe imen s based on olun a y mo emen ha disca ds O -
F ames p esen ed good pe o mance - when he wo ke s did no disca d he O -F ame
wi h he solu ion, which could happen because he algo i hm was inco ec - we we e
unable o implemen olun a y suspension in p ac ice due o se e e un ime e o s
whene e we a emp ed o do so.
3.2.9 Summa y
We p esen ed di e en s a egies ha make di e en decisions ega ding how o sched-
ule wo k. We saw ha we may:
•Wai a ce ain amoun o ime;
•T y o always mo e down he ee;
•Mo e back o be able o mo e le ;
•Wai un il ailing he i s ime;
•Suspend wo k o mo e o le .
We also saw ha we should a oid sha ing oo li le which leads o ampling, o oo
much because sha ing is a slow ope a ion. Addi ional possibili ies a e p esen ed in
Chap e 5.
48
Expe imen al Resul s 4
In his chap e , we p esen expe imen al esul s o he s a egies p oposed in he
p e ious chap e , showing he speedups ha each s a egy was able o achie e and
how hey a y based on he size o he p oblem we wan o add ess. Ou esul s we e
ob ained using wo NUMA machines, which we e used independen ly om each o he .
Bo h ha e he same echnical speci ica ions: ou six-co e AMD Op e on 8425 HE
p ocesso s, o aling 24 co es, each wi h a clock speed o 2.1 GHz, wi h 128 GB RAM
and using Fedo a Co e 20 in 64-bi mode.
Since he pa allel ind i s /3 p edica e is no a ailable o Yap’s sequen ial e -
sion, all he speedups measu ed wi h a ce ain numbe o wo ke s a e ela i e o
unning ha same e sion o YapO wi h a single wo ke .
We an es s used he di e en s a egies we p esen ed wi h di e en p oblem sizes. As
expec ed o he exponen ial benchma k we used, we e i ied ha he execu ion imes
doubled when he size o he p oblem inc eased by 1. The e o e, o simplici y, we
always chose a size ha ook as close o 200 seconds as possible, when using a single
wo ke , o all he esul s p esen ed in his sec ion.
In he ables we p esen nex , ha a e accompanied by a g aphical ep esen a ion,
he e a e 4 ows:
1. The execu ion ime using 1 wo ke ;
2. The execu ion ime using he numbe o wo ke s indica ed in he cap ion;
3. The speedup ob ained;
4. The speedup ela i e o he de aul YapO s a egy.
To measu e he speedups, we an he benchma k p esen ed in Appendix A 12 imes
o each pai o s a egy and p oblem size and hen we disca ded he as es and he
49

CHAPTER 4. EXPERIMENTAL RESULTS 50
slowes uns, p esen ing he a e age o he emaining 10 uns. We do no p esen
esul s o pa allel indall/3 because ou es s e ealed ha hese s a egies do
no imp o e i s execu ion.
S a egy: YapO W B L1 L2 L3 F1 F2
1 wo ke : 174.142 174.621 174.271 174.923 174.612 175.232 173.965 174.672
4 wo ke s: 96.121 96.138 114.961 96.662 75.284 77.770 92.224 86.589
Speedup: 1.81 1.82 1.52 1.81 2.32 2.25 1.89 2.02
Rela i e: 1.00 1.01 0.84 1.00 1.28 1.24 1.04 1.12
Table 4.1: Execu ion imes and speedups ob ained wi h 4 wo ke s and p oblem size
30, o all s a egies.
0
0,2
0,4
0,6
0,8
1
1,2
1,4
YapO
W
B
L1
L2
L3
F1
F2
Figu e 4.1: Rela i e speedups ob ained wi h 4 wo ke s.
Looking a able 4.1 we immedia ely no ice ha :
•S a egy B signi ican ly dec eases he speedup compa a i ely o s anda d YapO ;
•S a egies W and L1 do no p oduce conside able changes;
•S a egies L2 and L3 inc ease speedups a li le bi , whe e s a egy L2 pe o ms
be e ;
•S a egies F1 and F2 inc ease speedups sligh ly and, ou o he wo, s a egy F2
is be e .
An in e es ing obse a ion ha is no immedia ely ob ious is ha s a egies F1 and F2
gene ally ha e simila un imes o YapO ’s s a egy bu spo adically p oduce esul s
51
in abou a hal o YapO ’s ime, ha is, hey ha e speedups close o 4. Ou o hese
s a egies, s a egy F2 appea s o ha e a highe likelihood o p oducing he solu ions
wi h a ela i ely good speedup.
In ou es s, he esul s ob ained when using 4 wo ke s a e e y simila o hose
ob ained o o he numbe s o wo ke s, in e ms o he speedup ha is achie ed. Fo
b e i y he emaining ables only show esul s o s anda d YapO , s a egy L2 and
s a egy F2.
S a egy: YapO L2 F2
1 wo ke : 203.044 204.957 203.002
8 wo ke s: 102.534 88.121 95.424
Speedup: 1.98 2.33 2.12
Rela i e: 1.00 1.18 1.07
Table 4.2: Execu ion imes and speedups ob ained wi h 8 wo ke s and p oblem size
34.
0,9
0,95
1
1,05
1,1
1,15
1,2
YapO
L2
F2
Figu e 4.2: Rela i e speedups ob ained wi h 8 wo ke s.
S a egy: YapO L2 F2
1 wo ke : 226.521 227.110 227.029
12 wo ke s: 118.145 96.612 112.103
Speedup: 1.92 2.35 2.03
Rela i e: 1.00 1.22 1.06
Table 4.3: Execu ion imes and speedups ob ained wi h 12 wo ke s and p oblem size
38.
A e analyzing hese ables side-by-side we can no ice a pa e n in he execu ion o
YapO : in gene al, when using a numbe a + n o wo ke s and using a lis ha has b
CHAPTER 4. EXPERIMENTAL RESULTS 52
0
0,2
0,4
0,6
0,8
1
1,2
1,4
YapO
L2
F2
Figu e 4.3: Rela i e speedups ob ained wi h 12 wo ke s.
S a egy: YapO L2 F2
1 wo ke : 250.255 251.978 252.001
16 wo ke s: 126.344 101.563 118.524
Speedup: 1.98 2.48 2.12
Rela i e: 1.00 1.25 1.08
Table 4.4: Execu ion imes and speedups ob ained wi h 16 wo ke s and p oblem size
42.
0
0,2
0,4
0,6
0,8
1
1,2
1,4
YapO
L2
F2
Figu e 4.4: Rela i e speedups ob ained wi h 16 wo ke s.
+ n ze os a he beginning and cones ollowing, he execu ion akes a simila amoun
o ime o ha o awo ke s, wi h a lis o bze os and cones. This is o be expec ed,
assuming ha all he naddi ional wo ke s ake he igh side o each o he i s n
choice poin s and, as such, educe he p oblem o he e sion wi hou hose nwo ke s
and he smalle lis .
53
S a egy: YapO L2 F2
1 wo ke : 142.813 143.122 144.672
20 wo ke s: 71.324 58.556 66.890
Speedup: 2.00 2.44 2.16
Rela i e: 1.00 1.22 1.08
Table 4.5: Execu ion imes and speedups ob ained wi h 20 wo ke s and p oblem size
45.
0
0,2
0,4
0,6
0,8
1
1,2
1,4
YapO
L2
F2
Figu e 4.5: Rela i e speedups ob ained wi h 20 wo ke s.
S a egy: YapO L2 F2
1 wo ke : 148.312 149.216 150.275
24 wo ke s: 74.142 60.922 70.443
Speedup: 2.00 2.45 2.13
Rela i e: 1.00 1.23 1.07
Table 4.6: Execu ion imes and speedups ob ained wi h 24 wo ke s and p oblem size
49.
We can also see ha , despi e ou e o s, he speedups do no inc ease in any consid-
e able manne wi h he addi ion o wo ke s, al hough he speedups end o s abilize
a a speedup o 2, wi h he s anda d YapO s a egy.
APPENDIX A. BENCHMARKING CODE 60
1#!/bin/bash
2pushd $(di name $0)2>&1>/de /null
3DIR=$(pwd)
4
5 o VERSION in "yap1" "yap2";do
6cd $DIR/../$VERSION 2>&1>/de /null
7echo "Size = $2"
8
9TIME1=$(echo "go($1,$2)." |
10 ./yap -l $DIR/bench.p o 2>&1>/de /null |
11 head -n3 | ail -n1)
12
13 TIMEN=$(echo "go($1,$2)." |
14 ./yap -l $DIR/bench.p o -w $CPUS 2>&1>/de /null |
15 head -n3 | ail -n1)
16
17 echo $TIME1
18 echo $TIMEN
19
20 i ["$TIMEN"== "0.000" ]; hen
21 TIMEN="0.001"
22 i
23
24 TIME1=$(echo "$TIME1"| awk ’{p in $6}’)
25 TIMEN=$(echo "$TIMEN"| awk ’{p in $6}’)
26
27 echo | awk ’{ es=’"$TIME1 /$TIMEN"’; p in "Speedup = %.2 n", es}’
28 done;
29
30 popd 2>&1> /de /null
Figu e A.2: Calcula es he speedup o he pa allel execu ion o A.1.
1#!/bin/bash
2LEFT=$#
3CPUS=$(lscpu | g ep "CPU(s):" | awk ’{p in $2;}’ | head -n1)
4echo $(hos name)"(1 wo ke VS" $CPUS "wo ke s):"
5
6while [$LEFT -g 0];do
7echo
8bash unbench.sh $CPUS $1
9shi
10 LEFT=$(echo "$LEFT -1"| bc)
11 done
Figu e A.3: A w appe ha calls A.2 o each p oblem size passed as an a gumen .