New data structures to handle speculative parallelization at runtime

7 h In e na ional Symposium on High-Le el Pa allel P og amming and Applica ions (HLPP 2014) Ams e dam, Ne he lands July 3-4, 2014 New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime Al a o Es ebanez ·Diego R. Llanos · A u o Gonzalez-Esc ibano Abs ac So wa e-based, h ead-le el specula ion (TLS) is a so wa e ech- nique ha op imis ically execu es in pa allel loops whose ully-pa allel seman- ics can no be gua an eed a compile ime. Mode n TLS lib a ies allow o handle a bi a y da a s uc u es specula i ely. This desi ed ea u e comes a he high cos o local s o e and/o emo e eco e y imes: The easie he local s o e, he ha de he emo e eco e y. Un o una ely, bo h imes a e on he c i ical pa h o any TLS sys em. In his pape we p opose a solu ion ha pe o ms local s o e in cons an ime, while eco e alues in a ime ha is in he o de o T, being T he numbe o h eads. As we will see, his solu- ion, oge he wi h some addi ional imp o emen s, makes he di e ence be- ween slowdowns and no iceable speedups in he specula i e pa alleliza ion o non-syn he ic, poin e -based applica ions on a eal sys em. Ou expe imen al esul s show a gain o 3.58× o 28×wi h espec o he baseline sys em, and a ela i e e iciency o up o, on a e age, 65% wi h espec o a TLS imple- men a ion speci ically ailo ed o he benchma ks used. Keywo ds h ead-le el specula ion ·specula i e pa allelism ·memo y imp o emen s 1 In oduc ion Th ead-Le el Specula ion (TLS) [3,29,30,34], also called Specula i e Pa al- leliza ion (SP) [8,10,14,37] o Op imis ic Pa allelism [16–21] ies o ex ac pa allelism o loops ha can no be conside ed ully pa allel a compile ime. A. Es ebanez ·D.R. Llanos ·A. Gonzalez-Esc ibano Depa amen o de In o ma ica, Uni e sidad de Valladolid, Valladolid, Spain 47011 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 Es ebanez e al. TLS op imis ically assumes ha dependence iola ions will no occu , launch- ing 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 dependence 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 p oceed. 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 a e no p i a e no sha ed a e labeled a compile ime as “specula i e”. All eads o a specula 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 specula 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. The bigges challenge in so wa e-based TLS is how o educe he ime needed o (a) ge he mos up- o-da e alue when eading specula i e da a, and (b) o sea ch o a possible dependence iola ion when a h ead w i es on a specula i e a iable. No e ha bo h ope a ions imply a e sing all he e sion copies main ained by o he h eads. In he i s case, he sea ch o an up- o- da e alue implies o a e se all he da a being kep by all p edecesso h eads ( ha is, h eads being execu ing ea lie chunks o i e a ions). In he second case, he sea ch implies o a e se all he specula i e da a being main ained by all successo s. Access o p edecesso and successo copies o he da a a e in he c i ical pa h o any TLS sys em. The p oblem is e en mo e di icul o sol e i he TLS lib a y allows o specula e o e dynamic s uc u es and/o poin e -based e e ences. Among all so wa e-based TLS app oaches p oposed in he li e a u e, ew o hem a e capable o specula i ely handling dynamic da a s uc u es [20, 34]. Conside ing he di icul y o he p oblem o sol e, i is no s ange ha he solu ions p oposed ely on abs ac app oaches ha a e di icul o bo h unde s and and implemen . The con ibu ion o his pape is o show a new solu ion o a e se specula- i e da a in a so wa e-based TLS lib a y. We will desc ibe how o d ama ically dec ease he numbe o memo y accesses when sea ching o p edecesso and successo e sions o specula i e da a, while keeping he cos o local da a s o - age in O(1). Ou expe imen al esul s wi h well-known benchma ks on a eal sys em show ha hese op imiza ions lead o signi ican educ ions in he num- be o accesses needed (by a ac o o h ee o de s o magni ude) compa ing wi h a compe i i e baseline implemen a ion ha lacks his ea u e. We also p opose addi ional solu ions o u he educe he memo y alloca ion calls, New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime needed o dynamically add new a iables o he specula i e s uc u es ha should be managed a un ime. The combined e ec o all hese imp o emen s is an imp essi e inc emen in he speedups ob ained. The es o his pape is s uc u ed as ollows: Sec ion 2 pu s his wo k in pe spec i e wi h he exis en solu ions in his ield. Sec ion 3 desc ibes he baseline solu ion de eloped in a p e ious esea ch. Sec ion 4 desc ibes bo h he expe imen al en i onmen and he benchma ks used o e alua e he baseline solu ion and ou new p oposals. Sec ion 5 e alua es he cos s o specula i e eads and w i es, om a heo e ical and expe imen al poin s o iew. Sec ion 6 add esses he imp o emen s applied o he lib a y in o de o imp o e i s pe o mance. Sec ion 7 desc ibes wo addi ional imp o emen s ha leads o an e e as e specula i e pa allel execu ion. Sec ion 8 shows some expe imen al esul s in e ms o pe o mance measu ed in a eal sys em. Finally, Sec ion 9 concludes his pape . 2 Rela ed wo k Memo y managemen is a c i ical ield in he con ex o specula i e pa al- leliza ion. As we will see in his pape , an adequa e handling o specula i e a iables makes a huge di e ence in e ms o pe o mance. We will i s e- iew some e o s in his ield, and la e we will concen a e on he p oblem o ensu ing as accesses o e sion da a. 2.1 TLS app oaches Se e al esea ches ha e been cen e ed in he pa alleliza ion o loops wi h c oss- i e a ion dependences h ough h ead-le el specula ion (TLS) echniques. Some o hem ha e been implemen ed in ha dwa e [5,7,11,15,24,31,32], h ough he design o speci ic chips, o he addi ion o some unc ionali ies. Bu he e a e also se e al so wa e app oaches ha suppo he men ioned pa allelism wi h no a chi ec u al changes [3,14,16,18,20,23,28,30,34]. One o his so wa e ap- p oaches is he wo k o Tian, Feng, Naga ajan and Gup a in [34,35], whe e hey p oposed he Copy-o -Disca d (Co D) execu ion model, in which he execu ion o pa allel h eads a e sepa a ely managed by he non-specula i e one. Spec- ula i e h eads ead alues o he non-specula i e h ead and pe o m hei compu a ion, a e ha , specula i e h eads a e commi ed in o de . A e ha esul s a e checked by non-specula i e h ead in o de o p ese e seman- ics o sequen ial o de . Commi ope a ion is pe o med by non-specula i e h ead h ough he Copy o Disca d mechanism ha checks whe he esul s a e co ec o be copied o he non-specula i e da a, o disca ded wi h no cos o he wise. Howe e , Co D app oach did no suppo hose applica ions whose specula i e a iables we e dynamically alloca ed, so in [33] Tian, Feng and Gup a de eloped mechanisms ha enable hei solu ion o do i . Es ebanez e al. Cin a and Llanos [3,4] con ibu ed ano he scheme mainly based on an agg essi e sliding window, wi h checks o da a dependence iola ions on spec- ula i e s o es ha educed synch oniza ion cons ain s, and wi h ine- uned da a s uc u es. Kulka ni e al. in he wo k desc ibed in [20,21], in oduced Galois a sys em o suppo complex poin e -based se s o elemen s in op imis ic pa allelism. They we e cen e ed on pa allelize applica ions wi h complex s uc u es as linked lis s, g aphs, ees, e c. In pa icula , hese app oaches su e ed om some speci ic bo lenecks be- cause a dynamic s uc u e could change hei size du ing he execu ion, and usually hey a e bigge han he s a ic s uc u es, so a e se hem could be e y ine icien . 2.2 The p oblem o a e sing e sion copies Ea lie so wa e-based TLS lib a ies such as [3] only allowed specula i e ac- cesses o s a ic da a s uc u es such as ec o s. In his way, i a gi en h ead wan ed o ge he mos up- o-da e alue o he i- h elemen o a specula i e ec o , i simply looked o i in he i- h posi ion o he e sion copy o each p edecesso . W i es we e handled in he same way, looking o he i- h posi ion o each successo ’s e sion copy o he specula i e da a. I is easy o see ha , wi h T h eads, he complexi y o his sea ch is in O(T), an a o dable alue aking in o accoun ha Tis usually in he o de o en hs o p ocesso s. Mode n TLS lib a ies allow o specula i ely access no only s a ic ec o s, bu a bi a y memo y loca ions. Usually, his da a is kep wi h no pa icula o de , an a ac i e solu ion since he cos o inse ing a new elemen o he s uc u e is exac ly in O(1). The p oblem wi h his solu ion is ha he sea ch o a p e ious alue (due o a ead ope a ion) and he sea ch o po en ial iola ions (due o a w i e) imply a e sing all e sion da a kep by all p e- decesso s and successo s, espec i ely. I we conside T h eads and Mda a elemen s in each e sion copy, his lead o a complexi y ha is in O(T×M), wi h Mpo en ially in he o de o millions o elemen s. The solu ion o s o ing alues using an o de ed da a s uc u e may seem easonable, bu his comes a he cos o a highe s o age ime, ha is also undesi able. As we will see, ou solu ion keeps he s o age cos in O(1) while he a e sing cos is in O(T×M H), wi h Han a bi a ily la ge cons an . In p ac ice, his solu ion leads o a a e sing cos ha is jus in O(T). Ceze e al. [2] add essed he p oblem o he complexi y o he basics ope - a ions in ol ed in TLS p ocesses. To do his hey used a kind o hash encode , called signa u e, ha manages he add esses accessed by each specula i e h ead. Each signa u e is a se o add esses and allowed o ea se e al ad- d esses as i hey we e a single one. They enhanced he a chi ec u e wi h some ha dwa e mechanism ha could e icien ly ope a e wi h his hashed in o ma- ion. The main di e ences wi h ou sys em a e ha hei ’s is ha dwa e-based New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime and he hash is used o pe o m ope a ions o a g oup o add esses ins ead a e sing hei da a. Kulka ni e al. [19] in oduced some imp o emen s ha inc eased he e - iciency o Galois. They implemen ed a me hod o pe o m da a pa i ioning in he da a in a way ha all elemen s o a se whe e mapped o an abs ac domain, and hen, ans o med again o physical co es. Mendez-Lojo e al. [26] also desc ibed h ee echniques o op imize i egula applica ions. The i s one is modi ying codes in a way ha all ead ope a ions a e done be o e any w i e ope a ion. The second one, based on he calcula ion o dependences be o e he execu ion. The las one, is used o hose algo i hms whose bo le- necks a e loca ed in he accesses o da a se s and i is based on emo ing he co espondence be ween i e a ion and ac i i ies. Unlike ou solu ion, all hese op imiza ions a e e e ed o algo i hms. Tian e al. [33] add essed he p oblems ela ed o s o age and loca ion o in e media e alues in Co D wi h he use o a mapping able ha ansla e add esses be ween specula i e and non-specula i e h eads. In ha wo k, au- ho s a i med ha using a hash unc ion was ine icien , wi h a 6×slowdown wi h espec o o he al e na i es due o he use o a complex hash unc ion. Ou wo k shows ha he use o a simple hash unc ion leads o imp essi e speedups in se e al applica ions. Meh a a e al. [25] desc ibed STMLi e, a so wa e ansac ional memo y model modi ied o suppo specula i e pa alleliza ion. I was specially designed o educe o e heads o accesses o a iables logs in ansac ions using a h ead ha managed he execu ion. Managemen o add esses was handled wi h he use o hash-based solu ions. Mo e so wa e ansac ional model sys ems ha e used hashes o imp o e hei pe o mance, i.e., Ha is e al. [12] used hashes o emo e duplica es in an undo log. Oancea e al. [27] desc ibed hei own TLS app oach called SpLIP, cen- e ed on dec easing o e heads o specula i e ope a ions o p e ious app oaches. They implemen ed non-locking ope a ions whe e was possible, and used a hash unc ion o imp o e loca ion o e sion copies. Thei hash is based on mapping adjacen zones o he a ay ha s o ed specula i e alues in a single place. As we will see, ou solu ion is no based on joining nea add esses, since we do no need o g oup specula i e a iables. A simila app oach o SpLIP[27], called MiniTLS, was de eloped by Yi- apanis e al. [36]. They in oduced a new s uc u e ha op imized memo y o e heads o classical app oaches based on he idea o mapping e e y use - accessed add ess in o an a ay o in ege s using a hash unc ion. Jimbo ean e al. [13] in oduced a TLS amewo k specially designed o specula i ely execu e nes ed loops. To do so, au ho s used ea u es o polyhe- d al model o dynamically ans o m code in a mo e op imized e sion ha led o highe speedups. F amewo k consis ed on di iding execu ion in wo pa s, one o gene a e some skele ons, and o he one ha selec ed he op imized code a un ime. Es ebanez e al. 3 Desc ip ion o he baseline solu ion So wa e specula i e schemes should alloca e some addi ional memo y in o de o hold he in o ma ion ela ed o specula i e execu ions. The use o his da a is manda o y o enable eco e y ope a ions ha could a ise in an op imis ic execu ion. In his con ex , memo y needed could be alloca ed dynamically, o s a ically, and he use o an app oach ins ead o he o he is a c i ical decision ha di ec ly in luences in he o e all memo y used in a p og am. Ou en i e esea ch amewo k elies on a i s , poin e -based e sion o a so wa e-based TLS lib a y ha s ic ly ollows he p inciples o he lib a y de eloped by Cin a and Llanos [3,4]. Tha wo ks es ablished he ounda ions o he co ec ness o he specula i e execu ion o sequen ial applica ions. Thei app oach only allowed o specula e on a iables encapsula ed inside a ec o . The use o his solu ion equi ed h eads o alloca e memo y o he en i e ec o , e en i many posi ions o i we e no used du ing he execu ion o he assigned chunk o i e a ions. So, in he case ha Mwas he specula i e a iables used in a p oblem execu ed wi h T h eads, and each a iable need a by e, a iables equi e M×(T+1) by es o be s o ed, because an addi ional space is equi ed o sa e he pe sis en copy. Mo eo e , using ec o s equi ed ha all he a iables used had o sha e he same ype. The e sion ha we use as a baseline in his wo k has been o iginally p esen ed in [9]. This baseline e sion 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, e e encing hese a iables ei he by name o by add ess. As we will see, al hough his lib a y e ec i ely e- mo es many cons ains o Cin a and Llanos’ solu ion, he s ic adhe ence o he o iginal a chi ec u e leads o unaccep able cos s o specula i e eads and w i es. In his sec ion we will b ie ly show he a chi ec u e o ou lib a y, since i will be used as he baseline o es some imp o emen s p oposed in his pape . 3.1 Da a s uc u es The da a s uc u es needed by he baseline specula i e lib a y a e depic ed in Fig. 1. A ma ix wi h Wwindow slo s ( ou in he igu e) implemen s a sliding window ha manages he un ime o he lib a y. Each slo is esponsible o manage he specula i e execu ion o a pa icula se o i e a ions. The slo s assigned o he non-specula i e and he mos -specula i e h eads a e indica ed by wo a iables, non-spec and mos -spec. Each slo is composed o wo ields, STATE wi h he s a e o he 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. New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime 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. 1 Da a s uc u es o ou new specula i e lib a y. An example o he execu ion o a loop is also depic ed in Fig. 1. The loop has been di ided in o h ee chunks o i e a ions, and i will be execu ed in pa allel using h ee h eads. 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 he co esponding slo o wo k in. This allows o main ain an o de ela ionship among he chunks being execu ed. In he depic ed example, 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 ol- lowing 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 a e ye o be commi ed. As we will see in Sec . 3.3, when he non-specula i e h ead wo king in slo 1 in- ishes, 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. 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. 1 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 Es ebanez e al. 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. 2 S a e ansi ion diag am o specula i e da a. 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. 2. Fig. 1 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. 3.2 Specula i e loads and s o es The in e ace o ou implemen a ion o specload() is as ollows: specload(VOID* add , UINT size, UINT chunk numbe , VOID* alue) The i s pa ame e is he add ess o he specula i e a iable; he second one is he size o he a iable; he hi d one is he numbe o he chunk being execu ed (needed o in e he slo being used); and he ou h one is a poin e o a place o s o e he da um eques ed. New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime 2 1E F A B D G C3 1 Non−spec window slo Poin e o e . copy Da a size Poin e o local e sion Ve sion s a e Poin e o e . copy Da a size Poin e o local e sion Ve sion s a e 18.997 b1 9 a1 9 a3 b3 25.8 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 Slo 1 Slo 2 Slo 3 Slo 4 RunningSTATE 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 &a 1 EXPLD MOD&b 4 &b3 &a3 8&c ELUP&c2 &b 4 EXPLD&b2 Running Ve sion copy da a s uc u es &a 1 &a2 MOD F eeRunning SQUASHED Mos −spec window slo 23 Fig. 3 S eps o a specula i e load (1..3) and specula i e s o e (A..G). Recall ha specload() should e u n he mos up- o-da e alue a ailable o he specula i e a iable. Fig. 3 shows how specula i e load wo ks. Suppose ha he h ead wo king in slo 2 has only accessed a iable cso a , and hen i calls specload(&b, sizeo (b), 2, & alue) o ob ain a alue o b. The h ead wo king in slo 2 scans om i s e sion copy da a s uc u e o i s p edecesso s’ un il he alue is ound (poin 1). O he wise, i alue has no been used be o e, i is ob ained om e e ence copy. In he Fig. 3 he h ead wo king in slo 1 has used b, so he h ead ha called specload() copies he alue o i s own local copy (poin 2), and add a ow o i s e sion copy da a s uc u e. No e ha he p ocess desc ibed in he poin 1 o Fig. 3, ha is, sea ching o a copy o a a iable is a sequen ial p ocess ha o igins big bo lenecks. The in e ace o specs o e() is simila as specload()’s, bu in his case he las pa ame e is a poin e o he alue o be s o ed. Recall ha specs o e() should no only s o e he new alue, bu also check whe he a successo has consumed an ou da ed alue o i . Fig. 3 shows he sequence o e en s ela ed o a specula i e s o e. Suppose ha he h ead wo king in slo 2 execu es specs o e(&a, sizeo (a), 2, & emp), whe e emp holds he alue 7. Th ead wo king in slo 2 sea ches o a local e sion copy o ain i s s uc u e (poin A). I i was ound, i s local alue would be upda ed, bu in his case, a new ow is added wi h he add ess o a, i s size, he add ess o he new local e sion (poin B), and i s s a e (poin C). Then, he h ead ha pe o med he call should check whe he any successo h ead has consumed an ou da ed alue o a(poin D). In his case, he h ead wo king in slo 3 has loaded his alue (poin E), so, i should be squashed (poin s F and G). No e ha he p ocess desc ibed in he poin D o Fig. 3, ha is, sea ching o copies o ou da ed a iables is a sequen ial p ocess ha o igins big bo lenecks. Es ebanez e al. 1 Non-spec window slo b' c' Poin e o e . copy Da a size Offse in local e sion Ve sion s a e Slo 1 Slo 2 Slo 3 Slo 4 STATE Poin e o e sion copy Sliding window floa b double c 23.4 32.88 specula i e a iables Use -labeled 8&c ELUP0 &b 4 EXPLD8 F ee Ve sion copy da a s uc u es F ee Mos -spec window slo 1 Running F ee Poin e o local e sion da a ec o Local e sion da a s uc u es Ac ual fi s ee posi ion 12 128.215 01 2 345 6 78 9 10 11 12 13 ... 18.997 Fig. 5 Reducing ope a ing sys em calls: Example wi h he new da a s uc u es #i de LP64 ypede s uc da acell { ypede unsigned long long in baseType; oid ∗o igPoin e ; #else unsigned in copyO se ; ypede unsigned long in baseType;sho unsigned in size; #endi sho unsigned in s a e; }da acell; ... ... baseType ma ix[HASH][4][ROWS]; da acell ma ix[HASH][ROWS] ... ... (a) (b) Fig. 6 Implemen a ion o a s a ic example o he da a s uc u e in (a) he baseline solu ion, and (b) he imp o ed e sion. 7.2 S uc u es ins ead o bu e s We ha e also modi ied he implemen a ion o e sion copy da a s uc u es in o de o imp o e da a alignmen [1] and he space needed by each e sion copy da a s uc u e. The baseline ep esen a ion is shown in Fig. 6(a). Al hough he di e en elemen s in a ow ha e di e en sizes, he decla a ion should alloca e space enough o s o e he bigges one, in ou case he poin e o he o iginal da a. This implemen a ion equi es 8 by es o each alue, ha is, a o al o 32 by es o he ep esen a ion o each ow. Ou new ep esen a ion, shown in Fig. 6(b), s a es a iables as a s uc . Wi h his ep esen a ion we achie e wo goals. Fi s , we educe he necessa y memo y o a hal , since he memo y needed o s o e his new s uc u e is 16 by es (a oid poin e needs 8 by es, an unsigned in needs 4 by es, and each unsigned sho in needs 2 by es). Second, his s uc u e also exploi s he memo y ep esen a ion o C s uc s because hese ypes a e usually s o ed wi h he ollowing pa e ns[1]: S uc u es be ween 1 New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime 0 1 2 3 4 5 6 7 1 3 5 7 9 11 13 15 Speedup Numbe o p ocesso s Baseline e sion Imp o ed e sion Cin a and Llanos’ e sion 1 3 5 7 9 11 13 15 Numbe o p ocesso s Baseline e sion Imp o ed e sion Cin a and Llanos’ e sion (a) (b) 0 1 2 3 4 5 6 7 1 3 5 7 9 11 13 15 Speedup Numbe o p ocesso s Baseline e sion Imp o ed e sion Cin a and Llanos’ e sion (c) Fig. 7 Pe o mance compa ison o 2D-Hull benchma k wi h h ee di e en inpu se s: (a) Disc, (b) Squa e, and (c) Kuzmin. and 4 by es o da a a e usually padded so ha he o al s uc u e is 4 by es; S uc u es be ween 5 and 8 by es o da a a e padded so ha he o al s uc u e is 8 by es; s uc u es be ween 9 and 16 by es o da a a e padded so ha he o al s uc u e is 16 by es; and s uc u es g ea e han 16 by es a e padded o 16 by e bounda y. A di e en o de o he a iables would add paddings because he compile may decide o s o e hem in 4-by es places. The e o e, ou new s uc u e is op imized o minimize he memo y space needed, hus educing he numbe o cache misses. 8 Expe imen al esul s Figs. 7 compa e he pe o mance esul s o he specula i e pa alleliza ion o he 2D-Hull wi h inpu se s. Bo h he baseline e sion o he lib a y and ou new solu ion a e compa ed. While he baseline sys em is no able o ob ain speedups in any case, he new solu ion leads o a maximum speedup o 1.681× o he Disc inpu se ( ep esen ing a 28×pe o mance inc emen wi h espec o he baseline TLS lib a y), 3.094× o he Squa e inpu se (14.19×pe o - mance inc emen ) and 4.188× o Kuzmin (8.63×pe o mance inc emen ). To Es ebanez e al. 0 1 2 3 4 5 6 7 8 1 3 5 7 9 11 13 15 Speedup Numbe o p ocesso s Baseline e sion Imp o ed e sion Cin a and Llanos’ e sion 1 3 5 7 9 11 13 15 Numbe o p ocesso s Baseline e sion Imp o ed e sion Cin a and Llanos’ e sion (d) (e) Fig. 8 Pe o mance compa ison o Delaunay benchma k wi h an inpu se o (a) 100K poin s, and (b) 1M poin s. pu hese esul s in o pe spec i e, we also show he bes speedups ob ained by Cin a and Llanos wi h hei specula i e un ime sys em. Recall ha hei solu ion, while e ec i e, is cons ained by many limi a ions, and i is no gen- e alizable o any applica ions. Resul s show ha ou solu ion allows o deli e a good pe cen age o he maximum speedup a ainable (up o 68%), while o e ing a specula i e solu ion applicable in many mo e cases. Figs. 8 compa es he pe o mance esul s o he specula i e pa alleliza ion o he Delaunay iangula ion wi h wo inpu se s. The new solu ion is again clea ly be e , wi h a maximum speedup o 3.646× o he 1M-poin s inpu se ( ep esen ing a 3.58×pe o mance inc emen wi h espec o he baseline TLS lib a y), and 3.873× o he 100K-poin s inpu se (5.40×pe o mance inc emen ). Again, ou solu ion is compa ed o he ailo ed lib a y o Cin a and Llanos, ob aining, on a e age, a 75% and a 68% o hei maximum speedup in he 1M-poin s and he 100K-poin s inpu se s, espec i ely. 9 Conclusions In his pape , we ha e shown a solu ion o a p oblem ha is common o any so wa e-based TLS lib a y: How o educe sea ch imes when accessing o emo e e sions o specula i e da a. To mi iga e his p oblem, we ha e im- plemen ed some op imiza ions such as he use o an ex emely-simple hash unc ion o a oid he need o a e sing all e sion da a, he educ ion in he numbe o memo y managemen sys em calls, and he de elopmen o new da a s uc u es o educe memo y consump ion and cache misses. Ou expe - imen al e alua ion wi h non-syn he ic benchma ks on a eal, sha ed-memo y mul ip ocesso clea ly shows ha hese imp o emen s ha e a d ama ic im- pac on pe o mance: All applica ions es ed had a be e execu ion imes han hose ob ained in he baseline e sion, and he pe o mance esul s a e a signi ican ac ion o hose ob ained wi h a sys em speci ically designed o handle hese benchma ks. New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime Acknowledgemen s The au ho s would like o hank he anonymous e iewe s o hei help ul commen s. The au ho s would also like o hank M . Se gio Aldea o his help in his wo k. This esea ch is pa ly suppo ed by he Cas illa-Leon Regional Go e nmen (VA172A12-2); Minis e io de Indus ia, Spain (CENIT OCEANLIDER); MICINN (Spain) and he Eu opean Union FEDER (MOGECOPP p ojec TIN2011-25639, CAPAP-H3 ne - wo k TIN2010-12011-E, CAPAP-H4 ne wo k TIN2011-15734-E). Re e ences 1. B yan , R., Da id Richa d, O.: Compu e sys ems: a p og amme ’s pe spec i e. P en ice Hall (2003) 2. Ceze, L., Tuck, J., To ellas, J., Casca al, C.: Bulk disambigua ion o specula i e h eads in mul ip ocesso s. In: P ocs o he 33 d in l symposium on Compu e A chi ec u e, ISCA ’06. IEEE Compu e Socie y, Washing on, DC, USA (2006) 3. 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) 4. 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) 5. Cin a, M., Ma ´ınez, J.F., To ellas, J.: A chi ec u al suppo o scalable specula i e pa alleliza ion in sha ed-memo y mul ip ocesso s. In: P oc. o he 27 h in l. symp. on Compu e a chi ec u e (ISCA), pp. 256–264 (2000) 6. 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) 7. Dai, W., An, H., Li, Q., Li, G., Deng, B., Wu, S., Li, X., Liu, Y.: A p io i y-awa e NoC o educe squashes in h ead le el specula ion o chip mul ip ocesso s. In: P ocs o he 2011 IEEE 9 h In . Symposium on Pa allel and Dis ibu ed P ocessing wi h Applica ions, ISPA ’11. IEEE Compu e Socie y, Washing on, DC, USA (2011) 8. 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) 9. Es ebanez, A., Llanos, D.R., Gonzalez-Esc ibano, A.: Desa ollo de un mo o de pa - alelizaci´on especula i a con sopo e pa a a i m´e ica de pun e os. In: P oceedings o he XXIII Jo nadas de Pa alelismo. Elche, Alican e, Spain (2012) 10. 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) (2013) 11. Hammond, L., Hubbe , B.A., Siu, M., P abhu, M.K., Chen, M., Oluko un, K.: The s an o d Hyd a CMP. IEEE Mic o 20(2), 71–84 (2000) 12. Ha is, T., Plesko, M., Shinna , A., Ta di i, D.: Op imizing memo y ansac ions. In: P oceedings o he 2006 ACM SIGPLAN Con e ence on P og amming Language Design and Implemen a ion, PLDI ’06, pp. 14–25. ACM, New Yo k, NY, USA (2006) 13. 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 pp. 1–17 (2013) 14. 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 ocs o he 7 h annual IEEE/ACM In l symp on Code gene a ion and op imiza ion, CGO ’09 (2009) 15. 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. Compu e s, IEEE T ansac ions on 48(9), 866–880 (1999) 16. Kulka ni, M., Bu sche , M., Inkulu, R., Pingali, K., Cas¸ca al, C.: How much pa allelism is he e in i egula applica ions? In: P ocs o he 14 h ACM SIGPLAN Symposium on P inciples and P ac ice o Pa allel P og amming, PPoPP ’09. New Yo k, USA (2009) 17. Kulka ni, M., Ca ibaul , P., Pingali, K., Ramana ayanan, G., Wal e , B., Bala, K., Chew, L.P.: Scheduling s a egies o op imis ic pa allel execu ion o i egula p og ams. In: P ocs o he 20 h Annual Symposium on Pa allelism in Algo i hms and A chi ec- u es, SPAA ’08, pp. 217–228. ACM, New Yo k, NY, USA (2008) Es ebanez e al. 18. Kulka ni, M., Nguyen, D., P oun zos, D., Sui, X., Pingali, K.: Exploi ing he commu a- i i y la ice. In: P ocs o he 32nd ACM SIGPLAN Con on P og amming Language Design and Implemen a ion, PLDI ’11. ACM, New Yo k, NY, USA (2011) 19. Kulka ni, M., Pingali, K., Ramana ayanan, G., Wal e , B., Bala, K., Chew, L.P.: Op i- mis ic pa allelism bene i s om da a pa i ioning. In: P oceedings o he 13 h In e na- ional Con e ence on A chi ec u al Suppo o P og amming Languages and Ope a ing Sys ems, ASPLOS XIII, pp. 233–243. ACM, New Yo k, NY, USA (2008) 20. 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) 21. 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) 22. Lee, D., Schach e , B.: Two algo i hms o cons uc ing a delaunay iangula ion. In- e na ional Jou nal o Compu e & In o ma ion Sciences 9(3), 219–242 (1980) 23. M. Gup a and R. Nim: Techniques o specula i e un- ime pa alleliza ion o loops. Supe compu ing (1998) 24. 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) 25. Meh a a, M., Hao, J., Hsu, P.C., Mahlke, S.: Pa allelizing sequen ial applica ions on commodi y ha dwa e using a low-cos so wa e ansac ional memo y. In: P ocs o he 2009 con on P og. language design and implemen a ion, PLDI ’09. NY, USA (2009) 26. M´endez-Lojo, M., Nguyen, D., P oun zos, D., Sui, X., Hassaan, M.A., Kulka ni, M., Bu sche , M., Pingali, K.: S uc u e-d i en op imiza ions o amo phous da a-pa allel p og ams. In: P oceedings o he 15 h ACM SIGPLAN Symposium on P inciples and P ac ice o Pa allel P og amming, PPoPP ’10, pp. 3–14. ACM, New Yo k, USA (2010) 27. 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) 28. P abhu, M.K., Oluko un, K.: Using h ead-le el specula ion o simpli y manual pa al- leliza ion. In: P oceedings o he Nin h ACM SIGPLAN Symposium on P inciples and P ac ice o Pa allel P og amming, PPoPP ’03. ACM, New Yo k, NY, USA (2003) 29. 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) 30. Rauchwe ge , L., Padua, D.: The LRPD es : Specula i e un- ime pa alleliza ion o loops wi h p i a iza ion and educ ion pa alleliza ion. SIGPLAN No . 30(6) (1995) 31. Sanka alingam, K., Naga ajan, R., Liu, H., Kim, C., Huh, J., Bu ge , D., Keckle , S., Moo e, C.: Exploi ing ILP, TLP, and DLP wi h he polymo phous TRIPS a chi ec u e. In: P ocs o he 30 h Annual In l Symp on Compu e A chi ec u e, ISCA ’03 (2003) 32. S e an, J.G., Colohan, C.B., Zhai, A., Mow y, T.C.: A scalable app oach o h ead-le el specula ion. In: P oceedings o he 27 h annual in e na ional symposium on Compu e a chi ec u e, ISCA ’00, pp. 1–12. ACM, New Yo k, NY, USA (2000) 33. 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) 34. 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) 35. Tian, C., Feng, M., Naga ajan, V., Gup a, R.: Specula i e pa alleliza ion o sequen ial loops on mul ico es. In . J. Pa allel P og am. 37(5), 508–535 (2009) 36. 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) (2013) 37. 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)