Thread assignment in multicore/multithreaded processors: A statistical approach

1 Th ead Assignmen in Mul ico e/Mul i h eaded P ocesso s: A S a is ical App oach Pe a Radojko i´ c, Paul M. Ca pen e , Miquel Mo e ´ o, Vladimi ˇ Caka e i´ c, Ja ie Ve d´ u, Alex Pajuelo, F ancisco J. Cazo la, Ma io Nemi o sky and Ma eo Vale o, Fellow, IEEE Abs ac —The in oduc ion o mul ico e/mul i h eaded p ocesso s, comp ised o a la ge numbe o ha dwa e con ex s ( i ual CPUs) ha sha e esou ces a mul iple le els, has made p ocess scheduling, in pa icula assignmen o unning h eads o a ailable ha dwa e con ex s, an impo an aspec o sys em pe o mance. Ne e heless, h ead assignmen o applica ions unning on s a e-o - he a p ocesso s is an NP-comple e p oblem. O e he yea s, nume ous s udies ha e p oposed heu is ic-based algo i hms o h ead assignmen . Since he h ead assignmen p oblem is in ac able, i is in gene al impossible o know he pe o mance o he op imal assignmen , so he oom o imp o emen o a gi en algo i hm is also unknown. I is he e o e ha d o decide whe he o in es mo e e o and ime o imp o e an algo i hm ha may al eady be close o op imal. In his pape , we p esen a s a is ical app oach o he h ead assignmen p oblem. Fi s , we p esen a me hod ha p edic s he pe o mance o he op imal h ead assignmen , based on he obse ed pe o mance o each h ead assignmen in a andom sample. The me hod is based on Ex eme Value Theo y (EVT), a b anch o s a is ics ha analyses ex eme de ia ions om he popula ion mean. We also p opose sample p uning, a me hod ha signi ican ly educes he ime equi ed o apply he s a is ical me hod by educing he numbe o candida e solu ions ha need o be measu ed. Finally, we show ha , i no sui able heu is ic- based algo i hm is a ailable, a sample o se e al housand andom h ead assignmen s is enough o ob ain, wi h high con idence, an assignmen wi h pe o mance close o op imal. The p esen ed app oach is a chi ec u e and applica ion independen , and i can be used o add ess he h ead assignmen p oblem in a ious domains. I is especially well sui ed o sys ems in which he wo kload seldom changes. An example is ne wo k sys ems, which ypically p o ide a cons an se o se ices ha a e known in ad ance, wi h ne wo k applica ions pe o ming a simila p ocessing algo i hm o each packe in he sys em. In his pape , we alida e ou me hods wi h an indus ial case s udy o a se o mul i h eaded ne wo k applica ions on an Ul aSPARC T2 p ocesso . This a icle is an ex ension o ou p e ious wo k [44], which was published in P oceedings o 17 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-2012). Index Te ms—Scheduling, Th ead assignmen , Mul i h eading, S a is ical es ima ion, Ex eme alue heo y F 1 INTRODUCTION Mul i h eaded p ocesso s1a e comp ised o se e al co es execu ing h eads ha sha e esou ces a mul iple le - els [57]. Fo example, in a CMP p ocesso whe e each co e suppo s concu en execu ion o se e al h eads h ough SMT, all simul aneously unning h eads sha e global e- sou ces such as he las le el o cache and he I/O. In addi ion o his, h eads unning in he same co e sha e co e esou ces such as he Ins uc ion Fe ch Uni , and he L1 ins uc ion and da a caches. The e o e, he way ha h eads a e assigned o co es de e mines which esou ces hey sha e, and his, in u n, may signi ican ly a ec he •P. Radojko i´ c, P. M. Ca pen e , M. Mo e ´ o, and V. ˇ Caka e i´ c a e wi h Ba celona Supe compu ing Cen e (BSC), Ba celona, Spain. email: {pe a . adojko ic, paul.ca pen e , miquel.mo e o, ladimi .caka e ic}@bsc.es •J. Ve d´ u and A. Pajuelo a e wi h UPC, Ba celona, Spain. email: {j e du, mpajuelo}@ac.upc.edu •F. Cazo la is Scien i ic Resea che in he Spanish Na ional Resea ch Council (IIIA-CSIC) and wi h BSC, Ba celona, Spain. email: an- [email p o ec ed] •M. Nemi o sky is ICREA Resea ch P o esso and wi h BSC, Ba celona, Spain. email: ma io.nemi o[email p o ec ed] •M. Vale o is wi h UPC and BSC, Ba celona, Spain. email: ma- [email p o ec ed] 1. In his pape , he e m “mul i h eaded p ocesso ” e e s o any p ocesso ha has suppo o mo e han one h ead unning a a ime. Chip Mul ip ocesso s (CMPs), Simul aneous Mul i h eading (SMT), Coa se- g ain Mul i h eading, Fine-G ain Mul i h eading p ocesso s, o any com- bina ion o hem a e mul i h eaded p ocesso s. sys em pe o mance. In p ocesso s wi h se e al le els o esou ce sha ing, h ead scheduling is comp ised o wo s eps. In he i s s ep, usually called wo kload selec ion, he OS selec s he se o h eads (wo kload) ha will be execu ed in he p ocesso in he nex ime slice, om a se o eady- o- un h eads. In he second s ep, called h ead assignmen , each h ead in he wo kload is assigned o a ha dwa e con ex ( i ual CPU) o he p ocesso . Dynamic h ead scheduling may po en ially a y he amoun o p ocessing ime made a ailable o applica ions du ing hei execu ion, which can signi ican ly a ec he pe o mance o HPC applica ions [24][40] and educe he pe o mance p o ided by comme cial ne wo k p ocesso s. Since maximizing he amoun o compu a ion powe deli - e ed o unning pa allel applica ions is c i ical o achie ing high pe o mance and scalabili y, many comme cial sys- ems al eady use Ligh weigh Ke nels (LWKs) wi h s a ic scheduling, such as CNK [50] in BlueGene HPC sys ems, and Ne a DPS [2] which is mainly used in ne wo king. LWKs wi h s a ic scheduling a e especially well sui ed o ne wo k sys ems. Typically, hese sys ems p o ide a cons an se o se ices which is known in ad ance, and ne wo k applica ions gene ally pe o m a simila p ocessing algo i hm o each packe in he sys em. The e o e, in a ne wo king en i onmen , he wo kload is ypically known be o ehand, and i changes in equen ly a un ime. In hese sys ems, dynamic h ead scheduling is no indispensable, This pape is published in IEEE T ansac ions on Compu e s, ol. 65, no. 1, pp. 256-269, 2016. The inal publica ion is a ailable a h p://dx.doi.o g/10.1109/TC.2015.2417533. 2 and he main scheduling decision is o de e mine a good assignmen o concu en ly- unning h eads. In gene al, in sys ems in which he wo kload seldom changes, inding a good h ead assignmen becomes he mos impo an p ocess scheduling p oblem. In s a e-o - he-a mul i h eaded p ocesso s, inding an op imal h ead assignmen is an in ac able p oblem. I is NP-comple e e en o simpli ied models o he applica ions and sys em a chi ec u e [22]. The p oblem is especially complica ed when he numbe o ha dwa e con ex s ( i ual CPUs) is la ge, o when p ocesso esou ces a e sha ed a mul iple le els [47][57]. In his case, i is ha d o p edic he impac o esou ce sha ing on sys em pe o mance, as shown by se e al s udies in di e se applica ion domains; e.g. pa allel applica ions on massi e mul i h eaded p oces- so s [47], mul iple applica ions unning on SMTs [16], and da a cen e applica ions on commodi y CPUs [55]. As he numbe o possible h ead assignmen s is as (e.g. 1050) [16][18][29][45], and inc eases apidly, bo h wi h he numbe o h eads and wi h he numbe o ha dwa e con ex s, i is imp ac ical o use exhaus i e sea ch o ind he op imal h ead assignmen . O e he yea s, nume ous s udies (see Sec ion 7) ha e p oposed heu is ic-based algo i hms o add ess he h ead assignmen p oblem. Since he h ead assignmen p oblem is in ac able, i is in gene al impossible o know he pe o mance o he op imal assignmen , so he oom o imp o emen o a gi en algo i hm is also unknown. I is he e o e ha d o decide whe he o in es e o o y o imp o e an algo i hm ha may al eady be close o op imal. In his pape , we p esen a s a is ical app oach o he h ead assignmen p oblem. Fi s , we p esen a me hod ha p edic s he pe o mance o he op imal h ead assignmen based on he obse ed pe o mance o each h ead assign- men in a andom sample. This me hod is based on Ex eme Value Theo y (EVT), a b anch o s a is ics ha analyses ex eme de ia ions om he popula ion median. We also p opose and e alua e sample p uning, a me hod ha educes he numbe o andom h ead assignmen s ha need o be execu ed on he a ge pla o m, which in u n educes he ime needed o he o e all analysis. Finally, we show ha he pe o mance o he bes obse ed h ead assignmen in a andom sample is likely o be close o op imal, so i no sui able heu is ic-based algo i hm is a ailable, a good h ead assignmen could be ound using andom sampling on i s own. This pape ex ends ou p e ious wo k [44], as discussed in Sec ion 7. EVT is an impo an b anch o s a is ics, which has ound mul iple applica ions in ci il enginee ing, inance and eme gency planning. I p o ides many powe ul heo ems and ools, bu i s applica ion in compu e science and enginee ing is ma ginal. The s a is ical app oach desc ibed in his pape can be applied o o he in ac able p oblems in many di e se ields o compu e science and enginee ing. In ac , we ha e al eady applied i success ully o compila ion o mul i h eaded s eaming applica ions [43]. The s a is ical analysis in e s he popula ion maximum (o minimum) based on a andom sample, in a way ha is independen o he p oblem being add essed. As such, i does no equi e a p o ound unde s anding o he a ge sys em, so i can be employed wi hou a signi ican in es men in e o o ime. The me hod is pa icula ly use ul in he e alua ion o any new p oposed heu is ics-based algo i hm. The es o his pape is o ganized as ollows. Sec- ion 2 desc ibes he applica ion domain and mo i a es he need o s a ic h ead assignmen . Sec ion 3 p esen s he expe imen al en i onmen used in ou s udy. Sec ion 4 p esen s he s a is ical me hod ha es ima es he op imal sys em pe o mance, wi h an emphasis on unde s anding and in ui ion. Sec ion 5 p oposes sample p uning, which educes he ime needed o apply he s a is ical me hod. Sec ion 6 p esen s he andom sampling me hod, which can ind a good solu ion when no sui able heu is ic is a ailable. Sec ion 7 desc ibes he ela ed wo k, and Sec ion 8 p esen s he conclusions. Finally, Appendix includes de ailed de- sc ip ion o he benchma ks and he s a is ical me hod. 2 BACKGROUND In his pape , we ocus on he p oblem o h ead assignmen o ne wo k applica ions unning on mul i h eaded p oces- so s. Ne wo k applica ions a e inc easing in impo ance, wi h he inc easing numbe and complexi y o In e ne se ices, and he emendous g ow h in In e ne a ic. P o iding high-pe o mance ne wo k se ices is c i ical o sus aining online se ices and a oiding packe d op, since ne wo k p ocesso s a e sa u a ed by he high ne wo k bandwid h, and i is cons an ly inc easing. In o de o p o ide high h oughpu and low la ency, ne wo k applica ions impose speci ic equi emen s on he ha dwa e and ope a ing sys em. Ne wo k applica ions ex- hibi signi ican pa allelism a mul iple le els [58], so hey a e well sui ed o un on massi ely mul i h eaded p ocesso s. These p ocesso s a e able o p ocess nume ous packe s concu en ly, h ough he simul aneous execu ion o a la ge numbe o ha dwa e con ex s. Ne wo k-o ien ed sys ems equi e un- ime en i onmen s ha p o ide high pe o mance, high-speed packe p ocess- ing and p edic able execu ion ime. To ha end, hese sys- ems use low-o e head low-noise un- ime en i onmen s, which educe he pe o mance impac o sys em o e head incu ed by managemen h eads [2]. Such un ime en i- onmen s educe sys em o e head by p o iding only he essen ial sys em se ices. One ea u e omi ed by se e al widely used ligh weigh un ime en i onmen s is dynamic h ead scheduling. In ne wo king en i onmen s, h eads a e ypically mapped o ha dwa e con ex s s a ically, i.e. be o e un ime. This is because ne wo k applica ions ypically pe o m a ixed p ocessing algo i hm, applied o each packe ha a i es, which is known be o ehand and seldom changes o e ime. Op imal h ead assignmen equi es a deep knowledge o he esou ce equi emen s o he a ious h eads and an unde s anding o how he h eads in e ac a each sha ed p ocesso esou ce. I is di icul o de e mine he op imal 3 h ead assignmen wi hou unning many expe imen s, he numbe o which apidly inc eases wi h he numbe o ha d- wa e con ex s, amoun o esou ce sha ing, and he numbe o concu en ly unning h eads. The p oblem is e en ha de when he applica ions hemsel es a e mul i h eaded, since o de e mine he bo lenecks, he designe mus be awa e o how he h eads communica e. Th ead assignmen is ypically done in one o h ee ways: (1) Manual assignmen : A skilled designe de e mines a good h ead assignmen based on a de ailed analysis o he a ge a chi ec u e and o line p o iling [57]. The analysis is complex, and i s complexi y inc eases wi h he numbe o p ocesso ha dwa e con ex s, numbe o le els o esou ce sha ing, and numbe o simul aneously unning h eads. Manual h ead assignmen is expensi e and ime consuming, and any change in he applica ion o ha dwa e pla o m equi es he whole analysis o be epea ed. (2) Pe o mance p edic o s: Nume ous s udies p opose me hods o p edic he pe o mance o di e en h ead assignmen s o a gi en wo kload, based on a chi ec u e- dependen heu is ics (see Sec ion 7). Since he numbe o possible h ead assignmen s is huge, i is in easible o p e- dic he pe o mance o all assignmen s. The p edic o s a e he e o e used o es ima e pe o mance o a sample o as- signmen s and de e mine he bes assignmen in he sample. In addi ion, he p edic o s in oduce an e o when es ima - ing pe o mance, so he assignmen wi h he bes p edic ed pe o mance may no be he ac ual bes one. Ano he d aw- back o mos cu en ly-a ailable pe o mance p edic o s is ha hey do no suppo mul i h eaded applica ions. In bo h, manual h ead assignmen and pe o mance p e- dic o s, a change in a chi ec u e o wo kload may equi e signi ican ex a ime and e o o ecalcula e he h ead assignmen . When h ead assignmen is done manually, he designe mus epea he analysis. When using pe o mance p edic o s, he p edic ion algo i hm may equi e signi ican changes. (3) Load balancing and cache a ini y: S a e-o - he- a ully- ledged OSs, such as Linux and Sola is, use a load balancing mechanism [3][56] o equally dis ibu e he load o he unning h eads among all a ailable scheduling domains (e.g. co es o he CMP a chi ec u e). In addi ion, cache and TLB a ini y algo i hms [3][56] keep each h ead assigned o a single logical CPU in o de o a oid cache and TLB misses ha would be caused by h ead mig a ion. Al hough hese echniques imp o e pe o mance, hey a e insu icien o ully exploi he capabili ies o cu en mul i- h eaded p ocesso s wi h se e al le els o esou ce sha ing. Load balancing does no ake in o accoun he di e ing amoun s o p ocesso esou ces used by he a ious co- unning h eads, and he e o e i may igno e he bes schedules, conside ing hem o be “unbalanced” [16]. In ou p e ious s udies [44][45][46], we e alua e load-balancing h ead assignmen o ne wo king applica ions unning on he Ul aSPARC T2 p ocesso , measu ing a signi ican pe o mance loss compa ed wi h he op imal assignmen , o up o 48%. Ha dwa e Pipeline 0 IFU IFU LSU L1 Ins uc ion Cache L1 Da a Cache DTLB ITLB Ha dwa e Pipeline 1 Co e 0 Co e 1 Co e 7 ..... ..... C ossba I/O L2 Cache IEU IEU H a d w a e P i p e l i n e 0 I F U I F U L S U L 1 I n s u c i o n C a c h e L 1 D a a C a c h e D T L B I T L B H a d w a e P i p e l i n e 1 C o e 0 C o e 1 C o e 7 . . . . . . . . . . C o s s b a I / O L 2 C a c h e I E U I E U Fig. 1. Schema ic iew o he h ee esou ce sha ing le els o he Ul aSPARC T2 p ocesso Impo ance o knowing he op imal sys em pe o - mance. Nume ous s udies p esen algo i hms o h ead assignmen on mul i h eaded p ocesso s (see Sec ion 7). A new p oposal would, in an ideal wo ld, be compa ed wi h he op imal solu ion, bu , in gene al, he op imal canno be ound wi hou unning all alid h ead assignmen s. Se e al au ho s [4][18][45], he e o e, e i y hei p oposals wi h espec o ei he a nai e h ead assignmen , in which h eads a e andomly assigned o he i ual CPUs o he p ocesso , o Linux-like assignmen s, in which he numbe o h eads pe co e o pe scheduling domain is balanced. I is ou posi ion ha he e alua ion o hese p oposals would be signi ican ly imp o ed i hey we e compa ed o an es ima e o he op imum. This a gumen is desc ibed in mo e de ail in he ASPLOS publica ion [44]. 3 EXPERIMENTAL ENVIRONMENT AND METHODOLOGY We e alua ed he s a is ical analysis using mul i h eaded ne wo k applica ions unning in a eal indus ial en i on- men . We used wo SPARC En e p ise T5220 se e s, each o which con ained one Ul aSPARC T2 p ocesso . One T5220 machine gene a ed he ne wo k a ic using he O acle Ne wo k T a ic Gene a o (NTGen) [2]. NTGen is a so wa e ool ha p oduces IP 4 TCP/UDP packe s, wi h a se o con igu a ion pa ame e s con olling a ious packe heade ields. This machine was connec ed ia a 10Gb link o he second T5220 machine, on which we execu ed he selec ed h ead assignmen s. In all expe imen s p esen ed in he s udy, we e i ied ha NTGen gene a ed su icien a ic o sa u a e he ne wo k p ocessing machine. The pe o mance bo leneck was he e o e he packe p ocessing speed, which is de e mined by he pe o mance o he selec ed h ead assignmen . 3.1 Ul aSPARC T2 p ocesso The Ul aSPARC T2 is a mul i h eaded p ocesso [1] wi h eigh co es connec ed h ough a c ossba o a sha ed L2 cache (see Fig. 1). Each co e suppo s eigh ha dwa e con ex s, ou on each execu ion pipeline, gi ing a o al o 64 ha dwa e con ex s o he en i e p ocesso . Th eads may, he e o e, sha e (and compe e o ) ha dwa e esou ces a h ee di e en le els: In aPipe,In aCo e, and In e Co e. Resou ces a he In aPipe le el, such as he Ins uc ion Fe ch Uni (IFU) and he In ege Execu ion Uni s (IEU), a e sha ed among h eads unning in he same ha dwa e 4 pipeline. The In aCo e esou ces, such as he Load S o e Uni (LSU), L1 ins uc ion cache, L1 da a cache, da a and ins uc ion TLBs, as well as Floa ing Poin and G aphic Uni (FPU), and C yp og aphic P ocessing Uni , a e sha ed among h eads unning on he same co e. Finally, he In e Co e esou ces, including he L2 cache, on-chip in- e connec ion ne wo k (c ossba ), memo y con olle s, and he in e ace o o -chip esou ces, a e sha ed among all h eads unning on he p ocesso [57]. 3.2 Ne a DPS Ne wo king sys ems use ligh weigh un ime en i onmen s o educe he o e head ha would be in oduced by a ully- ledged OS [42]. One o hese en i onmen s is O acle’s Ne a DPS [2]. In o de o educe o e head and noise, Ne a DPS omi s ce ain common OS ea u es, includ- ing i ual memo y, in e up handling, daemons, con ex swi ching, and he un- ime p ocess schedule . A h ead always uns o comple ion on i s assigned ha dwa e con ex , wi hou p eemp ion. The assignmen o unning h eads o p ocesso ha dwa e con ex s ( i ual CPUs) mus he e o e be pe o med s a ically a compile ime. I is he esponsi- bili y o he p og amme o oolchain o de e mine which ha dwa e con ex will execu e each pa icula h ead. 3.3 Benchma ks This sec ion b ie ly desc ibes he benchma ks ha we used in his s udy. De ailed p esen a ion o he benchma ks is included in Appendix A. No e ha , since Ne a DPS omi s s anda d OS ea u es including dynamic memo y alloca ion and ile managemen , we had o adap some o he benchma ks o execu e in his en i onmen . The benchma ks used a e desc ibed nex : (1) IP Fo wa ding (IPFwd) applica ion decides whe e o o wa d a packe o he nex hop based on he des ina ion IP add ess. Depending on he size o he lookup able and des ina ion IP add esses o he packe s ha a e o be p ocessed, IPFwd may exhibi signi ican ly di e en memo y beha io . In o de o co e di e en cases o IPFwd memo y beha io , we c ea ed wo a ian s o he IPFwd applica ion, bo h based on he IPFwd applica ion included in he Ne a DPS dis ibu ion [2]: (i) The lookup able i s in he L1 da a cache (IPFwd-L1); (ii) The lookup able en ies a e ini ialized o make IPFwd con inuously access he main memo y (IPFwd-Mem benchma k). (2) Packe analyze is a p og am ha can in e cep and log a ic passing o e a ne wo k o pa o a ne wo k [15]. The packe analyze used in he expe imen s cap u es each packe ha passes h ough he Ne wo k In e ace Uni (NIU), decodes he packe , and analyzes i s con en acco ding o he app op ia e RFC speci ica ions. (3) Aho-Co asick is a s ing ma ching algo i hm. S ing ma ching is he basic echnique o analyze ne wo k a ic a he applica ion laye . In he expe imen s p esen ed in his pape , we used he Aho-Co asick algo i hm o sea ch he packe payloads o he keywo ds in he Sno Denial-o - Se ice se o in usion de ec ion ules ( e sion 2.9). Memo y Queue Ne wo k In e ace Uni R PMemo y Queue T Ne wo k In e ace Uni Ne wo k In e ace Uni Ne wo k In e ace Uni T a ic om NTGen Fig. 2. The schema ic iew o he benchma ks (4) S a e ul packe p ocessing is an impo an com- ponen o s a e-o - he-a ne wo k moni o ing ools and in usion p e en ion and de ec ion sys ems. Unlike s a eless applica ions, which p ocess packe s independen ly (exam- ples include he IPFwd, Packe analyze , and Aho-Co asick benchma ks abo e), s a e ul packe p ocessing keeps in o - ma ion om he p ocessing o p e ious packe s. Benchma k implemen a ion: As shown in Fig. 2, each benchma k is di ided in o h ee h eads: Recei ing (R), P ocessing (P), and T ansmi ing (T). R, P, and T h eads communica e h ough memo y queues and p ocess ne wo k packe s in a pipelined ashion. The wo kload consis s o se e al benchma k ins ances unning concu en ly, each o which has he R, P, and T h eads. This is a common way o implemen ne wo k applica ions [2][62]. Summa y: The p esen ed benchma ks ep esen a good es bed o he analysis o h ead assignmen echniques because: (1) Each benchma k ins ance has h ee di e en h eads, so e en when he wo kload consis s o se e al ins ances o he same benchma k, he sys em mus deal wi h he e oge- neous h eads. (2) The benchma ks s ess he ha dwa e esou ces o he Ul aSPARC T2 p ocesso a all h ee sha ing le els [57]. (3) Each benchma k ins ance has h eads ha communi- ca e h ough sha ed memo y queues. The benchma k pe - o mance also depends on he dis ibu ion o in e connec ed h eads among p ocesso co es (L1 cache domains). (4) Th ead assignmen has a signi ican impac on pe - o mance. We de ec pe o mance a ia ion o up o 49% be ween di e en h ead assignmen s o he same wo kload. 3.4 EVT equi emen s and sampling me hods EVT has wo main p e equisi es, which should be ali- da ed be o e applying he heo y o a pa icula eal-li e p oblem [25]. The i s p e equisi e is ha he sample unde s udy is comp ised o independen and iden ically dis ibu ed (i.i.d.) obse a ions. The second p e equisi e is ha he p obabili y dis ibu ion o he s a is ics unde s udy should be con inuous. These equi emen s and he s a is ical es s used o hei e alua ion a e discussed in de ail in Appendix B.2. 3.5 Me hodology In all expe imen s, we simul aneously execu ed eigh benchma k ins ances, gi ing 24 h eads. We could no execu e mo e han eigh benchma k ins ances because o a limi a ion in he expe imen al en i onmen : he on-chip Ne wo k In e ace Uni (NIU) o he Ul aSPARC T2 p ocesso can spli he incoming ne wo k a ic in o up 5 o eigh DMA channels, and, unde Ne a DPS, each DMA channel can be bound o a mos one ecei ing h ead. In o de o ensu e s able esul s, we measu ed he execu ion ime o p ocess h ee million ne wo k packe s pe benchma k ins ance. This means ha each applica ion h ead had a loop ha execu ed h ee million imes. The execu ion ime o each expe imen was a ound 1.5 seconds, wi h he p ecise du a ion depending on he benchma k and on he pe o mance o he h ead assignmen unde es . 4 ESTIMATION OF THE OPTIMAL PERFOR- MANCE – POT METHOD The bes way o e alua e any h ead assignmen app oach is o compa e he pe o mance o he h ead assignmen p o ided by he app oach wi h he pe o mance o he op- imal assignmen , i.e. wi h he op imal sys em pe o mance. The di e ence in pe o mance gi es he maximum po en ial o imp o emen o he p oposed scheduling app oach. Since h ead assignmen is NP-comple e and he numbe o possible h ead assignmen s is as , he op imal sys em pe o mance canno be de e mined [29]. In his pape , we p opose using s a is ical in e ence me hods o es ima e he op imal sys em pe o mance, based on he measu ed pe o mance o a sample o andom h ead assignmen s. 4.1 Peak O e Th eshold (POT) me hod We es ima e he pe o mance o he op imal h ead as- signmen using Ex eme Value Theo y (EVT). EVT is a b anch o s a is ics ha s udies ex eme de ia ions om he popula ion median [7][10]. One o he EVT app oaches is he Peak O e Th eshold (POT) me hod. The POT me hod akes in o accoun he dis ibu ion o he obse a ions ha exceed a gi en (high) h eshold. Fo example, in Fig. 3, he obse a ions x1,x4,x5, and x7exceed he h eshold uand cons i u e ex eme alues ha can be used in POT analysis. The POT me hod can be explained using he cumula i e dis ibu ion unc ion (CDF). Fo example, assume ha F is he CDF o a andom a iable X, which is de ined as F(x) = P(X≤x). The POT me hod can be used o es ima e he cumula i e dis ibu ion unc ion Fuo alues o xabo e a ce ain h eshold u. The unc ion Fuis called he condi ional excess dis ibu ion unc ion and i is de ined as: Fu(y) = P(X−u≤y|X > u),0≤y≤xF−u, whe e Xis he obse ed andom a iable, uis he h eshold, y=x−ua e he exceedances o e he h eshold, and xF≤ ∞ is he igh endpoin o he cumula i e dis ibu ion unc ion F. Fig. 4 shows he CDF o a andom a iable X(uppe cha ) and he co esponding condi ional excess dis ibu ion unc ion Fu(y)(lowe cha ). The POT me hod is based on he Pickands-Balkema- de Haan heo em [6][41]: Theo em 1: Fo a la ge class o unde lying dis ibu ion unc ions F, he condi ional excess dis ibu ion unc ion Pe o mance Obse a ions Fig. 3. Ex eme alues o e he h eshold u 0 1 0 1 Fig. 4. Cumula i e dis ibu ion unc ion F(x)and co e- sponding condi ional excess dis ibu ion unc ion Fu(y) Fu(y), o ula ge, is well app oxima ed by Gene alized Pa e o Dis ibu ion Gξ,σ(y)whe e Gξ,σ(y) = 1−(1 + ξ σy)−1/ξ o ξ6= 0 1−e−y/σ o ξ= 0 o y∈[0,(xF−u)] i ξ≥0and y∈[0,−σ ξ]i ξ < 0. 4.2 Applica ion o POT o h ead assignmen Theo em 1 means ha he Fuo nume ous dis ibu ions ha p esen eal-li e p oblems can be app oxima ed wi h GPD. Fo each pa icula p oblem, he decision as o whe he GPD can be used o model he p oblem, is made based on how well he sample o obse a ions can be i ed o Gene - alized Pa e o Dis ibu ion (GPD). GPD is de ined wi h wo pa ame e s: shape pa ame e ξand scaling pa ame e σ. An impo an cha ac e is ic o GPD used in his s udy is ha o ξ < 0, he uppe bound o he obse ed alue (in ou s udy, he pe o mance o he op imal h ead assignmen ) can be compu ed as u−σ ξ, whe e uis he selec ed h eshold and σand ξa e he GPD pa ame e s [23][30]. We use he POT me hod o es ima e he op imal sys em pe o mance, i.e. he pe o mance o he op imal h ead assignmen , o a gi en wo kload based on he measu ed pe o mance o he sample o andom h ead assignmen s. Applica ion o POT me hod o he h ead assignmen p ob- lem is explained in de ail in Appendix B. In his sec ion, we p esen a b ie in ui i e o e iew o he main s eps o he analysis. The applica ion o he POT me hod o he h ead assign- men p oblem in ol es he ollowing ou s eps: S ep 1: Gene a e he sample o andom h ead assign- men s, execu e he assignmen s on he a ge machine, and measu e he pe o mance o each assignmen . The me hod used o gene a e andom h ead assignmen s and 6 0% 5% 10% 15% 20% Numbe o andom h ead assignmen s in he sample Es ima ed pe o mance imp o emen [%] 0% 5% 10% 15% 20% Numbe o andom h ead assignmen s in he sample Es ima ed pe o mance imp o emen [%] (a) Aho-Co asick benchma k (b) IPFwd-L1 benchma k Fig. 5. Impac o he sample size on he es ima ion o he op imal pe o mance expe imen al me hodology a e desc ibed in de ail in Ap- pendix B.2 and Sec ion 3.5, espec i ely. S ep 2: Selec he h eshold u.Selec ion o he h eshold uis an impo an s ep in POT analysis. In his s udy, he h eshold uis selec ed using g aphical me hods: sample mean excess plo [23][30] and quan ile plo [7][30]. S ep 3: Fi he GPD unc ion o he obse a ions ha exceed he h eshold and es ima e pa ame e s ξand σ. Once he h eshold uis selec ed, he obse a ions o e he h eshold can be i ed o GPD, and he pa ame e s o he dis ibu ion can be es ima ed. Di e en me hods can be used o es ima e he pa ame e s o GPD om a sample o obse a ions [9][26][27][53]. In ou s udy, GPD pa ame e s we e es ima ed using he likelihood unc ion, a s a is ical me hod ha es ima es dis ibu ion pa ame e s based on a se o obse a ions [5]. S ep 4: Es ima e he op imal sys em pe o mance, i.e. he uppe pe o mance bound o all h ead assignmen s. The poin es ima e o he Uppe Pe o mance Bound (UPB) is compu ed as d UPB =u−ˆσ/ˆ ξ, whe e ˆσand ˆ ξa e es ima ed alues o he GPD pa ame e s. The uppe bound o he obse ed alue can be de e mined only o ˆ ξ < 0which is sa is ied o all da a se s ha a e p esen ed in his pape . In addi ion o he UPB poin es ima e, in o de o indica e he con idence o he es ima e, we compu e he con idence in e als o he es ima ed UPB. UPB con idence in e al is compu ed using likelihood a io es [5] and Wilks’s heo em [13][60][61]. 4.3 POT E alua ion This sec ion e alua es he POT s a is ical me hod by apply- ing i o he h ead assignmen p oblem o mul i h eaded ne wo k applica ions on he Ul aSPARC T2 p ocesso . Also, we de e mine how many andom h ead assignmen s a e equi ed o ob ain a p ecise es ima e o he op imal pe o mance. 4.3.1 Applicabili y o he POT me hod o he h ead assignmen p oblem The e a e se e al easons why he POT me hod may ail o p oduce an es ima e. Fi s , he exceedances may no i o a GPD. This can be easily de ec ed in S ep 2 and S ep 3 o he POT analysis (see Appendix B.3). Second, he uppe bound o he es ima ed op imal pe o mance may di e ge o in ini y (ξ≥0). Finally, he es ima ion o he op imal sys em pe o mance (S ep 4 o he POT me hod) is based on an i e a i e me hod ha may no con e ge o a solu ion ( o mo e de ails, see Appendix B.3). The e o e, he i s s ep o ou e alua ion is o check whe he o no he POT me hod is able o p oduce an es ima e o he op imal pe o mance. Fo each benchma k, we gene a ed a uni o mly dis ibu ed sample o 5,000 andom h ead assignmen s and execu ed hem on he Ul aSPARC T2 p ocesso . We hen a emp ed o apply he POT me hod o he 5,000 obse ed pe o mance measu e- men s. The me hod success ully p oduced an es ima e o he op imal pe o mance, o all benchma ks unde s udy. 4.3.2 P ecision o he es ima ion In o de o unde s and how he p ecision o he es ima e depends on he sample size, we a ied he numbe o h ead assignmen s in he andom sample be ween 1,000 and 5,000, and es ima ed he op imal pe o mance o di e en sample sizes. Samples ha comp ise om 1,000 o 4,500 obse a ions a e selec ed as a andom subse om he comple e sample o 5,000 h ead assignmen s. In ui i ely, we would expec ha , as he sample size is inc eased, he p ecision o he pe o mance es ima e would also inc ease. In gene al, la ge samples con ain mo e h ead assignmen s wi h pe o mance abo e he h eshold, so ha mo e da a alues a e i ed o he Gene alized Pa e o Dis ibu ion (GPD), and consequen ly he es ima ed GPD pa ame e s and he op imal pe o mance a e all mo e p e- cise. This is wha we obse e. Fo all he benchma ks used in he s udy, we de ec ed ha he wid h o he con idence bounds educes as he numbe o h ead assignmen s in he sample inc eases. We also no iced ha , as he sample size inc eases, he poin es ima ion o he op imal pe o mance emains oughly he same, and he con idence bounds con e ge o his alue. Fig. 5 shows mo e de ail o wo illus a i e benchma ks: Aho-Co asick and IPFwd-L1. In each cha , he x-axis lis s he sample size, while he y-axis shows he es ima ed pe o mance imp o emen — he ela i e di e ence be ween he es ima ed op imal pe o mance and he ac ual pe o - mance o he bes h ead assignmen in he andom sample. The c oss ma ke s co espond o he poin es ima ion o he op imal pe o mance, and he e o ba s show he con idence bounds o he 0.95 con idence le el. Fo he Aho-Co asick benchma k, wi h 1,000 andom 7 1 0 Min measu ed pe o mance Max measu ed pe o mance S ep 2: Selec he h eshold u S ep 1: Gene a e 1000s o andom h ead assignmen s. Execu e hem on he a ge HW pla o m. Measu e he pe o mance. S ep 3: Fi he pe o manace o h ead assignmen s o e he h eshold o he GPD (a mos 5% o he ini ial sample size) S ep 4: Es ima e he op imal sys em pe o man ce Empi ical Cumula i e Dis ibu ion Func ion Empi ical Cumula i e Dis ibu ion Func ion 1 0 Max measu ed pe o mance S ep 1: Gene a e 1000s o andom h ead assignmen s. P edic hei pe o mance. 0.5 Min measu ed pe o mance S ep 4: Selec he h eshold u S ep 5: Fi he pe o manace o h ead assignmen s o e he h eshold o he GPD (a mos 5% o he ini ial (gene a ed) sample size) S ep 3: Execu e he emaining h ead assignmen s on he a ge HW pla o m. Measu e hei pe o mance. Plo he igh po ion o he eCDF. S ep 2: Dis ega d p edic ed low-pe o ming h ead assignmen s S ep 6: Es ima e he op imal sys em pe o mance Empi ical Cumula i e Dis ibu ion Func ion (a) Baseline POT algo i hm (b) Sample-p uning SP-POT algo i hm Fig. 6. Applica ion o he s a is ical me hods o he h ead assignmen p oblem h ead assignmen s, he wid h o he 0.95 con idence in- e al is a ound 5%, which is s ill su icien o es ima e he op imal pe o mance wi h high p ecision. On he o he hand, o he IPFwd-L1 benchma k, an es ima ion based on 1,000 andom h ead assignmen s has wide con idence bounds o almos 20%, as can be seen in Fig. 5(b). Fo his benchma k, p ecise es ima ion o he op imal pe o mance equi es a leas 2,000 h ead assignmen s. Resul s o he IPFwd-Mem,Packe Analyze , and S a e ul benchma ks ollow a simila end as ha o he IPFwd-L1 benchma k (Fig. 5(b)). We he e o e conclude ha he app op ia e sample size o p ecise es ima ion o he op imal pe o mance depends on he benchma k unde s udy. I he use equi es a pa ic- ula p ecision, we p opose he ollowing i e a i e me hod. The use i s gene a es a small sample, o app oxima ely 1,000 h ead assignmen s, and p oduces an es ima e o he op imal pe o mance using he POT me hod. I he p ecision o he es ima e does no sa is y he use ’s equi emen s, hen he sample size should be inc eased and he analysis epea ed, un il i does. 5 SAMPLE PRUNING – SP-POT METHOD Ou analysis o he ime needed o he POT me hod shows ha mos o ha ime was spen on execu ing andom h ead assignmen s on he Ul aSPARC T2 p ocesso . This sec ion p oposes sample p uning, a me hod ha educes he ime equi ed o he s a is ical analysis, by execu ing a smalle numbe o h ead assignmen s on he a ge machine. We also p esen he Sample P uning POT (SP-POT) me hod, which in eg a es sample p uning in o he POT me hod. We hen e alua e SP-POT pe o mance, inding an eigh old educ ion in analysis ime o a negligible di e ence in he es ima e. 5.1 SP-POT Mo i a ion The POT me hod equi es pe o mance measu emen s o housands o andom h ead assignmen s. Ob aining his da a equi es ha each h ead assignmen is execu ed on he ha dwa e pla o m unde s udy, which in ol es, in o al, a signi ican amoun o execu ion ime. Fo example, in ou s udy, execu ing 5,000 andom h ead assignmen s on he Ul aSPARC T2 p ocesso ook, depending on he benchma k, be ween 1.5 and 2.5 hou s. On he o he hand, he emaining s eps o he analysis can be comple ed in a ew minu es: gene a ing 5,000 uni o mly dis ibu ed andom h ead assignmen s akes less han a minu e, and he POT s a is ical analysis is done wi hin a simila ime. This means ha , in ou s udy, mo e han 95% o he ime needed o he o e all analysis was expended on execu ing he andom h ead assignmen s on he ha dwa e pla o m. In o de o examine he oppo uni y o educe he expe - imen a ion ime, we analyze he POT algo i hm p esen ed in Sec ion 4. Fig. 6(a) shows an o e iew o he POT algo i hm om he pe spec i e o he Empi ical Cumula i e Dis ibu ion Func ion (ECDF) o he pe o mance mea- su emen s on he ha dwa e pla o m. The x-axis gi es he pe o mance o he h ead assignmen s, om he minimal o he maximal obse ed in he sample. The y-axis is he ac ion o he h ead assignmen s in he sample wi h pe o mance less han o equal o he alue on he x-axis. In he POT algo i hm, S eps 3 and 4, which i he GPD unc ion o he obse a ions hen es ima e he op imal sys em pe o mance, only depend on he h ead assignmen s ha exceed h eshold u, as does calcula ing he con idence in e al using he me hod desc ibed in he appendix. Since he GPD is i ed o he ail o he dis ibu ion, his h eshold is ypically chosen a he 95 h pe cen ile o abo e [23][30], meaning ha only abou 5% o he h ead assignmen s a e used in S eps 3 and 4 (see Fig. 6(a)). The emaining h ead assignmen s, which comp ise a leas 95% o he execu ion ime, a e dis ega ded om he es o he analysis. 5.2 Sample P uning and SP-POT Algo i hm We p opose sample p uning, a me hod ha educes he numbe o andom h ead assignmen s ha need o be execu ed on he a ge pla o m, which in u n educes he ime o apply he o e all analysis. Bo h he sample p uning echnique and he enhanced e sion o he POT algo i hm, which is known as SP-POT, a e illus a ed in Fig. 6(b). This igu e plo s he ECDF o he pe o mance measu emen s, in a simila way o Fig. 6(a). Applica ion o he POT s a is ical me hod wi h sample p uning o he h ead assignmen p oblem is comp ised o he ollowing six s eps: S ep 1: Gene a e he sample o andom h ead assign- men s, and p edic he pe o mance o each o hem. The 8 pe o mance o a gi en h ead assignmen can be p edic ed using a heu is ic based on analysis o he applica ion ha dwa e equi emen s and p ope ies o he a ge pla - o m. P e ious s udies ha add ess he p ocess scheduling p oblem o mul i h eaded p ocesso s [20][45][46][51][52] p esen se e al sys ema ic me hods o p edic he pe o - mance o wo kloads execu ed on mul i h eaded p ocesso s. Any such me hod may be used o p edic he pe o mance o he andomly-gene a ed h ead assignmen s. S ep 2: Dis ega d p edic ed low-pe o ming h ead assignmen s. Th ead assignmen s p edic ed o ha e low o medium pe o mance a e unlikely o be in he uppe ail o he ECDF, i.e. hey a e unlikely o be in he 5% o he bes -pe o ming assignmen s, and he e o e unlikely o be i ed o he GPD. We he e o e disca d hem om u he analysis. In his s udy, we analyze h ee le els o sample p uning, by elimina ing he h ead assignmen s wi h p edic ed pe o mance in he bo om 50%, 75%, and 90%, espec i ely. S ep 3: Execu e he emaining h ead assignmen s on he a ge ha dwa e pla o m, and measu e hei pe o mance. These alues a e used o c ea e he igh -hand po ion o he ECDF, as illus a ed in Fig. 6(b). This igu e shows he case whe e 50% o he h ead assignmen s a e o be execu ed on he eal ha dwa e. As be o e, he x-axis o he ECDF anges om he minimal o maximal pe o mance, bu as measu ed in he p uned sample ( he diag am has he same scale as be o e only o simplici y in p esen a ion). Since he ECDF is plo ed o he 50% o h ead assignmen s wi h medium o high p edic ed pe o mance, he y-axis anges om 0.5 o 1. S ep 4: Selec he h eshold u. S ep 5: As be o e, i he GPD unc ion o he pe o - mance obse a ions ha exceed he h eshold, and es ima e pa ame e s ξand σ. S ep 6: P oduce he poin es ima e and con idence bounds o he op imal sys em pe o mance, as be o e. S eps 4, 5, and 6 o he SP-POT algo i hm, which includes sample p uning, a e exac ly he same as S eps 2, 3, and 4 o he baseline POT algo i hm om Sec ion 4 (compa e also Fig. 6(a) and 6(b)). 5.3 SP-POT E alua ion This sec ion e alua es he SP-POT me hod by applying i o all he benchma ks unde s udy, in a simila way o he analysis o he POT me hod in Sec ion 4.3. The bench- ma ks we e execu ed in he en i onmen ha comp ises Ul aSPARC T2 p ocesso and Ne a DPS low-o e head un ime en i onmen , as desc ibed in Sec ion 3. In all he expe imen s, we simul aneously execu ed 24 so wa e h eads, he maximum numbe ha could be execu ed in he cu en expe imen al en i onmen (see Sec ion 3.5). In S ep 1 o SP-POT algo i hm, we p edic ed he pe - o mance o he h ead assignmen s using he BlackBox schedule [46]. The BlackBox schedule is a model ha p edic s he pe o mance o di e en h ead assignmen s o applica ions unning on mul i h eaded p ocesso s. The e a e h ee p incipal easons ha mo i a ed us o choose his 4.10 4.12 4.14 4.16 4.18 4.20 No sample p uning 50% 75% 90% Millions P uning le el - Po ion o he andom h ead assignmen s ha a e dis ega ded a e he pe o mance p edic ion Es ima ed pe o mance o he op imal h ead assinmen [Packe s Pe Second - PPS] Fig. 7. Sample p uning e alua ion (Aho-Co asick) pe o mance p edic o . Fi s , he BlackBox schedule is one o he ew me hods designed o p edic he pe o mance o mul i h eaded applica ions. Second, he model can be easily adap ed o di e en applica ions, since i equi es no da a abou he ha dwa e equi emen s o he applica ions unde s udy, no does i equi e any modi ica ions o he applica ion sou ce code. Thi d, he model equi es minimal in o ma ion abou he a ge p ocesso a chi ec u e and i can be easily applied o di e en ha dwa e pla o ms. Ou analysis has h ee main goals. Fi s , we e alua e whe he o no he SP-POT algo i hm wi h sample p uning could p oduce a pe o mance es ima e o he op imal h ead assignmen . Second, we quan i y he e o ha is in oduced by sample p uning. Finally, we analyze he speedup in analysis ime, compa ed wi h he baseline POT algo i hm. Fo each o he benchma ks unde s udy, we applied he SP-POT s a is ical algo i hm o he same sample o 5,000 andomly-gene a ed h ead assignmen s used in Sec ion 4.3. We applied h ee le els o sample p uning, a he 50%, 75%, and 90% le els, meaning ha he indica ed p opo ion o h ead assignmen s we e disca ded, lea ing 50%, 25%, o 10% o hem o be execu ed on he Ul aSPARC T2 p ocesso . The SP-POT algo i hm success ully es ima ed he pe o mance o he op imal h ead assignmen in all he expe imen s. Fig. 7 quan i ies he es ima ion e o in oduced by sam- ple p uning, in he case o he Aho-Co asick benchma k. This benchma k is ep esen a i e o ou esul s, since we obse ed simila beha iou o all benchma ks unde s udy. The igu e plo s he poin es ima e and con idence bounds o he baseline POT algo i hm, wi h no sample p uning, and o he SP-POT algo i hm a mul iple p uning le els. The algo i hm and p uning le els a e indica ed on he x-axis. When 50% o 75% o he h ead assignmen s wi h p edic ed low/mid pe o mance we e disca ded om he analysis, he op imal pe o mance es ima e ma ched he es ima ion o he baseline POT algo i hm. A he 90% p uning le el, i.e. in he expe imen in which only 10% o he gene a ed andom h ead assignmen we e execu ed on he ha dwa e pla o m, he e o in oduced by sample p uning is s ill negligible. The e o o he poin es ima ion is 2,100 packe s pe second (PPS) o 0.05%. The e o o he es ima ed con idence bound wid h is 6,700 PPS, which co esponds o 0.16% o he poin es ima e. Finally, we compa e he ime needed o he o e all s a is ical analysis wi h and wi hou sample p uning. Gen- e a ing 5,000 andom h ead assignmen s equi ed less 9 han a minu e. Execu ing he h ead assignmen s, o he Aho-Co asick benchma k on he Ul aSPARC T2 p ocesso , equi ed a ound wo hou s. Finally, he POT analysis is done in app oxima ely wo minu es. The o e all analysis o he Aho-Co asick benchma k wi hou any sample p uning he e o e equi ed app oxima ely 2 hou s and 3 minu es. Sample p uning did no a ec he ime needed o gene a e he andom h ead assignmen s, no did i a ec he ime o he POT s a is ical analysis. The SP-POT algo i hm equi es an addi ional s ep: p edic ion o he pe o mance o each andomly-gene a ed h ead assignmen . In ou expe imen s, he BlackBox schedule p edic ed he pe o mance o all 5,000 h ead assignmen s in abou wo seconds. This ime was oughly he same o all benchma ks unde s udy. On he o he hand, he ime equi ed o un he andom h ead assignmen s was oughly p opo ional o he numbe o h ead assignmen s execu ed, so i educed signi ican ly. Fo example, o he Aho-Co asick benchma k a he 90% p un- ing le el, all expe imen s on he Ul aSPARC T2 p ocesso we e execu ed in less han 12 minu es. The o e all analysis ime using he SP-POT me hod a he 90% sample p uning le el was he e o e a ound 15 minu es, eigh imes as e han he baseline POT me hod. The analysis ime o a gi en benchma k depends on how long i akes o execu e on he a ge ha dwa e pla - o m. Ne e heless, all benchma ks unde s udy ga e esul s compa able wi h hose p esen ed o Aho-Co asick. To summa ize, he p esen ed case s udy showed ha sample p uning is a p omising way o signi ican ly educe he ime equi ed o apply he POT me hod o he h ead as- signmen p oblem. We showed ha e en agg essi e p uning a he 90% p uning le el in oduced a negligible es ima ion e o . In his case, applying he sample p uning echnique o he Aho-Co asick benchma k educed he o e all analysis ime om mo e han 2 hou s o 15 minu es. 5.4 Excessi e p uning Since a mos 5% o he bes -pe o ming h ead assignmen s a e i ed o he GPD, one may conside a mo e agg essi e le el o p uning, by execu ing jus 5% o he h ead assignmen s on he a ge pla o m. This app oach, howe e , did no p o ide a good op imal pe o mance es ima e. The main eason o his was he p edic ion e o o he BlackBox schedule . The BlackBox schedule is a simpli ied model, so, like all pe o mance p edic o s, i is subjec o e o . The e o e, some o 5% o he p edic ed bes -pe o ming h ead assignmen s we e no wi hin he ac ual bes -pe o ming ones. The pe o mance p edic ion e o o he BlackBox schedule signi ican ly al e ed he shape o he da ase s used by he POT s a is ical me hod. The SP-POT me hod a he 5% le el ailed o p oduce a pe o mance es ima e, o all benchma ks unde s udy. In gene al, i is impo an o no e ha he accu acy o SP- POT depends on he accu acy o he pe o mance p edic o . E alua ion o mul iple pe o mance p edic o s and hei sui abili y o sample p uning is an in e es ing a enue o u u e wo k. 6 RANDOM SAMPLING APPROACH TO THREAD ASSIGNMENT In his sec ion, we analyze whe he a good h ead assign- men can be ound by aking he bes h ead assignmen om he andom sample. This app oach is especially use ul i a heu is ic-based algo i hm is no a ailable o he use ’s p oblem. Fi s , we compu e he p obabili y ha a andom sample o n h ead assignmen s cap u es a leas one o he p% o he bes -pe o ming assignmen s, whe e pis be ween 0 and 100. We hen e alua e he andom sampling app oach by compa ing i s pe o mance wi h he es ima e o he op imal h ead assignmen p oduced by he s a is ical echniques. 6.1 P obabili y ha andom sampling de ec s a good h ead assignmen The p obabili y ha a sample o andom assignmen s selec ed om a as popula ion con ains he assignmen wi h he op imal pe o mance is low. Howe e , i is no clea wha he p obabili y is ha a sample o andom assignmen s con ains a leas one o he assignmen s wi h agood pe o mance. Assume ha e en Ais he p obabili y ha a sample con ains a leas one h ead assignmen om he p%o bes -pe o ming assignmen s. E en A0is he opposi e o e en A, ep esen ing he p obabili y ha he andom sample con ains ze o h ead assignmen s om p%o he bes -pe o ming assignmen s. I he numbe o possible h ead assignmen s is la ge (i.e. he popula ion is la ge), he p obabili y ha a single assignmen is in he lowe (100 −p)% o he popula ion is 100−p 100 . We assume ha he sample is selec ed om a ini e popula ion o all h ead assignmen s using sampling wi h eplacemen . Sampling wi h eplacemen means ha a any d aw, all assignmen s in he popula ion a e gi en an equal chance o being d awn, no ma e how o en hey ha e al eady been d awn [14]. In addi ion o his, we assume ha he selec ed h ead assignmen s in he sample a e mu ually independen and uni o mly dis ibu ed. Taking in o accoun hese assump- ions, he p obabili y ha all nassignmen s in he sample a e con ained in he lowe (100 −p)% o he popula ion is compu ed as: P(A0)=(100−p 100 )n. As Aand A0a e opposi e e en s, he sum o p obabili ies ha hey occu is equal o 1, since P(A) + P(A0) = 1. The e o e, he p obabili y o he e en Acan be compu ed as: P(A)=1−P(A0)=1−100 −p 100 n We obse e ha he p obabili y ha a sample o andom h ead assignmen s con ains a leas one o he p%o he bes -pe o ming assignmen is independen o he popula- ion size (i.e. he numbe o possible h ead assignmen s). Howe e , we ha e o be awa e ha his is alid only o la ge popula ions wi h uni o m sampling, which is sa is ied in he case o h ead scheduling p oblems in s a e-o - he-a mul i h eaded p ocesso s [44]. Fig. 8 plo s he p obabili y P(A) o he samples o di e en size and o di e en pe cen ages o he