A Run ime Analysis Fo Communica ion
Calcula ion on Dis ibu ed-Memo y Sys ems
Ana Mo e on-Fe nandez
Depa amen o de In o m´
a ica, Edi .
Tec. de la In o maci´
on, Uni e sidad
de Valladolid, Valladolid, Spain
ana@in o .u a.es
A u o Gonzalez-Esc ibano
Depa amen o de In o m´
a ica, Edi .
Tec. de la In o maci´
on, Uni e sidad
de Valladolid, Valladolid, Spain
a[email p o ec ed]
Diego R. Llanos
Depa amen o de In o m´
a ica, Edi .
Tec. de la In o maci´
on, Uni e sidad
de Valladolid, Valladolid, Spain
diego@in o .u a.es
Abs ac
Pa allel machines a e becoming mo e he e ogeneous, mix-
ing de ices wi h di e en capabili ies in he con ex o
hyb id clus e s, wi h hie a chical sha ed- and dis ibu ed-
memo y le els. P og amming o hese he e ogeneous sys-
ems is challenging and e o -p one. Many au oma ic code
gene a ion app oaches ha e been p oposed o ans o m
high-le el pa allel p og ams o sequen ial codes o low-
le el pa allel p og ams o hyb id clus e s wi h dis ibu ed
memo y. Many o hese dis ibu ed-memo y app oaches a e
based on compile- ime au oma ic solu ions [1–3]. These
echniques abs ac many issues ela ed o he execu ion pla -
o m, while s ill deli e good pe o mance. Howe e , hey
gene a e a gene ic code ha canno ake in o accoun some
speci ic de ails abou he inal machines whe e he applica-
ion would be execu ed. As example, he mos sophis ica ed
code gene a o s o dis ibu ed memo y (in e ms o da a
olume communica ed, and pa ame ic in he numbe o
p ocesses and p oblem sizes) s ill needs o ix a single ile
size a compile ime, e en i he dis ibu ed sys em has nodes
wi h di e en capabili ies.
On he o he hand, compile scalabili y is a well known
p oblem. Cu en ly, acco ding o [4], he cos ly in ege p o-
g amming algo i hms used o gene a e op imized codes
make hei use imp ac ical in eal scien i ic applica ions o
he common use s.
We p opose o mo e o un ime pa o he compile-
ime analysis needed o gene a e he communica ion code
o dis ibu ed-memo y sys ems. Communica ion s ages on
dis ibu ed-memo y sys ems ha e a signi ican impac on
pe o mance, hus he educ ion o he communica ion imes
is key o imp o ing pe o mance in e ms o un ime execu-
ion. We ha e de eloped a echnique ha uses a hie a chical
iling a ay lib a y o ep esen and manage ec angula in-
dex spaces a un ime. The da a o be ecei ed and/o sen by
a local p ocess o ano he one is calcula ed by in e sec ing
he se o indexes ead o w i en by a p ocess wi h he se o
indexes w i en o ead by he local p ocess.
The main ad an age o ou echnique is ha i au oma i-
cally compu es, a un ime, he exac coa se-g ained commu-
nica ions o be used by a dis ibu ed message-passing model.
By exac communica ions we mean: a) only needed da a a e
communica ed; (b) each needed da a elemen is communi-
ca ed o a a ge p ocess only once ( edundan communica-
ion is a oided due o he un ime analysis); and c) no con-
ol in o ma ion exchange is needed. Addi ionally, he com-
munica ions pe o med a e coa se-g ained. Communica ion
calcula ion is done once o he whole index space mapped
o a p ocess a un ime, independen ly o he numbe o he
sizes o iles gene a ed inside he p ocess a e wa ds. This
also allows he use, in he same compu a ion, o di e en ile
sizes o di e en p ocesses a he same hie a chical le el, a
use ul ea u e o dis ibu ed-memo y sys ems ha include
machines wi h di e en a chi ec u es [5].
Ou expe imen al esul s o se e al cases o s udy indi-
ca e ha , despi e ou un ime calcula ion, we ob ain simila
esul s o op imized codes di ec ly w i en wi h MPI and we
ou pe o m he esul s o o he communica ion code gene a-
o s.
Re e ences
[1] U. Bondhugula. Compiling a ine loop nes s o dis ibu ed-
memo y pa allel a chi ec u es. In 2013 SC-In e na ional Con-
e ence o High Pe o mance Compu ing, Ne wo king, S o age
and Analysis (SC), pages 1–12. IEEE, 2013.
[2] M. Claßen and M. G iebl. 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, pages 7–pp. IEEE, 2006.
[3] O. Kwon, F. Jubai , R. Eigenmann, and S. Midki . A hyb id
app oach o openmp o clus e s. In P oceedings o he 17 h
ACM SIGPLAN symposium on P inciples and P ac ice o Pa -
allel P og amming (PPoPP), 2012.
[4] S. Meh a and P.-C. Yew. Imp o ing compile scalabili y: op-
imizing la ge p og ams a small p ice. In P oceedings o he
36 h ACM SIGPLAN Con e ence on P og amming Language
Design and Implemen a ion (PLDI), 2015.
[5] S. Meh a, G. Bee aka, and P.-C. Yew. Tile size selec ion e is-
i ed. ACM T ansac ions on A chi ec u e and Code Op imiza ion
(TACO), 10(4):35, 2013.
12016/11/17