TuCCompi: a multi-layer model for distributed heterogeneous computing with tuning capabilities

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.