Moody Scheduling for Speculative Parallelization

Moody Scheduling o Specula i e Pa alleliza ion Al a o Es ebanez1, Diego R. Llanos1, Da id O den2, and Belen Palop1 1Dp o. In o m´a ica, Uni e sidad de Valladolid Campus Miguel Delibes, 47011 Valladolid, Spain {al a o,diego,bpalop}@in o .u a.es 2Dp o. F´ısica y Ma em´a icas, Uni e sidad de Alcal´a Alcal´a de Hena es, Mad id, Spain [email p o ec ed] Abs ac . Scheduling is one o he ac o s ha mos di ec ly a ec pe - o mance in Th ead-Le el Specula ion (TLS). Since loops may p esen dependences ha canno be p edic ed be o e un ime, inding a good chunk size is no a simple ask. The mos used mechanism, Fixed-Size Chunking (FSC), equi es many “d y- uns” o se he op imal chunk size. I he loop does no p esen dependence iola ions a un ime, schedul- ing only needs o deal wi h load balancing issues. Fo loops whe e he gene al pa e n o dependences is known, as is he case wi h Randomized Inc emen al Algo i hms, specialized mechanisms ha e been designed o maximize pe o mance. To make TLS a ailable o a wide communi y, a gene al scheduling algo i hm ha does no equi e a-p io i knowledge o he expec ed pa e n o dependences no p e ious d y- uns o adjus any pa ame e is needed. In his pape , we p esen an algo i hm ha es ima es a un ime he bes size o he nex chunk o be scheduled. This algo i hm akes ad an age o ou p e ious knowledge in he design and es o o he scheduling mechanisms, and i has a solid ma hema ical basis. The esul is a me hod ha , using in o ma ion o he execu ion o he p e ious chunks, decides he size o he nex chunk o be scheduled. Ou expe imen al esul s show ha he use o he p oposed scheduling unc ion compa es o e en inc eases he pe o mance ha can be ob- ained by FSC, g ea ly educing he need o a a cos ly and ca e ul sea ch o he bes ixed chunk size. Keywo ds: Th ead-le el specula ion, specula i e pa alleliza ion, spec- ula i e mul i h eading, scheduling 1 In oduc ion Th ead-Le el Specula ion (TLS) [4, 18, 20] is he mos p omising echnique o au oma ic ex ac ion o pa allelism o i egula loops. Wi h TLS, loops ha can no be analyzed a compile ime a e op imis ically execu ed in pa allel. A ha dwa e o so wa e mechanism ensu es ha all h eads access o sha ed da a acco ding o sequen ial seman ics. A dependence iola ion appea s when one h ead inco ec ly consumes a da um ha has no been gene a ed by a p ede- cesso ye . In he p esence o such a iola ion, ea lie so wa e-only specula i e 2 solu ions (see, e.g. [10, 20]) in e up he specula i e execu ion and e-execu e he loop se ially. Subsequen app oaches [5, 7, 21] squash only he o ending h ead and i s successo s, e-s a ing hem wi h he co ec da a alues. Mo e sophis i- ca e solu ions [9, 15, 22] squash only he o ending h ead and subsequen h eads ha ha e ac ually consumed any alue om i . I is easy o see ha equen squashes ad e sely a ec he pe o mance o a TLS amewo k. One way o educe he cos o a squash is o assign smalle subse s (called chunks) o i e a ions o each h ead, educing bo h he amoun o wo k being disca ded in he case o a squash, and he p obabili y o occu ence o a dependence iola ion. Howe e , smalle chunks also imply mo e equen com- mi ope a ions and a highe scheduling o e head. The e o e, a co ec choice o he chunk sizes is c i ical o specula ion pe o mance. Mos scheduling me hods p oposed so a in he li e a u e deal wi h independen blocks o i e a ions, and we e no designed o ake in o accoun he cos o e-execu ing h eads in he con ex o a specula i e execu ion. A widely used mechanism o sol e his p oblem is o choose a ixed, op imum size by ial and e o . This me hod, called Fixed-Size Chunking [12] equi es many d y- uns o ind an accep able alue. Mo eo e , a pa icula size ound o one applica ion is o li le use o ano he one, o e en o a di e en inpu se o he same applica ion. In his wo k we add ess he gene al p oblem o scheduling chunks o i e - a ions o hei specula i e execu ion, ega dless o he numbe o dependence iola ions ha may ac ually appea . We ha e ound ha he pa e n o de- pendence iola ions hea ily depends on he applica ion. The e o e, a scheduling s a egy ha is able o dynamically adap he size o chunks a un ime is e y desi able. In his pape , we in oduce a scheduling me hod, called Moody Scheduling, ha ies o p edic , a un ime, he bes chunk size o he nex chunk o be scheduled. To do so, we ely on he numbe o e-execu ions o he p e ious chunks, no only by using he mean o he las e-execu ions, bu also hei en- dency. Wi h his me hod, we a e able o (a) p o ide a gene al solu ion ha does no need an in-dep h s udy o he dependence iola ion pa e n, and (b) g ea ly educe he need o epe i i e execu ions o une he scheduling mechanism used. The es o he pape is o ganized as ollows. Sec ion 2 e iews some o he ex- is en scheduling al e na i es cu en ly used wi h TLS. Sec ion 3 in oduces he main aspec s o ou p oposal. Sec ion 4 desc ibes he unc ion om a ma hema i- cal poin o iew. Sec ion 5 explo es wo di e en uses o ou Moody Scheduling. Sec ion 6 gi es some expe imen al esul s, compa ing he new algo i hm wi h FSC, while Sec . 7 concludes his pape . 2 Rela ed wo k Since he size o he chunk assigned o each p ocesso di ec ly a ec s pe o - mance in TLS, nume ous algo i hms ha e been p oposed o gi e a solu ion o his p oblem. The simples one, called Fixed-Size Chunking (FSC), was ini ially 3 p oposed by K uskal and Weiss [12]. Wi h his mechanism, each h ead is as- signed a cons an numbe o i e a ions. Finding he igh cons an needs se e al d y- uns on each pa icula inpu se o each pa allelized loop. When no depen- dence iola ions a ise a un ime, his echnique is pe ec ly adequa e. The only emaining conce n is o achie e a good load balance when he las i e a ions a e being scheduled. Some examples o mechanisms ha implemen load-balancing echniques can be ound in [11] o [23]. The e a e solu ions based on compile- ime dependence analysis [19, 25]. In hese app oaches, scheduling decisions a e aken by e iewing he possible de- pendence pa e n ha can a ise, so an in-dep h analysis o he loop is needed. O he app oaches ely on he expec ed dependence pa e n o he loop o be pa allelized. In pa icula , o Randomized Inc emen al Algo i hms, whe e dependences end o accumula e in he i s i e a ions o he loop, wo me hods ha e been shown o imp o e pe o mance. The i s one, called Mese a [16], di ides he execu ion in h ee s ages. In he i s one, chunks o inc easing sizes a e scheduled, aiming o compensa e o possible dependence iola ions, un il a lowe bound o he p obabili y o inding a dependence is eached. F om hen on, a second s age applies FSC o execu e mos o he emaining i e a ions. A hi d s age g adually dec eases he chunk size, aiming o achie e a be e load balancing. The second mechanism is called Jus -In-Time (JIT) Scheduling [17]. This me hod also ocuses on andomized inc emen al algo i hms, whe e dependences a e mo e likely o appea du ing he execu ion o he i s chunks. JIT Scheduling de ines di e en loga i hmic-based unc ions ha issue chunks o inc easing size, and elies on un ime in o ma ion o modula e hese unc ions acco ding o he numbe o dependence iola ions ha e ec i ely appea . Kulka ni e al. [13] also discussed he impo ance o scheduling s a egies in TLS. These au ho s de ined a schedule h ough h ee s eps, i.e., h ee design choices ha speci y he beha io o a schedule, namely clus e ing,labeling and o de ing. They es ed se e al s a egies o each de ined module, using hei Galois amewo k. Thei esul s show ha each applica ion analyzed was closely linked o a di e en scheduling s a egy. In summa y, we can conclude ha p oposed solu ions so a ei he depend on he expec ed dependency pa e n o he loop o be specula i ely execu ed, o equi e a big numbe o aining expe imen s o be uned, as in he case o FSC. In his pape we p esen a new mechanism ha issues chunks o di e en sizes, by aking in o accoun he ac ual occu ence o dependence iola ions, wi hou using any p io knowledge abou hei dis ibu ion. 3 Moody Scheduling: Design guidelines Ou main pu pose is o design a scheduling unc ion ha is able o p edic he bes size o he ollowing chunk o be issued a un ime, wi hou he need o a knowledge o he unde lying p oblem. In o de o decide he size o he nex chunk o be scheduled, we will use he numbe o imes ha he las h 4 Numbe o execu ions Chunk numbe h Numbe o execu ions Chunk numbe h h δ δ (a) (b) Fig. 1. (a) A possible execu ion p o ile o a gi en loop, and (b) an example o he use o linea eg ession o measu e he endency o he las hchunks. Recall ha he y-axis does no ep esen he chunk size, bu he numbe o e-execu ions o each chunk. chunks ha e been squashed and e-execu ed due o dependence iola ions. As an example, Fig 1(a) shows, o each scheduled chunk (x-axis), he numbe o imes i has been execu ed so a (y-axis). Gi en he numbe o execu ions o he las hchunks ( ega dless whe he hey we e al eady commi ed o no ), we will conside wo pa ame e s. The i s one is he a e age numbe o execu ions o he las hchunks, which we call meanH and whose alue is, a leas , 1. The second one is he endency o hese e-execu ions. This alue, which we call d, lies in he in e al (−1,1) and de e mines i he numbe o execu ions is dec easing (d < 0), inc easing (d > 0), o emaining unchanged (d= 0). As we will see, ddepends on he angle δbe ween he linea eg ession line o he las hchunks and he ho izon al axis (see Fig. 1(b)). The size o he ollowing chunk o be scheduled will depend on hese wo pa- ame e s. We will i s p esen an in o mal desc ip ion o he idea. The ollowing sec ion shows he ma hema ical backg ound and he implemen a ion de ails. 1. I he endency o e-execu ions is dec easing (dclose o -1): (a) I meanH is e y low (close o 1), we will (op imis ically) se he chunk size o he maximum size sui able o his p oblem. We will call his maximum alue maxChunkSize. (b) I meanH is be ween he minimum alue (1) and an accep able alue ( ha we call accMeanH), we will (op imis ically) inc ease he chunk size. (c) I meanH is be ween accMeanH and an uppe limi ( ha we call maxMeanH), we will keep he same chunk size, wi h he aim ha i s execu ion will help o u he educe meanH. (d) I meanH is highe han maxMeanH, we se he size o he ollowing chunk o 1. 2. I he endency o e-execu ions is s able (dclose o 0): (a) I meanH is e y low (close o 1), hen we will (op imis ically) issue a la ge chunk size. 5 Table 1. Changes on he ollowing chunk sized acco ding o dand meanH pa ame e s. meanH ≈1 meanH ≈accMeanH meanH ≈maxMeanH meanH >maxMeanH d→ −1↑%= 1 d≈0%=&1 d→1 = &1 1 (b) I meanH is accep able (close o accMeanH), hen we will keep he same chunk size. (c) I meanH is be ween accMeanH and maxMeanH, hen we will (pessimis i- cally) dec ease he chunk size. (d) I meanH is highe han maxMeanH, we se he size o he ollowing chunk o 1. 3. I he endency o e-execu ions is inc easing (dclose o 1): (a) I meanH is e y low (close o 1), hen we p opose o keep he same chunk size, wai ing o he nex da a o con i m i meanH eally ge s la ge . (b) I meanH is accep able (close o accMeanH), hen we dec ease he chunk size, in ending o educe he numbe o execu ions. (c) I meanH is close o (o highe han) maxMeanH, hen we p opose a chunk o size 1 in ending o minimize he numbe o e-execu ions. The las ques ion is wha size we should use o issue he i s chunk, whe e he e is no pas his o y o ely on. As we will see in Sec . 6, se ing his ini al alue o 1 leads o a good pe o mance in all he applica ions conside ed. Table 1 summa izes he beha io o ou scheduling mechanism. Using his ap- p oach, gi en he cu en las ChunkSize and a pai o alues (d, meanH) ou unc- ion will use he guidelines desc ibed abo e o p opose a alue o nex ChunkSize. The ollowing sec ion discusses he implemen a ion de ails. 4 Moody Scheduling unc ion de ini ion A e he in o mal desc ip ion p esen ed abo e, he ollowing s ep is o de ine a unc ion ha de e mines he alue o nex ChunkSize using he cu en alue o las ChunkSize, oge he wi h dand meanH. In o de o ob ain he alue o δ, we compu e he eg ession line de ined by he las hpoin s in ou execu ion window (see Fig. 1(b)). The main p oblem wi h he in ui i e beha io desc ibed abo e is ha i s s aigh o wa d implemen a ion (wi h nes ed i . . . hen cons uc s) leads o a discon inuous unc ion. This is no a desi able si ua ion, since he beha io o he scheduling unc ion would d as ically change o e y simila si ua ions. Ins ead, we de ine a bidimensional unc ion ha , o a gi en alue o meanH and d, e u ns he size o he nex chunk o be scheduled. Figu e 2(a) shows a 3D ep esen a ion o he Moody Scheduling unc ion p oposed. Figu e 2(b) shows i s p ojec ion on o a ho izon al plane, using he same g ey scale as in Table 1. 6 nCS=maxChunkSize nCS=maxChunkSize nCS=maxChunkSize nCS=las ChunkSize nCS=las ChunkSize nCS=las ChunkSize nCS=1 nCS=1 nCS=1 nCS=1 nCS=maxChunkSize nCS = 1 nCS < las ChunkSize nCS > las ChunkSize nCS = 1 (a) (b) 1 accMeanH maxMeanH meanH 1 maxChunkSize las ChunkSize nex ChunkSize α β P (c) Fig. 2. (a) 3D ep esen a ion o he Moody Scheduling unc ion, ha e u ns a alue o nex ChunkSize (nCS) p o ided he cu en las ChunkSize and depending on dand meanH; (b) 2D ep esen a ion ha connec s ou unc ion wi h he in ui i e beha io desc ibed in Sec . 3; (c) In e sec ion o he g aphic o nex ChunkSize(d, meanH) wi h d= 0. To p ope ly de ine his scheduling unc ion, se e al pa ame e s should be se . The alue o dis calcula ed by measu ing he angle δo he endency wi h espec o he ho izon al axis. This angle lies in (−π/2, π/2). Ou g ow h endency d∈(−1,1) will be gi en by d=δ π/2. The ollowing pa ame e o be de ined is accMeanH, ha is, he highes alue o meanH conside ed o be accep able. We ini ially se accMeanH = 2, conside ing ha , on a e age, we will accep ha chunks ha e o be eexecu ed a mos once. The e a e wo emaining pa ame e s: maxChunkSize and maxMeanH, whose alues depend on he slopes o he g aphic o he bidimensional scheduling unc- ion as ollows. I we ix d= 0 in he scheduling unc ion, we ob ain he plo depic ed in Fig. 2(c). In his case, we can de ine wo angles, αand β(see ig- u e). The angle α ep esen s how op imis ically he chunk size is going o be 7 4 5 6 7 8 9 10 11 12 13 non−spec h ead mos −spec h ead 25 28 33 54 69 8940 1112111 Las T h eads . . . . . . Chunk sizes Chunk numbe s Execu ion coun e s non−spec h ead mos −spec h ead 4 5 6 7 8 9 10 11 12 13 4 5 6 7 8 9 10 11 12 13 non−spec h ead mos −spec h ead 4 5 6 7 8 9 10 11 12 13 non−spec h ead mos −spec h ead . . . . . . (i) 25 1 28 33 54 69 8940 112111 . . . . . . (ii) 25 1 28 33 54 69 8940 112111 114 1 . . . . . . (iii) 25 1 28 33 54 6940 112112 Chunk sizes Chunk numbe s Chunk numbe s Chunk sizes Execu ion coun e s Execu ion coun e s Chunk numbe s Chunk sizes Execu ion coun e s Las T+1 h eads 109 2 81 (a) (b) Fig. 3. (a) Dynamic Moody Scheduling. The size o he ollowing chunk o be execu ed (#10) is calcula ed once (89 i e a ions). I s size will be p ese ed ega dless o he numbe o e-execu ions o his chunk. (b) Adap i e Moody Scheduling. (i) Size o chunk #10 is calcula ed wi h he Moody Scheduling unc ion (89 i e a ions). (ii) Chunk #9 issues a squash ope a ion. (iii) Squashed h eads ecalcula e in p og am o de he new sizes o he chunks o be execu ed, using he new alues o he execu ion coun e s. inc eased. The highe he alue o α, he mos op imis ic he scheduling unc- ion will be. Analogously, β ep esen s how pessimis ically he chunk size is going o be dec eased. I we ix he alue o hese wo angles, he alue o maxChunkSize is de e mined by he in e sec ion be ween he segmen om P wi h angle α, and he e ical line de ined by meanH = 1. Analogously, he alue o maxMeanH is de e mined by he in e sec ion be ween he segmen om P wi h angle β, and he ho izon al line de ined by nex ChunkSize = 1. In he case ha las ChunkSize = 1, βwill be 0. On he o he hand, α6= 0 as long as accMeanH will ne e be se o 1. The nine pa icula poin s de ined by meanH ∈ {1,accMeanH,maxMeanH} and d∈ {−1,0,1}a e de ined by he alues desc ibed abo e. Gi en ha he call o nex ChunkSize(d, meanH) will e u n maxChunkSize o he h ee poin s (−1,1), (−1,accMeanH), and (0,1), he unc ion will also e u n maxChunkSize o all poin s inside his iangle. Analogously, o all poin s inside he iangle wi h e ices (1,accMeanH), (1,maxMeanH), and (0,maxMeanH), he unc ion will e u n 1. No ice ha poin s on he diagonals (1,1) o (0,accMeanH), and om he e o (−1,maxMeanH) will e u n las ChunkSize. These h ee ac s p o ide a na u al iangula ion o he space in Figu e 2(b). 5 Dynamic and adap i e implemen a ions I no dependences a ose du ing he pa allel execu ion, he size o he ollowing chunk would be calcula ed only once, ha is, jus be o e issuing i s execu ion. 8 Table 2. Cha ac e is ics o he algo i hms and inpu sizes used. Algo i hm Inpu se desc ip ion Loop Loop ime I e a ions % o FSC chunk pa allelized as % o pe dependence size used o al ime in oca ion iola ions (i e a ions) TREE O -axis pa ab. collision accel 10 94 4 096 0 100 2D-Hull Kuzmin, 10M poin s Main loop 99 9 999 997 0.0008 11 000 2D-Hull Squa e, 10M poin s Main loop 99 9 999 997 0.0032 3 000 2D-Hull Disc, 10M poin s Main loop 99 9 999 997 0.021 1 250 2D-MEC Disc, 10M poin s Inne loop 99 Changes 0.009 1 800 dynamically Delaunay 100K poin s Main loop 99 95 000 0.5 2 O he wise, i he execu ion o he chunk ails, i gi es he un ime sys em an oppo uni y o adjus i s calcula ion by calling he scheduling unc ion wi h upda ed un ime in o ma ion. As i happens in [17], his leads o wo di e en ways o use he scheduling unc ion: – To calcula e he size o he ollowing chunk only he i s ime his pa icula chunk will be issued. Subsequen e-execu ions will keep he same size. See Fig.3(a). – To e-calcula e he size o he ollowing chunk each ime he chunk is sched- uled. This solu ion is called adap i e scheduling in [17]. See Fig.3(b). The ad an age o adap i e o e dynamic scheduling is ha he i s calcu- la ion o he chunk size may ely on incomple e in o ma ion, since some o all o he p e ious chunks a e s ill being execu ed, and he e o e hey may su e addi ional squashes. Adap i e scheduling will always econside he si ua ion using upda ed da a. Na u ally, his comes a he cos o addi ional calls o he scheduling unc ion. 6 Expe imen al e alua ion We ha e used ATLaS, a so wa e-based TLS amewo k [1, 8], o execu e in pa allel ou di e en applica ions ha p esen non-analyzable loops wi h and wi hou dependences among i e a ions. The i s benchma k used is TREE om [2]. This applica ion spends a la ge ac ion o i s sequen ial execu ion ime on a loop ha can no be au oma ically pa allelized by s a e-o - he-a compile s because i has dependence s uc u es ha a e ei he oo complica ed o be analyzed a compile ime o dependen on he inpu da a. We conside h ee addi ional applica ions ha p esen loops wi h depen- dences. The i s one is he 2-Dimensional Con ex Hull (2D-Hull), an inc emen- al andomized algo i hm due o Cla kson e al. [6]. The algo i hm compu es he con ex hull (smalles enclosing con ex polygon) o a se o wo-dimensional poin s in he plane. We ha e es ed his applica ion using h ee di e en inpu se s: Disc and Squa e, ha a e composed o poin s uni o mly dis ibu ed inside a 9 disc and a squa e, and Kuzmin, ha is composed o poin s ha ollow a Kuzmin dis ibu ion [3]. The second applica ion, called he 2-Dimensional Minimum Enclosing Ci cle (2D-MEC) [24], inds he smalles enclosing ci cle con aining a gi en se o poin s in he plane. The cons uc ion is also inc emen al. In his case, a dependence iola ion o ces no only an upda e o he cu en solu ion, bu he ecalcula ion o he en i e enclosing ball. This ac p oduces de as a ing e ec s when he benchma k is specula i ely pa allelized. The las benchma k is he Delaunay iangula ion [14] o a wo-dimensional se o poin s. We ha e used an inpu se o 100K poin s. Table 6 summa izes he cha ac e is ics o each applica ion conside ed. 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. Applica ions we e compiled wi h gcc. Times shown below ep e- sen he ime spen in he execu ion o he main loop o he applica ion. The ime needed o ead he inpu se and he ime needed o ou pu he esul s ha e no been aken in o accoun . Figu e 4 shows he ela i e pe o mance o he men ioned applica ions when execu ed wi h he ATLaS specula i e pa alleliza ion amewo k [1] and h ee di e en scheduling mechanisms: Adap i e Moody Scheduling, Dynamic Moody Scheduling and Fixed-Size Chunking (FSC). The plo s show he pe o mance ob ained when an op imum chunk size is used o FSC (a choice ha equi ed mo e han 20 expe imen s pe applica ion) and o Moody Scheduling, whose choice o pa ame e s equi ed less han i e expe imen s in all cases. In he case o Moody Scheduling, we ha e used a alue o 2 o accMeanH, β=π 4, and a alue o h( he size o he window o be consid- e ed) equal o wice he numbe o p ocesso s o all applica ions. Rega ding α, we ha e used alues ∈(π 20 ,π 6), depending on whe he he applica ion is known o p oduce dependence iola ions a un ime. Fu he mo e, Moody Scheduling u ns ou o be compe i i e e en wi hou any uning: I we se o 1 he ini ial chunk size, i s pe o mance eaches 88.3% o he bes FSC on geome ic a e age. Meanwhile, he pe o mance o FSC wi h chunk size 1 d ops almos o ze o (excep o Delaunay, when he bes chunk size o FSC is 2). Rega ding 2D-Hull (Figs. 4(a), 4(b), and 4(c)), he esul s o he Disc and Squa e inpu se s show ha ou scheduling me hod leads o a be e pe o mance han FSC. Fo he Disc inpu se , he highes speedup (2.17×) is achie ed wi h 32 p ocesso s and he Dynamic e sion. Fo he Squa e inpu se , he bigges speedup (6.81×) is achie ed wi h he Dynamic e sion and 40 p ocesso s. Finally, he pe o mance igu es when p ocessing he Kuzmin inpu se a e simila o all he scheduling al e na i es. The bes pe o mance (11.11×) is achie ed wi h 56 p ocesso s and he Adap i e e sion. The wo emaining applica ions lead o simila pe o mance esul s wi h all he scheduling mechanisms conside ed.