... manusc ip No.
(will be inse ed by he edi o )
Au oma ic Run ime Calcula ion o Communica ions
o Da a-Pa allel Exp essions wi h Pe iodic
Condi ions
Ana Mo e on-Fe nandez ·A u o
Gonzalez-Esc ibano
Recei ed: da e / Accep ed: da e
Abs ac Many eal-wo ld applica ions ea u e da a accesses on pe iodic do-
mains. Manually implemen ing he synch oniza ions and communica ions as-
socia ed o he da a dependences on each case, is cumbe some and e o -p one.
I is inc easingly in e es ing o suppo hese applica ions in high-le el pa allel
p og amming languages o pa allelizing compile s. In his pape we p esen a
echnique ha , o dis ibu ed-memo y sys ems, calcula es he speci ic com-
munica ion pa e ns de i ed om da a-pa allel codes wi h o wi hou pe i-
odic bounda y condi ions on a ine access exp essions. I makes anspa en o
he p og amme he managemen o agg ega ed communica ions o he cho-
sen da a pa i ion. Ou echnique mo es o un ime pa o he compile- ime
analysis ypically used o gene a e communica ion code o a ine exp essions,
in oducing a comple e new echnique ha also suppo s he pe iodic bound-
a y condi ions. We p esen an expe imen al s udy o e alua e ou p oposal
using se e al s udy cases. Ou expe imen al esul s show ha ou app oach
can au oma ically ob ain communica ion codes as e icien as hose ound in
MPI e e ence codes, educing he de elopmen e o .
Keywo ds Dis ibu ed memo y ·Pe iodic bounda y condi ion ·Communi-
ca ion pa e ns ·Pa allel p og amming
1 In oduc ion
Many eal-wo ld applica ions ea u e da a accesses on pe iodic domains; do-
mains on which a leas one dimension is o oidal, and a walk h ough he
A. Mo e on-Fe nandez ·A. Gonzalez-Esc ibano
Depa amen o de In o m´a ica, Uni e sidad de Valladolid, Valladolid, Spain
A. Mo e on-Fe nandez E-mail: [email p o ec ed]a.es
A. Gonzalez-Esc ibano E-mail: [email p o ec ed]a.es
2 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
dimension becomes an in ini e ou on which he same elemen s o he do-
main a e pe iodically a e sed once and again. When his kind o domains
a e disc e ized and ep esen ed by a se o indexes, ad ancing pas he las
index in he pe iodic dimension, ins ead o ge ing ou o he domain, means
a i ing a he i s index. Fo example, physical phenomena can be modelled
using sphe ical g ids wi h pe iodic bounda y condi ions [25], using a s encil
p og am o e a pe iodic domain. Manually implemen ing he synch oniza ions
and communica ions associa ed o he da a dependences o each speci ic ap-
plica ion, is cumbe some and e o -p one. Thus, i is inc easingly in e es ing
o suppo hese applica ions in high-le el pa allel p og amming languages o
pa allelizing compile s.
Cu en s a e-o - he a compile s ocus on he ans o ma ion o high-
le el pa allel p og ams (e.g. [10]), o sequen ial codes (e.g. [6]), o low-le el
pa allel p og ams. Typically, hey a ge s a ic-con ol p og ams wi h a ine
exp essions, using compile- ime au oma ic echniques [11,4,17]. These ech-
niques abs ac many issues ela ed o he execu ion pla o m, while hey s ill
deli e good pe o mance. Howe e , hey p oduce a gene ic code ha does no
ake in o accoun some speci ic de ails o he execu ion machine. Fo example,
he mos sophis ica ed code gene a o s o dis ibu ed memo y [4], ha only
suppo a ine exp essions, educe he olume o communica ed da a and a e
pa ame ic in he numbe o p ocesses and p oblem sizes. Ne e heless, hey
s ill need o ix a single ile size a compile ime, e en i he sys em has nodes
wi h di e en capabili ies. Mo eo e , he applica ion o hese echniques o
pe iodic domains is mo e complica ed. In gene al, hey need o compu e a
ansi i e closu e o dependencies, which is ypically a e y ha d p oblem a
compile ime.
In his pape we p esen a echnique ha , au oma ically calcula es a un-
ime he coa se-g ained communica ion pa e ns 1 ha a e needed o a co ec
and e icien execu ion o SPMD (Single P og am Mul iple Da a) p og ams de-
i ed om da a-pa allel codes wi h pe iodic a ine exp essions in da a accesses.
I makes anspa en o he p og amme he managemen o agg ega ed com-
munica ions o he chosen da a pa i ion. This echnique has been ecen ly
announced o he communi y [20]. I mo es o un ime pa o he compile- ime
analysis needed o gene a e he communica ion code. I p oduces p og ams
mo e adap able o di e en execu ion en i onmen s, allowing, o example,
he use o di e en ile sizes a he same hie a chical le el, a good app oach
o clus e s ha include machines wi h di e en a chi ec u es [19].
To show he applicabili y o ou app oach, we de elop he echnique in he
T asgo pa allel p og amming sys em p oposed in [12]. Ou implemen a ion au-
oma ically gene a es MPI p og ams om abs ac da a-pa allel exp essions.
We es six benchma ks wi h pe iodic access exp essions: An illus a i e exam-
ple based on he o a e ou ine o he STL lib a y [28], he pe iodic e sions o
1Communica ion pa e ns: Abs ac s uc u es de e mining which da a should be mo ed
ac oss each pai o p ocesses a a gi en p og am poin . Fo example, in he MPI message-
passing in e ace a speci ic ins ance o an MPI All oall unc ion call can be ep esen ed as
a communica ion pa e n.
Ti le Supp essed Due o Excessi e Leng h 3
Hea 1-D, 2-D and 3-D applica ions [5], a ma ix mul iplica ion p og am us-
ing Cannon’s algo i hm [8] and a mul i-g id V-cycle 3D-s encil applica ion, he
NAS MG benchma k [1]. Ou expe imen al esul s, compa ing pu e MPI e -
e ence codes and he p og ams au oma ically gene a ed, in bo h dis ibu ed-
and sha ed-memo y en i onmen s, show ha he use o ou app oach can au-
oma ically ob ain e icien codes while educing he de elopmen e o . Fo
example, he use o ou solu ion leads o a educ ion o 44.42% in he numbe
o code lines and a educ ion o 65.71% in he McCabe Cycloma ic Complexi y
o he NAS MG Benchma k.
2 Rela ed Wo k
Many ask-o ien ed p og amming app oaches (like S a Ss, OmpSs [7,24]) a e
based on i e a o s o gene a e pools o asks wi h explici inpu and ou pu
wo king se s. The wo king se s analysis allows dependence g aphs o be buil .
Howe e , due o he ask execu ion model based on dynamic scheduling wi h
ask-queues, synch oniza ions, and dynamic mapping in o ma ion, hese mod-
els canno de i e agg ega ed communica ion calcula ions o g oups o asks.
Mo eo e , he use o hese ask-o ien ed app oaches in dis ibu ed memo y
leads o pe o mance penal ies in he gene al case, due o he ask c ea ion and
des uc ion, he managemen o dis ibu ed queues, he synch oniza ion and
load balancing mechanisms, and he da a communica ions due o dynamic ask
scheduling and/o mig a ion. Ou app oach minimizes synch oniza ion o e -
heads, by gene a ing p og ams wi h s a ic-scheduled p ocesses ha pe o m
coa se-g ained compu a ion and communica ion phases.
PGAS (Pa i ioned Global Add ess Space) models p esen an abs ac ion
o wo k wi h mixed dis ibu ed- and sha ed-memo y en i onmen s simila
o T asgo. The PGAS language ha is mo e closely ela ed o ou wo k is
Chapel [9]. I p oposes a sepa a ion o domain and mapping modules o gene -
a e dis ibu ed a ays. Howe e , he bes communica ion agg ega ion me hods
p esen ed so a o Chapel abs ac ions a e es ic ed o speci ic ope a ions,
o domain mapping p ope ies. Fo example, he wo k in [26] is es ic ed o
global a ay assignmen s wi h block o cyclic dis ibu ions. The wo k in [27]
p esen s a symbolic subs i u ion o mapping a ibu es in a ine access exp es-
sions wi h he same inspi a ion as ou app oach. Howe e , he Chapel un ime
canno agg ega e se e al exp essions ac oss di e en loops o gene a e he ull
ask oo p in . Also, i needs o ely on non-agg ega e communica ions when
he whole se o da a accessed by an exp ession is no ully alloca ed in he
same emo e p ocesso . I only wo ks o cyclic o block-cyclic dis ibu ions.
Fo an-D compile echniques o calcula ing communica ion in SPMD
p og ams [15] use domain calcula ions o gene a e, a compile ime, di e en
communica ion code depending on he da a pa i ion selec ed. This cons ain
a oids o change da a pa i ion ea u es a un ime. Howe e , pe o ming a
da a pa i ion based on he de ails o he a ge machines is key o achie e a
4 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
good pe o mance and a balanced wo kload, especially in dis ibu ed-memo y
sys ems ha include machines wi h di e en a chi ec u es.
The polyhed al model p o ides a o mal amewo k o de elop au oma ic
ans o ma ion echniques a he sou ce code le el o gene a e low-le el code
o sha ed- o dis ibu ed-memo y sys ems [4,2,31,16]. Using he cu en dis-
ibu ed-memo y app oaches, communica ions canno be calcula ed ac oss di -
e en a ine loop nes s sec ions unless loop usion can be done. Mo eo e , using
hese me hods he e a e s ill cases o duplica ed o unnecessa y da a commu-
nica ions, ha ou p oposal can a oid, as i will be shown in Sec . 6. The
wo k in [17] p esen s a hyb id compile - un ime ansla o scheme simila o
ou app oach ha calcula es he communica ion pa e n needed in an SPMD
p og amming model. Howe e , hey only suppo egula and epe i i e appli-
ca ions whe e he communica ion pa e n is he same in all he i e a ions o
an ou e se ial loop ha encloses he SPMD block. Ou echnique is applicable
o p og ams ha change hei communica ion s uc u e on each i e a ion.
Applying he iling echnique o a se o indexes enables a medium-g ained
pa alleliza ion. Some app oaches ha e been p esen ed o sol e he p oblem o
iling wi h pe iodic bounda y condi ions. The closes me hod o ou app oach
is a cu ing-and-pas ing echnique. In his echnique, he dependencies which
a e a ec ed by he pe iodic condi ions a e b oken and displaced. I is simila o
a ci cula loop skewing. This app oach needs a compu a ion o he ansi i e
closu e o dependencies o de e mine he se o i e a ions which ano he ile
depends on. Some lib a ies such as ISL [30] a e capable, o some p oblems, o
compu ing a compile ime he ansi i e closu e o dependencies e icien ly.
Howe e , he ansi i e closu e compu a ion ypically is a e y ha d p oblem
o solu ions ha wo k a compile ime. Recen ly, ano he me hod o ile
and op imize ime-i e a ed compu a ions o e pe iodic domains was p esen ed
in [5]. This echnique i s spli s he i e a ion domain, cu ing close o he
mid-poin wha hei au ho s call long dependences. A e his cu , hey apply
a sepa a e a ine ans o ma ion on each hal o he space. All hese app oaches
a ge sha ed-memo y sys ems. P og amming o dis ibu ed-memo y sys ems
is mo e challenging due o he managemen o he dis ibu ed da a s uc u es.
Mo eo e , communica ions among p ocesses should be de ised in e ms o ,
o example, message-passing ope a ions, aking in o accoun all he po en ial
combina ions o p ope da a pa i ions o ma ix sizes. Ou echnique makes
anspa en all hese issues.
3 Illus a i e Example
This sec ion p esen s an illus a i e applica ion o show an example o how
a pa ame izable algo i hm can be ackled wi h ou p oposed solu ion. We
selec ed an example based on he o a e ou ine o he STL lib a y [28]. Re e
o he sequen ial algo i hm in Fig. 1. The ou ine applies a o a ion o he
ec o elemen s while applying a unc ion () on each one o hem. The ou ine
ecei es an in ege pa ame e size, a ec o o elemen s (wi h he size indica ed
Ti le Supp essed Due o Excessi e Leng h 5
** Sequen ial o a e algo i hm
Inpu s: size: Vec o size
< ype> M[size]: Vec o wi h ini ial alues
o : Amoun o posi ions o o a e he elemen s
: unc ion o compu ing each elemen
Ou pu s: < ype> M2[size]: Vec o wi h esul alues
1. < ype> M2[size];
2. Fo i = 0 o size-1
M2[i] = (M[(i+ o ) mod size])
Fig. 1 Sequen ial algo i hm o he illus a i e example assuming a posi i e alue o o .
Inpu s:
size: Vec o size
myRank: local p ocess Id
L: mapping unc ion
Ou pu s:
< ype> M[ ]: Dis ibu ed ec o
o : Amoun o posi ions o o a e
< ype> M2[ ]: Dis ibu ed ec o
2. .......
** B ing da a om emo e p ocesses
** Decla e local pa o M2
1. < ype> M2[ L(myRank).b : L(myRank).e ]
** Local compu a ion
3. o ( i=L(myRank).b ; i<=L(myRank).e; i++)
M2[i] = ( M[ (i+ o ) mod size ] )
Comm.
S age
SPMD
Comp.
Fig. 2 Pa allel algo i hm o he illus a i e example in a SPMD model assuming a p e i-
ously dis ibu ed inpu a ay. Boxes indica e he logical s eps in SPMD compu a ions.
by he p e ious pa ame e ), and ano he in ege pa ame e o . The pa ame e
o is used in he access exp essions o selec , a un ime, he amoun o
posi ions ha he elemen s in he ec o should be shi ed.
A dis ibu ed pa allel e sion o his algo i hm is shown in Fig. 2. In his
case, he inpu pa ame e s a e: (1) The size o he o iginal inpu ec o , size;
(2) he local p ocess iden i ie , myRank; (3) a mapping unc ion L ha ecei es
a p ocess iden i ie and e u ns he se o indexes, in he ange [0:size-1],
assigned o ha p ocess (band ewill indica e he limi s o he se o his
p ocess) ; (4) An inpu ec o M ha was p e iously dis ibu ed among he
di e en p ocesses using he mapping unc ion L; (5) The in ege pa ame e
o ha is assumed o be posi i e in his example.
Fi s , he local pa o he dis ibu ed ou pu ec o M2 is de ined, also
using he mapping unc ion L. Thus, each p ocess s o es he same pa o bo h
a ays, Mand M2. A e ha , each p ocess pa icipa es in he o a ion o he
whole ec o elemen s, and applies he unc ion () on i s pa (SPMD block).
When a p ocess applies he access exp ession (i+ o )mod size o i s assigned
index domain, i is possible ha pa o he esul ed indexes a e ou o he
assigned domain. Hence, we inse a communica ion s age be o e he SPMD
block o ensu e ha e e y p ocess has he necessa y da a o compu e ().
A e he communica ion and compu a ion, p ocesses will be able o upda e
i s pa o he M2 ou pu ec o . Ou echnique calcula es au oma ically hese
necessa y communica ion pa e ns.
We illus a e he communica ion calcula ion o his example in Fig. 3. In
he le o he igu e, we see in S age 1 he se o indexes assigned by he
mapping unc ion L o each p ocess. In S age 2, we see he se o indexes

6 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
...
...
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
Fig. 3 Communica ion s uc u es calcula ion. Using he ead da a-access exp ession inside
he pa allel compu a ion o he illus a i e example o build he unc ions ha calcula e he
wo king inpu indexes se (WI) o M o he p ocesses 2 and 4. This example uses con iguous
ec angula shapes, an i egula da a pa i ion policy, and conside s he pa icula case o
o = 3, o a domain wi h |M0|= 25.
esul ed by applying he exp ession (i+ o ) o he indexes assigned o he
p ocesses 2 and 4. In ou example, he domain accessed by p ocess 2 o e laps
wi h he domain owned by p ocess 3. Thus, in o de o compu e, p ocess 2
needs o ecei e hose da a om p ocess 3. Fo p ocess 4 we ob ain wo se s
o indexes: (a) A se loca ed in o he o iginal a ay domain (i will be named
s◦), and (b) a se loca ed ou side o he o iginal a ay domain. This se is
ep esen ed in whi e and i will be named s+. No ice ha s+is a se o
indexes highe han he end o he a ay domain, due o he posi i e alue o
o in he example. I he alue o o had been nega i e, we would ha e had
a se o indexes lowe han he s a o he a ay domain, named s−.
The applica ion o he pe iodic bounda y condi ion (mod size) o e he
se o indexes esul ed o applying i+ o in p ocess 4, ans o m hem o he
se o indexes shown in S age 3. The whi e egion on S age 2 co esponds o
he s ipped egion ha belongs o p ocess 1 a S age 3. We will need an ex a
communica ion o ecei e he s ipped egion om p ocess 1 in p ocess 4.
4 Agg ega ed-Communica ion Model
In his sec ion, we p esen a gene ic model ha calcula es a un ime he
necessa y communica ion pa e ns o compu e SPMD blocks, ha con ain
a ine access exp essions on he indexes o he pa allel loops (SPMD blocks)
wi h op ional pe iodic bounda y condi ions. In his pape we assume an owne -
compu es pa adigm, wi h he esul o a un ime mapping unc ion indica ing
he owne ship. We desc ibe he model o calcula e communica ion pa e ns o
mo e da a om owne p ocesses o he p ocesses whe e hese da a a e accessed
o execu e compu a ion. The same model can be applied o mo e compu ed
da a o des ina ion posi ions, in he case o w i e accesses which a e gene ic
exp essions ha ans o m he domain indexes.
Ti le Supp essed Due o Excessi e Leng h 7
In his sec ion, i s , we p esen he no a ion used in his pape . A e
ha , a simpli ied one-dimensional o e iew o he communica ion calcula ion
is p esen ed. Finally, he gene ic mul i-dimensional model is desc ibed.
4.1 De ini ions
In his sec ion, we de ine he e ms used du ing he model desc ip ion.
– Numbe o elemen s (N): numbe o elemen s in an a ay M.
– Numbe o dimensions (n): numbe o dimensions o an a ay M.
– Ca dinali y (|Mx|): numbe o indexes o he a ay Min he x- h dimen-
sion.
– Signa u e (Shb, e, zi): is a iple o h ee in ege numbe s begin (b), end
(e), and s ide (z). A signa u e de ines a subse o in ege one-dimensional
indexes om he begin o he end, using he s ide as s ep. We will use he
classical Fo an90 no a ion [b:e:z] o simplici y in ou discussion. The
se o all possible signa u es is S∗.
– Domain (Dn): An n-dimensional domain o med by he Ca esian p oduc
o nsigna u es (a hype ec angle). The se o all possible domains in n
dimensions is deno ed as D∗
n.
– Compu a ion indexes (−→
i): The se o indexes whe e a pa allel compu-
a ion will be pe o med.
– A ine exp ession (ρx(−→
i)): In ou echnique we conside a ine exp es-
sions on he x- h dimension wi h he o m:
ρx(−→
i) = α0×i0+... +αn−1×in−1+β
whe e he coe icien s αx, β a e in a ian in he body o he SPMD block.
We can also apply an a ine exp ession o a whole se o indexes desc ibed
by a signa u e (ρx(s)).
– Pe iodic exp ession (cyc(ρx(−→
i))): I deno es pe iodic bounda y condi-
ions on he esul o an a ine exp ession.
– Mapping unc ion (L(p)): I is a unc ion ha ecei es he index o a
p ocess and e u ns he domain ep esen ing he se o indexes mapped o
ha p ocess.
– Access exp ession (M[cyc(ρ0(−→
i))]...[cyc(ρn−1(−→
i))]): An exp ession in
he code ha accesses he da a in a da a s uc u e M. A pe iodic bounda y
condi ion is applied on each dimension o he da a s uc u e.
– Se o a ine exp essions (φ(−→
i)): The se o a ine exp essions (one o
each dimension) o a single access exp ession.
4.2 Model o Calcula ing Communica ion Pa e ns in 1-D Applica ions
In his sec ion we p esen an o e iew o he p oposed echnique o calcula e
he communica ion pa e ns o only one-dimensional index domains. Recall
8 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
he pa allel algo i hm p esen ed in Fig. 1, ha pe o ms he o a ion o he
elemen s o a ec o also applying a unc ion (). A communica ion phase
is needed be o e he SPMD block o ealloca e some da a ac oss p ocesses,
ensu ing ha each p ocess has he necessa y da a o compu e.
The ollowing analysis is done independen ly o each da a s uc u e, and
o each SPMD block. The Inpu Wo king Se o Indexes (WA,k
I(p, L, −→
δ)) is a
unc ion buil based on he access exp essions on a SPMD block. I e u ns he
se o indexes o he da a s uc u e A, ead by a gi en p ocesso p, du ing he
k- h SPMD block in he code ( emind S age 2 o Fig. 3). The pa ame e s o
he unc ion a e: The p ocesso iden i ie p, a mapping unc ion L ha e u ns
he se o indexes mapped o any p ocesso , and −→
δ, he alues o he symbolic
pa ame e s ha appea in he exp essions. The unc ion applies a un ime
he a ine exp essions (φ) ound in ead accesses o Ainside he k- h SPMD
block, one by one, o he indexes se e u ned by he mapping unc ion (L(p)).
See a calcula ion example in S age 2 o Fig. 3.
Fo he one-dimensional case, we ob ain a se o indexes ha can be ep-
esen ed by a se o signa u es. These signa u es can be classi ied as:
–Se o signa u es whose indexes a e lowe han he begin o he o iginal
a ay domain (S−
0).
–Se o signa u es whose indexes in e sec wi h he o iginal domain (S◦
0).
–Se o signa u es whose indexes a e highe han he end o he o iginal
a ay domain (S+
0).
We gene a e he code o he unc ions ha compu e he se o indexes ead
pe each SPMD block, and each da a s uc u e (WA,k
I(p, L, −→
δ)). These unc-
ions e u n a se o signa u es ep esen ing he se o indexes ead. Wi h hese
unc ions, a p ocess can calcula e he inpu wo king se o a da a s uc u e,
o any p ocess, once he pa ame ic alues a e known. These unc ions simply
apply he access exp essions o he index-space limi s a un ime o calcula e
he wo king-se s (see he implemen a ion o hese unc ions in Sec . 5).
Once we ha e he se o signa u es ha esul o applying he a ine ex-
p essions, we can apply he pe iodic bounda y condi ions, whe e i is equi ed.
This eloca es he indexes ha a e he applica ion o he a ine exp ession
a e ou o he o iginal a ay domain, in o he domain. See S age 3 in Fig. 3. We
de ine wo unc ions o apply he pe iodic condi ions o signa u es. Remind
ha |M0|is he numbe o elemen s o Min he i s dimension.
–Fo signa u es in S−we de ine ψ:S∗→S∗whe e
ψ(s) = s0:


s0.b =−((−s.b)mod |M0|) + |M0|,
s0.e =−((−s.e)mod |M0|) + |M0|,
s0.z =s.z
(1)
–Fo signa u es in S+we de ine ϕ:S∗→S∗whe e
ϕ(s) = s0:


s0.b =s.b mod |M0|,
s0.e =s.e mod |M0|,
s0.z =s.z
(2)
Ti le Supp essed Due o Excessi e Leng h 9
ALGORITHM 1: Model o calcula e he ecei e communica ion pa -
e n o a SPMD block, o a gi en da a s uc u e A.
Inpu :
P: Numbe o p ocesses;
myRank: Local p ocess id;
L(): Mapping unc ion;
−→
δ: Symbolic pa ame e s;
|A0|: Ca dinali y o he 1-D a ay;
WA,k
I(): Func ion o compu e he wo king inpu se ;
ψ(), ϕ(): Pe iodic ans o ming unc ions
Ou pu :CR: Se o comm- uples ha indica es da a o be ecei ed
CR← ∅
o p: 1 o P do
lp ←L(p)
o all s∈T(WA,k
I(myRank, L, −→
δ)) do
s0←s∩lp.S0
i s06=∅ hen
mp0← ∅
i p6=myRank and s∈S◦ hen
mp0←s0
end
i s∈ψ(S−) hen
mp0←s0− |A0|
end
i s∈ϕ(S+) hen
mp0←s0+|A0|
end
CR←CR∪ hp, h mp0ii
end
end
end
A unc ion T:D∗
n→D∗
n ans o ms he wo king inpu se by applying
he wo p e ious unc ions o eloca e all he indexes back in o he o iginal
a ay domain, as i was showed in S age 3 o Fig. 3. We can exp ess he
ans o ma ion wi h he ollowing unc ion:
T(WA,k
I(p, L, −→
δ)) = 


i s ∈S−;s0=ψ(s),
i s ∈S◦;s0=s,
i s ∈S+;s0=ϕ(s)
(3)
An example o he applica ion o T(WA,k
I(p, L, −→
δ) o he illus a i e ex-
ample can be seen also in S age 3 on he igh o Fig. 3.
Algo i hm 1 uses a simpli ied one-dimensional model o calcula e he da a
o be ecei ed a any p ocess. The ou pu is a se o communica ion uples
(CR). A comm- uple hp, D∗iassocia es he index o he emo e p ocess p, wi h
he se o indexes D∗o he s uc u e whose da a alues should be communi-
ca ed. Fo each da a s uc u e, he local p ocess, named myRank, calcula es
he exac da a o be ecei ed om a emo e p ocess p. In o de o do ha ,
16 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
Table 3 Compa ison o de elopmen e o measu es o h ee case s udies.
KDSI McCabe’s C.C. Hals ead D.E.
T asgo 24 6 74K
Ro a e C+MPI 62 21 1 890K
Reduc ion 61.29% 71.43% 96.08%
T asgo 57 4 19K
Cannon’s MM C+MPI 175 4 122K
Reduc ion 67.43% 0.00% 84.43%
T asgo 772 72 19 477K
NAS MG C+MPI 1389 210 29 568K
Reduc ion 44.42% 65.71% 34.13%
0.0001
0.001
0.01
0.1
1
10
100
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -1d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
0.0001
0.001
0.01
0.1
1
10
100
1000
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -2d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
0.0001
0.001
0.01
0.1
1
10
100
1000
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -3d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
Fig. 8 Compu a ion, communica ion calcula ion, and communica ion execu ion imes in
seconds o he Hea examples on he dis ibu ed-memo y machine (log scale). using he
p oblem sizes o Tab. 1.
o app oaches is ha hese au oma ic calcula ions do no gene a e ce ain
communica ion op imiza ions ac oss SPMD blocks ha could posi i ely im-
pac pe o mance. An open ques ion is whe he hese pa icula op imiza ions
could be applied a e he use o his kind o echniques.
7.3 S udy 2: Ease o p og amming
Ou echnique a oids o he p og amme he managemen o he communica-
ion and/o da a pa i ion codes. This leads o a educ ion on he pa allel p o-
g amming complexi y. Table 3 shows, o ou s udy cases, se e al complexi y
and de elopmen e o me ics, including KDSI me ic used in he COCOMO
model [3] (numbe o lines), McCabes cycloma ic complexi y [18], and Hals ead
de elopmen e o [14]. These me ics a e used o compa e he po en ial p o-
g amming e o needed when using he di e en al e na i es conside ed. We
obse e ha he de elopmen e o needed is highly educed when using ou
app oach. As can be seen in Tab. 3, he educ ions o he di e en me ics
used ange om 44% o 96% in all cases, excep in he McCabe complexi y
o he Cannon’s ma ix mul iplica ion, whe e his measu e is ex emely low
in bo h codes.
7.4 S udy 3: Rela i e cos o calcula ing communica ions
Ou echnique o calcula e he communica ion pa e ns is pe o med a un-
ime. In his sec ion we show an expe imen al s udy whe e we ocus on he cos

Ti le Supp essed Due o Excessi e Leng h 17
0.0001
0.001
0.01
0.1
1
10
100
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -1d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
0.0001
0.001
0.01
0.1
1
10
100
1000
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -2d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
0.0001
0.001
0.01
0.1
1
10
100
1 4 8 16 32 64
Execu ion ime (sec.)
P ocesses
Hea -3d: Communica ion and compu a ion imes
Compu a ion
Comm. Execu ion
Comm. Calcula ion
Fig. 9 Compu a ion, communica ion calcula ion, and communica ion execu ion imes in
seconds o he Hea examples on he sha ed-memo y machine (log scale) using he p oblem
sizes o Tab. 1.
o ou calcula ion and synch oniza ion imes wi h espec o he main compu-
a ion imes. The expe imen was execu ed in wo di e en a chi ec u es, he
dis ibu ed- and he sha ed-memo y machines, CETA and A las.
Figu e 8 and 9 show he measu es o he compu a ion and he communica-
ion imes, also sepa a ing in communica ion calcula ion and communica ion
execu ion imes. We show esul s o he pe iodic e sions o he Hea -1d,
Hea -2d and, Hea -3d benchma ks [5], o di e en numbe o MPI p ocesses
launched (no ice he loga i hmic scale in he plo s). We see ha he com-
pu a ion ime dec eases when he numbe o p ocesses inc eases, excep in
one si ua ion (Hea -2D wi h 8 p ocesses in he dis ibu ed-memo y sys em).
This phenomenon is no ela ed o he da a communica ion ha is he ocus
o his s udy. We also obse e ha he ime spen by ou echnique in he
un ime calcula ion o he communica ion pa e ns inc eases wi h he numbe
o p ocesses, as expec ed. Howe e , hese imes can be conside negligible, as
hey a e se e al o de s o magni ude smalle han he compu a ion and he
communica ion execu ion imes.
In summa y, ou echnique au oma ically and e icien ly calcula es a un-
ime he communica ion pa e ns needed in a dis ibu ed-memo y pa allel
p og am wi h pe iodic access exp essions, allowing he selec ion a un ime o
he pa i ion policies, and he choice o he p ope ile sizes o he cu en
execu ion pla o m.
8 Conclusion
This pape desc ibes a echnique ha calcula es a un ime exac agg ega ed
coa se-g ained dis ibu ed-memo y communica ions, o algo i hms wi h a ine
exp essions wi h pe iodic bounda y condi ions. I is based on: (1) calcula ing
a un ime di e en oo p in s h ough cu ing-and-pas ing me hods in e ms
o he mapping unc ions chosen and, (2) in e sec ing a un ime he emo e
and local oo p in s. Pe o mance esul s o six cases o s udy, including a
eal-wo ld benchma k, indica e ha using ou echnique, we ob ain simila
e iciency o op imized MPI codes, while he de elopmen e o is educed.
Fu u e wo k includes he applicabili y o he p oposed echnique in cu en
polyhed al model amewo ks.
18 Ana Mo e on-Fe nandez, A u o Gonzalez-Esc ibano
Acknowledgemen s This esea ch has been pa ially suppo ed by MICINN (Spain) and
ERDF p og am o he Eu opean Union: HomP og-He Sys p ojec (TIN2014-58876-P), CAPAP-H6
Ne wo k (TIN2016-81840-REDT), and COST P og am Ac ion IC1305: Ne wo k o Sus ainable
Ul ascale Compu ing (NESUS). By he compu ing acili ies o Ex emadu a Resea ch Cen e o
Ad anced Technologies (CETA-CIEMAT), unded by he Eu opean Regional De elopmen Fund
(ERDF). CETA-CIEMAT belongs o CIEMAT and he Go e nmen o Spain.
Re e ences
1. Bailey, D., Ha is, T., Saphi , W., an de Winjgaa , R., Woo, A., Ya ow, M.: The
NAS Pa allel Benchma ks 2.0. Repo RNR-95-020, NASA Ad anced Supe compu ing
(NAS) Di ision (1995)
2. Bikshandi, G., Guo, J., Hoe linge , D., Almasi, G., F aguela, B.B., Ga za n, M.J.,
Padua, D., on P aun, C.: P og amming o pa allelism and locali y wi h hie a chi-
cally iled a ays. In: P oc. o he ACM SIGPLAN PPoPP, pp. 48–57. ACM, New
Yo k, New Yo k, USA (2006)
3. Boehm, B.W., e al.: So wa e enginee ing economics, ol. 197. P en ice-hall Englewood
Cli s (NJ) (1981)
4. Bondhugula, U.: Compiling a ine loop nes s o dis ibu ed-memo y pa allel a chi ec-
u es. In: P oc. SC’2014. ACM, Den e , CO, USA (2013)
5. Bondhugula, U., Bandish i, V., Cohen, A., Po on, G., Vasilache, N.: Tiling and op i-
mizing ime-i e a ed compu a ions on pe iodic domains. In: P oceedings o he 23 d
in e na ional con e ence on Pa allel a chi ec u es and compila ion, pp. 39–50. ACM
(2014)
6. Bondhugula, U., Ha ono, A., Ramanujam, J., Sadayappan, P.: A p ac ical au oma ic
polyhed al p og am op imiza ion sys em. In: ACM SIGPLAN Con e ence on P og am-
ming Language Design and Implemen a ion (PLDI) (2008)
7. Bueno, J., Ma o ell, X., Badia, R., Ayguad´e, E., Laba a, J.: Implemen ing OmpSs
suppo o egions o da a in a chi ec u es wi h mul iple add ess spaces. In: P oc.
ICS’13, pp. 359–368. ACM (2013)
8. Cannon, L.: A cellula compu e o implemen he Kalman il e algo i hm. Doc o al
disse a ion, Mon ana S a e Uni e si y Bozeman (1969)
9. Chambe lain, B., Dei z, S., I en, D., Choi, S.E.: Use -de ined dis ibu ions and layou s
in Chapel: Philosophy and amewo k. In: 2nd USENIX Wo kshop on Ho Topics in
Pa allelism (2010)
10. Cha a asi, P., Shi ako, J., Sa ka , V.: Polyhed al op imiza ions o explici ly pa allel
p og ams. In: 2015 In e na ional Con e ence on Pa allel A chi ec u e and Compila ion
(PACT), pp. 213–226. IEEE (2015)
11. Claßen, M., G iebl, M.: Au oma ic code gene a ion o dis ibu ed memo y a chi ec u es
in he poly ope model. In: Pa allel and Dis ibu ed P ocessing Symposium, 2006. IPDPS
2006. 20 h In e na ional, pp. 7–pp. IEEE (2006)
12. Gonzalez-Esc ibano, A., Llanos, D.: T asgo: A nes ed-pa allel p og amming sys em. The
Jou nal o Supe compu ing 58(2), 226–234 (2011)
13. Gonzalez-Esc ibano, A., To es, Y., F esno, J., Llanos, D.: An ex ensible sys em o
mul ile el au oma ic da a pa i ion and mapping. IEEE TPDS 25(5), 1145–1154 (2013).
(doi:10.1109/TPDS.2013.83)
14. Hals ead, M.H.: Elemen s o So wa e Science (Ope a ing and p og amming sys ems
se ies). Else ie Science Inc. (1977)
15. Hi anandani, S., Kennedy, K., Tseng, C.W.: Compiling o an d o mimd dis ibu ed-
memo y machines. Communica ions o he ACM 35(8), 66–80 (1992)
16. Kong, M., Pouche , L.N., Sadayappan, P., Sa ka , V.: Pipes: a language and compile
o ask-based p og amming on dis ibu ed-memo y clus e s. In: P oceedings o he
In e na ional Con e ence o High Pe o mance Compu ing, Ne wo king, S o age and
Analysis, p. 39. IEEE P ess (2016)
17. Kwon, O., Jubai , F., Eigenmann, R., Midki , S.: A hyb id app oach o openmp o
clus e s. ACM SIGPLAN No ices 47(8), 75–84 (2012)
Ti le Supp essed Due o Excessi e Leng h 19
18. McCabe, T.J.: A complexi y measu e. So wa e Enginee ing, IEEE T ansac ions on 4,
308–320 (1976)
19. Meh a, S., Bee aka, G., Yew, P.C.: Tile size selec ion e isi ed. ACM T ansac ions on
A chi ec u e and Code Op imiza ion (TACO) 10(4), 35 (2013)
20. Mo e on, A., Gonzalez-Esc ibano, A., Llanos, D.R.: A un ime analysis o communica-
ion calcula ion. In: P oceedings o he In e na ional Symposium on Code Gene a ion
and Op imiza ion (CGO) (pos e , 2017)
21. Mo e on-Fe nandez, A., Gonzalez-Esc ibano, A., Llanos, D.: Exploi ing dis ibu ed and
sha ed memo y hie a chies wi h Hi map. In: P oc. HPCS’2014, pp. 278–286. Bologna
(I aly) (2014)
22. Mo e on-Fe nandez, A., Gonzalez-Esc ibano, A., Llanos, D.R.: A new high-le el pa allel
po able language o hie a chical sys ems in T asgo. In: Compu a ional and Ma he-
ma ical Me hods in Science and Enginee ing (CMMSE) (2015)
23. Mo e on-Fe nandez, A., Gonzalez-Esc ibano, A., Llanos, D.R.: On he un- ime cos o
dis ibu ed-memo y communica ions gene a ed using he polyhed al model. In: High
Pe o mance Compu ing & Simula ion (HPCS), 2015 In e na ional Con e ence on, pp.
151–159. IEEE (2015)
24. Planas, J., Badia, R., Laba a, E.A.J.: Hie a chical ask-based p og amming wi h
S a Ss. IJHPCA 23(3), 1145–1154 (2009)
25. Randall, D.A., Ringle , T.D., Heikes, R.P., Jones, P., Baumga dne , J.: Clima e mod-
eling wi h sphe ical geodesic g ids. Compu ing in Science and Enginee ing 4(5), 32–41
(2002)
26. Sanz, A., Asenjo, R., L´opez, J., La osa, R., Na a o, A., Li ino , V., Choi, S.E.,
Chambe lain, B.: Global da a e-alloca ion ia communica ion agg ega ion in chapel.
In: P oc. SBAC-PAD’2012. IEEE (2012)
27. Sha ma, A., Smi h, D., Fe guson, M., Koehle , J., Ba ua, R.: A ine loop op imiza ion
based on modulo un olling in chapel. In: P oc. PGAS’2014. ACM, Eugene, OR USA
(2014)
28. S epano , A., Lee, M.: The S anda d Templa e Lib a y. Tech. Rep. 95-11(R.1), HP
Labo a o ies (1995)
29. Upad as a, R., Cohen, A.: Sub-polyhed al scheduling using (uni -) wo- a iable-pe -
inequali y polyhed a. ACM SIGPLAN No ices 48(1), 483–496 (2013)
30. Ve doolaege, S.: Isl: An in ege se lib a y o he polyhed al model. In: Ma hema ical
So wa e–ICMS 2010, pp. 299–302. Sp inge (2010)
31. Yuki, T., Rajopadhye, S.: Pa ame ically iled dis ibu ed memo y pa alleliza ion o
polyhed al p og ams. Tech. Rep. CS13-105, Colo ado S a e Uni e si y (2013)