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)