Evaluating the capabilities of the Xeon Phi platform in the context of software-only, thread-level speculation

Noname manusc ip No. (will be inse ed by he edi o ) E alua ing he capabili ies o he Xeon Phi pla o m in he con ex o so wa e-only, h ead-le el specula ion Al a o Es ebanez ·Diego R. Llanos · A u o Gonzalez-Esc ibano Recei ed: da e / Accep ed: da e Abs ac In el Xeon Phi accele a o s a e one o he newes de ices used in he ield o pa allel compu ing. Howe e , he e a e compa a i ely ew s udies conce ning hei pe o mance when using mos o he exis ing pa alleliza ion echniques. One o hem is h ead-le el specula ion, a echnique ha op imis i- cally ies o ex ac pa allelism o loops wi hou he need o a compile- ime analysis ha gua an ees ha he loop can be execu ed in pa allel. In his a icle we e alua e he pe o mance deli e ed by an In el Xeon Phi cop ocesso when using a so wa e, s a e-o - he-a h ead-le el specula- i e pa alleliza ion lib a y in he execu ion o well-known benchma ks. Ou esul s show ha , al hough he Xeon Phi deli e s a ela i ely good speedup in compa ison wi h a sha ed-memo y a chi ec u e in e ms o scalabili y, he low compu ing powe o i s compu a ional uni s when speci ic ec o iza ion and SIMD ins uc ions a e no exploi ed, indica es ha u he de elopmen o new speci ic echniques o his pla o m is needed o make i compe i i e o he applica ion o specula i e pa alleliza ion compa ing wi h high-end p ocesso s o con en ional sha ed-memo y sys ems. Keywo ds Th ead-Le el Specula ion ·Specula i e Pa alleliza ion ·Op i- mis ic Pa alleliza ion ·TLS ·Xeon Phi A. Es ebanez ·D.R. Llanos ·A. Gonzalez-Esc ibano Depa amen o de In o ma ica, Uni e sidad de Valladolid, Campus M. Delibes, 47011 Val- ladolid, Spain E-mail: al [email p o ec ed]a.es D.R. Llanos E-mail: [email p o ec ed]a.es A. Gonzalez-Esc ibano E-mail: [email p o ec ed]a.es 2 Es ebanez e al. 1 In oduc ion Cu en ly, physical limi a ions o single co e chips a e inducing a quick de el- opmen o mul ico e a chi ec u es. One o he mos ecen app oaches is he In el R Xeon PhiTM [3,11,20], a cop ocesso wi h mo e han 60 co es able o execu e ei he o loaded and na i e codes. None heless, due o i s own no el y, his cop ocesso has no ye been ex ensi ely es ed wi h non- egula pa al- lel codes. The dissemina ion o expe imen al esul s unde hese condi ions would be eally use ul o es he beha io and capabili ies o his compu ing esou ce. In his pape we use a Xeon Phi cop ocesso o un i egula applica ions ha we e specula i ely pa allelized, wi h he help o a so wa e-only, specula- i e pa alleliza ion lib a y. Th ead-Le el Specula ion (TLS) [8,34,35,42], also called Specula i e Pa alleliza ion (SP) [14,18,22,46] o Op imis ic Pa allelism [25,26] ies o ex ac pa allelism o loops ha can no be conside ed ully pa allel a compile ime. TLS op imis ically assumes ha dependence iola- ions will no occu , launching he pa allel execu ion o he loop. A ha dwa e o so wa e moni o ensu es he co ec ness o ha assump ion. I a depen- dence iola ion is de ec ed, o ending h eads a e s opped and e-s a ed in o de . A e sol ing he issue, he op imis ic, pa allel execu ion is allowed o con inue. The a ge o TLS sys ems a e usually o loops. O he loops can be conside ed as well, bu as long as hei numbe o i e a ions can no be so easily p edic ed, he applicabili y o TLS solu ions is limi ed by scheduling p oblems. In o de o handle he specula i e pa alleliza ion o a loop, all a iables ha e o be classi ied as p i a e, sha ed, o “specula i e”1. All eads o a spec- ula i e a iable a e eplaced a compile ime wi h a unc ion ha eco e s he mos up- o-da e alue o his a iable. In a simila way, all w i es o a spec- ula i e a iable a e eplaced wi h a unc ion ha no only pe o ms he w i e ope a ion, bu also ensu es ha no h ead execu ing a subsequen i e a ion has al eady consumed an ou da ed alue o his a iable. The mos common solu ion o main ain specula i e da a is o allow each h ead o keep a e sion copy o all he specula i e a iables ha ha e been locally accessed. Once a h ead inishes he execu ion o i s chunk o i e a ions, all changes in he specula i e da a a e commi ed o main memo y. TLS is use ul when execu ing codes ha p esen sca ce dependence io- la ions a un ime. O he wise, cos s associa ed o check o co ec ness, s op and e y execu ions, and commi men s, make his echnique ine icien . The con ibu ion o his pape is o es he pe o mance o a s a e-o - he-a TLS un ime lib a y using an In el Xeon Phi. This cop ocesso has a big numbe o pa allel h eads, he e o e, i is in e es ing o measu e i s beha io wi h a sha ed-memo y echnique such as TLS, when da a is pe ma- nen ly sha ed among h eads. Ou expe imen al esul s show ha he bench- 1This issue can be add essed by he p og amme , o by he use o speci ic compile s such as [4]. E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 3 ma ks conside ed scale well when unning hem wi h a Xeon Phi cop ocesso . Howe e , ou esul s also show ha , due o he i egula na u e o he a - ge applica ions o TLS echniques, and he modes compu ing capabili ies o each indi idual co e when ec o ized and SIMD ins uc ions a e no ex- ploi ed, execu ion imes a e much highe han hose gauged in con en ional sha ed-memo y sys ems. The es o his pape is s uc u ed as ollows: Sec ion 2 desc ibes he main cha ac e is ics o he Xeon Phi cop ocesso . Sec ion 3 desc ibes he so wa e- based, TLS amewo k used o es he cop ocesso . Sec ion 4 desc ibes bo h he expe imen al en i onmen and he benchma ks used. Sec ion 5 shows some expe imen al esul s in e ms o pe o mance measu ed in a sha ed-memo y sys em wi hou cop ocesso , and in a Xeon Phi cop ocesso . Sec ion 6 summa- izes some wo ks ha helps o pu in o pe spec i e ou con ibu ion. Finally, Sec . 7 concludes his pape . 2 In el Xeon Phi in a nu shell In el Xeon Phi [3,11,20] is a cop ocesso launched by In el in 2012. I is called cop ocesso because, al hough i can un a Linux ope a ing sys em by i sel , i should be placed aside ano he p ocesso o wo k p ope ly. Al hough i s imp essions migh sugges a numbe o simila i ies, i is no an accele a o such as GPUs. Whe eas he In el Xeon Phi co es a e mo e simila o classical comple e CPUs, he GPUs h ead scheduling ha dwa e is di e en . Fu he - mo e, In el Xeon Phi cop ocesso s do no use he g id, and g oups o h eads concep 2in he same way, and also he memo y la ency hiding mechanisms a e di e en . This issue hinde s easy code mig a ions o he la e kind o accele a- o s, and equi es and in-dep h unde s anding o special p og amming models as CUDA [30], o OpenCL [23]. On he o he hand, he Xeon Phi cop ocesso is able o use all s anda d pa allel p og amming models such as OpenMP [12], POSIX h eads, MPI [43], o e en OpenCL. Thus, using his new cop ocesso only equi es a minimum lea ning cu e, assuming ha he p og amme knows a leas one o hese common pa allel p og amming models. 2.1 In e nal de ails In el Xeon Phi cop ocesso s ha e up o 61 co es a 1090 MHz, in e connec ed by a high-speed bidi ec ional ing. Each co e is enhanced wi h ou ha dwa e h eads (up o 244 h eads pe cop ocesso ), and wi h a 512-KB L2 cache. L2 2As he eade may know, GPUs ha e a hie a chical ha dwa e a chi ec u e, so hey should be p og ammed wi h a hie a chical h ead s uc u e in mind [7], ha uses he concep o h eads, blocks, and g ids. A h ead is he simples uni o execu ion, in ended o p ocess a speci ic code. A block is de ined as a g oup o h eads, whe e h eads can be execu ed concu en ly o sequen ially wi h no o de . A his le el, a block allow he coo dina ion o i s h eads wi h he use o ba ie s. A g id is a g oup o blocks wi hou any possible synch oniza ion among hem. 4 Es ebanez e al. PCIe Clien Logic GDDR MC GDDR MC GDDR MC GDDR MC 4- h eads Co e L2 4- h eads Co e L2 TDTD 4- h eads Co e L2 4- h eads Co e L2 TDTD 4- h eads Co e L2 4- h eads Co e L2 TDTD 4- h eads Co e L2 4- h eads Co e L2 TDTD Fig. 1 O e iew o he mic oa chi ec u e o an In el Xeon Phi cop ocesso . cache le els a e sha ed by all co es. Fu he mo e, in addi ion o 64-bi x86 ins uc ions, co es o e 512-bi wide SIMD ec o s, making ec o iza ion he mos powe ul way o gain pe o mance. The cop ocesso is gene ally connec ed o he hos sys em ia he PCI Exp ess bus, and suppo s up o 8 GB GDDR5 memo y. Figu e 1 b ie ly desc ibes he a chi ec u e o he In el Xeon Phi. 2.2 Use o he Xeon Phi The e a e mainly wo ways o execu ing an OpenMP p og am in o a Xeon Phi cop ocesso : Na i e Execu ion: The In el Xeon Phi cop ocesso is capable o unning a Linux ope a ing sys em. I is possible o log in o he Xeon Phi om he hos p ocesso using SSH, h ough a mic0 ne wo k in e ace, added o he ke nel by a module p o ided by In el, and use i na i ely. Thus, i allows he execu ion o he ypical Linux-based commands as well as ou own p og ams. O load Ex ensions om he hos : In el de ined a se o p agmas and keywo ds o be used in pa allel codes in o de o execu e hem in cop ocesso s. A p og amme only needs o decla e he egion which should be exe- cu ed in a cop ocesso . Inside his egion, any kind o unc ion can be used. Fo example, in he case o OpenMP, a single p agma de ined as #p agma o load a ge {mic} should be used, whe e mic ep esen s he iden i ie o he a ge Xeon Phi cop ocesso . In addi ion, we should poin ou he a iables ha will be used in he cop ocesso , decla ing hei use E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 5 wi h he clauses in(),ou (), o inou (). The use o a iables wi h dy- namic size equi es o explici ly decla e he size, e.g. in(a:leng h(n)). These a iables will be copied om he hos o he de ice, and/o ice e sa, depending on hei usage. As can be seen, he Xeon Phi p og amming me hodology is eally con e- nien in o de o gain speedup wi h a ela i ely low p og amming e o . 3 Desc ip ion o he ATLaS un ime lib a y The ATLaS amewo k [4] enhances OpenMP wi h a new clause o allow he specula i e use o a iables inside a p og am. The use o his ool is simple: A p og amme only needs o include he lis o specula i e a iables in he p ede- ined specula i e clause o al pa allel o di ec i e. The compila ion and un ime sys em au oma ically ans o ms he code o a e sion capable o unning in pa allel while p ese ing sequen ial seman ics. To do so, he sys em augmen s all accesses o specula i e a iables, adap ing hem o he unc ions o he ATLaS un ime lib a y [15], ha ensu es sequen ial consis ency. In his wo k, we ha e modi ied he un ime lib a y so as o adap i o pa icula i ies o he In el Xeon Phi cop ocesso . Howe e , ou aim was doing as ew modi ica ions as possible. A mo e in-dep h adap a ion would equi e a deep modi ica ion o he lib a y implemen a ion, ha is ou o he scope o his pape . The ATLaS un ime lib a y suppo s he specula i e execu ion o o loops wi h dynamic and poin e - e e enced specula i e a iables, handling dynamic memo y, and managing, on demand, he space needed o specula i e a iables in each h ead. This TLS un ime lib a y allows he pa alleliza ion o loops wi h a iables o any da a ype, allowing he p og amme o e e ence hese a iables ei he by name o by add ess. In his sec ion we will b ie ly show he a chi ec u e o ou lib a y in o de o unde s and he s uc u es and ope a ions in which he In el Xeon Phi will be es ed. 3.1 ATLaS un ime da a s uc u es Fig. 2 ou lines he da a s uc u es needed by he specula i e un ime lib a y. In his sec ion we will only b ie ly desc ibe he main cha ac e is ics o his solu ion: A de ailed explana ion can be ound in [4,15]. A he op o he igu e, we can see wo poin e s o he non-spec and he mos -spec h eads, ha a e he h eads in cha ge o he execu ion o he non-specula i e and mos - specula i e chunks o i e a ions. The non-specula i e chunk is he one whose execu ion is no specula i e, while he mos -specula i e one is he one ha is mo e likely o su e a dependence iola ion om a p edecesso h ead. Below hese poin e s he e is a ma ix wi h Wwindow slo s ( ou in he igu e) implemen ing a sliding window ha manages he un ime o he lib a y. Each slo is esponsible o handle he specula i e execu ion o a pa icula se o i e a ions. Each slo is composed o wo ields, STATE wi h he s a e o he 6 Es ebanez e al. 1 Non−spec window slo 3 Mos −spec window slo Poin e o e . copy Da a size Poin e o local e sion Ve sion s a e 18.997 b1 9 a1 Poin e o e . copy Da a size Poin e o local e sion Ve sion s a e 7 a3 b3 25.8 &a 1 EXPLD MOD&b 4 &b3 &a3 18.997 b2 c2 128.215 7 a2 Poin e o e . copy Da a size Poin e o local e sion Ve sion s a e 8&c ELUP&c2 &b 4 EXPLD&b2 &a 1 &a2 MOD Running Done Running F eeSTATE Poin e o e sion copy Sliding window loa bcha a double c 9 23.4 32.88 specula i e a iables Use −labeled &a &b &b1 MOD EXPLD&a11 4 Ve sion copy da a s uc u es Slo 1 Slo 2 Slo 3 Slo 4 Fig. 2 Da a s uc u es o ou new specula i e lib a y. execu ion being ca ied ou in each slo ; and a poin e o main ain he posi ion o he specula i e a iables used by each slo in he execu ion. We can also ollow a possible execu ion wi h he aid o he Fig. 2. In ha igu e, he sys em is execu ing h ee consecu i e chunks o i e a ions in pa allel using h ee h eads. Ea lie chunks ha e al eady been commi ed, and he execu ion o “ u u e chunks” has no been launched ye . I is e y impo an o unde s and ha he e is no a ixed associa ion be ween h eads and slo s. Whene e a h ead is assigned a new chunk o i e a ions, i is also assigned a slo o wo k in, ha is loca ed a he igh o he mos -specula i e slo . This allows o main ain an o de ela ionship among he chunks being execu ed. In he example, he h ead wo king in Slo 1 is execu ing he non-specula i e chunk o i e a ions (as indica ed by i s RUNNING s a e); he ollowing chunk has been al eady execu ed and i s da a has been le he e o be commi ed a e he non-spec chunk inishes (since i is in DONE s a e), while he las one, he mos -specula i e chunk launched so a , is also RUNNING. In o he wo ds, he h ead in cha ge o he second chunk has al eady inished, while he non-spec and mos -spec h eads a e wo king. I mo e chunks we e pending, he eed h ead would be assigned he ollowing chunk, s a ing i s execu ion in Slo 4. Slo 2 can no be e-used ye , because he execu ion o chunk 2 le changes o specula i e a iables ha s ill ha e o be commi ed. When he non-specula i e h ead wo king in Slo 1 inishes, i will commi i s esul s and he esul s s o ed in all subsequen DONE slo s, since commi s should be ca ied ou in o de . A e ha , in ou example, he non-spec poin e will be ad anced o Slo 3 o e lec he new si ua ion. E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 7 Exp. Loaded and Upda ed (ELUP) Exposed Loaded (EXPLD) No Accessed Modi ied (MOD) s o e load s o e Spec. Spec. Spec. Spec. load Spec. load / Spec. s o e Spec. load / Spec. s o e Fig. 3 S a e ansi ion diag am o specula i e da a. In addi ion o i s STATE, each slo poin s o a da a s uc u e ha holds he e sion copies o he da a being specula i ely accessed. Fig. 2 ep esen s a loop wi h h ee specula i e a iables. A a gi en momen , he h ead execu ing he non-specula i e chunk has specula i ely accessed a iables aand b. Each ow o he e sion copy da a s uc u e keeps he in o ma ion needed o manage he access o a di e en specula i e a iable. The i s column indica es he add ess o he o iginal a iable, known as he e e ence copy. The second one indica es he da a size. The hi d one indica es he add ess o he local copy o his a iable associa ed o his window slo . Finally, he ou h column indica es he s a e associa ed o his local copy. Once accessed by a h ead, he e sion copies o he specula i e da a can be in h ee di e en s a es: Exposed Loaded, indica ing ha he h ead has o wa ded i s alue om a p edecesso o om he main copy; Modi ied, indica ing ha he h ead has w i en o ha a iable wi hou ha ing consumed i s o iginal alue; and Exposed Loaded and Upda ed, whe e a h ead has i s o wa ded he alue o a a iable and has la e modi ied i . The ansi ion diag am o hese s a es is shown in Fig. 3. Fig. 2 ep esen s a si ua ion whe e he h ead wo king in Slo 1 has pe - o med a specula i e load om a iable a(ob aining i s alue om he e e - ence copy) and a specula i e s o e o a iable b. Rega ding a, he igu e shows ha he h ead wo king in Slo 3 has o wa ded i s alue. Wi h espec o a iable b, he in o ma ion in he igu e shows ha bhas been o e w i en bo h by h eads wo king in Slo s 1 and 3 wi hou aking in o accoun i s p io alue (since bo h e sion a e in Modi ied s a e). When he commi men o he da a gene a ed by hese h eads ake place, a iable bwill be i s o e w i en by he e sion copy p oduced by he non-specula i e h ead. A e inishing his commi ope a ion, he non-spec poin e ad ances one posi ion, and when 8 Es ebanez e al. he h ead loca ed in Slo 2 inishes, i will o e w i en again he a iable b wi h he new alue. 3.2 Specula i e ope a ions In o de o manage e sioning and de ec dependence iola ions on specula i e a iables, all accesses o specula i e a iables a e eplaced a compile ime wi h a unc ion ha manages he s uc u es desc ibed abo e. Reading a specula i e a iable implies o ob ain he mos upda ed alue o his a iable, in o de o a oid, as much as possible, dependence iola ions. Fo he same eason, w i e ope a ions a e also eplaced wi h a unc ion ha , in addi ion o s o ing he alue in an in e media e place, checks i any successo h ead (a h ead which execu es a chunk o subsequen i e a ions) has used an ou da ed e sion o his a iable. In his case, he h ead should disca d he da a calcula ed so a du ing he execu ion o he cu en chunk o i e a ions and es a i . When doing so, he h ead will o wa d he co ec alue o he a iable. As can be in e ed, while a load o s o e ope a ion o a scala da um only equi es o pe o m a single memo y access, he ans o ma ion o his ope a ion in a specula i e load o s o e equi es o eplace he single memo y access o a unc ion call ha pe o ms all he equi ed ac ions. This implies ha he ime consumed by he specula i e load o s o e ope a ion can be easily wo o h ee o de s o magni ude highe han he o iginal one. The pa ial commi ope a ion is exclusi ely ca ied ou by he non-specula i e h ead. E e y ime a h ead should check i i s da a ha e o be commi ed o disca ded, i i s checks i i has no been squashed and i is he non-specula i e h ead. I he h ead is specula i e, he slo is le , since i will be commi ed la e by he non-spec h ead. I is in e es ing o no e ha each h ead only w i es on i s local e sion copy da a s uc u e, so no c i ical sec ions a e needed o p o ec hem. The only c i ical sec ion used p o ec s he sliding window da a s uc u e, because, wi hou i , a h ead could o e w i e ano he h ead’s s a e. 4 Expe imen al se up The goal o his wo k is o es he Xeon Phi cop ocesso in o -loading mode o specula i ely execu e in pa allel di e en , well-known benchma ks. In his way, he ATLaS un ime lib a y was adjus ed o o load he execu ion o he pa allel loop o he Xeon Phi cop ocesso , wi hou u he op imiza ions such as ec o iza ion, one o he mos impo an ea u es o he Xeon Phi. In any case, his ea u e is no e y use ul o ou benchma ks, mainly composed o i egula code. To es he pe o mance o he ATLaS TLS un ime, we ha e used h ee di e en eal-wo ld benchma ks, oge he wi h a syn he ic one. The eal-wo ld applica ions include he 2-dimensional Con ex Hull p oblem (2D-Hull) [10], E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 9 he Delaunay T iangula ion p oblem [29,13], and a C implemen a ion o he TREE benchma k [5]. The syn he ic benchma k is he Fas [4]. The 2D-Hull p oblem sol es he compu a ion o he con ex hull (smalles enclosing polygon) o a se o poin s in he plane. We ha e pa allelized Cla kson e al. [10]’s implemen a ion. The algo i hm s a s wi h he iangle composed by he i s h ee poin s and adds poin s in an inc emen al way. I he poin lies inside he cu en solu ion, i will be disca ded. O he wise, he new con ex hull is compu ed. No e ha any change o he solu ion ound so a gene a es a dependence iola ion, because o he successo h eads may ha e used he old enclosing polygon o p ocess he poin s assigned o hem. The p obabili y o a dependence iola ion in he 2D-Hull algo i hm depends on he shape o he inpu se . The e o e, we ha e used h ee di e en , en-million-poin inpu se s o un his benchma k. The Kuzmin inpu se ollows a Gauss- Kuzmin dis ibu ion, wi h a highe densi y o poin s a ound he cen e o he dis ibu ion space, which leads o e y ew dependence iola ions, since poin s a om he cen e a e e y sca ce. The wo o he inpu se s, Squa e and Disc, cause mo e dependence iola ions han Kuzmin, wi h hei poin s uni o mly dis ibu ed inside a squa e and a disc, espec i ely. The Squa e inpu se leads o an enclosing polygon wi h ewe edges han he Disc inpu se , hus gene a ing ewe dependence iola ions. The second eal-wo ld applica ion is he andomized inc emen al cons uc- ion o he Delaunay T iangula ion using he Jump-and-Walk s a egy, which was in oduced by M¨ucke e al. [29,13]. This inc emen al s a egy s a s wi h a numbe o poin s, called ancho s, whose con aining iangles a e known. The algo i hm inds he closes ancho o he poin o be inse ed ( he jump phase), and hen a e ses he cu en iangula ion un il he iangle ha con ains he poin o be inse ed is ound ( he walk phase). The goal o he algo i hm is o ind he ne wo k o iangles in which all he ci cumci cles o all iangles in he ne wo k a e emp y, i.e., he ci cumci cle o each iangle con ains no o he e ices han hose h ee ha de ine he iangle. We ha e used an inpu se o 5000 ancho s, and one million poin s o be inse ed. The TREE p oblem [5], unlike he p e ious wo applica ions, does no su - e om dependence iola ions, bu i is s ill no pa allelizable a compile ime because he compile is no able o ensu e ha he e a e no da a dependencies. Compile s also ind hu dles in se e al sum and maximum educ ions con ained in he code. We ha e un his benchma k wi h a 4096-poin inpu se . We ha e also used a syn he ic benchma k called Fas [4], which p esen s almos no dependences be ween i e a ions, and which was designed o es he e iciency o he specula i e scheduling mechanism, wi h ew i e a ions We ha e used wo di e en pla o ms o compa e he scalabili y o he spec- ula i e execu ion o ou benchma ks. The i s one is He acles, a 64-p ocesso se e , equipped wi h ou 16-co e AMD Op e on 6376 p ocesso s a 2.3GHz and 256GB o RAM, which uns Cen OS 7 Linux. The second one is Chime a, a se e equipped wi h wo In el Xeon E5-2620 V2 p ocesso s wi h six co es each, 32 Gb o RAM, and a Xeon Phi 3120A cop ocesso wi h 6 Gb o RAM unning a 1.1 GHz. The sys em also uns Cen OS 7 Linux. 16 Es ebanez e al. o applica ions) and i an e o was p oduced, he execu ion was es o ed o a co ec , sa ed s a e, ins ead o being es a ed. Some essays a e ocused in he implemen a ion o exis ing algo i hms in o cop ocesso s. Fo example, [33] de eloped a mul i-node 1D FFT implemen a- ion on cop ocesso s; [27] implemen ed a spa se ma ix- ec o mul iplica ion; and [32] de eloped a SQL engine ha bene i ed om he inhe en pa allelism ela ed o Xeon Phi cop ocesso s. Fu he mo e, as i is he case, he e a e many o he pape s cen e ed on he measu emen o he pe o mance ob ained om a Xeon Phi. [38] was one o he i s pape s ha used In el Xeon Phi cop ocesso ( ha was called In el Knigh s Fe y) o e alua e he pe o mance o scien i ic applica ions. La e , C ame e al. [11] e alua ed he beha io o some OpenMP benchma ks in a Xeon Phi cop ocesso . They a i med ha common OpenMP codes could be easily mig a ed o In el Xeon Phi, gaining mo e pa allel pe o mance wi hou adding o e heads. This s udy was enhanced in [39]. [16] also es ed he Xeon Phi h ough he de elopmen o some mic obenchma ks. 7 Conclusions In his wo k we ha e e alua ed he beha io o he Xeon Phi cop ocesso in he con ex o so wa e-only, h ead-le el specula ion (TLS), a pa allel ech- nique ha op imis ically execu es in pa allel sequen ial codes wi hou a p io dependence analysis. In el Xeon Phi cop ocesso s a e one o he s a e-o - he- a a chi ec u e ha aims o execu e pa allel codes. Ou expe imen al esul s show ha he pa icula memo y a chi ec u e o he Xeon Phi leads o be e scalabili y wi h ega ds o specula i e execu ion, wi h be e ela i e speedups han hose ob ained using a con en ional, sha ed-memo y a chi ec u e. How- e e , he ela i e low compu ing powe o i s compu a ional uni s when speci ic ec o iza ion and SIMD ins uc ions a e no exploi ed, indica es ha u he de elopmen o new speci ic echniques o his pla o m is needed o make i compe i i e o he applica ion o specula i e pa alleliza ion compa ing wi h high-end p ocesso s o con en ional sha ed-memo y sys ems. Al hough he use o a Xeon Phi cop ocesso o execu e so wa e-based, TLS codes is no compe i i e, he Xeon Phi a chi ec u e migh be use ul when com- bining TLS solu ions wi h o he exis ing echniques such as alue p edic ion o helpe h eads. In his way, some o he a ailable h eads could be used o help TLS execu ion, educing dependence iola ions and hus imp o ing pe o mance. Acknowledgemen s This esea ch is pa ly suppo ed by he Cas illa-Leon Regional Go - e nmen (VA172A12-2); MICINN (Spain) and he Eu opean Union FEDER (MOGECOPP p ojec TIN2011-25639, HomP og-He Sys p ojec TIN2014-58876-P, CAPAP-H5 ne wo k TIN2014-53522-REDT). E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 17 Re e ences 1. AMD Op e onTM 6300 Se ies p ocesso - quick e e ence guide. URL h ps://www. amd.com/Documen s/Op e on_6300_QRG.pd . [Las isi : June 2015] 2. In el R Xeon PhiTM p oduc amily: P oduc b ie . URL h ps://www-ssl. in el.com/con en /dam/www/public/us/en/documen s/p oduc -b ie s/ high-pe o mance-xeon-phi-cop ocesso -b ie .pd . [Las isi : June 2015] 3. In el R Xeon PhiTM cop ocesso ins uc ion se a chi ec u e e e ence manual. URL h ps://so wa e.in el.com/si es/de aul / iles/ o um/278102/327364001en.pd . [Las isi : June 2015] 4. Aldea, S., Es ebanez, A., Llanos, D., Gonzalez-Esc ibano, A.: An openmp ex ension ha suppo s h ead-le el specula ion. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems PP(99), 1–1 (2015). DOI 10.1109/TPDS.2015.2393870 5. Ba nes, J.E.: TREE. Ins i u e o As onomy. Uni e si y o Hawaii (1997). URL p: //hubble.i a.hawaii.edu/pub/ba nes/ eecode/ 6. Cadambi, S., Co iello, G., Li, C.H., Phull, R., Rao, K., Sanka adass, M., Chak ad- ha , S.: Cosmic: Middlewa e o high pe o mance and eliable mul ip ocessing on xeon phi cop ocesso s. In: P oceedings o he 22Nd In e na ional Symposium on High- pe o mance Pa allel and Dis ibu ed Compu ing, HPDC ’13, pp. 215–226. ACM, New Yo k, NY, USA (2013). DOI 10.1145/2462902.2462921. URL h p://doi.acm.o g/10. 1145/2462902.2462921 7. Cai, P., Cai, Y., Chand aseka an, I., Zheng, J.: A gpu-enabled pa allel gene ic algo i hm o pa h planning o obo ic ope a o s. In: Y. Cai, S. See (eds.) GPU Compu ing and Applica ions, pp. 1–13. Sp inge Singapo e (2015). DOI 10.1007/978-981-287-134-3 1. URL h p://dx.doi.o g/10.1007/978-981-287-134-3_1 8. Cin a, M., Llanos, D.R.: Towa d e icien and obus so wa e specula i e pa alleliza ion on mul ip ocesso s. In: P oceedings o he SIGPLAN Symposium on P inciples and P ac ice o Pa allel P og amming (PPoPP) (2003) 9. Cin a, M., Llanos, D.R.: Design space explo a ion o a so wa e specula i e pa alleliza- ion scheme. IEEE T ans. on Pa al. and Dis . Sys ems 16(6), 562–576 (2005) 10. Cla kson, K.L., Mehlho n, K., Seidel, R.: Fou esul s on andomized inc emen al con- s uc ions. Compu . Geom. Theo y Appl. 3(4), 185–212 (1993) 11. C ame , T., Schmidl, D., Klemm, M., an Mey, D.: Openmp p og amming on in el xeon phi m cop ocesso s: An ea ly pe o mance compa ison (2012) 12. Dagum, L., Menon, R.: OpenMP: an indus y s anda d API o sha ed-memo y p o- g amming. IEEE Compu a ional Science & Enginee ing 5(1), 46–55 (1998). DOI 10.1109/99.660313 13. De oye, L., M¨ucke, E.P., Zhu, B.: A no e on poin loca ion in Delaunay iangula ions o andom poin s. Algo i hmica 22, 477–482 (1998) 14. Dou, J., Cin a, M.: Compile es ima ion o load imbalance o e head in specula i e pa - alleliza ion. In: P ocs o he 13 h In . Con . on Pa allel A chi ec u es and Compila ion Techniques, PACT ’04. IEEE Compu e Socie y, Washing on, DC, USA (2004) 15. Es ebanez, A., Llanos, D., Gonzalez-Esc ibano, A.: New da a s uc u es o handle specula i e pa alleliza ion a un ime. In e na ional Jou nal o Pa allel P og amming pp. 1–20 (2015). DOI 10.1007/s10766-014-0347-0. URL h p://dx.doi.o g/10.1007/ s10766-014-0347-0 16. Fang, J., Sips, H., Zhang, L., Xu, C., Che, Y., Va banescu, A.L.: Tes -d i ing in el xeon phi. In: P oceedings o he 5 h ACM/SPEC In e na ional Con e ence on Pe o mance Enginee ing, ICPE ’14, pp. 137–148. ACM, New Yo k, NY, USA (2014). DOI 10.1145/ 2568088.2576799. URL h p://doi.acm.o g/10.1145/2568088.2576799 17. F anklin, M., Sohi, G.S.: ARB: A ha dwa e mechanism o dynamic eo de ing o mem- o y e e ences. IEEE T ans. Compu . 45(5), 552–571 (1996). DOI 10.1109/12.509907 18. Gao, L., Li, L., Xue, J., Yew, P.C.: SEED: A s a ically-g eedy and dynamically-adap i e app oach o specula i e loop execu ion. IEEE T ansac ions on Compu e s 62(5), 1004– 1016 (2013) 19. Gopal, S., Vijaykuma , T.N., Smi h, J., Sohi, G.: Specula i e e sioning cache. In: High-Pe o mance Compu e A chi ec u e, 1998. P oceedings., 1998 Fou h In e na- ional Symposium on, pp. 195–205 (1998). DOI 10.1109/HPCA.1998.650559 18 Es ebanez e al. 20. Je e s, J., Reinde s, J.: In el Xeon Phi cop ocesso high-pe o mance p og amming. Newnes (2013) 21. Jimbo ean, A., Clauss, P., Dollinge , J.F., Loechne , V., Ma inez Caamao, J.: Dynamic and specula i e polyhed al pa alleliza ion using compile -gene a ed skele ons. In e na- ional Jou nal o Pa allel P og amming 42(4), 529–545 (2014) 22. Kelsey, K., Bai, T., Ding, C., Zhang, C.: Fas ack: A so wa e sys em o specula i e p og am op imiza ion. In: P oceedings o he 7 h Annual IEEE/ACM In e na ional Symposium on Code Gene a ion and Op imiza ion, CGO ’09, pp. 157–168. IEEE Com- pu e Socie y, Washing on, DC, USA (2009). DOI 10.1109/CGO.2009.18 23. Kh onos: Open Compu ing Language (OpenCL) (2010). h p://www.kh onos.o g/ opencl/, Las isi : Decembe 2, 2013 24. K ishnan, V., To ellas, J.: A chip-mul ip ocesso a chi ec u e wi h specula i e mul i- h eading. IEEE T ansac ions on Compu e s 48(9), 866–880 (1999) 25. Kulka ni, M., Pingali, K., Wal e , B., Ramana ayanan, G., Bala, K., Chew, L.P.: Op i- mis ic pa allelism equi es abs ac ions. In: PLDI 2007 P oceedings. ACM (2007) 26. Kulka ni, M., Pingali, K., Wal e , B., Ramana ayanan, G., Bala, K., Chew, L.P.: Op i- mis ic pa allelism equi es abs ac ions. Commun. ACM 52(9), 89–97 (2009) 27. Liu, X., Smelyanskiy, M., Chow, E., Dubey, P.: E icien spa se ma ix- ec o mul- iplica ion on x86-based many-co e p ocesso s. In: P oceedings o he 27 h In e na- ional ACM Con e ence on In e na ional Con e ence on Supe compu ing, ICS ’13, pp. 273–282. ACM, New Yo k, NY, USA (2013). DOI 10.1145/2464996.2465013. URL h p://doi.acm.o g/10.1145/2464996.2465013 28. Ma cuello, P., Gonzalez, A., Tubella, J.: Specula i e mul i h eaded p ocesso s. In: P ocs o he 12 h In l con e ence on Supe compu ing, ICS ’98. ACM, New Yo k, USA (1998) 29. M¨ucke, E.P., Saias, I., Zhu, B.: Fas andomized poin loca ion wi hou p ep ocessing in wo- and h ee-dimensional Delaunay iangula ions. In: SoCG ’96 P oceedings, pp. 274–283 (1996) 30. NVIDIA: NVIDIA CUDA A chi ec u e In oduc ion and O e iew Ve sion 1.1 (2009) 31. Oancea, C.E., Myc o , A., Ha is, T.: A ligh weigh in-place implemen a ion o so - wa e h ead-le el specula ion. In: P oceedings o he wen y- i s annual symposium on Pa allelism in algo i hms and a chi ec u es, SPAA ’09. ACM, New Yo k, USA (2009) 32. Olsen, S., Romose , B., Zong, Z.: Sqlphi: A sql-based da abase engine o in el xeon phi cop ocesso s. In: P oceedings o he 2014 In e na ional Con e ence on Big Da a Science and Compu ing, BigDa aScience ’14, pp. 17:1–17:6. ACM, New Yo k, NY, USA (2014). DOI 10.1145/2640087.2644172. URL h p://doi.acm.o g/10.1145/2640087.2644172 33. Pa k, J., Bikshandi, G., Vaidyana han, K., Tang, P.T.P., Dubey, P., Kim, D.: Te a-scale 1d wi h low-communica ion algo i hm and in el® xeon phi™ cop ocesso s. In: P oceedings o he In e na ional Con e ence on High Pe o mance Compu ing, Ne - wo king, S o age and Analysis, SC ’13, pp. 34:1–34:12. ACM, New Yo k, NY, USA (2013). DOI 10.1145/2503210.2503242. URL h p://doi.acm.o g/10.1145/2503210. 2503242 34. Raman, E., Vahha ajani, N., Rangan, R., Augus , D.I.: Spice: specula i e pa allel i - e a ion chunk execu ion. In: P ocs o he 6 h annual IEEE/ACM In l symposium on Code gene a ion and op imiza ion, CGO ’08. ACM, New Yo k, USA (2008) 35. Rauchwe ge , L., Padua, D.: The l pd es : Specula i e un- ime pa alleliza ion o loops wi h p i a iza ion and educ ion pa alleliza ion pp. 218–232 (1995). DOI 10.1145/ 207110.207148 36. Rezaei, A., Co iello, G., Li, C.H., Chak adha , S., Muelle , F.: Snapi y: Cap u ing snapsho s o o load applica ions on xeon phi manyco e p ocesso s. In: P oceedings o he 23 d In e na ional Symposium on High-pe o mance Pa allel and Dis ibu ed Compu ing, HPDC ’14, pp. 1–12. ACM, New Yo k, NY, USA (2014). DOI 10.1145/ 2600212.2600215. URL h p://doi.acm.o g/10.1145/2600212.2600215 37. Ro enbe g, E., Benne , S., Smi h, J.E.: T ace cache: A low la ency app oach o high bandwid h ins uc ion e ching. In: P oceedings o he 29 h Annual ACM/IEEE In- e na ional Symposium on Mic oa chi ec u e, MICRO 29, pp. 24–35. IEEE Compu e Socie y, Washing on, DC, USA (1996) E alua ing he Xeon Phi pla o m in he con ex o so wa e-only TLS 19 38. Sa ish, N., Kim, C., Chhugani, J., Sai o, H., K ishnaiye , R., Smelyanskiy, M., Gi ka , M., Dubey, P.: Can adi ional p og amming b idge he ninja pe o mance gap o pa - allel compu ing applica ions? In: P oceedings o he 39 h Annual In e na ional Sympo- sium on Compu e A chi ec u e, ISCA ’12, pp. 440–451. IEEE Compu e Socie y, Wash- ing on, DC, USA (2012). URL h p://dl.acm.o g/ci a ion.c m?id=2337159.2337210 39. Schmidl, D., C ame , T., Wienke, S., Te bo en, C., Mlle , M.: Assessing he pe o mance o openmp p og ams on he in el xeon phi. In: F. Wol , B. Moh , D. an Mey (eds.) Eu o-Pa 2013 Pa allel P ocessing, Lec u e No es in Compu e Science, ol. 8097, pp. 547–558. Sp inge Be lin Heidelbe g (2013). DOI 10.1007/978-3-642-40047-6 56. URL h p://dx.doi.o g/10.1007/978-3-642-40047-6_56 40. Sohi, G.S., B each, S.E., Vijaykuma , T.N.: Mul iscala p ocesso s. In: P oceedings o he 22nd annual in e na ional symposium on Compu e a chi ec u e, ISCA ’95, pp. 414–425. ACM, New Yo k, NY, USA (1995). DOI 10.1145/223982.224451 41. Tian, C., Feng, M., Gup a, R.: Suppo ing specula i e pa alleliza ion in he p esence o dynamic da a s uc u es. In: P ocs o he 2010 ACM SIGPLAN con on P og amming language design and implemen a ion, PLDI ’10. ACM, New Yo k, NY, USA (2010) 42. Tian, C., Feng, M., Naga ajan, V., Gup a, R.: Copy o disca d execu ion model o specula i e pa alleliza ion on mul ico es. In: P ocs o he 41s annual IEEE/ACM In l Symp on Mic oa chi ec u e, MICRO ’41. Washing on, DC, USA (2008) 43. Walke , D.W.: The design o a s anda d message passing in e ace o dis ibu ed memo y concu en compu e s. Pa allel Compu . 20(4), 657–673 (1994). URL h p: //po al.acm.o g/ci a ion.c m?id=180103 44. Wallace, S., Calde , B., Tullsen, D.M.: Th eaded mul iple pa h execu ion. In: P o- ceedings o he 25 h Annual In e na ional Symposium on Compu e A chi ec u e, ISCA ’98, pp. 238–249. IEEE Compu e Socie y, Washing on, DC, USA (1998). DOI 10.1145/279358.279392 45. Yiapanis, P., Rosas-Ham, D., B own, G., Luj´an, M.: Op imizing so wa e un ime sys- ems o specula i e pa alleliza ion. ACM T ans. A chi . Code Op im. 9(4), 39:1–39:27 (2013) 46. Zhao, Z., Wu, B., Shen, X.: Specula i e pa alleliza ion needs igo : p obabilis ic analysis o op imal specula ion o ini e-s a e machine applica ions. In: P ocs 21s In l Con on Pa allel a chi ec u es and compila ion echniques, PACT ’12. New Yo k, USA (2012)