TaskPoin : Sampled Simula ion o
Task-Based P og ams
Thomas G ass∗†, Alejand o Rico‡, Ma c Casas†, Miquel Mo e o∗†, Edua d Ayguad´
e∗†
∗Uni e si a Poli `
ecnica de Ca alunya, †Ba celona Supe compu ing Cen e , ‡ARM Inc.
Abs ac —Sampled simula ion is a ma u e echnique o e-
ducing simula ion ime o single- h eaded p og ams, bu i is no
di ec ly applicable o simula ion o mul i- h eaded a chi ec u es.
Recen mul i- h eaded sampling echniques assume ha he
wo kload assigned o each h ead does no change ac oss mul iple
execu ions o a p og am. This assump ion does no hold o
dynamically scheduled ask-based p og amming models. Task-
based p og amming models allow he p og amme o speci y
p og am segmen s as asks which a e ins an ia ed many imes
and scheduled dynamically o a ailable h eads. Due o sys em
noise and a ia ion in scheduling decisions, wo consecu i e
execu ions on he same machine ypically esul in di e en
ins uc ion s eams p ocessed by each h ead.
In his pape , we p opose TaskPoin , a sampled simula ion
echnique o dynamically scheduled ask-based p og ams. We
le e age ask ins ances as sampling uni s and simula e only
a ac ion o all ask ins ances in de ail. Be ween de ailed
simula ion in e als we employ a no el as - o wa d mechanism
o dynamically scheduled p og ams. We e alua e he p oposed
echnique on a se o 19 ask-based pa allel benchma ks and
wo di e en a chi ec u es. Compa ed o de ailed simula ion,
TaskPoin accele a es a chi ec u al simula ion wi h 64 simula ed
h eads by an a e age ac o o 19.1 a an a e age e o o 1.8%
and a maximum e o o 15.0%.
I. INTRODUCTION
Compu e a chi ec u e esea ch hea ily elies on simula ion.
Inc easing design complexi y and inc easing co e coun s in
mode n mul i-co e p ocesso s p esen new challenges o a chi-
ec u al simula ion. Fi s , simula ing a mo e complex design
equi es mo e ime o a gi en wo kload. Second, he mo e
complex a design, he la ge he simula ed wo kload needs o
be in o de o meaning ully s ess he design.
One echnique o educe simula ion ime is sampling. Sam-
pled simula ion educes simula ion ime by only simula ing
a ac ion o a wo kload. Sampling is a well-es ablished
echnique o simula ion o single- h eaded a chi ec u es. The
p e alen echniques pe o m de ailed simula ion o ei he only
he ep esen a i e p og am pa s iden i ied in p o iling [1] o
pe iodically ia ime-based sampling [2].
While sampled simula ion is a well-es ablished echnique
o single- h eaded a chi ec u es, echniques a ge ing mul i-
h eaded a chi ec u es ha e only been ecen ly p oposed. The
main challenge in sampling mul i- h eaded simula ions is o
ensu e ha a he beginning o each de ailed simula ion in e al
all h eads ha e made he same amoun o p og ess as in a
ull de ailed simula ion. A echnique p oposed by Ca lson e
al. [3] achie es his by selec ing a pe iodic sampling in e al
du ing o line p o iling and, du ing simula ion, es ima ing he
a e a which o as - o wa d each h ead be ween in e als o
de ailed simula ion. Ca lson e al. [4] also p opose a echnique
based on he insigh ha a e a global ba ie all h eads
a e synch onized and esume execu ion simul aneously. The
echnique le e ages he in e -ba ie egions in ba ie syn-
ch onized p og ams as sampling uni s.
Task-based p og amming models ha e been p oposed o
educe load imbalance and hus inc ease pa allel e iciency
o u u e la ge-scale mul i-co e machines [5]. A ask-based
p og amming model allows he p og amme o speci y p o-
g am pa s as asks and o speci y dependencies be ween
hose asks. Tasks a e ypically ins an ia ed many imes du ing
he execu ion o a p og am. O e -decomposi ion ensu es ha
he e a e many mo e ask ins ances han he e a e execu ion
h eads. The o e -decomposi ion o a pa allel p og am in o
asks, oge he wi h dynamic scheduling o ask ins ances o
h eads, dynamically balances he amoun o wo k assigned o
each h ead. In e - ask dependencies en o ce synch oniza ion
only when necessa y. The lack o global ba ie s and he
dynamically scheduled execu ion o ask-based p og ams make
hem unsui able o exis ing sampled simula ion echniques.
In his wo k we p esen TaskPoin , a sampled simula ion
me hodology o dynamically scheduled ask-based p og ams
execu ed on sha ed memo y mul i-co e machines. TaskPoin
le e ages ask ins ances as sampling uni s and only simula es
a small numbe o hem in de ail. The emaining ask ins ances
a e simula ed in a as e simula ion mode, ensu ing ha
p og ess in di e en h eads is modelled co ec ly.
In his pape , we make he ollowing con ibu ions:
•We compa e he pe o mance a ia ion o ask-based
p og ams in na i e execu ion and a chi ec u al simula ion.
This mo i a es he design o ou TaskPoin me hodology,
i s sampling policies and i s as - o wa ding me hodology.
•We p esen TaskPoin , a sampled simula ion echnique
o mul i-co e a chi ec u es p og ammed wi h a dynami-
cally scheduled, ask-based p og amming model. In his
con ex , we in oduce wo sampling policies, pe iodic
sampling and lazy sampling. Lazy sampling simula es
ask ins ances in de ail based on hei ype while pe iodic
sampling conside s hei ype and dis ibu ion o e ime.
•We p opose a mechanism o accu a ely as - o wa d an
a chi ec u al simula ion o a ask-based p og am. Du ing
as - o wa d, we model he pe o mance o a gi en ask
ins ance based on p e ious ins ances o he same ask
ype. We accoun o di e en ask inpu sizes ac oss
he applica ion execu ion by ac o ing in he numbe o
ins uc ions o he gi en ask ins ance acco dingly.
© 2016 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any
cu en o u u e media, including ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses,c ea ing
new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse o any copy igh ed componen o his wo k in
o he wo ks.
2dcon olu ion
3ds encil
a omicmon eca lo
dynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
20
15
10
5
0
5
10
15
20
IPC a ia ion[%]
28
24
Fig. 1: IPC a ia ion ac oss all ask ins ances o na i e execu ion wi h 8 h eads, no malized pe ask ype
•We e alua e TaskPoin simula ing 19 ask-based pa al-
lel benchma ks, including 6 ask-based e sions o he
PARSEC benchma k sui e. We e alua e he sensi i i y o
TaskPoin o di e en a chi ec u es by es ing di e en
numbe s o simula ed h eads on wo di e en con igu-
a ions co e ing he opposi e ex emes o he mul i-co e
design space: high-pe o mance and low powe .
The emainde o his pape is o ganized as ollows. In
Sec ion II, we p o ide backg ound and mo i a ion o ou
wo k. In Sec ion III, we p esen ou TaskPoin me hodology.
Nex , we in oduce ou expe imen al se up in Sec ion IV. We
e alua e TaskPoin in Sec ion V. Finally, we p esen ela ed
wo k in Sec ion VI, be o e we conclude in Sec ion VII.
II. BACKGROUND AND MOTIVATION
This sec ion p o ides backg ound on ask-based p og am-
ming models. We hen mo i a e ou wo k wi h an analysis
o pe o mance a ia ion in na i e execu ion o 19 ask-based
pa allel benchma ks.
A. Pa allel P og amming Models
In adi ional pa allel p og amming models o sha ed mem-
o y sys ems, like POSIX Th eads [6], he p og amme ex-
plici ly decomposes an applica ion in o concu en ins uc ion
s eams and manages synch oniza ion be ween hose. These
ins uc ion s eams a e p ocessed simul aneously by di e en
h eads. A common p oblem wi h mul i- h eaded p og ams is
load imbalance. Load imbalance occu s when di e en h eads
each a synch oniza ion poin a di e en poin s in ime.
Task-based p og amming models ha e he po en ial o al-
le ia e load imbalance and hus inc ease pa allel e iciency.
When implemen ing a pa allel p og am using a ask-based p o-
g amming model, he p og amme speci ies p og am pa s as
asks and, op ionally, da a dependencies be ween hese asks.
Tasks a e ins an ia ed many imes du ing he execu ion o a
p og am, esul ing in a la ge numbe o ask ins ances, each
o which ope a es on di e en da a. A un ime en i onmen
dynamically schedules ask ins ances o execu ion h eads.
Due o a ine-g ained o e -decomposi ion o he applica ion,
he e a e ideally mo e ask ins ances eady o execu ion han
he e a e h eads. This allows he un ime en i onmen o
dynamically balance he wo kload assigned o each h ead [5].
Fu he op imiza ions a e possible i he a chi ec u e in e aces
di ec ly wi h he un ime en i onmen [7, 8].
In his wo k, we di e en ia e be ween ask ypes and ask
ins ances. E e y execu ion o a ask decla a ion s a emen a
un ime esul s in he c ea ion o a ask ins ance. All ask
ins ances esul ing om he same ask decla a ion s a emen in
he sou ce code a e said o be o he same ask ype. In a ypical
ask-based p og am, he numbe o ask ypes is small, whe eas
he numbe o ask ins ances lies in he o de o housands.
B. Pe o mance Va ia ion o Task-Based P og ams
In o de o mo i a e TaskPoin , ou sampled simula ion
echnique o ask-based pa allel p og ams, we analyze pe -
o mance a ia ion in na i e execu ion o 19 benchma ks. The
in es iga ed benchma ks a e in oduced in Sec ion IV.
Di e en benchma ks, and e en di e en ask ypes o he
same benchma k, gene ally show di e en a e age ins uc ions
pe cycle (IPC). Fo an easy compa ison o pe o mance
a ia ion ac oss benchma ks, we no malize he IPC o all ask
ins ances o he a e age IPC o hei espec i e ask ype. Fo
each benchma k, we use one box plo o hese no malized IPC
alues o isualize pe o mance a ia ion ac oss ask ins ances.
Figu e 1 shows IPC a ia ion ac oss ask ins ances obse ed
in a na i e execu ion wi h 8 h eads on a sys em wi h an
In el SandyB idge-EP E5-2670 CPU unning a 2.6 GHz and
128 GB o DDR3-1600 as main memo y. The solid box o
each box plo indica es he ange om he i s o he hi d
qua ile o he no malized IPC alues, while he whiske s
ex end om he i h o he 95 h pe cen ile. IPC alues o
ask ins ances below he i h and abo e he 95 h pe cen ile
a e ea ed as ou lie s. The Figu e shows ha o 15 ou o 19
benchma ks pe o mance a ia ion lies wi hin ±5%. We show
ha pe o mance a ia ion is closely e lec ed in simula ion
when we in oduce he TaskSim simula o in Sec ion IV.
We mo i a e TaskPoin based on he insigh ha pe o -
mance o ask-based p og ams is gene ally egula ac oss
ins ances o he same ask ype. A no el y o TaskPoin is ha
i le e ages he concep o asks decla ed by he p og amme
o iden i y ask ins ances o he same ask ype as sampling
uni s o simila pe o mance.
III. SAMPLED SIMULATION OF TASK-BASED PROGRAMS
In his sec ion, we p esen ou TaskPoin me hodology. Fi s ,
we in oduce he p e equisi es which need o be ul illed by
an a chi ec u al simula o in o de o se e as an implemen a-
ion pla o m o TaskPoin . Nex , we p esen he di e en
2
A1
Th ead 1
Th ead 2
Time
B1
...
wa mup
...
1 2 3 4
A2B2
A3B3
A4B4
A5
A6
B5
B6
A7
An-1
Bn
Bn+1
... An
An+1 Bn+3
An+2 Bn+4
An+3 Bn+5
5
An+4
An+5
Bn+6
Bn+7
An+6 ...
measu e sample as - o wa d wa mup measu e sample
0
Bn+2
de ailed
simula ion
as - o wa d
Xi
i- h ins ance
o ask- ype X
Fig. 2: Ini ial wa mup, sampling, as - o wa ding and esampling in TaskPoin
phases o TaskPoin ’s sampling mechanism, namely wa m-
up, sampling and as - o wa ding. A e wa ds, we in oduce
ou pe iodic sampling policy. The sepa a ion in o sampling
mechanism and policy allows o he in eg a ion o o he
sampling policies wi h low implemen a ion e o .
A. Requi emen s o he A chi ec u al Simula o
Ou objec i e is o p o ide a sampled simula ion me hod-
ology o ask-based p og ams which does no depend on
a speci ic a chi ec u al simula o . The e o e, we keep he
equi emen s o he a ge simula o o a minimum. In o de
o se e as a sui able pla o m o implemen ing ou me hodol-
ogy, a simula o needs o ul il he ollowing wo equi emen s:
1) The simula o needs o ea u e a de ailed and a as
simula ion mode.
2) The as mode has o be capable o ope a ing a a use -
speci ied IPC.
Mos con empo a y a chi ec u al simula o s ea u e se e al
le els o de ail [9, 10, 11], allowing o ade o speed o
accu acy. Thus, we assume he i s equi emen o be i ially
ul illed. Rega ding he second equi emen , i a simula o does
no suppo ixed-IPC simula ion by de aul , we conside he
implemen a ion o his unc ionali y o be a mino e o .
B. Sampling Mechanism
TaskPoin ope a es on he le el o g anula i y o ask
ins ances. A ask ins ance is simula ed ei he in de ailed o
in as mode. Simula ion in de ailed mode se es o wa ming
a chi ec u al s a e o o measu e samples, whe eas simula ion
in as mode accu a ely as - o wa ds simula ion ime. Swi ch-
ing be ween de ailed and as mode only occu s be ween wo
consecu i e ask ins ances.
Figu e 2 illus a es he di e en phases o TaskPoin . Fo
each ask ype, we main ain wo ec o s holding he IPC
his o ies o he mos ecen ly simula ed ask ins ances. The
size Ho hese ec o s is a pa ame e e e ed o as he his o y
size. Bo h ec o s a e FIFO bu e s in which a newly added
elemen eplaces he oldes one. The i s ec o con ains he
his o y o ask ins ances which a e alid samples, i.e. which
a e simula ed a e wa ming up a chi ec u al s a e. We e e
o i as he his o y o alid samples. The second ec o holds
he his o y o all ask ins ances simula ed in de ailed mode,
ega dless o he simula ion being p ope ly wa med. We e e
o i as he his o y o all samples. While he o me is he
sample his o y we usually use o de e mine which IPC o use
in as mode, he la e is needed i he e a e ask ypes ha
occu in equen ly and can no be sampled in a single sampling
in e al. We e e o hese ask ypes as a e ask ypes.
In mul i- h eaded applica ions, co-exis ing h eads in e e e
wi h each o he , e.g. by compe ing o sha ed esou ces,
h ough in e - h ead synch oniza ion o by in alida ing da a
esiding in emo e caches. In o de o co ec ly model h ead
in e e ence, we simula e all h eads ei he in de ailed mode
o in as mode. Since we assume ha mode swi ching only
occu s be ween wo consecu i e ask ins ances, he e a e sho
phases du ing which some h eads a e simula ed in as -
o wa d mode, while o he s a e simula ed in de ailed mode
(see 2, 3and 5in Figu e 2).
Simula ion Wa mup:Be o e conduc ing pe o mance mea-
su emen s, a simula ion needs o be wa med, i.e. i needs o be
pu in a ep esen a i e s a e. Wa ming mic o-a chi ec u al s a e
in sampled simula ion is well-s udied [1, 2, 12, 13, 14, 15]. In
his pape , we wa m he simula ion by simula ing an empi i-
cally de e mined numbe o ask ins ances in de ail and a oid
complex wa mup schemes. Ins ead, we ocus on he sampling
me hodology i sel . Howe e , we dis inguish be ween wa ming
a simula ion s a and wa ming be o e esampling a e a
simula ion phase in as mode. When a ask ins ance simula ed
o wa mup inishes execu ion, i s IPC is added o he his o y
o all samples.
A simula ion s a , all simula ed mic o-a chi ec u al s uc-
u es a e in hei ini ial (cold) s a e. Du ing de ailed simula ion,
s a e-holding elemen s begin o ill un il occupancy eaches a
s eady s a e. In his wo k, we assume ha simula ing W ask
ins ances pe h ead a simula ion s a is su icien o pu ing
he simula o in o a ep esen a i e (wa m) s a e. We e e o
Was he size o he wa m-up in e al and e alua e di e en
alues o Win Sec ion V.
A e a simula ion phase in as mode, mic o-a chi ec u al
s a e is s ale. Be o e esampling he simula ion, wa mup makes
su e ha mic o-a chi ec u al s a e is (app oxima ely) he same
as i he whole p og am was simula ed in de ail. Be o e
esampling, we pe o m de ailed simula ion un il e e y h ead
has simula ed one ask ins ance in de ail.
Sampling:Like simula ion wa mup, sampling is pe o med
in de ailed simula ion mode. When wa mup is inished, we
s a ea ing he simula ed ask ins ances as alid samples.
When a alid sample ask ins ance inishes simula ion, i s
a e age IPC is added o he his o y o alid samples and o he
his o y o all samples. We igge he ansi ion o as mode
when one o he ollowing wo condi ions is ul illed:
1) The his o y o alid samples is ully popula ed.
3
Th ead 1
Th ead 2
Time
Time
1
1
2
2
P-1
P-1
P
P
1
1
2
2
... ... ...
...
...
Th ead 1
Th ead 2
1
1
2
2
P-1
P-1
P
P
sampling
as - o wa d
(a) Pe iodic sampling
(b) Lazy sampling
wa mup
Fig. 3: Illus a ion o pe iodic sampling (a) and lazy sampling (b) as a special case o pe iodic sampling wi h in ini e sampling
pe iod P
2) A ce ain numbe o ask ins ances has been simula ed
wi hou encoun e ing any ins ance o a a e ask ype
whose his o y o alid samples is no ye ully popula ed.
The i s condi ion means ha all ask ypes a e ully sampled.
The second condi ion is needed o a oid spending an excessi e
amoun o ime on de ailed simula ion in he p esence o
a e ask ypes. In his pape , we cu o sampling when all
h eads ha e simula ed 5 ask ins ances wi hou encoun e ing
an ins ance o a p e iously obse ed a e ask ype.
Accu a e Fas -Fo wa ding:When he ansi ion o as
mode is igge ed, all ask ins ances s a ing in he u u e a e
simula ed in as mode. Howe e , ask ins ances which s a ed
in he pas a e simula ed in de ailed mode un il hey comple e.
Task ins ances inishing simula ion a e he ansi ion o as
mode a e only added o he his o y o all samples.
A ask ins ance simula ed in as mode is simula ed wi h he
a e age IPC o he his o y o alid samples o i s ask ype.
I a ask ins ance belongs o a a e ask ype whose his o y o
alid samples is emp y, we use he a e age IPC o he his o y
o all samples ins ead. I he his o y o all samples o he
co esponding ask ype is also emp y, we igge esampling.
Ra e ask ypes end o occu in equen ly du ing he
execu ion o an applica ion. They accoun only o a small
pe cen age o he o al ins uc ion coun o an applica ion
and a e used o in equen asks, e.g. se ing up and dele ing
da a s uc u es. We ind he impac o using non- ep esen a i e
samples o as simula ion o a e ask ypes o be negligible.
One con ibu ion o his pape is he p esen ed as -
o wa ding mechanism o a chi ec u al simula ion o ask-
based pa allel p og ams. Ou echnique as - o wa ds each
h ead a a a e depending on he ask ype o he ask ins ance
cu en ly being simula ed.
C. Pe iodic Sampling Policy
A sampling policy decides when o esample a simula ion
unning in as - o wa d mode. The pe iodic sampling policy,
illus a ed in Figu e 3a, wa ms and samples a simula ion a
simula ion s a . A e wa ds, i swi ches he simula ion o as -
o wa d mode. When a h ead has execu ed a numbe Po ask
ins ances o any ask ype in as - o wa d mode, he simula ion
is esampled. We e e o he pa ame e Pas he sampling
pe iod. When a simula ion is esampled, he en ies o he
his o y o alid samples a e disca ded. When esampling is
comple e, he simula ion e u ns o as - o wa d mode and he
p ocess epea s.
Th ead 1
Th ead 2
Time
...
Th ead 3
Th ead 4
...
Task ype B Task ype A
(a) Change in numbe o execu ion h eads a ime , hus al e ing a e age
pe o mance due o esou ce con en ion
Th ead 1
Th ead 2
Time
...
Th ead 3
Th ead 4
...
(b) Ins ance o a e ask ype s a ing execu ion a ime
Fig. 4: Illus a ion o changing numbe o execu ion h eads
(a) and a e ask ype (b)
Simula ion speedup is de e mined by he size o he sam-
pling pe iod. The la ge he sampling pe iod, he mo e ask
ins ances a e simula ed in as mode. In he special case o
an in ini e sampling pe iod, esampling is ne e igge ed by
he sampling policy. We e e o his case as lazy sampling.
Lazy sampling is illus a ed in Figu e 3b. I he numbe o ask
ins ances o a p og am is oo small o he sampling pe iod is
oo la ge, a simula ion inishes du ing he i s as - o wa d
in e al, be o e any h ead has simula ed P ask ins ances. In
his case, pe iodic sampling is equi alen o lazy sampling.
Besides he a o emen ioned case o a h ead ha ing sim-
ula ed P ask ins ances in as mode, esampling is also
igge ed when i is impossible o accu a ely simula e a ask
ins ance in as mode. This happens in he ollowing wo cases.
Figu e 4a shows a case whe e he numbe o h eads
pa icipa ing in ask execu ion changes a un ime, e.g. when
he simula ed applica ion en e s a phase exposing mo e pa -
allelism. When he numbe o execu ion h eads changes, so
does he con en ion on sha ed esou ces, like sha ed caches
and main memo y. This a ec s pe - h ead pe o mance and
in alida es p e iously measu ed samples. Resampling a oids
p edic ion e o s due o non- ep esen a i e samples.
Figu e 4b shows a case whe e he i s ins ance o a
new ask ype is encoun e ed while simula ing in as mode.
When encoun e ing an ins ance o a p e iously unknown ask
ype, he ask ype’s sample his o y is emp y. The e o e, i
is impossible o simula e his ask ins ance in as mode. We
ci cum en his p oblem by igge ing esampling.
4
Wi h his esampling s a egy, bo h pe iodic sampling and
lazy sampling accoun o phase changes in he applica ion.
I a new phase is implemen ed wi h di e en ask ypes, he
simula ion is esampled. The same holds o changes in he
a ailable compu a ion esou ces o he a ailable pa allelism.
IV. EXPERIMENTAL SETUP
In his sec ion, we in oduce he expe imen al se up we
use o implemen and e alua e TaskPoin . Fi s , we in oduce
he ask-based p og amming model OmpSs. Subsequen ly, we
p esen he 19 benchma ks and he wo a chi ec u es we use in
ou e alua ion. Finally, we elabo a e on he TaskSim simula o
and ou implemen a ion o as simula ion a a bi a y IPC
and show an analysis o pe o mance a ia ion obse ed in
simula ion o ask-based p og ams.
The OmpSs P og amming Model:Fo ou e alua ions we
choose he OmpSs p og amming model [16]. The OmpSs com-
pile and un ime en i onmen a e a ailable as open sou ce.
OmpSs allows o decla e asks and anno a e hem wi h da a
inpu s and ou pu s. Using his in o ma ion, he OmpSs un ime
sys em schedules ask ins ances aking da a dependencies in o
accoun and pe o ms synch oniza ion only when necessa y.
These OmpSs ea u es we e included in o he speci ica ions
o OpenMP 3.0 and 4.0.
Benchma ks:Table I lis s he benchma ks used in ou
e alua ion. They ep esen a a ie y o wo kloads and a e
implemen ed using he OmpSs p og amming model. While he
majo i y o benchma ks ep esen wo kloads common o high-
pe o mance compu ing (HPC), blackscholes,body ack,can-
neal,dedup, eqmine and swap ions a e pa o he PARSEC
benchma k sui e [17]. Whene e possible, we gene a ed aces
equi alen o a leas en seconds o single- h eaded execu ion
on a s a e-o - he-a machine. Fo he PARSEC benchma ks we
used he simla ge inpu se s. Table I lis s he numbe o ask
ins ances and he ime equi ed o a de ailed simula ion o
he en i e benchma k o 1 and 64 execu ion h eads using he
TaskSim simula o . TaskSim is in oduced la e in his sec ion.
Simula ed A chi ec u es:We e alua e he ideli y o ou
me hodology by in es iga ing simula ion speedup and execu-
ion ime e o o mul i- h eaded simula ions o wo adically
di e en mul i-co e a chi ec u es. One esembles a se e -
class sys em, while he o he esembles a low-powe mobile
pla o m. Table II lis s he key cha ac e is ics o he simula ed
a chi ec u es. The high pe o mance a chi ec u e ea u es a
la ge eo de bu e and a h ee-le el cache hie a chy, as ound
in HPC sys ems. The low-powe a chi ec u e has a smalle
eo de bu e and wo le els o cache memo ies, as is ypical
o ba e y powe ed mobile sys ems. Recen ly, low-powe
sys ems a e gaining in e es o applica ions in HPC [18].
The TaskSim Simula o :We e alua e ou me hodology
using he TaskSim simula o [19, 20]. TaskSim is a cycle-
accu a e, ace-d i en pe o mance simula o o mul i-co e
a chi ec u es. I in e aces wi h an unmodi ied e sion o he
OmpSs un ime sys em. The un ime sys em schedules he ask
ins ances o he simula ed applica ion o execu ion on he
simula ed p ocesso co es.
TaskSim has a de ailed and a as simula ion mode. The
de ailed mode is based on he Reo de -Bu e Occupancy
Analysis model p oposed by Lee e al. [21]. When unning in
de ailed mode, TaskSim models a use -de ined memo y hie a -
chy including p i a e and sha ed cache memo ies, in e connec
s uc u es and DRAM.
In he as mode, called bu s mode, TaskSim only accoun s
o he numbe o CPU cycles be ween e en s, in ou case
be ween he beginning and he end o he execu ion o a
ask ins ance. In he exis ing implemen a ion, TaskSim eads
a ask ins ance’s cycle coun om he applica ion ace. In he
implemen a ion o ou as - o wa d mechanism, he du a ion o
a ask ins ance is calcula ed a he beginning o i s execu ion.
Using he mean IPC o he sample his o y o a ask ins ance i’s
ask ype Tand i s dynamic ins uc ion coun Ii, we es ima e
i s numbe o execu ion cycles Ciacco ding o Ci=Ii
IP CT
.
The esul is he numbe o cycles i akes o execu e he ask
ins ance a an IPC o IP CT, he a e age IPC o he ins ance’s
ask ype. The dynamic ins uc ion coun is ead om he
applica ion ace.
In he scope o his wo k, we ex ended TaskSim wi h he
capabili y o swi ch be ween de ailed and as - o wa d mode
a un ime. We also ex ended i s as simula ion mode. Ins ead
o using p e iously eco ded cycle coun s om a ace, ou
implemen a ion o as mode uses cycle coun s p edic ed by
ou as - o wa d mechanism. To he bes o ou knowledge,
his is he i s as - o wa d mechanism applying di e en IPCs
o di e en pa s o a p og am. Ou mechanism allows as -
o wa ding dynamically scheduled pa allel p og ams in which
he pe - h ead ins uc ion s eam is a-p io i unknown. Nex ,
we e alua e pe o mance a ia ion o ask-based p og ams
obse ed in simula ion wi h TaskSim.
Figu e 5 shows IPC a ia ion ac oss ask ins ances in an
a chi ec u al simula ion wi h 8 execu ion h eads. The pa am-
e e s o he simula ed a chi ec u e ma ch he machine used
o na i e execu ion, as a as hey a e publicly a ailable.
All benchma ks showing a pe o mance a ia ion o less
hen ±5% in na i e execu ion (see Figu e 1) also do so
in simula ion. Con e sely, h ee ou o he ou benchma ks
showing a a ia ion la ge han ±5% in na i e execu ion also
do so in simula ion. The excep ion is spa se-ma ix- ec o -
mul iplica ion, which in na i e execu ion exhibi s a a ia ion
o nea ly ±10%, compa ed o less han ±5% in simula ion.
The h ee benchma ks wi h he la ges deg ee o pe o mance
a ia ion in na i e execu ion, namely checkSpa seLU,dedup
and eqmine, also show he la ges a ia ion in simula ion.
Due o modelling inaccu acies in TaskSim’s de ailed simu-
la ion mode, he magni udes o pe o mance a ia ion in na i e
execu ion and simula ion do no ma ch exac ly. Howe e , o
18 ou o 19 benchma ks we co ec ly iden i y i a benchma k
exposes a pe o mance a ia ion o mo e o less han 5%.
V. EVALUATION
In his sec ion, we conduc a sensi i i y analysis o Task-
Poin ’s model pa ame e s. Then, we e alua e execu ion ime
e o and simula ion speedup o pe iodic sampling and lazy
5

TABLE I: Task-based pa allel benchma ks used o he e alua ion o TaskPoin
Benchma k # Task # Task Simula ion ime [h:min]P ope ies
Types Ins ances 1 Th ead 64 Th eads
2d-con olu ion 1 16384 31:37 59:34 Ke nel: s ided memo y accesses
3d-s encil 1 16370 9:12 40:51 Ke nel: s ided memo y accesses
a omic-mon e-ca lo-dynamics 1 16384 8:38 15:16 Ke nel: emba assingly pa allel
dense-ma ix-mul iplica ion 1 17576 70:14 127:10 Ke nel: high da a euse, compu e bound
his og am 1 16384 6:02 12:13 Ke nel: a omic ope a ions
n-body 2 25000 8:15 12:31 Ke nel: i egula memo y accesses
educ ion 2 16384 1:51 5:15 Ke nel: pa allelism dec eases o e ime
spa se-ma ix- ec o -mul iplica ion 1 1024 0:33 1:26 Ke nel: load imbalance, memo y bound
ec o -ope a ion 1 16400 24:25 191:00 Ke nel: egula , memo y bound
checkSpa seLU 11 22058 7:25 17:17 Decomposi ion o la ge, spa se ma ices
cholesky 4 19600 33:42 59:29 Decomposi ion o He mi ian posi i e-de ini e ma ices
kmeans 6 16337 75:21 141:02 Clus e ing based on Lloyd’s algo i hm
knn 2 18400 31:28 65:27 Ins ance-based machine lea ning algo i hm
blackscholes 2 24500 8:42 17:19 Op ion p ice calcula ion
body ack 7 21439 15:24 31:28 Human body acking wi h mul iple came as
canneal 1 16384 11:13 29:38 Cache-awa e simula ed annealing
dedup 4 15738 10:08 23:32 Deduplica ion: combina ion o global and local comp ession
eqmine 7 1932 23:52 34:13 F equen Pa e n G ow h me hod o F equen I em Mining
swap ions 1 16384 29:27 70:25 Mon e-Ca lo simula ion o calcula e swap ion p ices
2dcon olu ion
3ds encil
a omicmon eca lo
dynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
20
15
10
5
0
5
10
15
20
IPC a ia ion[%]
26 39
21
Fig. 5: IPC a ia ion ac oss all ask ins ances o simula ion o high-pe o mance a chi ec u e wi h 8 h eads, no malized pe
ask ype
TABLE II: A chi ec u al pa ame e s o high pe o mance and
mobile con igu a ions used o model alida ion
Pa ame e High-pe . Low-powe
Reo de -bu e size 168 40
Issue wid h 4 3
Commi a e 4 3
Cache line size 64 B 64 B
L1 cache 32 kB p i a e
4 cycles la ency
8-way associa i e
32 kB p i a e
4 cycles la ency
2-way associa i e
L2 cache 2 MB p i a e
11 cycles la ency
8-way associa i e
1 MB sha ed
21 cycles la ency
16-way associa i e
L3 cache 20 MB sha ed
28 cycles la ency
20-way associa i e
none
sampling. Finally, we es he obus ness o ou model by using
he same pa ame e s o simula e a low-powe a chi ec u e.
A. Adjus ing he Model Pa ame e s
We de e mine he op imal model pa ame e s ollowing an
inc emen al app oach. Fi s , we de e mine he op imal numbe
Wo ask ins ances needed o wa mup a simula ion s a .
A e wa ds, we conside di e en numbe s o ask ins ances
Hcons i u ing he sample his o y. Finally, we explo e a ange
o alues o he sampling pe iod P.
In o de o de e mine he op imal alue o Wwe se H=
10 and P=∞and e alua e di e en alues anging om
W= 0 (no wa mup) o W= 10. Figu e 6a shows e o and
speedup, a e aged o e simula ions wi h 32 and 64 h eads.
The epo ed alues a e a e aged o e he benchma ks and
ke nels wi h an e o >5% o a leas one alue o H, namely
2d-con olu ion,3d-s encil,a omic-mon e-ca lo-dynamics,knn
and blackscholes. We ound ha W= 2 yields an a e age
e o o less han 2%. La ge alues o Wdo no signi ican ly
educe he a e age e o , bu hey educe simula ion speedup.
The e o e, o he emainde o his pape , we se W= 2.
Nex , we e alua e di e en alues o H, he size o he
sample his o y. Fo his pu pose, we se P=∞. No e ha
we al eady se W= 2. Figu e 6b shows e o and speedup
o di e en sizes Ho he sample his o y, a e aged o e
simula ions wi h 32 and 64 h eads o he a o emen ioned
benchma ks. We ound ha H= 4 minimizes he a e age
e o . This alue also minimizes he s anda d de ia ion o he
a e age e o , which is no shown in he Figu e. La ge alues
o Hdo no only esul in a la ge a e age e o , bu also in
lowe simula ion speedup. The e o e, o he emainde o his
pape , we se H= 4.
Finally, we explo e di e en sizes o he sampling pe iod P.
Wi h W= 2 and H= 4 al eady ixed, Pis he only emaining
pa ame e . Figu e 6c shows he a e age e o o alues o
P anging om 10 o 1,000. We ind ha a e age e o
6
0 2 4 6 8 10
Numbe 
W
o  askins ances o wa mup
0
2
4
6
8
10
A e agee o [%]
0
50
100
150
200
A e agespeedup
E o
Speedup
(a) E o and speedup o di e en sizes Wo wa mup in e al, a e age o
32 and 64 h eads
1 2 3 4 5 6 7 8 9 10
Size
H
o samplehis o y
0
2
4
6
8
A e agee o [%]
0
10
20
30
40
A e agespeedup
E o
Speedup
(b) E o and speedup o di e en sizes Ho ask ins ance his o y, a e age
o 32 and 64 h eads
101102103
Size
P
o samplingpe iod
0.0
0.5
1.0
1.5
2.0
2.5
A e agee o [%]
0
5
10
15
20
25
A e agespeedup
E o
Speedup
(c) E o and speedup o di e en sizes Po sampling pe iod, a e age o
32 and 64 h eads
Fig. 6: E o and speedup o di e en sizes o wa mup in e al
(a), sample his o y (b) and sampling pe iod (c)
and speedup inc ease wi h he size o he sampling pe iod.
The la ge he alue o P, mo e ask ins ances a e simula ed
in as mode. Since he o al numbe o ask ins ances o
a p og am is cons an , he ac ion o de ailed simula ion
dec eases, esul ing in inc easing speedup. Fo P≥1000
e o and speedup emain cons an . A his poin , none o
he in es iga ed p og ams has a su icien numbe o ask
ins ances o esampling he simula ion a leas once and
pe iodic sampling becomes equi alen o lazy sampling.
We aim o a simula ion e o o less han 1%. A sampling
pe iod P= 250 yields an e o o 0.8% and a simula ion
speedup o 15.1x, a e aged o e he benchma ks used in
ou sensi i i y analysis. In he emainde o his sec ion, we
e alua e TaskPoin o pe iodic sampling wi h P= 250 and
o lazy sampling (pe iodic sampling wi h P=∞).
B. Pe iodic Sampling
Fi s , we e alua e pe iodic sampling, simula ing he high-
pe o mance a chi ec u e in Table II, which we also use o ind
he sampling pa ame e s. A e wa ds, we simula e he low-
powe a chi ec u e using he same sampling pa ame e s.
High-Pe o mance A chi ec u e:Figu e 7 shows execu ion
ime e o and simula ion speedup o all in es iga ed bench-
ma ks, simula ed wi h he pa ame e s W= 2,H= 4 and
P= 250. The a e age execu ion ime e o is less han 2%
o 8, 16, 32 and 64 simula ed h eads. The e o o 1, 2
and 4 simula ed h eads is less han 1% and no shown in he
Figu e. We obse e he la ges simula ion speedup o 76.2 o
spa se-ma ix- ec o -mul iplica ion execu ed wi h 8 h eads.
We obse e he highes e o o 8.9% in he simula ion o
eqmine wi h 8 h eads. F eqmine consis s o 7 di e en ask
ypes, one o which accoun s o 93% o he o al numbe o
dynamic ins uc ions. The dynamic ins uc ion coun o he
ins ances o his ask ype anges om 490 o 11,000,000.
Inspec ing he sou ce code e eals a cons uc o nes ed i -
s a emen s in a ask decla a ion. This causes di e en ins ances
o he same ask ype o ollow comple ely un ela ed con ol
low pa hs. The unbalanced size ac oss ask ins ances makes
sampling he simula ions wi h 32 and 64 h eads ine ec i e.
Since hese con igu a ions a e simula ed almos en i ely in
de ail, he e o is negligible and speedup is close o 1.
F om his inding, we de i e a ecommenda ion o p o-
g amme s o imp o ing pe o mance p edic abili y o ask-
based p og ams: One should a oid la ge-scale con ol low
di e gence among ins ances o he same ask ype. In p ac ice,
his is achie ed by decla ing code pe o ming un ela ed wo k
as di e en ask ypes.
The second la ges e o o 7.3% is shown by dedup o 64
h eads. Dedup consis s o 4 ask ypes, one o which accoun s
o 99.9% o he dynamic ins uc ion coun . The dynamic
ins uc ion coun o he ins ances o his ask ype anges
om 3,500,000 o 25,100,000. The domina ing ask ype
pe o ms de-duplica ion as well as comp ession, which a e
highly inpu dependen ope a ions. P e ious wo k iden i ied
inpu dependence as a sou ce o pe o mance a ia ion [22].
Pe o mance a ia ion makes i di icul o de e mine a ask
ype’s a e age pe o mance du ing sampling.
We ecognize ha , in ce ain cases, inpu dependence can
no be a oided. One way o imp o e he accu acy o sam-
pled simula ion o p og ams showing inpu dependence is o
classi y ask ins ances in o classes o simila pe o mance. We
en ision clus e ing o ins ances o he same ask ype based on
mic o-a chi ec u e independen me ics, e.g. ins uc ion coun
o ins uc ion mix. We lea e his o u u e wo k.
Nex , we e alua e he gene aliza ion capabili y o pe iodic
sampling. We simula e a low-powe a chi ec u e which is
adically di e en om he high-pe o mance a chi ec u e we
used o de e mine he sampling pa ame e s.
Low-Powe A chi ec u e:Figu e 8 shows execu ion ime
e o and simula ion speedup o simula ions o all benchma ks
execu ed on he low-powe a chi ec u e in oduced in Table II
wi h 1, 2, 4 and 8 h eads. We no ice ha , o inc easing
7
0
2
4
6
8
10
Absolu ee o [%]
8 h eads
16 h eads
32 h eads
64 h eads
2dcon olu ion
3ds encil
a omicmon e
ca lodynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
a e age
100
101
102
Speedup
Fig. 7: E o and speedup o pe iodic sampling; high-pe o mance a chi ec u e; P= 250
0
2
4
6
8
10
Absolu ee o [%]
11.0
13.0
1 h ead
2 h eads
4 h eads
8 h eads
2dcon olu ion
3ds encil
a omicmon e
ca lodynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
a e age
100
101
102
Speedup
Fig. 8: E o and speedup o pe iodic sampling; low-powe a chi ec u e; P= 250
h ead coun s, speedup deg ades less han in he case o
he high-pe o mance a chi ec u e. Since we simula e smalle
h ead coun s, he simula ion is esampled mo e o en and he
pe cen age o ask ins ances simula ed in as mode is mo e
simila ac oss di e en h ead coun s.
Wi h an e o o 13.0% o 4 h eads, eqmine is he
benchma k wi h he highes e o . This is consis en wi h he
simula ion o he high-pe o mance a chi ec u e. We a ibu e
his e o o he same eason as in he case o he high-
pe o mance a chi ec u e, namely he highly imbalanced size
o he ins ances o he dominan ask ype.
We obse ed he second la ges e o o 8.4% o spa se-
ma ix- ec o -mul iplica ion wi h 8 h eads. Depending on he
s uc u e o he inpu ma ix, memo y accesses a e mo e o
less egula [23]. We conclude ha , due o he wo-le el cache
hie a chy, he smalle las -le el cache and he lowe memo y
bandwid h, his has a highe impac on pe o mance a ia ion
han in he high-pe o mance a chi ec u e. This is ano he
example o inpu dependence, simila o he case o dedup
explained in he p e ious sec ion.
C. Lazy Sampling
Fo ou e alua ion o lazy sampling, we se W= 2,H= 4
and P=∞. We simula e he benchma ks lis ed in Table I
execu ing on he high pe o mance a chi ec u e and he low-
powe a chi ec u e lis ed in Table II.
High-Pe o mance A chi ec u e:Figu e 9 shows execu-
ion ime e o and simula ion speedup o he lazy sampling
policy o he in es iga ed benchma ks execu ed on he high-
pe o mance a chi ec u e. The a e age e o is less han 2%
o all simula ed h ead coun s (including 1, 2, and 4 h eads,
which a e no shown in he Figu e).
Dedup and eqmine a e s ill he benchma ks showing he
highes e o . Compa ed o pe iodic sampling, he highes
obse ed e o o dedup inc eases om 7.3% o 15.0% o
he simula ion wi h 64 h eads. In he case o eqmine, he
highes obse ed e o inc eases om 8.9% o 9.6% o he
simula ion wi h 8 h eads.
While he a e age e o o lazy sampling is compa able
o he e o o pe iodic sampling, we obse e a signi ican
inc ease o a e age simula ion speedup. Compa ed o pe iodic
sampling, we obse e he la ges inc ease om 44.4 o 178.5
o he a e age speedup o he simula ions wi h 8 h eads. The
smalles gain in speedup is obse ed o he simula ions wi h
64 h eads, in which speedup inc eases om 15.8 o 19.1. Fo
1 h ead, which is no shown in he Figu e, speedup inc eases
om 43.2 o 1019.
Low-Powe A chi ec u e:Figu e 10 shows execu ion ime
e o and simula ion speedup o he low-powe a chi ec u e.
We obse e a ma ginal inc ease o he maximum e o o
spa se-ma ix- ec o -mul iplica ion and eqmine, he bench-
8
0
2
4
6
8
10
Absolu ee o [%]
14.2
15.0
8 h eads
16 h eads
32 h eads
64 h eads
2dcon olu ion
3ds encil
a omicmon e
ca lodynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
a e age
101
102
103
104
Speedup
Fig. 9: E o and speed-up o lazy sampling; high-pe o mance a chi ec u e
0
2
4
6
8
10
Absolu ee o [%]
10.3
11.2
13.1
11.3
1 h ead
2 h eads
4 h eads
8 h eads
2dcon olu ion
3ds encil
a omicmon e
ca lodynamics
densema ix
mul iplica ion
his og am
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
kmeans
knn
blackscholes
body ack
canneal
dedup
eqmine
swap ions
a e age
101
102
103
104
Speedup
Fig. 10: E o and speed-up o lazy sampling; low-powe a chi ec u e
ma ks wi h he la ges e o s in he simula ions o he low-
powe a chi ec u e employing pe iodic sampling. Howe e , in
he case o dedup, he e o inc eases o all simula ed h ead
coun s. We obse e he highes inc ease, om 3.2% o 11.3%,
o he simula ion wi h 8 h eads.
Summa y:The esul s o ou e alua ion show ha Task-
Poin accu a ely p edic s execu ion ime o ask-based p o-
g ams. Fo lazy sampling, he a e age e o is 1.8% wi h a
maximum e o o 15% and a simula ion speedup o 19.1.
We show ha lazy sampling achie es much g ea e speedup
han pe iodic sampling a a compa able e o . The e o e, we
ad oca e he use o lazy sampling o e alua ions equi ing
a la ge numbe o simula ions, e.g. du ing he ea ly phase o
design space explo a ion. We ecommend o employ pe iodic
sampling in la e phases o design space explo a ion when he
size o he design space has al eady been signi ican ly educed.
VI. RELATED WORK
In his sec ion, we i s in oduce di e en simula o s o
mul i-co e sys ems. Then, we p esen he p e alen ech-
niques o sampled simula ion o single- h eaded a chi ec u es.
A e wa ds, we e iew ecen wo k on sampled simula ion
o mul i- h eaded a chi ec u es. Finally, we p esen wo k on
pe o mance analysis o ask-based p og ams.
Mul i-Th eaded A chi ec u al Simula ion: COTSon [10]
is a ull-sys em simula o decoupling unc ional and iming
simula ion. Func ional simula ion elies on jus -in- ime com-
pila ion o he simula ed p og am. COTSon ea u es se e al
le els o de ail and suppo s sampling.
In addi ion o pe o mance, ESESC [24] also simula es a
u u e design’s powe consump ion and he mal beha iou .
ESESC is he i s simula o applying ime-based sampling
o simula ion o mul i- h eaded applica ions.
The ull-sys em simula o gem5 [11] ea u es CPU models
a se e al le els o de ail, anging om a model employing
na i e execu ion o a de ailed model o a supe scala ou -o -
o de CPU. Besides o he s, gem5 suppo s he x86 and ARM
a chi ec u es, which a e he mos p e alen a chi ec u es oday.
In con as o he a o emen ioned simula o s, Snipe [25]
ea u es a pu ely analy ic CPU model. Ins ead o modelling
mic o-a chi ec u al s uc u es wi hin he CPU, i employs he
mechanis ic In e al Simula ion model [26]. The highe le el
o abs ac ion o in e al simula ion is di ec ly e lec ed in a
highe simula ion speed, compa ed o mo e de ailed models.
Single-Th eaded Simula ion Sampling:In hei SimPoin
me hodology [1], She wood e al. use basic block ec o s
o iden i y he mos ep esen a i e code sec ions. The majo
simula ion e o is spen on hese sec ions SimPoin s equi es
a-p io i p o iling o he applica ion o be simula ed in o de o
9