Noname manusc ip No.
(will be inse ed by he edi o )
TuCCompi: A Mul i-Laye Model o Dis ibu ed
He e ogeneous Compu ing wi h Tuning Capabili ies
Hec o O ega-A anz ·Yu i To es ·
A u o Gonzalez-Esc ibano ·
Diego R. Llanos
Recei ed: da e / Accep ed: da e
Abs ac Du ing he las decade, pa allel p ocessing a chi ec u es ha e be-
come a powe ul ool o deal wi h massi ely-pa allel p oblems ha equi e
High Pe o mance Compu ing (HPC). The las end o HPC is he use o
he e ogeneous en i onmen s, ha combine di e en compu a ional p ocessing
de ices, such as CPU-co es and GPUs (G aphics P ocessing Uni s). Maxi-
mizing he pe o mance o any GPU pa allel implemen a ion o an algo i hm
equi es an in-dep h knowledge abou he GPU unde lying a chi ec u e, be-
coming a edious manual e o only sui ed o expe ienced p og amme s. In
his pape , we p esen TuCCompi, a mul i-laye abs ac model ha sim-
pli ies he p og amming on he e ogeneous sys ems including ha dwa e accel-
e a o s, by hiding he de ails o synch oniza ion, deploymen , and unning.
TuCCompi chooses op imal alues o hei con igu a ion pa ame e s using a
ke nel cha ac e iza ion p o ided by he p og amme . This model is e y use-
ul o ackle p oblems cha ac e ized by independen , high compu a ional-load
independen asks, such as emba assingly-pa allel p oblems. We ha e e alu-
a ed TuCCompi in di e en , eal-wo ld, he e ogeneous en i onmen s using he
All-Pai Sho es -Pa h p oblem as a case s udy.
Keywo ds Abs ac pa allel model ·Au o-Tunig ·CUDA ·GPU ·
He e ogeneous sys em ·HPC amewo k ·MPI ·OpenMP
1 In oduc ion
Some compu ing-in ensi e p oblems a e di ided in o many independen asks
ha can be execu ed in pa allel wi hou equi ing any communica ion among
hem. They a e called emba assingly-pa allel p oblems [1]. Many eal p ob-
lems a e included in his ca ego y, such as index p ocessing in web sea ch [2],
bag-o - asks applica ions [3], a ic simula ions [4] o Bi coin mining [5].
Hec o O ega-A anz ·Yu i To es ·A u o Gonzalez-Esc ibano ·Diego R. Llanos
Depa amen o de In o m´a ica, Uni e sidad de Valladolid, Spain.
Tel.: (+34) 983.423.000 Ex . 5642
E-mail: {hec o |yu i. o es |a u o |diego}@in o .u a.es
2 Hec o O ega-A anz e al.
Al hough he pa alleliza ion o emba assingly-pa allel p oblems does no
equi e a e y complex algo i hm o ake ad an age o pa allel compu ing en i-
onmen s, hei high amoun o compu a ional wo k equi es High Pe o mance
Compu ing (HPC). Deploymen , load balancing, and asks synch oniza ion de-
ails should be ackled by he p og amme in a speci ic way o di e en appli-
ca ions, and di e en execu ion en i onmen s. In o de o gi e suppo o he
massi e demand o HPC, he las ends ocus on he use o he e ogeneous en-
i onmen s including compu a ional uni s o di e en na u e, such as common
CPU-co es, g aphics p ocessing uni s (GPUs) and o he ha dwa e accele a o s.
The exploi a ion o hese en i onmen s o e s a highe peak pe o mance and
a be e e iciency compa ed o he classical homogeneous clus e sys ems [6].
Due o hese ad an ages, and since he cos o building he e ogeneous sys-
ems is low, hey a e being inco po a ed in o many di e en compu a ional
en i onmen s, om academic esea ch clus e s o supe compu ing cen e s.
Despi e he wide use o he e ogeneous en i onmen s o execu e massi ely-
pa allel p oblems, he e a e wo issues ha limi he usabili y o hese sys ems.
The i s one is he lack o compu ing amewo ks ha can easily schedule he
wo kload in such complex en i onmen s. Some wo ks ha e been p esen ed o
in eg a e he use o di e en p og amming languages o ools [7,8]. Howe e ,
he p og amme s ill needs o ackle di e en design and implemen a ion p ob-
lems ela ed wi h each le el o pa allelism. These p oblems a e specially mo e
complex when in eg a ing GPU p og amming echniques. The second limi-
a ion is he lack o a uning me hodology ha e icien ly unleashes all he
powe o GPU de ices. Al hough he e a e languages, such as CUDA, ha
aim o educe he p og amme ’s bu den in w i ing pa allel applica ions, i is
a di icul exe cise o co ec ly une he code in o de o e icien ly exploi all
unde lying GPU esou ces. Se e al s udies [9,10] ha e shown ha , in some
cases, he alues ha a e ecommended by CUDA do no lead o he op imum
pe o mance, lea ing o he p og amme s he esponsibili y o sea ching o he
bes alues. This sea ch usually implies o ca y ou se e al ime-consuming
ial-and-e o es s. The e is no a pa allel model ha au oma ically selec s
he op imal alues o CUDA con igu a ion pa ame e s, such as he h ead-
Block size-shape, o he s a e o L1 cache memo y, o each ke nel. These
op imiza ion echniques signi ican ly enhance he GPU pe o mance.
In his pape , we p esen TuCCompi (Tuned, Concu en Cuda, OpenMP
and MPI), a mul i-laye , skele on-based abs ac model, ha anspa en ly
exploi s he e ogeneous sys ems and squeezes he GPU capabili ies by au o-
ma ically choosing he op imal alues o impo an con igu a ion pa ame e s.
Mo eo e , i easily suppo s he inclusion o wo k dis ibu ion policies as plug-
ins. Each laye ep esen s a le el o pa allelism. The i s laye handles he
dis ibu ed-memo y en i onmen , coo dina ing di e en sha ed-memo y sys-
ems (nodes). The second laye manages he compu a ional uni s ha a e in-
side he nodes. The hi d laye au oma ically deploys he execu ion in he ha d-
wa e accele a o s, such as he GPUs. The ou h laye au oma ically handles
concu en wo ks inside hese GPUs. Finally, an in e nal uning mechanism
au oma ically selec s he op imal alues o GPU con igu a ion pa ame e s
TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 3
o each ke nel, and each GPU a chi ec u e. We ha e de eloped a p o o ype
amewo k o es his model, allowing a use o anspa en ly ake ad an-
age o all compu a ional capabili ies o bo h, CPU-co es and GPU de ices,
dis ibu ed ac oss di e en sha ed-memo y sys ems, wi hou ha ing a deep
knowledge o pa allel p og amming me hods. The case s udy used o e alua e
he model is he All-Pai Sho es -Pa h p oblem. The expe imen s ha e been
un in an academic he e ogeneous en i onmen .
The con ibu ions o his wo k a e: (a) a mul i-laye abs ac pa allel model
ha simpli ies p og amming in he e ogeneous sys ems including ha dwa e ac-
cele a o s, by hiding he de ails o synch oniza ion, load balancing, and deploy-
men ; (b) a p o o ype implemen a ion ha exploi s mode n GPU capabili ies,
such as concu en ke nel execu ion on a GPU, o pa ame e uning o GPU
execu ion; and (c) a echnique o allow he p og amme o supply abs ac
ke nel cha ac e iza ions o he GPU codes o help he amewo k o chose op-
imal alues o impo an CUDA uning pa ame e s. These op imal alues
a e alid o any cu en GPU a chi ec u e, and a e based on he wo k o [10].
Expe imen al wo k wi h he p o o ype amewo k shows ha he new abs ac-
ion laye s easily allow o ob ain pe o mance imp o emen s o up o 12 % in
he es case, wi h minimum ex a p og amming e o , compa ed wi h using
only he adi ional h ee i s ones.
The es o his pape is o ganized as ollows. Sec ion 2 desc ibes some
ela ed wo k. Sec ion 3 in oduces ou concep ual app oach. Sec ion 4 desc ibes
he use o he model h ough some code snippe s. Sec ion 5 shows he in e nals
o he TuCCompi amewo k. Sec ion 6 explains he case s udy used. In Sec . 7
we p esen he expe imen al en i onmen and he esul s ob ained. Finally,
Sec . 8 summa izes ou conclusions and desc ibes he u u e wo k.
2 Rela ed wo k
The e a e se e al wo ks ha in eg a e languages on ools o conside se e al
le els o pa allelism. llCoMP [7] is a sou ce- o-sou ce compile ha ansla es
C anno a ed code o MPI + OpenMP o CUDA code. The use needs o speci y
he sequen ial code he wan s o pa allelize. The au ho s a e only ocused in
pa allel-loop p oblems. This compile does no suppo he join use o CUDA
wi h any o he pa allel model, he e o e, i is no app op ia e o be used in
he e ogeneous en i onmen s. Besides his, he llCoMP compile does no easily
suppo a new GPU a chi ec u e o o he kind o accele a o s.
The au ho s in [8] p opose a amewo k called OMPICUDA o de elop pa -
allel applica ions on hyb id CPU/GPU clus e s by mixing OpenMP, MPI and
CUDA models. This amewo k p esen s some limi a ions: i canno be easily
modi ied o suppo a new pa allel model, and i is no conside any policy o
selec p ope alues o CUDA con igu a ion pa ame e s. Ano he pa allel p o-
g amming app oach using hyb id CUDA, MPI and OpenMP p og amming is
p esen ed in [11]. The au ho s ocus on he model o sol e i e a i e p oblems,
and hey do no ake in o accoun any gene ic CUDA op imiza ion echnique.
I does no suppo any mechanism o include new load dis ibu ion policies.
4 Hec o O ega-A anz e al.
Main P og am
P og amme Applica ion
Plug-in
CPU
Code
Plug-in
GPU
Code
accULL
Ke nels
+
Plug-in
CPU
Code
Plug-in
GPU
Code
Ke nels
+
Ocelo
Fig. 1 Usage o TuCCompi wi h code- ans o ma ion modules.
The au ho s in [12] ha e c ea ed an hyb id ool, ha includes he same
pa allel models used by he p e ious men ioned wo ks, o sol e aycas ing
olume ende ing algo i hm. They es he sys em scalabili y when he inpu
da a size is inc eased. This ool is only ocused in a single pa allel applica ion
and does no include any CUDA op imiza ion echnique, no any au oma ic
mechanism o e icien ly exploi he e ogeneous en i onmen s.
O he p og amming lib a ies o hyb id a chi ec u es suppo ing GPUs a e
SkelCL [13], S a PU [14] and SkePU [15]. The i s ies o enhace he OpenCL
in e ace in o de o coo dina e di e en GPUs o he same sha ed-memo y
machine. Howe e , i does no suppo load dis ibu ion be ween GPUs o di -
e en machines, o e en, o he compu a ional uni s o di e en na u e, such as
he CPU-co es. These limi a ions a e no p esen in S a PU and SkePU, bu
hey do no suppo he exploi a ion o he concu en -ke nels ea u e o mod-
e n GPUs. S a PU does no e en conside he use o uning echniques o be -
e exploi ing GPU capabili ies. SkePU ies o ind he op imal h eadblock
size by au oma ically checking all possibili ies using ial-and-e o execu ions,
bu i does no p o ide a model o uning his pa ame e .
The e a e o he wo ks ha aim o ans o m sequen ial code o pa allel
code, and ice- e sa. Fo example, accULL [16] ecei es a sequen ial code and
au oma ically ans o ms i o pa allel GPU code. Ano he example o code
ans o ma ion is Ocelo [17], ha wo ks in he opposi e way. Gi en a GPU
implemen a ion, Ocelo ans o ms i o sequen ial code. TuCCompi model
does no aim o deal wi h code ans o ma ions, bu hese wo ks can be easily
a ached as p e ious unc ional modules o ou mul ilaye model (see Fig. 1).
Ano he a achable module could be he wo k o elas ic ke nels p esen ed in
[18]. They do manual sou ce- o-sou ce code ans o ma ions in o de o ob ain
GPU ke nels ha exploi mo e he mul ike nel ea u e o he GPU de ices.
3 TuCCompi A chi ec u e
TuCCompi in eg a es se e al execu ion laye s wi h di e en coo dina ion mech-
anisms, ha a e abs ac ed o p o ide an uni ied iew o he compu ing he -
e ogeneous sys em o he p og amme . He has o p og am his applica ions in
wo p og amming le els: (1) a coo dina ion le el, ha abs ac s he wo k dis-
ibu ion ac oss he compu a ional uni s inside he dis ibu ed sha ed-memo y
nodes; and (2) a deploymen le el, ha abs ac s he managemen o compu a-
ional uni o di e en na u e. This sec ion gi es a desc ip ion o hese di e en
laye s de ined in ou model. A g aphical ep esen a ion is depic ed in Fig. 2.
TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 5
MPI
OpenMP
CUDA
Concu en
Ke nel
Node 1
Desk op
Node 2
Desk op
Node n
Lap op
CPU
co e
GPU
1..c 1
GPU
1..c 2
CPU
co e
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
Mul iple Ke nels
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
Mul iple Ke nels
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
Mul iple Ke nels
GPU
1..c 1
CPU
co e
2nd laye
1s laye
4 h laye
3 d laye
Dis ibu ed en i onmen
Sha ed-memo y sys ems
Fig. 2 Laye deploymen o TuCCompi model in a he e ogeneous clus e .
The 1s laye (dis ibu ed en i onmen ) Nowadays, one o he mos
economic ways o assemble a he e ogeneous sys em is o in e connec a se o
di e en indi idual machines, also called nodes, such as pe sonal compu e s,
lap ops, complex i ual hos machines, o e en o he supe compu ing sys ems
composed in u n by o he machines. I is necessa y o apply communica ion
and synch oniza ion mechanisms in o de o coo dina e hese nodes. The i s
laye o TuCCompi (see Fig. 2) is esponsible o managing his node coo di-
na ion wi hou aking in o accoun he ha dwa e de ails and ea u es o each
machine. This laye is abs ac ed a he coo dina ion le el, allowing he p o-
g amme o skip hinking in e ms o mo e complex message-passing models.
The 2nd laye (sha ed-memo y sys ems) Nodes a e nowadays com-
posed by se e al p ocessing uni s ha sha e a global add ess space. Addi ion-
ally, he e a e o he accele a o de ices, such as GPUs, FPGAs and Xeon Phi,
ha a e usually con olled by a hos sys em (CPU) and a e capable o exe-
cu ing ke nels independen ly. In his laye o TuCCompi we use he concep
o “compu a ional uni ” o any CPU-co e o de ice hos ed in a node. This
second laye is esponsible o he coo dina ion o all compu a ional uni s inside
he node. Fo he p og amme ’s poin o iew, his laye is also encapsula ed in
he abs ac ion o he coo dina ion le el. I also hides he ac ha each special
de ice is con olled by a dedica ed h ead ha execu es a di e en code. The
p og amme sees all de ices and CPU-co es in an homogeneous o m.
The 3 d laye (GPU de ices) This laye implemen s he abs ac ion
used a he deploymen le el. I is he esponsible o he coo dina ion and
deploymen ac ions needed o special de ices, such as GPUs, FPGAs, o Xeon
Phis, in an homogeneous o m. This is done by hiding he de ails needed o
manage di e en add ess spaces, o loading codes, e c.
The 4 h laye (concu en GPU ke nel execu ion) The mos e-
cen NVDIA GPUs suppo concu en -ke nel execu ion [19], whe e di e en
ke nels o he same applica ion con ex can be execu ed on a GPU a he same
ime. This ea u e is e y help ul when ke nels ha use jus ew esou ces a e
launched, allowing a concu en execu ion o o he ke nels, and hus, exploi -

6 Hec o O ega-A anz e al.
ing a he same ime all esou ces o he de ice. Al hough a i s glance his
ea u e seems o be p o i able only when low esou ce-consuming ke nels a e
launched, he concu en execu ion o highe esou ce-consuming ke nels also
gi es pe o mance gains. This occu s because se e al ke nels o he same ap-
plica ion con ex wo k on he same memo y a eas aking ad an age o he L1
da a-cache, o igina ing less numbe o cache-misses and he e o e alle ia ing
he global memo y bo lenecks. The p og amme p o ides a pa ame e o de-
ine he numbe o asks ha will be concu en ly deployed in a single GPU o
each applica ion. This laye in e nally ake ca es o he synch oniza ion o he
concu en ke nel launching. I con ibu es o he unc ionali ies encapsula ed
in he deploymen le el.
The Tuning laye While co ec ness o an NVIDIA CUDA p og am
is easy o achie e, he op imal exploi a ion o he GPU compu a ional ca-
pabili ies is much mo e complica ed han in adi ional CPU co es. Usually,
i equi es an ex ensi e CUDA p og amming expe ience. Some examples o
code uning s a egies a e he choice o an app op ia e h eadBlocks size and
shape, he coalescing maximiza ion o he memo y accesses, o he occupancy
maximiza ion o he S eaming Mul ip ocesso s, among o he s. Mo eo e , he
esou ce di e ences be ween each GPU a chi ec u e and elease, such as he
numbe o compu a ional uni s, cache-sizes, and o he ea u es, make i e en
mo e di icul o ind he op imal con igu a ion o a gi en GPU. Besides his,
he op imal alues also depend on he memo y access pa e n and he cha ac-
e is ics o he code o each execu ed ke nel. This laye allow he p og amme
o supply o he deploymen le el wi h an abs ac ke nel cha ac e iza ion o
he CUDA codes in e ms o human-unde s andable ea u es. Wi h hese al-
ues, he model in e nally chooses p ope alues o he execu ion pa ame e s.
This solu ion opens he possibili y o in eg a e echniques o au oma ically
analyze and cha ac e ize he CUDA ke nel codes o speci ic GPU de ices.
4 TuCCompi Model Usage
To build a p og am using TuCCompi, a p og amme should p o ide he ol-
lowing elemen s (see Fig. 3): (1) Coo dina ion le el, implemen ed as a main C
language p og am wi h he TuCCompi p imi i es and mac os, and (2) Deploy-
men le el, including he sequen ial-CPU and he pa allel-GPU speci ic codes
o each applica ion, named as PLUG-IN CPU and PLUG-IN GPU espec i ely,
and cha ac e iza ions o he accele a o ke nel codes.
In his way, he applica ion p og amme does no ha e o p o ide: (a) he
alues o GPU con igu a ion pa ame e s o an op imal execu ion on each
di e en GPU, (b) he code implemen a ion o concu en ke nel deploymen ,
(c) he code implemen a ion o he managemen o he dis ibu ed and sha ed
compu a ional-uni s, no (d) he communica ion be ween all in ol ed nodes.
4.1 Coo dina ion Le el - TuCCompi Main P og am Implemen a ion
Figu e 4 shows an example o he code ha he use has o implemen in o de
o s a and con ol he execu ion. The p imi i e TuCCompi COMM in Line M01
TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 7
Main p og am:
C code + TuCCompi calls
P og amme Applica ion
Plug-in
GPU
Code A
Plug-in
GPU
Code B
Plug-in
CPU
Code A
Plug-in
CPU
Code B
Ke nel
A
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
GPU
SP SP SP SP
SP SP SP
SP SP SP
SP
SP
GPU
CPU
CPU
Scheduling
Policies
Cha ac e iza ion
Policies
TuCCompi
Sch
Plug-in
Sch
Plug-in
Sch
Plug-in
Cha
Plug-in
Clus e
Ke nel
Cha ac e iza ion
Ke nel
B
Ke nel
C
Fig. 3 TuCCompi model usage. Elemen s in he dashed box a e p o ided by he p og am-
me . No e ha he use can de elop di e en e sions o each plug-in (Code A, Code B, . . . )
bu only one a a ime will be deployed in o TuCCompi amewo k.
M00: main( ){
M01: TuCCompi COMM( );
M02: (main use code)
M03: TuCCompi SETMK( numbe );
M04: TuCCompi PARALLEL(MS, plugin Cpu(..), plugin Gpu(..));
M05: TuCCompi SYN( );
M06: (main use code)
M07: TuCCompi ENDCOMM( );
M08: }//main
Fig. 4 Use implemen a ion o he TuCCompi main-p og am. The p og amme has o add
o his code he boxed p imi i es.
ini ializes he sys em. A e wa ds, he use can in oduce his code, including
a iable decla a ions, ini ializa ions and he sequen ial code needed o he
applica ion. Line M03 shows he p imi i e needed o se he numbe o ke -
nels ha he GPU de ices will execu e concu en ly (in o ma ion o he 4 h
execu ion laye ). Line M04 shows he p imi i e used o ini ialize and execu e
he unc ions implemen ed in he co esponding plug-ins. This synch oniza ion
exp ession anspa en ly execu es he CPU-plugin code o he CPU-co es, o
he specialized GPU-plugin code o he GPU de ices, using he same seman-
ics, ac oss a whole he e ogeneous clus e . The i s pa ame e o his mac o
ep esen s he kind o scheduling policy desi ed by he use (desc ibed below).
I is used in e nally by he 1s and 2nd execu ion laye s o balance he wo k-
load ac oss he di e en compu a ional uni s. Line M05 shows he p imi i e
needed o make he p ocess wai un il all node compu a ional uni s ha e in-
ished. The use is ee o inse mo e code o execu e o he ke nels, be o e he
inaliza ion o he he e ogeneous clus e communica ion, shown in line M07.
4.2 Coo dina ion Le el - Wo kload Scheduling
The TuCCompi model includes h ee di e en policies o dis ibu e he wo k-
load be ween all a ailable clus e esou ces h ough he i s pa ame e o he
M04 p imi i e.
8 Hec o O ega-A anz e al.
C00: plugin Cpu(use a s ...) {
C01: (Cpu use code)
C02: }//pluginCPU
G00: plugin Gpu(use a s ...) {
G01: (Gpu use code)
G02: TuCCompi GPULAUNCH(k1, inpu size, TuCCompi PARLLMK( ec o 1, ype, lng), ...);
G03: TuCCompi GPUSYN( );
G04: TuCCompi GPULAUNCH(k2, inpu size2, TuCCompi PARLLMK( ec o 2, ype, lng), ...);
G05: TuCCompi GPUSYN( );
G06: }//pluginGPU
Fig. 5 Plugin Cpu ( op) and Plugin Gpu (down) in e aces. The p og amme adds o his
code he boxed a gumen s o deploy he Cpu plugin in TuCCompi, and he has o eplace
he CUDA ke nel launch p imi i es o he boxed TuCCompi mac os o he GPU plugin.
The i s one, EQ1, is an equi able policy ha schedules he same numbe o
asks o each node o he 1s laye (dis ibu ed memo y en i onmen ), indepen-
den ly o he numbe o CPU-co es, GPUs, o o he accele a o s ha he nodes
ha e inside. La e , each node equally di ides he assigned wo kload be ween
all i s own compu a ional uni s (CPU-co e/Accel.), also in a balanced way.
The second one, EQ2, is also an equi able policy, bu i di ides he wo kspace
s aigh be ween he compu a ional uni s o he whole clus e a he 2nd laye .
The wo kspace di ision does no conside he compu a ional uni na u e.
The hi d one, MS, ollows a mas e -sla e model. One compu a ional uni
is sac i iced o ac as he mas e , and he es o he compu a ional uni s
wo k as sla es. The sla es en e in o a wo king loop, eques ing asks om he
mas e when hey become idle, un il he mas e sends a e mina ion signal
o hem. Thus, he mo e powe ul uni s will ask o mo e wo k, and he e o e
hey will p ocess mo e asks han he less powe ul uni s. As he mas e can be
loca ed a any clus e node, hese asking- o - asks eques s a e issued h ough
dis ibu ed-en i onmen communica ions.
Addi ionally, TuCCompi also o e s he possibili y o including a scheduling
policy p og ammed by he use h ough he Scheduling plug-in (see Sec . 5.5.1).
4.3 Deploymen Le el - Use -code Plug-ins
Figu e 5 ( op) shows he in e ace o he sequen ial code ha will be execu ed
in a CPU compu a ional uni . The use is esponsible o inse ing he code o
implemen he algo i hm ha sol es a single ask (line C01, Cpu use code).
Figu e 5 (bo om) shows he code ha will be execu ed in a CPU h ead
o manage one o mo e associa ed GPUs. The con ol o he GPU o en in-
ol es ac i e wai s. In his case, a CPU-co e should be sac i iced o execu e
his GPU-con olle h ead. The use should de ine he code ha handles he
logic con ol o he algo i hm ha comp ises he use o one o se e al GPU
ke nels. This code will be esponsible o launching he co esponding ke nels.
Line G02 shows he TuCCompi mac o ha ca ies ou a ke nel launch, wi h
he name o he ke nel as i s pa ame e , and ollowed by o he use a iables
TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 9
Table 1 TuCCompi ke nel-cha ac e iza ion classi ica ion. The de choice can be used when
he use does no know he ke nel cha ac e iza ion.
Pa ame e Desc ip ion Choice
A Global memo y-access pa e n sca e /medium-coalesced/
coalesced/de
B Ra io o a i hme ic ins uc ions pe h ead high/low/none/de
compa ed o he global-memo y accesses
C Ra io o L1 cache memo y lines e ic ions high/medium/low/de
compa ed o he size o his memo y
D Ra io o memo y da a eu iliza ion compa ed o high/medium/low/de
he numbe o a i hme ic ins uc ion pe h ead
K00: TuCCompi KERNELCHAR(k1, 2, sca e , none, high, low);
K01: global oid k1 (...){
K02: (ke nel implemen a ion)
K03: }
K04: TuCCompi KERNELCHAR(k2, 1, coalesced, low, low, high);
K05: global oid k2 (...){
K06: (ke nel implemen a ion)
K07: }
Fig. 6 Ke nel cha ac e iza ions and implemen a ions. The p og amme adds he boxed
p imi i e be o e he ke nel implemen a ion o cha ac e ize i .
ha ha e been p e iously alloca ed in he GPU. T anspa en ly o he use ,
he model execu es as many ke nel ins ances as indica ed by he p og amme
in he main con ol p og am (MK alue) (see line M03 o Fig. 4). E e y con-
cu en ke nel launched will need i s own wo kspace o compu e i s esul s.
The second p imi i e o line G02 gi es o he ke nel one memo y poin e o
each da a s uc u e needed. The needed pa ame e s a e: The a iable name;
he na i e ype o he elemen s ha i con ains; and he numbe o elemen s
ha compounds i . As we said be o e, he algo i hm implemen a ion can e-
qui e he execu ion o di e en ke nels ha should be sequen ially launched
o a single ask compu a ion (line G04). The TuCCompi p imi i e o line G03
o ces he CPU o wai o he inaliza ion o an execu ing ke nel, o ke nels
concu en ly olaunched, p o iding a synch oniza ion mechanism.
4.4 Deploymen Le el - Ke nel Cha ac e iza ion
The use has o p o ide a gene al cha ac e iza ion o his ke nels along wi h
i s de ini ion. This in o ma ion is easily exp essed in ou p o o ype implemen-
a ion h ough he TuCCompi KERNELCHAR( ke nel name, num dims, A,B,
C,D)p imi i e. The alues o pa ame e s A,B,Cand Dha e o be chosen
om he ke nel-cha ac e iza ion classi ica ion shown in Table 1. TuCCompi
model will au oma ically op imize he use o he unde lying ha dwa e o any
kind o GPU ound in he pla o m, ollowing he guidelines and op imiza ions
p oposed in [10] o each possible combina ion o hese pa ame e s.
Figu e 6 shows some examples o he code used o cha ac e ize he ke -
nels. Lines K00 and K04 desc ibes he cha ac e iza ion o ke nels k1 and
k2 espec i ely, indica ing he ke nel name, he numbe o dimensions o he
h eadBlock, and he class chosen om he classi ica ion c i e ia desc ibed in
16 Hec o O ega-A anz e al.
Table 2 Summa y o ke nels cha ac e iza ion.
Ke nel A B C D
Relax sca e low high low
Minimum coalesced low low medium
Upda e coalesced low low low
Figu e 11 (le ) shows he mas e (lines 00-22) and sla e (lines 23-27) im-
plemen a ions. The mas e will manage he ask dis ibu ion while he e a e
ask o be execu ed (lines 01-16). To do so, he mas e wai s o a ask e-
ques om any sla e (line 3). I he sla e is a mode n GPU (Fe mi o Keple )
(line 04), he mas e checks i he e a e MK a ailable asks o be sen . In his
case, i sends he iden i ie o he i s ask o he pack o he co esponding
sla e using i s iden i ie , and upda es he ask coun e (lines 05-07). Howe e ,
i he e a e no enough asks o his ype o sla e, he mas e sends o i
he e mina ion signal and upda es he coun e o sla es ha ha e al eady
inished (lines 08-11). I he eques ing sla e is an old GPU (p e-Fe mi) o a
CPU-co e, he mas e only sends a single ask o he sla e (lines 12-15), hus,
he ask coun e is simply inc emen ed. When all asks ha e been scheduled
and ca ied ou , he mas e sends he e mina ion signal o he es o ac i e
sla es when hey eques mo e asks (lines 17-21).
Rega ding he sla e implemen a ion, i i s no i ies he mas e ha i is
idle (line 24). Then he sla e ecei es he iden i ie o he ask pack o be
execu ed, 1 ask o CPU-co es and P e-Fe mi GPUs, and MK asks o he
mode n GPUs in his p o o ype (line 25).
SSSP plug-ins: Bo h he CPU-co e sequen ial and he pa allel GPU codes a e
implemen a ions o he C ause algo i hm. Thei implemen a ion o his p ob-
lem has been aken om [23]. Algo i hm 1 shows he GPU pa allel pseudo-code
o C ause ’s algo i hm. Figu e 11 ( igh ) shows he TuCCompi implemen a ion
o he pluginGPU. This implemen a ion epea edly launches h ee ke nels ( e-
lax, minimum and upda e) wi h di e en ea u es. Following he classi ica ion
c i e ia desc ibed in Sec . 4.4, he ke nels a e cha ac e ized in Table 2.
7 Expe imen al e alua ion
This sec ion desc ibes he me hodology used o es he TuCCompi p o o-
ype, he pla o ms used, and he inpu se cha ac e is ics o he case s udy
( he APSP p oblem). Finally, he expe imen al esul s and a discussion a e
p esen ed.
7.1 Me hodology
In o de o e alua e TuCCompi o he e ogeneous en i onmen s, we ha e
es ed he APSP p oblem as a case s udy (see Sec . 6) in di e en scena ios.
Each scena io was designed wi h he aim o check he use o he laye s in ol ed
in an inc emen al ashion. A chi ec u e de ails a e shown in Table 3: (1) A sin-
gle GPU, ha uses he 3 d, 4 h, and he uning laye ; (2) Two GPUs, ha

TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 17
Table 3 Desc ip ion o he componen s ha compound he He e ogeneous Clus e s (HCs).
Small He e ogeneous Clus e (Small HC)
Node CPUIn o #CPU-co es GPU de ails
Pegaso IC2 i7 960 3.20GHz 8 GeFo ce GTX 480 +
GeFo ce GTX 680
Nodoyuna IC2 Q8200 2.33GHz 4 -
T asgo/Apolo IC2 Q6600 2.40GHz 4/4 -
Geopa IX E7310 1.6GHz 16 -
Pa an IC2 E6550 2.33GHz 2 -
A c01/02 IC2 6300 1.86GHz 2/2 GeFo ce 9600GT/-
A c03 AMD A X2 3600+ 2 GeFo ce 8500GT
A c09 IC Q8299 2.33GHz 4 -
Big He e ogeneous Clus e (Big HC): Small HC plus he ollowing machines
Node CPUIn o #CPU-co es GPU de ails
Ti an01/02/05 IX E5-2620 2.00GHz 4/4/12+12 -
Ti an03/04 IX E5645 2.40GHz 8+8/8+8 -
A c05/06 IX E5630 2.53GHz 8+8/4 -
A c07 IX X-5675 3.07GHz 12+12 -
A c08 IX E5-2620 2.00GHz 12+12 -
in ol e he 2nd laye in addi ion o he p e ious ones; (3)Pegaso: A sha ed-
memo y sys em wi h wo GPUs and eigh CPU-co es ( wo o handling he
GPUs and six o compu ing), in o de o es he 2nd laye by mixing wo
di e en kinds o compu a ional uni s; (4) Small HC : Small he e ogeneous
clus e , ha uses all laye s o TuCCompi; and (5) Big HC : Big he e ogeneous
clus e o e alua e he scalabili y o he model.
We se he pa ame e o he concu en ke nel execu ion o ou (MK=4).
The wo kload scheduling used o he scena ios desc ibed below is he cus-
omized mas e -sla e policy p esen ed in Sec . 6.2. No e ha he beha io o
he equi able policies, o ou he e ogeneous scena ios would esul in a bo -
leneck o he slowes node whe eas he es a e idle. Table 3 desc ibes he
he e ogeneous pla o ms used o ou expe imen s. Fo each node, we indica e
he numbe o CPU-co es and GPUs. The nodes un Ubun u Desk op 10.04
OS, wi h CUDA 4.2 and d i e 295.41. The Big HC con ains a o al o 180
CPU-co es and 4 GPUs. Howe e , each GPU de ice is go e ned by a single
CPU co e, hus, he o al numbe o eal compu a ional uni s is 180 (176 CPU-
co es plus 4 GPUs). The mul i-GPU sys em includes he 2 GPUs o he Pegaso
machine. The single GPU scena io uses he as es o hem, he GTX 480.
Finally, wi h he aim o es ing he pe o mance gain o e ed by he p o-
posed 4 h and Tuning laye s, we ha e compa ed he execu ion o a single GPU
connec ing o disconnec ing he op imiza ions in oduced by hese laye s. Fo
he non-au oma ically op imized e sions (wi hou 4 h and Tuning laye s), we
ha e chosen some o he op imal alues ecommended by CUDA ha maximize
he GPU occupancy execu ing a single ke nel a a ime.
7.2 Inpu Se Cha ac e is ics
The inpu se is composed o a collec ion o g aphs andomly gene a ed by a
g aph-c ea ion ool used by [24] in hei expe imen s. The g aph gene a ion
me hod leads o i egula loads when applying indi idual SSSP sea ches. The
18 Hec o O ega-A anz e al.
20
40
60
80
100
120
140
1000K 1500K 2000K 2500K
Time (sec x 10^3)
Numbe o G aph nodes
Execu ion ime o he di e en compu ing en i onmen s
1 GPU
2 GPUs
Pegaso
Small HC
Big HC
0
200
400
600
800
1000
1200
1K 2K 4K 8K 16K 32K
Time (sec)
Numbe o SSSP execu ions
The pe o mance imp o emen o he 4 h+Tuning laye s
CUDA alues
4 h+T alues
Fig. 12 Execu ion imes o he es ed scena ios o di e en g aph-sizes (le ). Pe o mance
imp o emen s ob ained by he 4 h and Tuning laye s wi h espec o CUDA ecommended
con igu a ion alues ( igh ).
0
35000
70000
105000
140000
175000
210000
245000
280000
315000
350000
EQ1 EQ2 MS
Numbe o execu ed asks
Wo kload Dis ibu ion
a c03
a c02
Pa an
Nodoyuna
a c01
T asgo
Apolo
a c09
a c06
i an01
i an02
Geopa
a c05
i an03
i an04
i an05
a c07
a c08
pegaso
Fig. 13 Numbe o execu ed asks pe node o he Big HC wi h he h ee scheduling policies.
g aphs a e s o ed in s anda d CSR o ma , and he edge weighs a e in ege s
ha andomly ange om 1 . . . 10. We ha e used ou di e en g aph-sizes,
whose numbe o e ices a e 1 049 088, 1 509 888, 2 001 408 and 2 539 008.
These sizes ha e been chosen because hey a e mul iple o he h eadBlock
sizes conside ed. In his way he GPU algo i hm is easie o implemen be-
cause we do no ha e o use padding echniques o a oid bu e o e un e o s.
The expe imen s ha e been ca ied ou jus compu ing enough ask se s (1 024,
2 048, 4 096, 8 102, 16 204, and 32 408) o p oduce su icien compu a ional load
o keep scalabili y in all scena ios.
7.3 Expe imen al esul s
GPUs s he he e ogeneous en i onmen s Figu e 12 (le ) shows he
execu ion imes o he single GPU, he mul i-GPU sys em and he wo he e o-
geneous clus e scena ios. Al hough he GPUs a e he mos powe ul de ices,
and hei combined use signi ican ly dec eases he execu ion imes, he addi-
ion o many less-powe ul compu a ional uni s enhances e en mo e he o al
pe o mance gain. Mo eo e , he use o his model has a communica ion o e -
head ac oss nodes lowe han 1%. In he Small-HC scena io, his o e head has
ne e su passed 0.589% o he o al execu ion ime. Figu e 13 shows he expe -
imen al dis ibu ion o asks pe clus e node using he MS scheduling policy,
TuCCompi: A Mul i-Laye Model o Dis ibu ed He e ogeneous Sys ems 19
compa ed wi h he heo e ical alues ha EQ1 and EQ2 s a ic policies would
ob ain.
The 4 h and Tuning laye s pe o mance gain Figu e 12 ( igh ) shows
he compa ison o he concu en ke nel execu ion, wi h MK=4, combined
wi h he alues p oposed in [10], wi h espec o one o he CUDA ecom-
mended alues o each kind o APSP ke nel on he GPU GeFo ce GTX 480,
wi h only one ke nel pe ime. The use o he concu en ke nel laye and he
op imiza ion uning educes he execu ion ime o ou es case up o 12%.
8 Conclusions and Fu u e Wo k
In his pape we p opose TuCCompi, a mul ilaye abs ac model ha helps
he p og amme o easily ob ain lexible and po able p og ams ha au oma i-
cally de ec a un- ime he a ailable compu a ional esou ces and exploi s hy-
b id clus e s wi h he e ogeneous de ices. This model o e s o he p og amme
a anspa en and easy mechanism o selec he op imal alues o GPU con ig-
u a ion pa ame e s jus cha ac e izing he na u e o he ke nels. Any pa allel
applica ion ha can be de ised as a collec ion o non-dependen asks wo king
on sha ed da a-s uc u es can be exploi ed wi h he TuCCompi model.
Compa ed wi h p e ious wo ks, TuCCompi adds a no el pa allel laye o
he adi ional pa allel dimensions, wi h he au oma ic execu ion o concu en
ke nels in a single GPU. Addi ionally, i squeezes e en mo e he compu a ional
powe o he GPUs by applying op imal alues o un ime con igu a ion pa-
ame e s, such as he h eadblock size. Fo ou es case, he use o hese bo h
new laye s leads o pe o mance imp o emen s o up o he 12%. Thus, hese
new laye s u n ou e y signi ican o he e ogeneous clus e s wi h GPUs.
The model is designed o p o ide a mechanism o plug-ins, in o de o easily
change: (1) The algo i hms o be deployed; (2) he scheduling policies o he
asks; and (3) he pa ame e alues o op imal con igu a ions o di e en
GPU a chi ec u es, wi hou making any change in he model. The use o his
model exploi s e en he less powe ul de ices o a he e ogeneous clus e , and i
co ec ly scales i mo e compu a ional uni s a e added o he en i onmen , wi h
a communica ion o e head less han one pe cen o he o al execu ion ime.
Ou u u e wo k includes he implemen a ion and es ing o new scheduling
plug-ins o new kinds o applica ions, also including p oblems wi h da a-
dependencies, and o speci ic da a pa i ion and da a dis ibu ion schemes,
needed in p oblems wi h la ge inpu da a se s. Rega ding he concu en
ke nel laye , we plan o inco po a e an op ional au o unning beha io ha
allows he amewo k o ind he op imal numbe o ke nels o be deployed
du ing he execu ion.
Acknowledgmen s
The au ho s would like o hank Ja ie Ramos L´opez o his suppo wi h echnical issues.
This esea ch has been pa ially suppo ed by Minis e io de Econom´ıa y Compe i i idad
and ERDF p og am o he Eu opean Union: CAPAP-H5 ne wo k (TIN2014-53522-REDT),
MOGECOPP p ojec (TIN2011-25639); Jun a de Cas illa y Le´on (Spain): ATLAS p ojec
(VA172A12-2); and he COST P og am Ac ion IC1305: NESUS.
20 Hec o O ega-A anz e al.
Re e ences
1. I. Fos e , Designing and Building Pa allel P og ams: Concep s and Tools o Pa allel
So wa e Enginee ing. Bos on, USA: Addison-Wesley Longman Publ., Inc., 1995.
2. U. Hoelzle and L. A. Ba oso, The Da acen e as a Compu e : An In oduc ion o he
Design o Wa ehouse-Scale Machines, 1s ed. Mo gan and Claypool Publishe s, 2009.
3. W. Ci ne, D. Pa anhos, L. Cos a, E. San os-Ne o, F. B asilei o, J. Sau e, F. A. B. Sil a,
C. Ba os, and C. Sil ei a, “Running bag-o - asks applica ions on compu a ional g ids:
The Myg id app oach,” in Pa allel P oc. In ICPP 2003, 2003, pp. 407–416.
4. A. A. Saba, S. Mohan, and R. Mangha am, “Any ime algo i hms o mul i-co e a chi-
ec u es,” P oceedings Wo k-in-P og ess Session, 2010.
5. M. Taylo , “Bi coin and he age o bespoke silicon,” in Compile s, A chi ec u e and
Syn hesis o Embedded Sys ems (CASES), 2013 In . Con e ence on, 2013, pp. 1–10.
6. A. R. B od ko b, C. Dyken, T. R. Hagen, J. M. Hjelme ik, and O. O. S o aasli, “S a e-
o - he-a in He . Compu ing,” Sci. P og am., ol. 18, no. 1, pp. 1–33, Jan. 2010.
7. R. Reyes and F. de Sande, “Op imiza ion s a egies in di e en CUDA a chi ec u es
using llCoMP,” Mic op ocess. Mic osys ., ol. 36, no. 2, pp. 78–87, Ma . 2012.
8. T. Liang, H. Li, and J. Chiu, “Enabling Mixed OpenMP/MPI P og amming on Hyb id
CPU/GPU Compu ing A chi ec u e,” in P oc. IEEE 26 h IPDPSW’12, pp. 2369–2377.
9. Y. To es, A. Gonzalez-Esc ibano, and D. Llanos, “Using Fe mi a chi ec u e knowledge
o speed up CUDA and OpenCL p og ams,” in Pa allel and Dis ibu ed P ocessing wi h
Applica ions (ISPA), 2012 IEEE 10 h In e na ional Symposium on, 2012, pp. 617–624.
10. Y. To es, A. Gonzalez-Esc ibano, and D. R. Llanos, “uBench: Exposing he impac o
CUDA block geome y in e ms o pe o mance,” J. Supe compu ing, pp. 1–14, 2013.
11. C. Yang, C. Huang, and C. Lin, “Hyb id CUDA, OpenMP, and MPI pa allel p og am-
ming on mul ico e GPU clus e s,” Comp . Physics Comm., ol. 182, pp. 266–269, 2011.
12. M. Howison, E. Be hel, and H. Childs, “Hyb id pa allelism o olume ende ing on
la ge-, mul i-, and many-co e sys ems,” Visualiza ion and Compu e G aphics, IEEE
T ansac ions on, ol. 18, no. 1, pp. 17–29, 2012.
13. M. S euwe and S. Go la ch, “SkelCL: Enhancing OpenCL o High-Le el P og amming
o Mul i-GPU Sys ems,” in Pa allel Compu ing Technologies, se . LNCS, V. Malyshkin,
Ed. Sp inge Be lin Heidelbe g, 2013, ol. 7979, p. 258272.
14. A.-E. Hugo, A. Gue mouche, P.-A. Wac enie , and R. Namys , “Composing Mul iple
S a PU Applica ions o e He e ogeneous Machines: A Supe ised App oach,” in P oc.
o IEEE 27 h IPDPSW’13. Washing on, USA: IEEE, 2013, pp. 1050–1059.
15. U. Das gee , J. Enmy en, and C. W. Kessle , “Au o- uning SkePU: A Mul i-backend
Skele on P og amming F amewo k o mul i-GPU Sys ems,” in P oc. o he 4 h
IWMSE. New Yo k, NY, USA: ACM, 2011, pp. 25–32.
16. R. Reyes, I. L´opez-Rod ´ıguez, J. J. Fume o, and F. de Sande, “accULL: an OpenACC
implemen a ion wi h CUDA and OpenCL suppo ,” in P oc. o he 18 h con e ence on
Pa allel P ocessing, se . Eu oPa ’12. Be lin, Heidelbe g: Sp inge , 2012, pp. 871–882.
17. N. Fa ooqui, A. Ke , G. F. Diamos, S. Yalamanchili, and K. Schwan, “A amewo k o
dynamically ins umen ing GPU compu e applica ions wi hin GPU Ocelo ,” in P oc.
o 4 h Wo kshop on GPGPU 2011, CA, USA, Ma ch 5, 2011. ACM, 2011, p. 9.
18. S. Pai, M. J. Thazhu ha ee il, and R. Go inda ajan, “Imp o ing GPGPU Concu ency
wi h Elas ic Ke nels,” SIGPLAN No ., ol. 48, no. 4, pp. 407–418, Ma . 2013.
19. NVIDIA, “NVIDIA CUDA P og amming Guide 6.0,” 2014.
20. D. B. Ki k and W. W. Hwu, P og amming Massi ely Pa allel P ocesso s: A Hands-on
App oach. Mo gan Kau mann, Feb. 2010.
21. E. W. Dijks a, “A no e on wo p oblems in connexion wi h g aphs,” Nume ische Ma h-
ema ik, ol. 1, pp. 269–271, 1959.
22. A. C ause , K. Mehlho n, U. Meye , and P. Sande s, “A pa alleliza ion o Dijks a’s
sho es pa h algo i hm,” in Ma hema ical Founda ions o Comp . Science 1998, se .
LNCS, L. B im, J. G uska, and J. Zla uˇska, Eds. Sp inge , 1998, ol. 1450, pp. 722–731.
23. H. O ega-A anz, Y. To es, D. R. Llanos, and A. Gonzalez-Esc ibano, “A New GPU-
based App oach o he Sho es Pa h P oblem,” in High Pe o mance Compu ing and
Simula ion (HPCS), 2013 In e na ional Con e ence on, 2013, pp. 505–512.
24. P. Ma ´ın, R. To es, and A. Ga ilanes, “CUDA solu ions o he SSSP p oblem,” in
Compu a ional Science – ICCS 2009, se . LNCS, G. Allen, J. Nab zyski, E. Seidel,
G. an Albada, J. Donga a, and P. Sloo , Eds. Sp inge , 2009, ol. 5544, pp. 904–913.