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