Communica o s: An abs ac ion
o ease he use o ha dwa e accele a o s
Alejand o Alonso-Mayo
Uni e sidad de Valladolid
alejand o.alonso.may[email p o ec ed]
Hec o O ega-A anz
Dep . In o m´
a ica
Uni e sidad de Valladolid
hec o @in o .u a.es
A u o Gonzalez-Esc ibano
Dep . In o m´
a ica
Uni e sidad de Valladolid
a u o@in o .u a.es
Abs ac
Nowadays he use o ha dwa e accele a o s, such as he G aphics
P ocessing Uni s (GPUs) o XeonPhi cop ocesso s, is key o sol e
compu a ionally cos ly p oblems ha equi e High Pe o mance
Compu ing (HPC). Howe e , p og amming solu ions o an e i-
cien deploymen in his kind o de ices is a e y complex ask ha
elies on he manual managemen o memo y ans e s and con ig-
u a ion pa ame e s. The p og amme has o ca y ou a deep s udy
o he pa icula da a needed o be compu ed in each momen a he
di e en compu ing pla o ms conside ing a chi ec u al de ails.
We in oduce he communica o concep as an abs ac en i y
ha allows he p og amme o easily manage he communica ions
and ke nel launching de ails on ha dwa e accele a o s o mul i-co e
de ices in a anspa en way. Fu he mo e, his model also gi es
he possibili y o he p og amme o launching CPU ke nels in he
mul i-co e p ocesso s wi h he same abs ac ion and me hodology
used o he accele a o s. In his way, he bu den o coding wo
di e en codes o managing he di e en compu a ional de ices is
alle ia ed.
Addi ionally, his en i y allows he p og amme o simpli y he
p ope selec ion o alues o ke nel-launching con igu a ion pa-
ame e s. This is done h ough a simple cha ac e iza ion p ocess o
he ke nel code o be execu ed. A p og amming model in ol ing
he communica o en i y is desc ibed in his a icle.
Finally, we also p esen a p o o ype lib a y ha implemen s he
communica o model, oge he wi h i s applica ion in se e al s udy
cases. I s use has led o educ ions in he de elopmen cos s wi h
signi ican ly low o e heads in he execu ion imes when compa ed
o manually p og ammed and op imized solu ions using CUDA and
OpenMP di ec ly.
Ca ego ies and Subjec Desc ip o s D.3.2 P og amming Lan-
guages [Language Classi ica ions]: Concu en , dis ibu ed, and
pa allel languages
Gene al Te ms Pa allel p og amming, So wa e
Keywo ds Communica o s, CUDA, GPUs, Ke nel cha ac e iza-
ion, Memo y ans e s, Op imiza ions
Pe mission o make digi al o ha d copies o all o pa o his wo k o pe sonal o
class oom use is g an ed wi hou ee p o ided ha copies a e no made o dis ibu ed
o p o i o comme cial ad an age and ha copies bea his no ice and he ull ci a ion
on he i s page. Copy igh s o componen s o his wo k owned by o he s han ACM
mus be hono ed. Abs ac ing wi h c edi is pe mi ed. To copy o he wise, o epublish,
o pos on se e s o o edis ibu e o lis s, equi es p io speci ic pe mission and/o a
ee. Reques pe missions om [email p o ec ed].
CONF ’yy, Mon h d–d, 20yy, Ci y, ST, Coun y.
Copy igh c
20yy ACM 978-1-nnnn-nnnn-n/yy/mm. . . $15.00.
h p://dx.doi.o g/10.1145/nnnnnnn.nnnnnnn
1. In oduc ion
Cu en ly, he sys ems used o High Pe o mance Compu ing
(HPC) include accele a o de ices. This end is no iceable om
pe sonal compu e s o classical supe compu e s. Examples o hese
HPC he e ogeneous en i onmen s can be seen in he i s posi ions
o he op 500 lis o cu en supe compu e s [15].
When de eloping solu ions o be deployed in he e ogeneous
sys ems we can: (1) Use a single p og amming model esponsi-
ble o managing he a chi ec u al and concep ual di e ences be-
ween he di e en compu a ional de ices, e.g. OpenACC [1]; o
(2) Use a combina ion o di e en p og amming models speci ic
o each kind o compu a ional de ices, e.g. MPI [9] oge he wi h
CUDA [8] o OpenCL [13], and OpenMP [3], as in he wo ks [2, 7].
One o he main d awbacks o he i s app oach is he di icul
o ep esen i egula p og ams wi h non- i ial communica ions o
synch oniza ions. Besides, he inal gene a ed code esul ing om
p og amming wi h his kind o models is no usually op imized as
he o iginal code. Mo eo e , he possible op imiza ions a p og am-
me can ob ain, by selec ing p ope alues o ke nel-launching
con igu a ion pa ame e s, a e no conside ed in he OpenAcc s an-
da d.
On he o he hand, implemen ing solu ions ollowing he second
app oach equi es he p og amme o ha e a deepe knowledge o
he di e en pa allel p og amming models in ol ed. Addi ionally,
she is he inal esponsible o p ope ly managing he da a ans e
among he di e en memo y spaces o he compu a ional de ices,
a he mos app op ia e imes, and o choose p ope alues o
ke nel-launching con igu a ion pa ame e s. Howe e , his gi es o
he p og amme he possibili y o op imize he use o he pa icula
esou ces o each speci ic de ice.
The e a e many lib a ies o speci ic unc ions o pa icula
ields, o de ices, ha include small abs ac ions o ease he man-
agemen be ween he accele a o and he hos (e.g. MCUDA [14]
o hiCUDA [6]), bu wi hou conside ing guided op imiza ions.
In his a icle is p esen ed he concep o communica o as an
abs ac en i y ha allows he p og amme o anspa en ly man-
age he launching o se ies o asks on accele a o de ices, and/o
mul i-co e CPU p ocesso s. This en i y uses he mos app op ia e
p og amming models (CUDA, OpenMP, ...) o con ol he com-
pu a ional esou ces o he accele a o s and hos s machines. The
communica o model includes wo ea u es: (1) An op imiza ion
sys em o selec p ope alues o ke nel-launching con igu a ion
pa ame e s, guided by simple code cha ac e iza ions p o ided by
he p og amme ; (2) a anspa en mechanism o memo y manage-
men , including op imized communica ions o he da a s uc u es
be ween he hos and he co esponding images in he accele a o s;
and (3) an abs ac ion o indexed da a s uc u es ha allows o cod-
i y simple ke nels ha can be used o di e en kinds o de ices
(such as GPUs, o mul i- h eaded ec o ial CPU co es) wi h none
o minimal changes.
A p o o ype ha implemen s he concep o his en i y is also
desc ibed in his a icle. This p o o ype is designed o exploi ing
NVIDIA GPUs using he CUDA pa allel p og amming model, o
he mul i-co e CPUs using OpenMP. Toge he wi h he desc ip ion
o he p o o ype, i is p esen ed an expe imen al s udy based on
h ee s udy cases (ma ix addi ion, ma ix mul iplica ion, and a
simple Jacobi s encil p og am). The s udy shows how he use o
he p o o ype implies a educ ion o he p og amming e o needed
when w i ing hese applica ions, compa ed o c ea ing hem using
he speci ic pa allel p og amming models. Besides, he use o he
p o o ype does no in oduce signi ican o e heads.
The s uc u e o he a icle is as ollows. Sec ion 2 p esen s
he communica o model. Sec ion 3 explains he in e ace o ou
lib a y, and i s usage o de elop a p og am. Sec ion 4 poses he
expe imen al se up which esul s a e p esen ed in Sec . 5. Finally,
Sec . 6 desc ibes he conclusions o his wo k and he di ec ions
ha can be add essed in u u e i e a ions.
2. Communica o Model
The communica o model in oduces a simpli ied way o p og am
applica ions ha can exploi he e ogeneous compu a ional pla -
o ms including accele a o s o /and mul i-co e CPUs. Communica-
o s coo dina e he execu ion o se ies o ke nels. These ke nels a e
speci ic unc ions, ha a e managed by he communica o en i ies.
Communica o s au oma ically manage he:
•Ke nel launching, ha is he deploymen /execu ion o se-
quences o unc ion ke nels in he compu a ional pla o m. The
communica o s can include policies o exploi concu en ke -
nel echniques, in e lea e compu a ions wi h communica ions,
o eo de he sequence o ke nels.
•Con igu a ion, ha is he layou o ce ain compu a ional pla -
o m a iables and con igu a ion pa ame e s in o de o ob ain
a pa icula execu ion beha io .
•Communica ions, ha a e he da a ans e s ca ied ou among
he memo ies o he hos and he accele a o s. No e ha his
o loading is only equi ed when he model launches execu ions
in accele a o de ices.
2.1 Ke nel launching
Ke nel launching is an ope a ion ha enqueues in a communica o
he o de o execu e a ke nel, wi h gi en eal pa ame e s, when he
associa ed de ice (accele a o o CPU co es) is a ailable. This is
done h ough a launching p imi i e. The communica o in e nally
ensu es ha he inpu da a has been ans e ed and p e ious ke nels
ha e ended be o e p oceeding o do he eal launch. The commu-
nica o execu ion policy could eo de he ke nels in he queue o
maximize he execu ion e iciency as a as he inpu /ou pu depen-
dencies ac oss ke nels a e no iola ed.
2.2 Con igu a ion o ke nels o execu ion
Ou model conside s wo main kinds o in o ma ion ha a e needed
a he communica o in e nals o choose p ope ke nel-launching
pa ame e s, and manage he de ice memo y:
(a) Ke nel code cha ac e iza ion in e ms o pa ame e s ela ed o
global memo y access pa e ns, compu a ional load a io, and
da a sha ing ac oss block a io.
(b) The inpu /ou pu ole o he ke nel pa ame e s. Wi h his in-
o ma ion he communica o can con ol which da a ans e s
among di e en memo ies a e needed.
2.3 Communica ions
Accele a o s may ha e hei own memo y spaces, o cing o ans-
e he da a o be p ocessed, and he ob ained esul s, be ween he
memo y o he hos pla o m and he memo y o he de ice accel-
e a o . The manual managemen o his ans e ing is cumbe some
and e o -p one. Mo eo e , i is di icul o p edic in ad ance when
asynch onous da a ans e s a e possible, o when da a should s ay
in he accele a o de ice memo y, as his depends on he exac se-
quence o ke nel launching. A communica o is associa ed, in he
momen o i s c ea ion, wi h a pa icula accele a o , and i ans-
pa en ly manages he a iable images o he memo y space o he
de ice.
The communica o can decide when and how hese ans e s
should be ca ied ou , depending on hei use inside hei co -
esponding ke nels and he ke nels enqueued o launching. The
model also allows he p og amme o use he o iginal names o he
a iables ins ead o de ining hei co esponding images in he ac-
cele a o de ice.
Depending on he ea u es o he used a iables inside hese
con ex s we can dis inguish wo ypes: Binded a iables and in-
e nal a iables.
Binded a iables
Binded a iables a e hos a iables ha ha e an image in he mem-
o y space o he accele a o . The model allows o bind on a hos
a iable o he communica o . Since hen, i becomes binded, and
i s da a should no be modi ied by he p og am a he hos side un il
an unbinding ope a ion is applied on i .
The i s ke nel equi ing he use o a binded a iable as an inpu
(IN ole) will o ce he communica o o anspa en ly ensu e ha
i s da a ha e been ans e ed. Applying an unbinding ope a ion
o a binded a iable will o ce he ans e o i s da a om he
accele a o o he hos i i is an ou pu a iable (OUT ole). The
main p og am wai s o he end o he ke nels using he a iable
and ansmission o he da a.
In e nal a iables
In e nal a iables a e a iables whose scope is delimi ed o he
code execu ed in he accele a o . They a e only handled inside he
memo y space o he de ice, and hey will no ha e alloca ion in he
hos memo y space. Thus, he da a a e no going o be ans e ed
o he hos memo y.
They a e c ea ed in he communica o h ough an ope a ion ap-
plied o he hos a iable. The p og amme decla es a da a s uc u e
wi hou alloca ing i in he hos . This is done jus o clone he ype,
size, and s uc u e in he communica o memo y space. Since his
momen , he image o his a iable could be used by he ke nels
launched in his communica o . To des oy an in e nal a iable i is
needed o apply ano he ope a ion using he e e ence name o he
hos a iable.
3. Communica o Lib a y In e ace
We ha e designed a lib a y implemen a ion o he communica o
model. In ou implemen a ion, a ke nel is a unc ion coded o a
compu a ional de ice wi h pa icula inpu /ou pu pa ame e s. The
communica o lib a y in e ace de ines p imi i es o:
1/* Communica o c ea ion . */
2Comunica o comGPU , comCPU ;
3CommC ea e (& comGPU , COMM_GPU , 2);
4CommC ea e (& comCPU , COMM_CPU );
5
6/* Tile decla a ion and alloca ion . */
7Hi Tile_ loa ma ixHos ;
8Hi Tile_ loa ma ixIn e nal;
9hi _ ileDomainAlloc (& ma ixHos , loa ,
10 2, ows , columns );
11 hi _ ileDomain (& ma ixIn e nal , loa ,
12 2, ows , columns );
13
14 /* Tile ini ializa ion. */
15 CommA ach (&comGPU , & ma ixHos );
16 CommIn e nalC ea e (& comGPU , & ma ixIn e nal );
17 CommLaunch (& comGPU , copyCell , _con ig ,
18 2, ma ixIn e nal , ma ixHos );
19 CommLaunch (& comGPU , upda eCell , _con ig ,
20 2, ma ixHos , ma ixIn e nal );
21
22 /* Use code
23 * ( no modi ying binded a iables ) */
24 ...
25
26 /* Unbinding and eeing esou ces . */
27 CommDe ach (&comGPU , & ma ixHos );
28 CommIn e nalDes oy (& comGPU ,& ma ixIn e nal );
29 CommDes oy (& comGPU );
30 CommDes oy (& comCPU );
Figu e 1. Example o main code using he communica o s p imi-
i es.
A) C ea e o communica o s,
B) Decla e he ke nels,
C) Cha ac e ize he ke nels,
C) Decla e da a s uc u es o anspa en memo y managemen o
di e en de ices, and
D) Launch he ke nels.
3.1 C ea ion o communica o s
A communica o is associa ed o a pa icula compu a ional pla -
o m (accele a o o CPU-co es se ) a he momen o i s c ea ion,
in o de o use he speci ic collec ion o unc ions ela ed o he as-
signed de ice. This is done h ough he CommC ea e unc ion. This
p imi i e has wo main pa ame e s: The name o he communica o
a iable, and he associa ed compu ing de ice. Fo he e ogeneous
sys ems hos ing mo e han one accele a o o a kind i is needed
he iden i ica ion numbe . Lines 3 and 4 o Fig. 1 show examples o
c ea ing communica o s associa ed o he hi d GPU o he sys em,
and associa ed o he ull se o CPU co es, espec i ely. A e us-
ing i , he p og amme can ee i s esou ces wi h he CommDes oy
unc ion (see Fig. 1, lines 29 and 30).
3.2 Decla a ion and con igu a ion o ke nels
A ke nel is decla ed by using he p imi i e KERNEL < ype>. Whe e
ype may be emp y o indica e a ke nel usable on any kind o
de ice, o a speci ic alue o a gi en ype o de ice. This is
use ul when di e en op imiza ions on he ke nel code a e equi ed
o di e en de ices. Cu en ly, he lib a y suppo s he speci ic
p imi i es KERNEL GPU and KERNEL CPU o NVIDIA GPUs and
se s o CPU co es.
1/* S uc u ed ype de ini ion :
2* Hi Tile_ loa */
3hi _ ileNewType ( loa );
4
5
6/* Ke nel cha ac e iza ions */
7
8KERNEL_CHAR (copyCell ,1,de ,de ,de )
9KERNEL_CHAR ( upda eCell ,1 , ull ,low , high )
10
11
12 /* Ke nel codes */
13
14 KERNEL ( copyCell , 2,
15 OUT , Hi Tile_ loa *, a _ds ,
16 IN , Hi Tile_ loa *, a _s c ){
17
18 /* code o copyCell ke nel */
19 }
20
21 KERNEL ( upda eCell , 2,
22 OUT , Hi Tile_ loa *, a _ds ,
23 IN , Hi Tile_ loa *, a _s c ){
24
25 /* code o upda eCell ke nel */
26 }
Figu e 2. Examples o ke nel cha ac e iza ions (KERNEL CHAR
p imi i es), and ole assignmen o he ke nel pa ame e s (KERNEL
p imi i es).
This p imi i e decla es in b acke s he numbe o pa ame e s he
ke nel needs and a uple o in o ma ion o each pa ame e wi h:
•I s co esponding ole:
IN: o inpu pa ame e s,
OUT: o ou pu pa ame e s, and
IO: o inpu and ou pu pa ame e s;
•The ype o he a iable; and
•The name o he a iable.
This con igu a ion allows he communica o s o de e mine i i
is necessa y o ca y ou da a ans e s wi h he main memo y o
he hos , o he case o accele a o de ices wi h sepa a ed memo y
spaces.
The p imi i e is ollowed by a s uc u ed block wi h he ke nel
code. Thus, i esembles a C unc ion heade . Lines 14 and 21 o
Fig. 2 show some examples o he use o his p imi i e.
3.3 Ke nel cha ac e iza ion
The ke nel cha ac e iza ion is a p ocess ha ob ains pa ame e ized
alues o special code ea u es ollowing a pa icula model. The
p o o ype lib a y uses he model p esen ed in he wo ks o [11, 16].
This cha ac e iza ion allows he communica o o au oma ically de-
cide which a e p ope alues o he GPU con igu a ion pa ame e s
(g id, h eadblock and L1 cache memo y sizes), and CPU h eads
g anula i y, in o de o imp o e pe o mance.
The p imi i e KERNEL CHAR, aken om [12], is used o p o ide
o he communica o he cha ac e iza ion o he ke nels ollowing
he ci ed model. The co esponding pa ame e s o he p imi i e a e
he ollowing:
a) Ke nel name,
b) Numbe o dimensions o he h eads se o he ke nel. The
alues can be 1, 2, o 3.
c) Memo y access pa e n: Deno es he way he h eads will access
o memo y. The alues can be ull (-coalesced), medium (-
coalesced), o sca e .
d) Compu a ional load a io: Numbe o a i hme ic/logic ope a ion
s. numbe o global memo y accesses. The alues can be high,
medium, o low.
e) Da a sha ing ac oss blocks: a io o da a sha ing compa ed o
he numbe o memo y accesses pe h ead. The alues can be
high, medium, o low.
Fo he case ha he p og amme is no able o pe o m he cha -
ac e iza ion o code pa ame e s (c, d, and e), we ha e added he
possibili y o use he oken de , ha will assign a de aul con ig-
u a ion. The pa icula alues o he de aul con igu a ion, aken
om he de aul con igu a ion o [12], (256 h eads pe block, aug-
men ed L1 cache size o NVIDIA GPUs) a e expec ed o p ope ly
wo k o he gene al case. Lines 8 and 9 o Fig. 2 show some exam-
ples o using his p imi i e, wi h he de aul con igu a ion and wi h
a pa icula ke nel cha ac e iza ion, espec i ely.
3.4 Da a s uc u es
Rega ding he da a s uc u es ha he model handles, we ha e de-
cided o use he Hi Tile s uc u e, an abs ac en i y o a ays and
iles. This s uc u e is de ined in Hi map [5], an e icien lib a y
o hie a chical iling and mapping o a ays. The Hi Tiles, in he
Hi map lib a y, a e da a s uc u es simila o n-dimensional a ays
ha allow an ad anced binding and pa i ioning, o c ea e sub iles
om ano he ile, o clone iles, e c. When c ea ing a Hi Tile a i-
able, we can speci y i s domain by a selec ion o a subspace o
a ay indexes, also known as shape (see Appendix A o a quick
o e iew o he Hi map lib a y).
Hi map also allows o pe o m communica ions be ween com-
pu ing machines in an easy way h ough an abs ac in e ace ha
in e nally uses a message passing pa adigm (exploi ing MPI). The
access o he elemen s o hese da a s uc u es is done using Hi map
access unc ions. They a e designed o maximum e iciency, and
a e used anspa en ly in he hos , o in he accele a o s, indepen-
den ly o he in e nal da a layou [5]. Thus, i p o ides an homoge-
neous in e ace o manage da a s uc u es in bo h, hos and accele -
a o de ice ke nels.
Binding a iables
In he p oposed in e ace, he unc ion CommA ach binds a ile
de ined in he code o he hos wi h a communica o . A e his
binding he hos should no manipula e he ile un il i is unlinked
by he unc ion CommDe ach.
The pu pose o a oiding he hos o modi y he ile is o delega e
he esponsibili y o keeping he da a cohe ence be ween he hos
a iable and i s co esponding image on he accele a o o he
communica o . In his way, he p og amme can w i e p og ams
wi hou being he esponsible o he ans e s. Fo he pa icula
case o communica o s associa ed o CPU p ocesso s he e is no
need o ans e ing hese da a because hey a e al eady he e. The
communica o associa ed o he CPU p ocesso is able o no ice his
ac and a oids o duplica e he da a.
Bo h he a ach and de ach unc ions ha e wo pa ame e s: The
communica o , and he poin e o he ile a iable o be binded/un-
binded. Lines 15 and 27 o Fig. 1 show examples o he c ea ion o
a link be ween a a iable and a communica o , and he co espond-
ing unbinding, espec i ely.
C ea ing in e nal a iables
The unc ion CommIn e nalC ea e c ea es an in e nal de ice
a iable and associa es i o a speci ic communica o . On he o he
hand, he unc ion CommIn e nalDes oy is used o ee he
memo y space in he assigned compu a ional de ice.
Bo h unc ions ecei e wo pa ame e s: The communica o , and
he poin e o a de ined ile a iable. Fo he case o communica o s
associa ed o accele a o s, his kind o a iables does no need
o ha e alloca ed memo y in he hos side. The communica o
will be he esponsible o ese ing he space in he memo y o
he co esponding compu ing de ice. Lines 16 and 28 o Fig. 1
show examples o he associa ion o an in e nal a iable wi h a
communica o , and he co esponding libe a ion, espec i ely.
3.5 Ke nel launching
The unc ion CommLaunch is used o launch a ke nel o he com-
pu a ional de ice o a communica o . The launched ke nel will be
enqueued, and e en ually execu ed wi h he co esponding con igu-
a ion de i ed om he in o ma ion p o ided by he p imi i es p e-
iously explained in Sec . 3.2.
The unc ion has he ollowing pa ame e s:
•The communica o ,
• he name o he ke nel,
• he index space o he h ead se ,
• he numbe o pa ame e s equi ed by he ke nel, and
• he eal pa ame e s o he ke nel execu ion.
These pa ame e s should be a iables associa ed o a communi-
ca o : In e nal o binded. Lines 17 and 19 o Fig. 1 show examples
o he launch o wo di e en ke nels.
4. Expe imen al Se up
This sec ion desc ibes he expe imen s we ha e ca ied ou o
check he unc ionali y and e alua e po en ial pe o mance issues
in oduced by he communica o p o o ype h ough he e alua ion
o he implemen ed p o o ype. We also e alua e he de elopmen
e o o using he communica o p o o ype when compa ed o
di ec ly using common na i e p og amming models (CUDA o
OpenMP).
4.1 Ta ge a chi ec u es
The hos machine used o he expe imen al e alua ion is an In-
el(R) Xeon [email p o ec ed], wi h 24 CPU co es and a global
memo y o 32GB DDR3 unning a Cen os 7 OS (Chime a). The
hos ed accele a o de ice is a NVIDIA GeFo ce GTX Ti an Black,
wi h a Keple GK110B a chi ec u e. The expe imen s ha e been
ca ied ou using GCC 4.8.3, wi h he O3 lag, and he CUDA
oolki 7.5, wi h he co esponding a chi ec u al lag a ch=sm 35.
We use also a pu e sha ed-memo y machine (He acles), a Dell
Powe Edge R815 se e , wi h 4 AMD Op e on 6376 p ocesso s a
2.3 GHz, wi h 16 co es each, and 64 co es in o al.
4.2 Case s udies
We ha e p og ammed solu ions o he ollowing h ee p oblems:
Ma ix addi ion (MA), Ma ix mul iplica ion (MM), and he Jacobi
PDE sol e (JS). Figu e 3 shows he implemen a ion o he ke nels
used o he implemen ed solu ions and Fig. 4 shows hei cha ac-
e iza ion.
Ma ix addi ion
The Ma ix addi ion consis s on he sum o wo di e en ma ices,
ha s o ing he esul in a hi d one: C=A+B. The compu a ion
1/* **** Ma ix addi ion , same ke nel o CPU and GPU *********************************** */
2KERNEL ( k_ma , 3, IN , Hi Tile_in *, a , IN , Hi Tile_in *, b , OUT , Hi Tile_in *, c ){
3 o (in k =0; k <100; k ++){
4hi _ ileElemA (*c , 2, h ead .x, h ead .y) += hi _ ileElemA (*a , 2, h ead .x, h ead .y) +
5hi _ ileElemA (*b , 2, h ead .x, h ead . y);
6}
7}
8
9/* **** Ma ix mul iplica ion , same ke nels o CPU and GPU ***************************** */
10
11 KERNEL_GPU (k_mm , 3, IN , Hi Tile_in *, a, IN , Hi Tile_in *, b, OUT , Hi Tile_in *, c){
12 o (in k = 0; k < hi _ ileDimCa d (*c, 0); k ++){
13 hi _ ileElemA (*c , 2, h ead.x, h ead .y) += hi _ ileElemA (*a, 2, h ead .x, k) *
14 hi _ ileElemA (*b , 2, k , h ead .y );
15 } }
16
17 /* **** Jacobi PDE sol e , same ke nels o CPU and GPU ******************************** */
18 KERNEL ( k_copy , 2, OUT , Hi Tile_ loa *, ds , IN , Hi Tile_ loa *, s c ){
19 hi _ ileElemA (* ds , 2, h ead .x , h ead .y) = hi _ ileElemA (* s c , 2, h ead .x, h ead .y);
20 }
21
22 KERNEL ( k_upda e , 2, OUT , Hi Tile_ loa *, ds , IN , Hi Tile_ loa *, s c ){
23 hi _ ileElemA (* ds ,2 , h ead .x+1 , h ead . y+1) = ( hi _ ileElemA (* s c ,2 , h ead .x+1 , h ead . y) +
24 hi _ ileElemA (* s c ,2 , h ead .x+1 , h ead . y+2) +
25 hi _ ileElemA (* s c ,2 , h ead .x , h ead .y +1) +
26 hi _ ileElemA (* s c ,2 , h ead .x+2 , h ead . y+1)) / 4;
27 }
Figu e 3. Communica o ke nel implemen a ion o he solu ions o he h ee case s udies.
o each cell does no imply any kind o dependencies wi h he
compu a ion o ano he one.
The GPU solu ion o he p oblem in ol es jus one ke nel wi h a
bidimensional g id and bidimensional h eadblocks. Depending o
he size o he g id and he ma ices, each block o h eads compu es
he esul alues o se e al blocks o he ma ix i e a i ely, ollow-
ing he implemen a ion o he examples p esen ed by he CUDA
communi y in he p og amming guide [10]. On each i e a ion he
accesses o global memo y a e ully coalesced. The CPU solu ion
is simila o he GPU e sion.
Ma ix mul iplica ion
The Ma ix mul iplica ion consis s on he p oduc o wo di e en
ma ices s o ing he esul in a hi d one: C=A∗B. The compu a-
ion o each cell o he esul ing ma ix is no dependen on ano he
compu a ion. Ne e heless, di e en cells used elemen s o A o B
ha a e also ead by o he cell compu a ions.
The cop ocesso s solu ion o his p oblem in ol es jus one
ke nel wi h a bidimensional g id and bidimensional h eadblocks.
Each GPU h ead i,j is esponsible o compu ing he p oduc
ope a ion (Pn−1
k=0 A[i][k]∗B[k][j]) in o one posi ion o he C
ma ix. Ou p og am does no exploi any op imiza ion ela ed o
he use o he sha ed memo y o en o ce a mixed coalesced and
no coalesced global memo y access pa e ns ( o ma ix A, and B
espec i ely). The CPU solu ion is simila o he GPU e sion.
Jacobi PDE sol e
This p og am compu es he s abili y poin o a Pa ial Di e en ial
Equa ion (PDE). In his case he Poisson equa ion o compu e he
Hea T ans e on a 2-dimensional su ace. I uses an i e a i e Jacobi
me hod o sol e he equa ion sys em gene a ed when ep esen ing
he space as a 2D g id o poin s wi h he same dis ances and
bounda y condi ions. On each i e a ion each cell o a ma ix is
upda ed depending on he alues o i s ou neighbo s (ho izon al
and e ical). When all he cell alues a e compu ed hen a new
i e a ion is s a ed un il a inishing c i e ion is ul illed. No e ha an
1/* Cha ac e iza ion o MA ke nel */
2KERNEL_CHAR (k_ma , 2, ull , low , low)
3
4/* Cha ac e iza ion o MM ke nel */
5KERNEL_CHAR (k_mm , 2, medium , medium , high )
6
7/* Cha ac e iza ion o JS ke nels */
8KERNEL_CHAR ( k_copy , 2, ull , low , low)
9KERNEL_CHAR ( k_upda e ,2 , medium , medium , medium )
Figu e 4. Cha ac e iza ions o he ke nels implemen ed in he so-
lu ions o he h ee case s udies.
auxilia y ma ix is equi ed o s o e he new alue o a cell wi hou
ace condi ions wi h he neighbo cells. The poin e s o he o iginal
ma ix and he auxilia y one a e o a ed on each i e a ion. Figu e 5
shows he pseudo code o he sequen ial a ian o his me hod.
Cop ocesso s solu ion consis on wo ke nels. The i s is he
ke nel upda e, ha is he esponsible o compu ing he new alues
and s o e hem in he auxilia y ma ix. The second is a ke nel copy,
ha is he esponsible o copying he new da a om he auxilia y
ma ix o he o iginal one o he las i e a ion i he numbe o
i e a ions is odd.
4.3 Measu es: De elopmen e o and pe o mance
o e head
The i s pa o ou expe imen al s udy e alua es how he use o
ou p oposed model a ec s he de elopmen e o when compa ed
wi h using he na i e p og amming models, o he wo ypes o
de ices conside ed in he cu en e sion o he p o o ype: CUDA
o GPUs, and OpenMP o mul i-co e CPUs.
We measu e h ee classical de elopmen e o me ics: CO-
COMO lines o code, numbe o okens, and McCabe cycloma ic
complexi y. The i s wo ones measu e he olume o code ha he
p og amme should de elop. The hi d one measu es he a ional

1// I e a ion loop
2 o (in i = 0; i < i e aciones; i++){
3
4// UPDATE each ma ix cell
5// wi h he mean o i s 4 neighbo s
6 o (in j = 1; j < Ma ixSide -1; j ++){
7 o (in k = 1; k < Ma ixSide -1; k ++){
8
9ma ix [j ][k] = ( ma ixAUX [j][k -1] +
10 + ma ixAUX [j ][k +1] +
11 + ma ixAUX [j -1][k] +
12 + ma ixAUX [j +1][k])/
13 / 4;
14 }
15 }
16
17 // SWAP o he ma ices poin e s
18 * ma ixTMP = * ma ixAUX ;
19 * ma ixAUX = * ma ix ;
20 * ma ix = * ma ixTMP ;
21 }
Figu e 5. Pseudo code o he sequen ial solu ion o he Jacobi
i e a i e me hod used o sol e he PDEs.
e o needed o p og am i in e ms o code di e gences and po en-
ial casuis y ha should be conside ed o de elop, es and debug.
We measu e hese me ics in: he baseline e sions, using he
speci ic p og amming models (OpenMP o he CPU a ian , and
CUDA o he GPU a ian ), and he e sions using ou commu-
nica o lib a y in e ace. Fo a ai ly compa ison bo h app oaches
use he same ke nels wi h he same alues o he con igu a ion pa-
ame e s, ha a e injec ed manually o he baseline e sions, and
h ough he p imi i es o he communica o ones.
The second pa o ou expe imen al s udy measu es he impac
o using ou communica o p o o ype in e ms o pe o mance. We
compa e he o al execu ion imes when launching he baseline and
he communica o p o o ype e sions o he h ee di e en s udy
cases wi h di e en sizes o he inpu se . 10 ×10,100 ×100,
1 000 ×1 000, and 10 000 ×10 000. We es he CPU e sions
using jus 1 h ead, and 24 h eads (maximum numbe o CPU co es
o he machine). On each case, he inal execu ion ime is aken as
he a e age o 10 epe i ions. The numbe o i e a ions execu ed o
he Jacobi PDE sol e is 100.
5. Expe imen al Resul s
This sec ion shows and desc ibes he esul s ob ained om ou
expe imen al e alua ions measu ing he de elopmen e o me ics
and he pe o mance o e head o he s udy cases.
5.1 De elopmen e o me ics
Table 1 shows he measu es o he me ics o he h ee s udy
cases. We can app ecia e ha he alues o all he me ics o he
GPU e sions a e signi ican ly educed. On he o he hand, o
CPU e sions when we compa e he communica o e sion wi h
di ec OpenMP implemen a ion de i ed om he sequen ial code
only is he cycloma ic complexi y is educed. Howe e , conside ing
he CPU co es as ano he cop ocesso de ice, as i can be done
in ou model, simpli ies he de elopmen e o o po ing one
solu ion o he o he de ice ype. Column (a) o Table 2 shows
he numbe o okens which should be modi ied o po he CUDA
GPU p og am o he OpenMP p og am, whe eas Column (b) o
he same able shows he numbe o okens ha changes be ween
ou communica o based p og ams o GPU and CPU co es. The
po abili y ac oss de ices in ou solu ion is ex emely educed.
S udy Ve sion Lines #Tokens Cycloma ic
Case o Code Complexi y
CUDA 68 747 5
Ma ix Comm. GPU 43 389 3
add. OpenMP 32 251 4
Comm. CPU 42 387 3
CUDA 70 778 6
Ma ix Comm. GPU 43 391 4
mul . OpenMP 35 269 5
Comm. CPU 45 405 5
CUDA 85 882 17
Jacobi Comm. GPU 61 617 13
sol e OpenMP 61 554 17
Comm. CPU 59 615 13
Table 1. Measu es o he de eloping e o me ics o he h ee
s udy cases. Me ic alues o communica o e sion (Comm.) lowe
han baseline e sion a e highligh ed.
S udy CUDA →Comm. GPUs →
Case OpenMP Comm. CPUs
Ma ix addi ion 130 10
Ma ix mul iplica ion 152 75
Jacobi sol e 284 17
(a) (b)
Table 2. Compa ison o de eloping e o in e ms o numbe o
okens when po ing om na i e p og amming languages (a), and
when po ing om ou communica o based GPU implemen a ion
o he communica o based CPU e sion. Communica o po ing
esul s lowe han na i e po ing ones a e highligh ed.
5.2 Pe o mance o e head
Figu es 6 and 7 show he execu ion imes o he h ee s udy cases
in a sha ed-memo y sys em. The communica o should pe o m
inse ions in he memo y map when a iables a e binded, and
sea ching in he memo y map when i launches a ke nel. E en so,
we obse e ha he codes ha use Communica o s do no in oduce
no iceable o e head in any s udy case.
6. Conclusions and Fu u e Wo k
In his pape we p opose he communica o model, a pa allel p o-
g amming model ha eases he coding o applica ions o he e oge-
neous sys ems. I is based on he communica o concep , an abs ac
en i y ha manages he launching o ke nel sequences on cop oces-
so s o se s o CPU co es.
I p o ides mechanisms: (1) o associa e communica o s o de-
ices, (2) o de ine po able ke nels ha can be eused ac oss di -
e en ypes o de ices, (3) o selec p ope alues o launching
pa ame e s on di e en de ices h ough he cha ac e iza ion o he
ke nels, and (4) o au oma ically deal wi h di e en memo y spaces
o he hos and he de ices when needed. This model homogenizes
he ke nel p og amming and managemen , b inging close he ac-
cele a o and mul i- h eaded p og amming, aking in o accoun he
a chi ec u al di e ences o he accele a o pla o ms o ob ain good
pe o mance.
Ou expe imen al s udy shows he ad an ages o using his
app oach in e ms o de elopmen e o me ics, and he e iciency
o ou p o o ype implemen a ion o compu a ional cos scena ios.
Ou u u e wo k includes he ex ension o he p o o ype in o -
de o suppo he managemen o o he ypes o accele a o s, such
as XeonPhi cop ocesso s, o he echniques ha exploi he mod-
e n ea u es o some accele a o s, such as async onous comuni-
1
10
100
1000
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
MMAdd size=15000x15000
Base.
Comm. CPU
1
10
100
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
Ma Mul size=3000x3000
Base.
Comm. CPU
0.01
0.1
1
10
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
Jacobi Sol e size=1000x1000 I e =100
Base.
Comm. CPU
Figu e 6. Execu ion imes (seconds) o he baseline (Base.) and communica o (Comm.) e sions o he h ee s udy cases in He acles.
1
10
100
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
MMAdd size=15000x15000
Base.
Comm. CPU
1
10
100
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
Ma Mul size=3000x3000
Base.
Comm. CPU
0.01
0.1
1
1 2 4 6 8 10 12 14 16 24
Execu ion ime (sec.)
P ocesso s
Jacobi Sol e size=1000x1000 I e =100
Base.
Comm. CPU
Figu e 7. Execu ion imes (seconds) o he baseline (Base.) and communica o (Comm.) e sions o he h ee s udy cases in Chime a.
ca ions, communica ion-compu a ion o e lapping, e iciency im-
p o emen s o ou p o o ype implemen a ion, and ke nel launching
policies.
A. Hi map Lib a y and o he de ini ions
Hi map [5] is a lib a y o he managemen and un- ime mapping
o hie a chical iling a ays. I is based on an SPMD model, and
he message-passing pa adigm. Hi map has h ee main unc ional-
i y modules: (a) Domain and ile managemen ; (b) Mapping mod-
ules; and (c) Communica ion pa e ns. Hi map de ines objec s o
decla e and manipula e mul idimensional index domains and di -
e en ypes o indexed da a s uc u es [4]. Hi map de ines a plug-
in sys em o include new mapping modules: Vi ual opology con-
s uc o s and mapping unc ions named Layou s. The modules gen-
e a e objec s ha can be que ied a un- ime o ob ain in o ma ion
abou he esul o he mapping. Finally, i con ains unc ionali-
ies o build eusable communica ion pa e ns o iles o sub iles
ac oss i ual p ocesses. These unc ions in e nally use he MPI
s anda d, exploi ing e icien echniques like de i ed da a ypes and
asynch onous communica ions.
A.1 De ini ions and no a ion
In his wo k, we ocus on a ays wi h egula dense and s ided
domains. Thei index Domain is a subspace o Zn. Rec angula n-
dimensional pa allelo ope domains, dense o s ided, can be ep e-
sen ed by a uple o nSigna u es. A Signa u e is a iple o in ege
numbe s Shb, e, si(meaning begin,end, and s ide). The se o in-
dexes exp essed by a signa u e is Shb, e, si={b≤i≤e: (i−b)
mod s= 0}.
A da a s uc u e o Tile (T:D→ ype) is an objec ha asso-
cia es da a elemen s o a gi en ype o index elemen s o a domain.
A ay iles associa e one da a elemen o each domain elemen . The
domain o a ile is deno ed as D(T). Hie a chical iling is a ech-
nique ha allows new Tile s uc u es o be hie a chically decla ed
wi h a subse o he domain o ano he Tile. The sub ile maps he
index elemen s o i s subdomain o he same da a elemen s o he
oo ile (T)( he ances o o he sub iling chain). The Selec ion
unc ion, s:T×D?→T, is used o decla e a new sub ile:
s( , d) = 0: ( ) = ( 0), D( 0) = D( )∩d.
A.2 In e ace
Hi map p o ides, among o he s, wi h he ollowing basic unc ion-
ali ies o dense da a s uc u es managemen .
Hi Sig
•Hi Sig hi sig(begin, end, s ide ):
C ea es a s uc u e o ype Signa u e.
Hi Shape
•Hi Shape hi shape(dims, sig [, sig] ... ):
C ea es a s uc u e o ype Shape o ep esen a domain.
Tile
• oid hi ileNewType(newType ):
De ines a new ype o ile s uc u e wi h he indica ed
da a ype newType .
• oid hi ileDomainShape( ile, ile da aType, shape ):
C ea es a ile using a domain de ined by a Shape s uc u e.
• oid hi ileAlloc( ile ):
Rese es memo y o he ile.
• oid hi ileF ee( ile ):
F ees he memo y o he ile.
• ype hi ileElemA ( ile, dims, ...):
Access o a pa icula elemen o a ile.
• oid hi ileSelec (newTile, oldTile, shape ):
C ea es a sub ile.
Acknowledgmen 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-H5 ne wo k (TIN2014-53522-REDT),
and COST P og am Ac ion IC1305: Ne wo k o Sus ainable Ul-
ascale Compu ing (NESUS).
Re e ences
[1] OpenACC Conso ium. OpenACC: Di ec i es o Accele a o s.
WWW, 2011–2015. on h p://www.openacc-s anda d.o g/.
[2] Q. K. Chen and J. K. Zhang. A S eam P ocesso Clus e A chi-
ec u e Model wi h he Hyb id Technology o MPI and CUDA. In
ICISE’2009, pages 86 –89, dec. 2009. .
[3] O. Conso ium. Openmp 4.0 speci ica ions. WWW, July 2013. on
h p://openmp.o g/wp/openmp-speci ica ions/.
[4] J. F esno, A. Gonzalez-Esc ibano, and D. R. Llanos. Blending ex ensi-
bili y and pe o mance in dense and spa se pa allel da a managemen .
IEEE T ans. Pa allel Dis ib. Sys ., 25(10):2509–2519, 2014.
[5] A. Gonzalez-Esc ibano, Y. To es, J. F esno, and D. R. Llanos. An
ex ensible sys em o mul ile el au oma ic da a pa i ion and mapping.
IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, 25(5):1145–
1154, 2014.
[6] T. D. Han and T. S. Abdel ahman. hiCUDA: a high-le el di ec i e-
based language o GPU p og amming. In D. R. Kaeli and M. Leese ,
edi o s, GPGPU, olume 383, pages 52–61. ACM, 2009. ISBN 978-
1-60558-517-8.
[7] N. Ka unadasa and D. Ranasinghe. Accele a ing high pe o mance
applica ions wi h CUDA and MPI. In ICIIS’2009, pages 331–336,
dec 2009. .
[8] D. B. Ki k and W.-m. W. Hwu. P og amming Massi ely Pa allel
P ocesso s: A Hands-on App oach. Mo gan Kau mann Publishe s
Inc., San F ancisco, CA, USA, 1s edi ion, 2010. ISBN 0123814723,
9780123814722.
[9] Message Passing In e ace Fo um. MPI: A Message-Passing In e ace
S anda d Ve sion 3.1. Technical epo , Uni e si y o Tennessee, 2015.
URL www.mpi- o um.o g/docs/mpi-3.1/mpi31- epo .pd .
[10] NVIDIA. NVIDIA CUDA C P og amming Guide 7.5, 2015. URL
h p://docs.n idia.com/cuda/pd /CUDA C P og amming Guide.pd .
Las isi : No embe 16 h, 2015.
[11] H. O ega-A anz, Y. To es, A. Gonzalez-Esc ibano, and D. R.
Llanos. Op imizing an APSP implemen a ion o NVIDIA GPUs us-
ing ke nel cha ac e iza ion c i e ia. The Jou nal o Supe compu ing,
70(2):786–798, 2014. ISSN 0920-8542. .
[12] H. O ega-A anz, Y. To es, A. Gonzalez-Esc ibano, and D. R.
Llanos. TuCCompi: A Mul i-laye Model o Dis ibu ed He e oge-
neous Compu ing wi h Tuning Capabili ies. In e na ional Jou nal o
Pa allel P og amming, 43(5):939–960, 2015. ISSN 0885-7458. .
[13] J. S one, D. Goha a, and G. Shi. OpenCL: A Pa allel P og amming
S anda d o He e ogeneous Compu ing Sys ems. Compu ing in Sci-
ence Enginee ing, 12(3):66 –73, may 2010. ISSN 1521-9615. .
[14] J. A. S a on, S. S. S one, and W.-M. W. Hwu. MCUDA: An E icien
Implemen a ion o CUDA Ke nels o Mul i-co e CPUs. In J. N.
Ama al, edi o , LCPC’2008, pages 16–30, Be lin, Heidelbe g, 2008.
Sp inge -Ve lag. ISBN 978-3-540-89739-2.
[15] TOP500.o g. Top500 supe compu ing si es. WWW, No 2014. on
h p://www. op500.o g/.
[16] Y. To es, A. Gonzalez-Esc ibano, and D. R. Llanos. uBench: expos-
ing he impac o CUDA block geome y in e ms o pe o mance.
The Jou nal o Supe compu ing, 65(3):1150–1163, 2013. ISSN 0920-
8542. .