An OpenMP Extension that Supports Thread-Level Speculation

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 1 An OpenMP Ex ension ha Suppo s Th ead-Le el Specula ion Se gio Aldea, Al a o Es ebanez, Diego R. Llanos, Senio Membe , IEEE, and A u o Gonzalez-Esc ibano Abs ac —OpenMP di ec i es a e he de- ac o s anda d o sha ed-memo y pa allel p og amming. Howe e , OpenMP does no gua an ee he co ec ness o he pa allel execu ion o a gi en loop i un ime da a dependences a ise. Consequen ly, many highly- pa allel egions canno be sa ely pa allelized wi h OpenMP due o he possibili y o a dependence iola ion. In his pape , we p opose o augmen OpenMP capabili ies, by adding Th ead-Le el Specula ion (TLS) suppo . Ou con ibu ion is h ee old. Fi s , we ha e de ined a new specula i e clause o a iables inside pa allel loops. This clause ensu es ha all accesses o hese a iables will be ca ied ou acco ding o sequen ial seman ics. Second, we ha e c ea ed a new, so wa e-based TLS un ime lib a y o ensu e co ec ness in he pa allel execu ion o OpenMP loops ha include specula i e a iables. Thi d, we ha e de eloped a new GCC plugin, which seamlessly ansla es ou OpenMP specula i e clause in o calls o ou TLS un ime engine. The esul is he ATLaS C Compile amewo k, which akes ad an age o TLS echniques o expand OpenMP unc ionali ies, and gua an ees he sequen ial seman ics o any pa allelized loop. Index Te ms—Pa allelism and concu ency, code gene a ion, h ead-le el specula ion, op imis ic pa alleliza ion F 1 INTRODUCTION THE ad en o mul ico e echnologies in he new cen u y made pa allel p ocessing ubiqui ous. Many pa allel languages and pa allel ex ensions o sequen ial languages ha e been p oposed o exploi he capabili ies o mode n mul ico e sys ems. The mos success ul p o- posal is OpenMP [1], a di ec i e-based pa allel ex ension o sequen ial languages (such as C, Fo an o C++) ha allows pa allel execu ion o use -de ined code egions. Figu e 1 shows an example o (a) a sequen ial C loop, and (b) i s pa alleliza ion wi h OpenMP di ec i es. As can be seen, all a iables inside he loop body should be classi ied as p i a e o sha ed. In o mally speaking, a iables whose alues a e always se in a gi en i e a ion be o e hei use should be labeled as p i a e, while a i- ables ha ha e alues isible by all h eads execu ing he loop in pa allel should be classi ied as sha ed. In ou example, a[] is a ead-only sha ed ec o , while [] is a sha ed ec o ha is modi ied by each i e a ion. As OpenMP is a simple and powe ul mechanism o code pa alleliza ion, i s use has se e al limi a ions. Fi s , he classi ica ion o all a iables inside he c i ical egion, acco ding o hei use, is a ime-consuming, e o -p one ask. Second, OpenMP does no ensu e he pa allel execu ion o he code acco ding o sequen ial seman ics, as he p og amme is esponsible o such a ask. In he example shown in Fig. 1, he p og amme is esponsible o ensu ing ha each h ead modi ies a di - e en elemen o []. Thi d, in many cases, po en ially- •S. Aldea, A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano a e wi h Dp o. In o má ica, Uni e sidad de Valladolid, Campus Miguel Delibes, 47011, Valladolid, Spain. E-mails: {se gio,diego,a u o}@in o .u a.es, [email p o ec ed] #p agma omp pa allel o p i a e (i,b) sha ed (a, ) o (i=0; i<MAX; i++) { o (i=0; i<MAX; i++) { b = unc(i); b = unc(i); [i] = b *a[i]; [i] = b *a[i]; } } (a) (b) Fig. 1. Example o loop pa alleliza ion wi h OpenMP. #p agma omp pa allel o p i a e (i,b) sha ed (a,k) specula i e( ) o (i=0; i<MAX; i++) { o (i=0; i<MAX; i++) { b = unc(i); b = unc(i); i (b==k) i (b==k) [i] = [i-b]; [i] = [i-b]; else else [i] = b *a[i]; [i] = b *a[i]; } } (a) (b) Fig. 2. A loop ha canno be sa ely pa allelized wi h cu en OpenMP clauses (a), and i s pa alleliza ion wi h ou new specula i e clause (b). pa allel egions canno be sa ely pa allelized because hei con ol low depends on un ime da a. Conside he code depic ed in Fig. 2. Suppose ha he alue o k is no known a compile ime. Assuming b>0 o a gi en i, i he pa allel execu ion o he loop calcula es i e a ion ibe o e i e a ion i-b, access o [i-b] may e u n an ou da ed alue, b eaking sequen ial seman ics. The only way o gua an ee a co ec beha io would be o se ialize he execu ion o i e a ions i−band i, a di icul ask in he gene al case. Sa ely pa allelizing loops ha may p esen un ime dependence iola ions can ha e a signi ican impac in e ms o pe o mance. We ha e p e iously measu ed he amoun o loop-le el pa allelism ha could be ex ac ed om he SPEC CPU 2006 benchma k, wi h di e en IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 2 echniques [2]. Ou esul s show ha , while a ound 48% o he loops p esen in he applica ions analyzed ( ep esen ing a ound 13% o hei agg ega e execu ion ime) a e po en ially pa allelizable wi h exis en pa allel p og amming models such as OpenMP, an addi ional 38% o loops ( ep esen ing a ound 20% o he execu ion ime) could be un in pa allel wi h he help o un ime specula i e pa alleliza ion echniques. Ou p oposal consis s in augmen ing OpenMP wi h so wa e-based, Th ead-Le el Specula ion (TLS) ech- niques o ensu e ha de ini ions and uses o sha ed a i- ables a e ca ied ou acco ding o sequen ial seman ics. This solu ion allows he OpenMP p og amming model o be used e en when dependence iola ions may a ise a un ime. To do so, we de ine a new specula i e clause. Va iables labeled as specula i e will be accessed ollowing wo simple ules: •All eads o a specula i e a iable will e u n he mos up- o-da e alue o his a iable. This alue can ei he be gene a ed p e iously by his h ead o by any o i s p edecesso s, de ined as h eads ha execu e ea lie i e a ions acco ding o sequen ial seman ics. This is called a o wa ding ope a ion. •All w i es o a specula i e a iable will s o e he alue in a local copy, and will check whe he a successo h ead ( ha is, h eads ha a e execu - ing “ u u e” i e a ions) has consumed an ou da ed alue o his a iable. In his case, he o ending h ead (and possibly some o i s successo s) will be s opped and e-s a ed, in o de o o ce hem o consume he upda ed alue o he a iable. This is called a squash ope a ion. As long as a dependence iola ion o ces he alues o specula i e a iables o be disca ded, all h eads main ain e sion copies o he specula i e a iables being accessed. When a non-specula i e h ead ( ha is, a h ead wi h no ali e p edecesso s) success ully inishes he execu ion o i s block o consecu i e i e a ions, all changes a e commi ed o he main copy o all specula i e a iables. A e his commi ope a ion, he h ead will become he mos specula i e one, since i will execu e he ollowing block o i e a ions ha emains unassigned. The h ee main con ibu ions o his pape a e he ollowing: 1) We ha e de ined an ex ension o OpenMP spec- i ica ions, adding a clause o suppo specula i e accesses o da a in omp pa allel o cons uc s. This clause ollows he guidelines p oposed by Aldea e al. [3]. 2) We ha e c ea ed a b and-new TLS un ime lib a y ha handles he pa allel execu ion o loops ha includes specula i e a iables, including suppo o specula i e access o poin e -based da a o any size wi hou he need o a compile- ime analysis. This un ime lib a y no only manages accesses o specula i e da a, bu also handles he scheduling o i e a ions among h eads and ensu es co ec ness in he pa allel execu ion o he loop. 3) Finally, we ha e de eloped a new plugin-based compile pass o he GCC OpenMP implemen a- ion o suppo he specula i e clause. This pass ans o ms he loop o be pa allelized, inse ing he un ime TLS calls needed o (a) dis ibu e blocks o i e a ions among p ocesso s, (b) pe o m specula- i e loads and s o es o specula i e a iables, and (c) pe o m pa ial commi s o he co ec esul s calcula ed so a . The esul is ATLaS, a comple e amewo k ha allows OpenMP o execu e loops in pa allel wi hou he need o a p io dependence analysis. Ou pe o mance e alua- ion, using bo h syn he ic and eal-wo ld applica ions on a eal mul ico e sys em, shows ha his app oach leads o pe o mance speedups. The es o he pape is o ganized as ollows. Sec ion 2 in oduces TLS key concep s. Sec ion 3 desc ibes some ela ed wo k. Sec ion 4 b ie ly desc ibes ou p oposal o a new OpenMP specula i e clause. Sec ion 5 desc ibes in de ail he a chi ec u e o ou new TLS un ime lib a y. Sec ion 6 shows how we ha e added suppo o handle ou new clause in he GCC OpenMP compile . Sec ion 7 p esen s he expe imen al e alua ion. Finally, Sec . 8 summa izes ou conclusions. 2 THREAD-LEVEL SPECULATION Specula i e pa alleliza ion (SP), also called Th ead-Le el Specula ion (TLS) o Op imis ic Pa alleliza ion [4], as- sumes ha sequen ial code can be op imis ically exe- cu ed in pa allel, and elies on a un ime moni o o ensu e ha no dependence iola ions a e p oduced. A dependence iola ion appea s when a gi en h ead gene a es a da um ha has al eady been consumed by a successo in he o iginal sequen ial o de . In his case, he esul s calcula ed so a by he successo (called he o ending h ead) a e no alid and should be disca ded. Ea ly p oposals [5], [6] s op he pa allel execu ion and es a he loop se ially. O he p oposals s op he o - ending h ead and all i s successo s, e-execu ing hem in pa allel [7], [8], [9], [10]. A hi d op ion (see e.g. [11], [12], [13]) is o only e-s a he o ending h ead and subsequen h eads ha ha e ac ually consumed any alue om i , leading o a no iceable pe o mance imp o emen in some cases. Figu e 3 shows an example o h ead-le el specula ion. The igu e ep esen s ou h eads execu ing agmen s o ou consecu i e i e a ions o he same loop. The alue o xwas no known a compile ime, so he compile was no able o ensu e ha accesses o he SV s uc u e do no lead o dependence iola ions when execu ing hem in pa allel. Howe e , he ac ual alues o x o each i e a ion a e known a un ime. Unde specula i e execu ion, each h ead main ains a e sion copy o he da a s uc u e ha is accessed specula i ely (he e, he SV ec o ). A compile ime, he o iginal code is augmen ed o pe o m specula i e IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 3 5 8 10 LocalVa 1 = SV[x] SV[x] = LocalVa 2 6 7 9 LocalVa 1 = SV[x] SV[x] = LocalVa 2 2 4 6 LocalVa 1 = SV[x] SV[x] = LocalVa 2 (c) In−o de commi o da a om success ully− inished h eads 0 1 3 SV[x] = LocalVa 2 Time LocalVa 1 = SV[x] Th ead 1 (non spec) (i e a ion 1, x = 1) (i e a ion 2, x = 1) Th ead 2 (i e a ion 3, x = 2) Th ead 3 Th ead 4 (mos −spec) (i e a ion 4, x = 2) Re e ence copy o s [2] (Time 4: Th ead 2 o wa ds upda ed alue o s [1] om h ead 1) (Time 3: h ead 1 de ec s no dependence iola ions) (Time 6: h ead 1 de ec s no dependence iola ions) (Time 8: Th ead 3 o wa ds alue o s [2] om e e ence copy) (Time 7: Th ead 4 o wa ds alue o s [2] om e e ence copy) (Time 10: Th ead 3 de ec s iola ion: h ead 4 squashed) (b) Specula i e loads wi h mos − ecen alue o wa ding (a) Specula i e s o es plus de ec ion o dependence iola ions Fig. 3. Example o specula i e execu ion o a loop and summa y o ope a ions ca ied ou by a un ime TLS lib a y. s o es, specula i e loads, and in-o de commi s. In addi- ion, he loop s uc u e is ea anged in o de o allow he e-execu ion o squashed i e a ions. The ollowing pa ag aphs desc ibe hese ope a ions in mo e de ail. Specula i e s o es A compile ime, all w i e ope a ions o he da a s uc u e being specula i ely accessed should be eplaced wi h a specula i e s o e unc ion. This unc ion w i es he da um in he e sion copy o he cu en h ead, and ensu es ha no h ead execu ing a subse- quen i e a ion has al eady consumed an ou da ed alue o his s uc u e elemen , a si ua ion called “dependence iola ion”. I such a iola ion is de ec ed, he o ending h ead and i s successo s a e s opped and es a ed. In he example depic ed in Fig. 3, he checks o depen- dence iola ions pe o med by Th eads 1 and 2 do no ind any successo ha has consumed an ou da ed alue o SV[1]. Howe e , a ime 10, Th ead 3 disco e s ha Th ead 4 has al eady consumed an ou da ed alue o SV[2], so a dependence iola ion has been ound. The e o e, Th ead 4 should be s opped and es a ed, in a so-called squash ope a ion. When Th ead 4 is es a ed, i will o wa d he upda ed alue o SV[2] om Th ead 3, being able o con inue he execu ion o he i e a ion assigned o i . Specula i e loads A compile ime, all eads o he specula i e da a s uc u e a e eplaced by a unc ion ha pe o ms a specula i e load. This unc ion ob ains he mos up- o-da e alue o he elemen being accessed. I a p edecesso ( ha is, a h ead execu ing an ea lie i e a ion) has al eady ead o w i en ha elemen , he alue is o wa ded (as Th ead 2 does in Fig. 3). I no , he unc ion ob ains he alue om he e e ence copy o he da a s uc u e (as Th ead 3 does in he igu e). Commi -o -disca d ope a ion I no dependence iola- ion a ises du ing he execu ion o a gi en h ead, i s changes o he specula i e da a s uc u e should be com- mi ed o he e e ence copy o he da a s uc u e. No e ha commi s should be done in o de , o ensu e ha he mos up- o-da e alues a e s o ed. In he case o a dependence iola ion, he in e media e esul s calcula ed by his h ead should be disca ded, an ope a ion known as h ead squash. In bo h cases, he scheduling un ime sys em should assign a new block o i e a ions o he h ead o con inue he pa allel wo k. Scheduling i e a ions unde TLS The scheduling me hod used wi h specula i e pa alleliza ion is di e en om classic scheduling me hods, e.g. [14], [15], [16]. Unde TLS, he execu ion o an i e a ion o chunk o i e a ions can be disca ded, so he scheduling me hod should be able o e-assign he squashed i e a ion o he same o a di e en h ead. The loop s uc u e should be changed o allow e-execu ion o i e a ions. 3 RELATED WORK So wa e-based TLS (STLS) p oposals Se e al wo ks p opose specula i e pa alleliza ion mechanisms ha bene i om di e en deg ees o code ans o ma- ions. Tian e al. [17] p opose he use o he Copy- o -Disca d (Co D) execu ion model o a oid expensi e s a e- eco e ing mechanisms in case o misspecula ion. This p oposal equi es an in-dep h analysis o he o igi- nal loop, and he use o code ans o ma ion echniques ha educe he p obabili y o misspecula ion. Specula- i e loads in his p oposal always ge he non-specula i e e sion o he da a, so successo s o he o ending h ead a e no a ec ed by misspecula ions. In [18], a so wa e- based TLS sys em is p oposed o help in he manual pa alleliza ion o applica ions. The sys em equi es he p og amme o ma k “possibly pa allel egions” (PPR) IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 4 in he applica ion o be pa allelized. The sys em elies on a so-called “ ou namen ” model, wi h di e en h eads coope a ing o execu e he egion specula i ely, while an addi ional h ead uns he same code sequen ially. I a single dependence a ises, specula ion ails en i ely and he sequen ial execu ion esul s a e used ins ead. The use ulness o his sys em is based on he assump ion ha he code chosen by he p og amme will likely no p esen any dependencies. An imp o emen o his scheme is desc ibed in [19], elying on dependence hin s p o ided by he p og amme o allow explici da a communica ion be ween h eads, hus educing un ime dependence iola ions. In [9], a model ha combines di e en echniques such as h ead-le el specula ion, helpe h eads and un-ahead execu ion is p oposed o dynamically choose he mos app op ia e combina ion a un ime. A wo k o he Co D g oup [20] aims o educe he cos o misspecula ion, by eco ding in e media e s a es du ing he specula i e execu ion. In his way, ins ead o abo ing a comple e ask, only a po ion o he ask is e-execu ed. This solu ion comes a he cos o a mo e complex code analysis, in o de o inse in e media e checkpoin s whe e he ea lies eads o he specula i e a iables a e ound. Oancea e al. de eloped SpLIP [21], an STLS app oach cen e ed on dec easing o e heads o specula i e op- e a ions. In his wo k, load and s o e ope a ions di- ec ly wo k wi h he main copy o he a iables, and dependences a e managed h ough excep ions. They ex ac many o he ideas om so wa e T ansac ional Memo y (STM), implemen ing non-locking ope a ions whe e possible, and p ese ing a log o a iables and imes amps o handle he execu ion. ATLaS’ un ime lib a y and SpLIP a e bo h STLS implemen a ions ha can ex ac speed-up om sequen ial applica ions wi h complex dependences. Concep ually, he main di e ence be ween ATLaS’ un ime lib a y and SpLIP is he way hey manage hei ope a ions, since ATLaS manages e sion copies, while SpLIP wo ks wi h he main e sion o specula i e da a. ATLaS also inco po a es a compile- ime phase ha g ea ly simpli ies he use o specula ion o p oduc ion pu poses. To ake ad an age o SpLIP, he use has o ew i e he en i e applica ion almos om sc a ch, since he code o be pa allelized and he unde lying lib a y a e ex emely highly coupled. ATLaS compile- ime and un ime ea u es a e ma u e enough o be used in p oduc ion en i onmen s wi h almos no e o . Finally, an adap i e app oach o specula i e loop execu ion, which handles nes ed loops, has ecen ly been p oposed [10]. Ou p oposal does handle nes ed loops anspa en ly, in he same way s anda d OpenMP does. TLS and So wa e T ansac ional Memo y Bo h TLS and so wa e T ansac ional Memo y (STM) [22] a e so- lu ions ha use specula i e echniques o imp o e he p og ammabili y and pe o mance o p og ams. TLS has se e al ea u es in common wi h TM, such as he use o specula i e eads and w i es ha can be olled back. Howe e , and despi e hei implemen a ion simila i ies, hey sol e di e en p oblems. The goal o TM is o help in explici pa allel p og amming by educing he cos s o he locks equi ed o a oid ace condi ions in c i ical sec ions [23], [24]. On he o he hand, TLS depa s om a sequen ial p og am, b eaks i in o asks and ies o execu e hem op imis ically in pa allel, while p ese ing sequen ial seman ics. The main di e ence be ween TLS and TM is ha TLS ensu es a o al o de in he commi ope a ion, which is always ca ied ou sequen ially om he non-specula i e o he mos -specula i e h ead. As long as TM does no p ese e any o de in he commi ope a ions, STM lib a ies canno be used di ec ly o mimic he beha io o loop-based specula i e pa alleliza ion whene e se- quen ial seman ics should be p ese ed. Sec ion 1 o he Supplemen al Ma e ial u he discusses his issue. Finally, he e a e se e al in e es ing TLS-TM hyb id app oaches. These solu ions a e e iewed in Sec . 2 o he Supplemen al Ma e ial. TLS ex ensions o OpenMP Ea ly wo ks, such as [25], p opose he use o OpenMP di ec i es o enable specula- i e pa allelism, he de ails o he implemen a ion being anspa en o he p og amme . In a simila way, [26] exposes he ad an ages o using OpenMP o gi e explici hin s o he compile and he unde lying ha dwa e o ex ac specula i e pa allelism. O he p oposals aim o in eg a e T ansac ional Mem- o y echnologies in o OpenMP (see [27], [28], [29], [30], [31], [32], [33], [34], [35]). These p oposals a e e iewed in Sec . 3 o he Supplemen al Ma e ial. 4 SEMANTICS OF OUR specula i e CLAUSE The p oblem o adding specula i e pa alleliza ion sup- po o OpenMP can be handled using wo app oaches. The i s one equi es he addi ion o a new di ec i e, such as p agma omp specula i e o . Howe e , he e a e many OpenMP ela ed componen s ha should be mod- i ied in o de o add a new di ec i e. A simple solu ion is o add a new OpenMP clause o he lis o a ailable pa allel cons uc s, which allows he p og amme o enume a e which a iables should be handled specula- i ely. The syn ax o his clause is: specula i e( a iable[, a _lis ]) In his way, i he p og amme is unsu e abou he use o a ce ain da a s uc u e, he can simply label i as specula i e. In his case, a ailo ed OpenMP implemen- a ion should eplace all de ini ions and uses o his da a s uc u e wi h he co esponding specload() and spec- s o e() unc ion calls. An addi ional commi _o _disca d() unc ion will be au oma ically inse ed once each h ead has inished i s chunk o i e a ions, o ei he commi he esul s, o o es a he execu ion i he h ead has been squashed due o a un ime dependence iola ion. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 5 Ou new TLS un ime lib a y, desc ibed in he ol- lowing sec ion, was indeed de eloped using s anda d OpenMP clauses. In o de o in eg a e ou lib a y in o an expe imen al OpenMP amewo k ha includes a new specula i e clause, wo pa icula i ies o ou TLS lib a y should be aken in o accoun . Fi s , since ou TLS un ime lib a y has also been de eloped using OpenMP, some p i a e and sha ed con ol a iables should be added o he a ge loop in o de o use i . The e o e, i a specula i e clause is ound by he compile , his occu ence, which implies he use o ou specula i e lib a y, should igge he inclusion o se e al p i a e and sha ed a iables o he exis ing lis s. As long as OpenMP allows he epe i ion o clauses, so he compile ime suppo o his new specula i e clause can add addi ional p i a e and sha ed clauses ha will la e be expanded by he compile . Second, he s anda d scheduling me hods imple- men ed by OpenMP a e no enough o handle spec- ula i e pa alleliza ion. These me hods assume ha he execu ion o a chunk o i e a ions will ne e ail, so hey do no conside he possibili y o es a ing a chunk ha has ailed due o a dependence iola ion. The e o e, i is necessa y o use a specula i e scheduling me hod. Ins ead o di iding he i e a ion space, we ha e ollowed he solu ion adop ed in [7], eplacing he o iginal loop s uc u e wi h a new loop composed by Ni e a ions, Nbeing he numbe o h eads. A he beginning o he loop, each h ead is assigned a di e en chunk o i e a ions o be execu ed. I a h ead has success ully inished a chunk, i will ecei e a new chunk ha has no ye been success ully execu ed. In he case o a de- pendence iola ion ha igge s a squash ope a ion, he scheduling me hod will y o eassign o ha h ead he chunk whose execu ion has ailed, in o de o imp o e locali y and cache eu iliza ion. 5 A NEW RUNTIME LIBRARY FOR TLS We ha e de eloped a new TLS un ime lib a y ha suppo s he specula i e execu ion o o loops. The lib a y a chi ec u e ollows he design p inciples o he specula i e pa alleliza ion lib a y de eloped by Cin a and Llanos [7], [36]. In o de o unde s and ou solu ion, a b ie desc ip ion o ha p oposal is needed. In [7], [36], Cin a and Llanos de eloped a un ime lib a y ha uses a sliding window mechanism ha al- lows he pa allel execu ion o Wconsecu i e chunks o i e a ions. Each ime he non-specula i e h ead inishes, a pa ial commi akes place; he h ead execu ing he ol- lowing chunk becomes he new, non-specula i e h ead; and he window ad ances, allowing he execu ion o new chunks o i e a ions. Despi e i s good pe o mance igu es, he un ime lib a y de eloped by Cin a and Llanos su e s om se e e limi a ions. Fi s , hei lib a y equi es all specula i e a iables o be packed in a single, one-dimensional ec o be o e he s a o he specula i e loop. Second, all specula i e a iables should sha e a single da a ype. Thi d, specula i e a iables can only be accessed by name inside he loop (no e e ences by ad- d esses o poin e s we e allowed). Finally, his un ime lib a y c ea es W e sion copies o he en i e specula i e da a s uc u e, being W he size o he sliding window being used, ins ead o jus keeping e sion copies o he da a elemen s ac ually accessed. These limi a ions p e en he use o his un ime lib a y o suppo a specula i e clause, whe e a iables and da a s uc u es labeled as specula i e may be o di e en da a ypes, can be accessed by name o add ess, and whe e specula i e da a s uc u es can be o any size. Ou TLS un ime lib a y o e comes all hese limi a- ions. I allows a iables o any da a ype o be specula- i ely accessed, bo h by name o add ess, and managing he space needed o e sion copies on demand. In his sec ion, we will b ie ly show he gene al a chi ec u e o he lib a y. A mo e de ailed desc ip ion o he design decisions aced can be ound in [37]. 5.1 Loop ans o ma ion o specula i e execu ion Figu e 4 b ie ly shows he ans o ma ion o a pa allel loop o specula i e execu ion. This ans o ma ion is igge ed by ou p oposed specula i e clause, and i is au oma ically ca ied ou by ou compile plugin. The changes a e b ie ly desc ibed below: •Line 1: Addi ional, in e nal a iables a e de ined. •Line 2: Be o e he loop, he omp_se _num_ h eads() unc ion is called o de ine he numbe o h eads o be used. •Line 3: Aspecbegin() unc ion is called o ini ialize he execu ion o he ollowing pa allel loop. I i is he i s loop being pa allelized, his unc ion also ini ializes he un ime specula i e lib a y. •Line 4: All a iables labeled as specula i e a e au o- ma ically eclassi ied as sha ed. Besides his change, all eads and s o es inside he loop body on hose specula i e a iables (see below) a e eplaced wi h calls o specload() and specs o e() unc ions, in o - de o keep sequen ial consis ency, as desc ibed in Sec . 2. Ou compile plugin also labels o he in e nal a iables needed by he un ime sys ems as p i a e and sha ed, such as id and h eads in ou example. •Line 5: The o iginal loop s uc u e is eplaced wi h a pa allel o loop wi h jus “ h eads” i e a ions. This launches he numbe o desi ed h eads. •Line 6: Awhile( ue) loop ensu es ha each h ead epea edly equi es a chunk o i e a ions om he o iginal loop o be p ocessed. I no chunks a e le , ab eak s a emen exi s his loop, hus eaching he end o he h ead (see line 12). •Line 7: Inside he loop, each h ead ecei es he index o he i s i e a ion o i s assigned chunk and p oceeds wi h he o iginal loop body. •Lines 8-10: The ead o b a iable in line 8 o Fig. 4(a) is eplaced wi h a call o he specload() IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 6 1: cha a; loa b; 1: cha a; loa b; cha emp; loa alue, in id, h eads; ... 2: omp_ge _num_ h eads( h eads); 3: specbegin(MAX); 4: #p agma openmp pa allel o 4: #p agma openmp pa allel o p i a e (i) specula i e (a,b) p i a e (i, id, emp, alue,...)sha ed (a,b, h eads,...) 5: o (i=0; i<MAX; i++) { 5: o ( id=0; id< h eads; id++) { 6: while( ue) { 7: i = assign_ ollowing_chunk( id, MAX,...); O iginal loop code, pa 1 O iginal loop code, pa 1 8: a = (b); 8: specload(&b, sizeo (b),..., & alue); 9: emp = ( alue); 10: specs o e(&a, sizeo (a),..., & emp); O iginal loop code, pa 2 O iginal loop code, pa 2 11: commi _o _disca d_da a( id,...); 12: i (no_chunks_le ( id, MAX,...)) b eak; 13: } 14: } 14: } (a) (b) Fig. 4. Loop ans o ma ion o allow i s specula i e execu ion: O iginal (a) and ans o med (b) code. unc ion, which eco e s he mos up- o-da e alue o his a iable. The exac beha io o specload() is desc ibed la e in his sec ion. The alue is s o ed in a p i a e, empo al loca ion. Line 8 o Fig. 4(a) also pe o ms a w i e on a. This w i e is eplaced wi h a call o specs o e() (line 9), which i s s o es he alue in a local e sion copy and hen checks whe he a successo has al eady consumed an ou da ed alue o a. I so, he o ending h ead and some o all o i s successo s (depending on he squash policy being de ined [13]) a e squashed. I is impo an o highligh ha only he lines o he o iginal loop body ha in ol e specula i e a iables a e changed in his way: he emaining code is le wi h no changes. •Line 11: Once he o iginal loop body is inished, a call o commi _o _disca d_da a() checks whe he he h ead has been squashed o no . I a squash op- e a ion was issued by a p edecesso , local copies o specula i e da a will be disca ded. I he h ead has no been squashed and i is he no -spec one, a pa ial commi will occu . Pa ial commi s will be desc ibed in Sec . 5.4. •Line 12: A e inishing hei asks ela ed o he cu en chunk, all h eads check whe he he e a e no pending chunks o be execu ed. I he e is no pending wo k, h eads lea e he while loop. When all h eads ha e exi ed he while( ue) loop, he end o he pa allel sec ion has been eached and (despi e he numbe o needed a emp s) all chunks o i e a ions ha e been success ully execu ed, and hei esul s com- mi ed o he specula i e a iables. 5.2 Da a s uc u es The da a s uc u es needed by he new specula i e lib a y a e depic ed in Fig. 5(a). The sliding window mechanism is implemen ed by a ma ix wi h Wwindow slo s ( ou in he igu e). Each slo ac s as a “sc a chpad” used o handle he specula i e execu ion o a pa icula chunk o i e a ions. Two global a iables, non-spec and mos -spec, indica es he slo assigned o he execu ion o he non-specula i e and mos -specula i e chunks o i e a ions a each pa icula momen . These a iables a e used as limi s o s op he sea ch o p edecesso e - sions and he sea ch o possible dependence iola ions, espec i ely. The STATE ield indica es he s a e o he execu ion being ca ied ou in each slo . The igu e ep esen s he pa allel execu ion o a loop. The loop has been di ided in o h ee chunks o i - e a ions, and 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 ixed associa ion be ween h eads and slo s. When- e e a h ead is assigned a new chunk o i e a ion, i is also assigned he co esponding slo o wo k in. This allows an o de ela ionship o be main ained be ween he chunks being execu ed. In ou 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 al eady been 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 he 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 canno 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 . 5.4, 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. 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. Figu e 5(a) ep esen s a si ua ion whe e he p og amme decla ed h ee a iables wi hin IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 7 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 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. s o e Spec. load Spec. load / spec. s o e (a) (b) Fig. 5. Da a s uc u es o ou new specula i e lib a y (a) and s a e ansi ion diag am o specula i e da a (b). ou specula i e clause. 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. No e ha , al hough en i e da a s uc u es may be labeled as specula i e, specula i e eads and w i es a e always ca ied ou o e scala a iables. The e o e, he maximum size o he da a being specula i ely ac- cessed will be he size o he bigges scala a iable in he a chi ec u e conside ed. This alue is 8 by es in 64-bi a chi ec u es. The hi d column 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. 5(b). Figu e 5(a) 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 s 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 bwas o e w i en by bo h h eads wo king in slo s 1 and 3. 5.3 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. Recall ha specload() should e u n he mos up- o- da e alue a ailable o he specula i e a iable. Figu e 6 shows how he specula i e load wo ks. Suppose ha he h ead wo king in slo 2 has only accessed o a iable c so a , and i hen calls specload(&b, sizeo (b), 2, & alue) o ob ain a alue o b. The sequence o e en s is he ollowing: 1) The h ead wo king in slo 2 scans i s e sion copy da a s uc u e o check whe he a alue o bhas been al eady s o ed he e. As long as he only specula i e a iable accessed so a is c, his sea ch p oduces no esul s. 2) Ou h ead goes o i s p edecesso e sion copy da a s uc u e and scans i in o de o ind a alue o b. I s p edecesso has s o ed a alue o i , so ou h ead copies i s alue o a new loca ion. No e ha , i no alue o bwe e ound he e, ou h ead would go o he nex p edecesso , un il he non- specula i e h ead is ound. I no p edecesso had used he alue, ou h ead would ge he alue om he e e ence copy. 3) A e s o ing a copy o b’s alue, he h ead wo k- ing in slo 2 adds a new ow o i s e sion copy da a s uc u e, s o ing he add ess o b, i s da a size, he add ess o he e sion copy o bbeing managed by he h ead, and he new s a e o his e sion copy, EXPLD. The call o specload() inishes by e u ning IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 8 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. 6. S eps o a specula i e load (1..3) and specula i e s o e (A..F). he alue 18.997 in he add ess indica ed by i s ou h pa ame e . The in e ace o specs o e() is he same as specload(), 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 . Figu e 6 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. The sequence o e en s is he ollowing: A) The h ead wo king in slo 2 sea ches o a local e sion copy o a. A his momen , only copies o c and ba e s o ed in i s e sion copy da a s uc u e, so he sea ch p oduces no esul s. I awe e ound, his h ead would upda e i s s a us acco ding o he s a e diag am o Fig. 5(b), and i would p oceed o s ep D. B) The h ead wo king in slo 2 c ea es a local copy o a, s o ing alue 7 on i . C) A new ow is added o he e sion copy da a s uc u e, wi h a poin e o a, i s size, he poin e o he local copy and he s a us, which, in his case, will be MOD (see Fig. 5(b)). D) A e s o ing he alue locally, he h ead wo king in slo 2 should check whe he any successo has consumed an ou da ed alue. To do so, ou h ead would scan (in inc easing o de o specula i eness) o any successo slo ha holds a copy o ain he EXPLD o ELUP s a es. These s a es would indica e ha he successo has used he alue. In ou example, he sea ch inds ou ha he h ead wo king in Slo 3 has consumed an inco ec alue o a. I no dependence iola ion was de ec ed, he call o specs o e() would inish he e. E) A dependence iola ion has been de ec ed. Th ead wo king in slo 3 should be squashed. To do so, he h ead wo king in slo 2 changes he s a e o slo 3 om Running o Squashed. Since all h eads check hei own s a e a he beginning o each specload(), specs o e(), and a he end o he execu ion o each chunk o i e a ions, h ead wo king in slo 3 will e en ually disco e ha i has been squashed, and will execu e a call o commi _o _disca d() o be assigned a new chunk (possibly he same) and s a he p ocess again. F) Finally, he h ead wo king in slo 2 ma ks i sel as he mos -specula i e h ead, since da a s o ed in associa ion wi h slo 3 is no longe alid. The mos - spec poin e will be ad anced la e by he h ead ha ecei es he ask o e-execu ing chunk 3. I , a e hese e en s, he h ead wo king in slo 2 inishes i s execu ion, while he h eads associa ed o slo s 1 and 3 a e s ill wo king, we each he si ua ion shown in Fig. 5(a). No e ha , a ha poin , he h ead wo king in slo 3 has al eady been e-s a ed and i has o wa ded he mos up- o-da e alue o a( ha is, 7) om slo 2. 5.4 Pa ial commi ope a ion 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 exe- cu es commi _o _disca d(), i i s checks i i has no been squashed and i i is he non-specula i e one. I he h ead is specula i e, he slo is le o be commi ed by he non-spec h ead. Suppose ha we a e in he si ua ion depic ed in Fig. 5(a), and he non-spec h ead wo king in slo 1 inishes. As long as i is he non-spec one, i will scan i s da a s uc u e o a iables in he ELUP o MOD s a es. In ou example, bhas been modi ied, so i copies he IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 9 con en o b1 in o b. A e commi ing he e sion copy da a s uc u e associa ed o slo 1, i changes i s s a e o FREE and ad ances he non-spec poin e o 2. As long as slo 2 is ma ked as DONE, i s da a should be commi ed as well. In ou example, da a s o ed in c2 and a2 should be commi ed o he use -de ined a iables. A e his, he s a e o he slo is also changed o FREE and he non- spec poin e is ad anced as well. The h ead wo king in slo 3 is s ill unning: When i inishes, i will be in cha ge o commi ing i s own da a. These commi ope a ions a e ca ied ou wi h he help o auxilia y da a s uc u es ha s o e a lis o elemen s in he ELUP o MOD s a es (no shown in ou examples), in o de o a oid a e sing he local copies en i ely only o commi ew da a elemen s. 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, o a oid ha a h ead o e w i es ano he h ead’s s a e. 5.5 Pe o mance hu dles One o he main ad an ages o ou new specula i e pa alleliza ion lib a y is ha each h ead only alloca es he memo y needed o s o e local copies o he spec- ula i e da a ac ually being accessed (see s ep (3) o he specula i e load ope a ion and s ep (B) o he specula i e s o e, abo e). In con as , Cin a e al.’s solu ion keeps T copies o he en i e lis o specula i e a iables. As will be seen in Sec . 7.2, he numbe o po en ially-specula i e a iables can be huge, so Cin a e al.’s solu ion se e ely limi s scalabili y. Ou imp o emen in e ms o memo y oo p in comes a he cos o longe imes o ind he mos -up- o-da e alue in specula i e loads, and longe imes o de ec dependence iola ions in specula i e s o es, since bo h ope a ions should a e se all he alues accessed by all he p edecesso s and successo s, espec i ely. T being he numbe o h eads, in [7], he ime complexi y o his ope a ion was in T×O(1) = O(T), since all he memo y needed o any da a ha migh be accessed was alloca ed in ad ance. In ou scheme, Nbeing he numbe o da a elemen s s o ed locally, he sea ch is done in T×O(N) = O(T N). The e o e, he pe o mance igu es o ou lib a y wi h his mechanism a e somewha lowe han he ones desc ibed in [7]. One way o speed up hese sea ches is o swi ch o a di e en da a s uc u e o hold local e sion copies o da a. Ins ead o using a single able pe h ead as e sion copy da a s uc u e, we ha e de eloped an al e na i e s uc u e wi h X ables, de ined by he p o- g amme (see [38] o mo e de ails). Be o e accessing he da a, a module ope a ion on he add ess o he use - de ined specula i e a iable ob ains a hash H, in he ange 0. . . (X−1). This hash is used o look in o he H h ables o all p edecesso s and successo s, e ec i ely speeding up he sea ch by an a e age ac o o Hwi h- ou inc easing he ime needed o add a new ow o he co esponding able, leading o O(T.N H)sea ch imes. We a e also e alua ing o he solu ions, such as dicho omic sea ch, which can be used o each sea ch alues in O(T. log(N)), bu i comes a he cos o spending mo e ime inding he place o s o e he da a locally. 6 COMPILER SUPPORT FOR THE specula i e CLAUSE The compile phase o ou sys em is implemen ed on he GCC C compile [39], ex ending i s unc ionali y h ough a plugin. Be o e desc ibing he implemen a ion o he plugin, i is necessa y o in oduce he GCC a chi ec u e. GCC a chi ec u e in a nu shell Figu e 7 shows he scheme o he GCC a chi ec u e [40], [41]. In basic e ms, GCC is a big pipeline ha con e s one p o- g am ep esen a ion in o ano he , in di e en s ages. Each s age gene a es a lowe -le el ep esen a ion, un il he assembly code is gene a ed a he las s age. GCC a chi ec u e has h ee clea ly-de ined blocks: F on End, Middle End and Back End. The e is one on end o each p og amming language. The pa se o each language con e s sou ce iles in o a uni ied ee o m, called GENERIC, which is a high-le el ee ep esen a ion. When i inishes, he F on End emi s a GENERIC in- e media e ep esen a ion (IR) o he code, which se es as he in e ace be ween he on end and he es o he compile . The Middle End wo ks on GIMPLE, which is a 3- add ess language wi h no high-le el con ol low s uc- u es. In GIMPLE, each s a emen does no con ain mo e han h ee ope ands (excep unc ion calls); con ol low s uc u es a e combina ions o condi ional s a emen s and go o ope a o s; and he e is a single scope o a i- ables. This kind o ep esen a ion is con enien o op i- mize he sou ce code. Once he sou ce code is in GIMPLE o m, an in e p ocedu al op imize is called, whe e inlining ope a ions, cons an p opaga ion, o s a ic a iable analysis a e pe o med. We ha e inse ed ou plugin a his poin . The ollowing s ep is he ans o ma ion om GIMPLE in o SSA (S a ic Single Assignmen ) ep esen a ion. In SSA o m, each a iable is assigned o w i en only once, c ea ing new e sions o each assignmen o he same a iable, which can be ead many imes. When di e en e sions o he same a iable a e w i en in o bo h b anches o a condi ional exp ession, a φ- unc ion is added jus a e he condi ional block, allowing he selec ion o he co ec e sion o he a iable, depending on he b anch execu ed. SSA ep esen a ion is used o se e al op imiza ions, such as o wa d exp ession subs i- u ion, loop in e change, ec o iza ion o pa alleliza ion, among o he s. These op imiza ions a e pe o med in a ound 100 passes. A e hese op imiza ions, he SSA ep esen a ion is con e ed back o he GIMPLE o m, which is ans- o med in o a egis e - ans e language (RTL) o m, in which he Back End wo ks on. RTL was he o iginal p ima y in e media e ep esen a ion used by GCC. I is a