Critical Sections and Software Transactional Memory Comparison in the Context of a TLS Runtime Library

P oceedings o he 16 h In e na ional Con e ence on Compu a ional and Ma hema ical Me hods in Science and Enginee ing, CMMSE 2016 4–8 July, 2016. C i ical Sec ions and So wa e T ansac ional Memo y Compa ison in he Con ex o a TLS Run ime Lib a y Se gio Aldea1, Diego R. Llanos1and A u o Gonzalez-Esc ibano1 1Depa amen o de In o m´a ica, Uni e sidad de Valladolid emails: [email p o ec ed],[email p o ec ed],[email p o ec ed] Abs ac T ansac ional Memo y (TM) is a echnique ha aims o mi iga e he pe o mance losses ha a e inhe en o he se ializa ion o accesses in c i ical sec ions. Some s ud- ies ha e shown ha he use o TM may lead o pe o mance imp o emen s, despi e he exis ence o managemen o e heads. Howe e , he ela i e pe o mance o TM, wi h espec o classical c i ical sec ions managemen depends g ea ly on he ac ual pe cen age o imes ha he same da a is handled simul aneously by wo ansac ions. In his pape , we compa e he ela i e pe o mance o he c i ical sec ions p o ided by OpenMP wi h espec o wo So wa e T ansac ional Memo y (STM) implemen a- ions. These h ee me hods a e used o manage concu en da a accesses in ATLaS, a so wa e-based, Th ead-Le el Specula ion (TLS) sys em. The complexi y o his appli- ca ion makes i ex emely di icul o p edic whe he wo ansac ions may con lic o no , and how many imes he ansac ions will be execu ed. Ou expe imen al esul s show ha he STM solu ions only deli e a pe o mance compa able o OpenMP when he e a e almos no con lic s. In any o he case, hei pe o mance losses make OpenMP he bes al e na i e o manage c i ical sec ions. Key wo ds: So wa e T ansac ional Memo y, STM, Th ead-Le el Specula ion, TLS, OpenMP, ATLaS 1 In oduc ion Cu en mul ico e p ocesso s o e an oppo uni y o speed up he compu a ion o sequen ial applica ions. To exploi hese pa allel echnologies, he so wa e needs o be pa allelized, ha is, ans o med in o de o co ec ly dis ibu e he wo k among di e en h eads. This p ocess usually in ol es synch onizing he accesses o ce ain memo y a eas ha a e c CMMSE ISBN: 978-84-608-6082-2 C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y sha ed by he concu en h eads, wi h he aim o a oiding po en ial da a aces. This synch oniza ion is usually pe o med by using c i ical sec ions ha p o ec sha ed memo y s uc u es. To simpli y his p ocess, pa allel p og amming models such as OpenMP [1] o e com- pile di ec i es, no only o pa allelize he code, bu also o synch onize accesses and de ine and manage c i ical sec ions. Despi e hei simplici y, hese solu ions p esen a p oblem: C i ical sec ions in oduce pe o mance losses, no only because hey se ialize he code, bu also because o he cos associa ed o locking managemen . So wa e T ansac ional Memo y (STM) [2] a ises as a possible solu ion o he i s p oblem, allowing p og amme s o ans o m c i ical sec ions in ansac ions ha a e con- cu en ly and a omically execu ed. This is based on he op imis ic assump ion ha he code inside he ansac ion will access o di e en loca ions o he sha ed memo y being p o ec ed. In hese cases, accesses a e ca ied ou concu en ly. I his is no he case, con lic i e ansac ions should be olled back and execu ed one a a ime. Wo ks such as [3] ha e shown ha STM can ou pe o m OpenMP c i ical sec ions, despi e he ela i ely high o e heads o STM. Howe e , he ela i e pe o mance o STM e sus OpenMP c i ical sec ions is highly dependen on he unning p o ile o each pa icula applica ion. Di e en pa e ns o accesses o he same c i ical sec ion may lead o di e en pe o mance igu es. This pape compa es he OpenMP c i ical sec ions app oach wi h wo STM lib a ies, using hem o handle he c i ical sec ions ha appea s in he un ime lib a y o ATLaS [4], a s a e-o - he-a , so wa e-based Th ead Le el Specula ion (TLS) sys em. Ou goal is o s udy he ela i e pe o mance o bo h app oaches when managing concu en accesses in such a complex piece o code. The es o his pape is s uc u ed as ollows: Sec ion 2 b ie ly desc ibes he undamen- als o so wa e TLS. Sec ion 3 de ails how ou TLS un ime lib a y handles he specula i e execu ion o a sou ce code, and how c i ical da a s uc u es a e p o ec ed o ensu e co - ec ness. Sec ion 4 desc ibes how his p o ec ion can be ensu ed using OpenMP and wo di e en STM lib a ies. Sec ion 5 shows he pe o mance esul s ob ained by each OpenMP and he STM lib a ies conside ed. Finally, Sec . 6 concludes his pape . 2 Th ead-Le el Specula ion in a Nu shell Specula i e pa alleliza ion (SP), also called Th ead-Le el Specula ion (TLS) o Op imis ic Pa alleliza ion [5, 6, 7, 8, 9, 10, 11], is a echnique ha allows he pa allel execu ion o ag- men s o code ( ypically blocks o i e a ions o a loop) wi hou he need o a compile- ime analysis, which gua an ees ha he agmen s do no p esen da a dependences be ween hem. Ins ead, TLS solu ions assume ha he loop can be op imis ically execu ed in pa - allel, and ely on a un ime moni o o ensu e ha no dependence iola ions appea . TLS c CMMSE ISBN: 978-84-608-6082-2 Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano solu ions can be implemen ed in so wa e o ha dwa e. F om he e on, we will ocus on so wa e-based TLS. 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 h ead execu ing a subsequen se o i e a ions wi h espec o 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]. Figu e 1 shows an example o h ead-le el specula ion. The igu e ep esen s ou h eads execu ing one ou o ou consecu i e i e a ions, and he sequence o e en s ha occu s when he loop is execu ed in pa allel. All h eads access ce ain da a elemen s om he SV ec o . I he alues o xa e no known a compile ime, he compile is 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 indexes o he da a elemen s being accessed a e known a un ime, so dependence iola ions can be de ec ed and co ec ed while he p og am is unning. Specula i e pa alleliza ion wo ks as ollows. I he p og amme labels he SV ec o as specula i e, he code should be ins umen ed a compile ime o moni o a un ime ha all uses o SV ollow sequen ial seman ics. A un ime, each h ead main ains a e sion copy o he elemen s o he SV ec o being accessed. All ead ope a ions o SV 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. This ope a ion is called o wa ding. 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 hen he alue is o wa ded (as Th ead 2 does in Fig. 1). I no , hen he unc ion ob ains he alue om he main copy o he specula i e da a s uc u e (as Th ead 3 does in he igu e). Rega ding modi ica ions o he specula i e da a s uc u e, all w i e ope a ions a e e- placed a compile ime by 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 p ocesso , and 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 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 a so-called squash ope a ion. I no dependence iola ion a ises o a gi en h ead, i should commi all he da a s o ed in i s e sion copy o he main copy o he specula i e 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. A e pe o ming he commi ope a ion, a h ead can assign i sel a new i e a ion o block o i e a ions o con inue he pa allel wo k. c CMMSE ISBN: 978-84-608-6082-2 C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y 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 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 (Time 6: h ead 2 de ec s no dependence iola ions) Figu e 1: 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. 3 The ATLaS amewo k and un ime lib a y We ha e de eloped an ex ension o OpenMP ha inco po a es Th ead-Le el Specula ion suppo . The ATLaS amewo k [4] allows any loop o be execu ed in pa allel wi hou he need o a p io dependence analysis. This is done by de ining a new OpenMP a iable classi ica ion clause, namely specula i e. I he use is unsu e abou whe he he access in pa allel o a a iable o s uc u e inside a gi en loop may lead o a dependence iola ion, he/she may simply classi y i as specula i e, ins ead o labeling i as p i a e o sha ed. In his case, he sou ce code is ins umen ed a compile ime o add TLS execu ion suppo . This is done wi h he help o a GCC compile plugin [12] ha ans o ms he code, inse ing calls o he ATLaS TLS un ime lib a y. When unning in pa allel, he un ime lib a y ensu es ha all he accesses o all da a elemen s classi ied as specula i e ollows sequen ial seman ics. The ATLaS un ime lib a y [13] suppo s all he ope a ions desc ibed in he p e ious sec ion. I ollows he design p inciples o he specula i e pa alleliza ion lib a y de eloped by Cin a and Llanos [7], wi h se e al imp o emen s ha allow, o example, he specula i e pa alleliza ion o loops ha use poin e a i hme ic o complex da a s uc u es. One o he key ad an ages o his lib a y o e p e ious designs is ha he ATLaS un ime lib a y is almos ee o c i ical sec ions. The only c i ical sec ion needed is he one ha manages he da a s uc u e ha main ains he assignmen o chunks o i e a ions c CMMSE ISBN: 978-84-608-6082-2 Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano Sliding window S a e Poin e o he e sion copy Ve sion copy da a s uc u es Th ead C I e : [0,9] Th ead B I e : [10,19] Th ead A I e : [20,29] Non-spec window slo 1 Mos -spec window slo 3 F ee RunningRunning Non-spec window slo 2 Mos -spec window slo 4 Th ead C finishes, and commi s i s copy Th ead B I e : [10,19] Th ead A I e : [20,29] Th ead C I e : [30,39] Ve sion copy da a s uc u es Running Running Running Running F ee Chunk exec. de ails Figu e 2: Upda ing he sliding window ha handles he pa allel, specula i e execu ion. A a gi en momen (le ), he h ead C wo king in slo 1 is unning. When Th ead C inishes, i ees i s slo and ge s a new one, upda ing non-spec and mos -spec poin e s ( igh ). o each h ead. ATLaS handles he pa allel execu ion o each chunk o i e a ions h ough a sliding window mechanism, which is implemen ed by a ma ix wi h Wcolumns ep esen ing Wwindow slo s. Figu e 2 depic s a simpli ied e sion o he sliding window implemen a ion (see [4, 13] o mo e de ails). The igu e ep esen s a sliding window wi h ou slo s, hos ing he execu ion o h ee pa allel specula i e h eads. The h ead execu ing he ea lies chunk o i e a ions (Th ead C in ou example) is called non-specula i e, since i has no p edecesso s ha may squash i . Con e sely, he h ead execu ing he la es chunk is called he mos -specula i e h ead. As can be seen in Fig. 2, wo poin e s indica e he slo s whe e he non-specula i e and mos -specula i e h eads a e being execu ed. The pa o he window being used is always he one om he non-spec poin e o he igh , up o he mos -spec poin e . The only c i ical sec ion in he ATLaS un ime lib a y is he one ha p o ec s his sliding window. I wo o mo e h eads inish a he same ime, hey could be assigned o he same F ee slo , esul ing in an inco ec execu ion. The e o e, in o de o ensu e he co ec ope a ion o he ATLaS un ime lib a y, i is necessa y o p o ec he accesses o hese sha ed s uc u es, including he ma ix ha implemen s he sliding window mechanism, and he a iables ha poin o he non- and mos -specula i e slo s. Figu e 2 shows wha happens when a non-specula i e h ead success ully inishes i s execu ion. Suppose ha Th ead C, he one execu ing he non-specula i e h ead, inishes i s execu ion and commi s i s da a ( he commi ope a ion is no shown in he igu e). A e his, i en e s he c i ical sec ion o pe o m se e al ac ions. I ma ks slo 1 as F ee; i ad ances he non-specula i e poin e o slo 2; a e checking ha he slo pas he mos - specula i e one is F ee, i assigns i o i sel , se ing he mos -specula i e poin e o 4 and c CMMSE ISBN: 978-84-608-6082-2 C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y changing i s s a e o Running; and inally, a e ge ing he ollowing chunk o i e a ions o be execu ed (i e a ions 30 o 39 in ou example), i exi s he c i ical sec ion. No e ha he implemen a ion o he sliding window wo ks in a ci cula way: When Th ead B e en ually inishes, i will assign i sel he slo ha ollows he one used by Th ead C, in ou case he le mos slo . The sliding window is modi ied in h ee di e en loca ions wi hin he ATLaS un ime lib a y. The e o e, he same lock is used in h ee di e en pa s o he code o p o ec he access o hese da a s uc u es. As will be seen, he place om whe e he access is pe o med has a no iceable impac in he pe o mance o he p o ec ing sys em being used. These places a e he ollowing: •(A) Each ime a dependence iola ion is de ec ed. In he case o a w i e o a specula i e a iable, he h ead in cha ge should upda e i s e sion copy, and check whe he a successo has consumed an ou da ed alue o his a iable. I his is he case, a dependence iola ion has happened, so he o ending h ead should be es a ed in o de o consume an upda ed e sion o he a iable. This is done in se e al s eps. Fi s , he h ead ha has de ec ed he si ua ion should en e he c i ical sec ion o change he s a e o he o ending h ead, om Running o Squashed, and he mos - specula i e poin e should be mo ed backwa ds o he las Running h ead. A e hese changes, he h ead exi s he c i ical sec ion and esumes i s no mal ope a ion. The o ending squashed h ead will e en ually disco e i s new s a e and will en e he c i ical sec ion (see below). •(B) Each ime a h ead inishes i s wo k, ei he because he chunk has been suc- cess ully execu ed o because he h ead disco e s ha i has been squashed. In bo h cases, he h ead en e s he c i ical sec ion o change i s own s a e om Running ( esp. Squashed) o F ee. A e his ope a ion, i he slo ollowing he mos -specula i e one is F ee, he h ead assigns i o i sel , and ad ances he mos -specula i e poin e by one. O he wise, i means ha he ollowing slo is occupied ei he by a Running h ead ( his means ha he window is ull) o by ano he Squashed h ead. In bo h cases ou h ead should exi he c i ical sec ion and a emp o e-en e again, in o de o gi e he h ead ha is using he slo he oppo uni y o ee i 1(see below). •(C) Each ime a h ead should wai o a ee slo . I a h ead is no able o ge a ee window slo o wo k, because he ollowing slo is no F ee ye , i should ge ou and y o gain access again o he c i ical sec ion o assign i sel he ollowing slo and o ad ance he mos -specula i e poin e . 1Ou h ead canno simply wai inside he c i ical sec ion, because i should ge ou in o de o le he h ead using ha slo o ge in and change i s own s a e. c CMMSE ISBN: 978-84-608-6082-2 Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano 4 P o ec ing da a accesses wi h OpenMP and STM The o iginal TLS un ime lib a y uses he OpenMP c i ical di ec i e o gua an ee exclusi e access o he h eads o he h ee pa s o he code men ioned abo e. Because he same da a s uc u es a e accessed om h ee di e en places, he same lock is used o p o ec hem in all cases. Recall ha a block o code ma ked wi h an OpenMP c i ical di ec i e is only execu ed by one h ead a a ime, whils he es o he h eads ha ha e eached he same poin in he code ha e o wai . This p ocedu e ensu es ha he sliding window is always in a consis en s a e, hus a oiding mul iple h eads concu en ly upda ing his s uc u e wi h he po en ial loss o consis ency. I is easy o see ha he se ializa ion o ope a ions desc ibed abo e should imply a no iceable o e head in he pe o mance o he specula i e un ime lib a y. A possible way o educe his pe o mance penal y would be o eplace he s ic , OpenMP c i ical cons uc wi h he mo e op imis ic cons uc s ha o e he T ansac ional Memo y pa adigm. The goal o STM is p ecisely 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 [14, 15]. While OpenMP c i ical cons uc s only allow one single h ead a a ime inside he c i ical sec ion, a ansac ional- based implemen a ion allows se e al h eads inside i , pe mi ing hei concu en execu ion as long as consis ency is no comp omised. Howe e , he op imism o STM, as well as ha o TLS, comes a he cos o some o e heads, because o he ex a ins umen a ion needed o handle he ansac ions, as well as he cos associa ed o he ex a uns o pa icula ansac ions when a con lic appea s. As can be seen, bo h OpenMP and STM app oaches o p o ec da a in eg i y ha e iden- i ied o e heads. I is ex emely di icul o p edic which app oach will be be e o a pa icula p oblem, since i depends on he applica ion, i s unning p o ile, and how o en he benchma k accesses he po en ially con lic i e sha ed a iables, among o he ac o s. Rega ding he p og ammabili y, OpenMP has been designed o simpli y, o a g ea ex en , he p ocess o pa alleliza ion, while he di ec use o STM lib a ies in ol es a non- i ial ins umen a ion o he sou ce code, om he de ini ion o he ansac ional egion o moni o ing each access o specula i e a iables. This e o is mi iga ed by he exis ence o STM solu ions ha ely on he compile o eplace STM cons uc s wi h calls o he STM lib a y. Some STM app oaches p opose language ex ensions o new cons uc s o decla e ansac ional code egions ha comp ises s a emen s ha mus be execu ed a omically. Then, ei he an ad-hoc compile , o an exis ing compile modi ied o his pu pose, pa ses hese new cons uc s, and gene a es all he ins umen a ion, in he same way as compile s p ocess OpenMP cons uc s. As we said abo e, OpenMP allows he use o delimi he c i ical sec ions wi h he cons uc omp c i ical. To decla e a ansac ional egion, STM lib a ies ely on di e en al e na i es, such as new cons uc s (e.g. GCC-TM’s ansac ion_a omic{} [16], he In el’s m_a omic{} [17], o he mo e gene ic ansac ion{}), new compile di ec i es (such c CMMSE ISBN: 978-84-608-6082-2 C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y Applica ion % Max. speedup % o i e a ions # o po en ially Size o C i ical a ge P = 64 ha p esen specula i e chunks Sec ions loop (Amhdahl) dep. iola ions scala a iables issued accessed FAST 100 64 0.001% 2 25 A, B TREE 95.17 15.84 0% 259 100 B 2D-MEC 43.75 1.76 0.009% 10 1 800 A, B 2D-Hull, Kuzmin 100 64 0.0008% 1 206 11 000 A, B, C 2D-Hull, Squa e 100 64 0.0032% 3 906 3 000 A, B, C 2D-Hull, Disc 100 64 0.0219% 26 406 1 250 A, B, C Delaunay 97.60 25.47 0.5% 12 030 060 2 A, B, C Table 1: Pe cen ages o po en ially pa allelism o he benchma ks and loops conside ed, oge he wi h some benchma ks’ cha ac e is ics. Chunk sizes we e selec ed o ob ain max- imum speedups. as IBM’s [18] m_a omic{}), o e en new OpenMP p agmas, such as omp ansac ion, de ined by OpenTM [19]. Un o una ely, In el STM compile and OpenTM a e no cu en ly a ailable, while he IBM compile ’s ansac ional buil -in memo y unc ions a e only alid o Powe 8 a chi ec u e and Blue Gene/Q. In his wo k, we ha e used OpenMP, he GCC-TM, and he TinySTM lib a ies [20, 21] o p o ec he accesses o he sliding window desc ibed p e iously. These h ee app oaches simpli y he pa alleliza ion p ocess wi h he men ioned cons uc s and di ec i es. Mo eo e , GCC-TM de ines a speci ica ion o ansac ional language cons uc s ha o he STM li- b a ies can le e age, and hence, changing he unde lying STM lib a y is jus a p ocess o p ope linking. In ac , TinySTM is compa ible wi h GCC-TM, allowing p og amme s o use he same in e ace and sa e some p og amming e o . Handling he c i ical sec ions wi h OpenMP is s aigh o wa d: The p og amme should simply delimi he egion by using he de ined omp c i ical di ec i e. This p ocess is simila when using he GCC-TM speci ica ion. Howe e , o ensu e ha he ansac ion is a omically execu ed, he e may be ce ain unc ions inside he ansac ion ha mus no be execu ed. Since he compile is no able o de ec his issue o he unc ions called wi hin a ansac ion, i is also necessa y o anno a e hei decla a ion and speci y whe he hey a e sa e o be called, wi h he ansac ion_sa e a ibu e. The ollowing sec ion desc ibes he pe o mance esul s ob ained by ATLaS when using hese h ee solu ions o execu e a se o eal-wo ld and syn he ic benchma ks. 5 Expe imen a ion Expe imen s we e ca ied ou on 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 Ubun u 12.04.3 LTS. All h eads had exclusi e access o he p ocesso s du ing he execu ion o he expe imen s, and we used wall-clock imes in ou measu emen s. We ha e used he OpenMP implemen a ion c CMMSE ISBN: 978-84-608-6082-2 Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano om GCC 4.8.2, and he ansac ional lib a ies om GCC-TM 4.8.2, and TinySTM 1.0.5. To pe o m he expe imen s, we used bo h eal-wo ld and syn he ic benchma ks. The eal-wo ld applica ions include he 2-dimensional Minimum Enclosing Ci cle (2D-MEC) p oblem [22], he 2-dimensional Con ex Hull p oblem (2D-Hull) [23], he Delaunay T i- angula ion p oblem [24, 25], and a C implemen a ion o he TREE benchma k [26]. 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 o e heads o he ATLaS un ime lib a y. Table 1 summa izes he cha ac e is ics o each benchma k, including he pe cen age o execu ion ime consumed by each a ge loop, an es ima ion o he maximum speedup a ainable (applying Amhdahls Law), he pe cen age o i e a ions o he a ge loop ha lead o un ime dependence iola ions, he numbe o specula i e a iables wi hin he loop, and he size o he chunk o consecu i e i e a ions specula i ely execu ed. I/O ime consumed by he benchma ks we e no aken in o accoun . We also gi e an indica ion o which accesses o he sliding window p o ec ed by he c i ical sec ion a e mo e equen in he benchma k (bold le e s indica e ha he co esponding call is mo e equen ). The pe o mance esul s ob ained by each benchma k and lib a y used a e summa ized in Fig. 3. The Fas benchma k was designed o es he e iciency o he specula i e scheduling mechanism, wi h ew i e a ions leading o a dependence iola ion, al hough hey a e enough o p e en a compile om pa allelizing he loop. This benchma k has e y ew dependence iola ions, so he c i ical sec ion is p ima ily accessed o ge he ollowing chunk o i e a ions o be execu ed (access o ype B in ou lib a y). As can be seen in he co esponding pe o mance plo , OpenMP and he STM lib a ies handle he c i ical sec ions equally well, deli e ing almos iden ical pe o mances, wi h a speedup o up o 37×wi h 64 p ocesso s. Unlike he es o he benchma ks, TREE 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. Since i does no p esen dependence iola ions, he code ha accesses he c i ical sec ion is p ima ily B. Again, OpenMP and STM solu ions deli e he same pe o mance, wi h a peak speedup o 6×when unning his benchma k wi h a 4096-poin inpu se . As can be seen in he igu e, he o e heads o he TLS un ime lib a y lead o a pe o mance loss when using 48 h eads o mo e, ega dless o he implemen a ion chosen o handle c i ical sec ions. The 2D-MEC benchma k is a icky code which has only 10 specula i e a iables ha a e equen ly accessed. This benchma k calls he specula i e loop many imes wi h a e y di e en numbe o i e a ions each ime, making h eads access he sliding window sys em equen ly o ge he ollowing chunk. As long as i p esen s some dependence iola ions, he c i ical sec ions a e accessed by codes A, bu mos ly B (C is a ely accessed in his benchma k). Fo his benchma k, he use o he OpenMP c i ical sec ions leads o he bes pe o mance, while he STM lib a ies leading o much poo e esul s. OpenMP ge s a peak c CMMSE ISBN: 978-84-608-6082-2