Simula ion me hodologies o u u e
la ge-scale pa allel sys ems
Thomas G ass
ADVERTIMENT La consul a d’aques a esi queda condicionada a l’accep ació de les següen s
condicions d'ús: La di usió d’aques a esi pe mi jà del eposi o i ins i ucional
UPCommons (h p://upcommons.upc.edu/ esis) i el eposi o i coope a iu TDX
(h p://www. dx.ca /) ha
es a au o i zada pels i ula s dels d e s de p opie a in el·lec ual
únicamen pe a usos p i a s
emma ca s en ac i i a s d’in es igació i docència. No s’au o i za
la se a ep oducció amb inali a s
de luc e ni la se a di usió i posada a disposició des d’un lloc
aliè al se ei UPCommons o TDX. No s’au o i za la
p esen ació del seu con ingu en una ines a
o ma c aliè a UPCommons ( aming). Aques a ese a de
d e s a ec a an al esum de p esen ació
de la esi com als seus con ingu s. En la u ili zació o ci a
de pa s de la esi és obliga indica el nom
de la pe sona au o a.
ADVERTENCIA La consul a de es a esis queda condicionada a la acep ación de las siguien es
condiciones de uso: La di usión de es a esis po medio del eposi o io ins i ucional UPCommons
(h p://upcommons.upc.edu/ esis) y el eposi o io coope a i o TDR (h p://www. dx.ca /?locale-
a ibu e=es) ha
sido au o izada po los i ula es de los de echos de p opiedad in elec ual
únicamen e pa a usos
p i ados enma cados en ac i idades de in es igación y docencia. No
se au o iza su ep oducción
con inalidades de luc o ni su di usión y pues a a disposición desde
un si io ajeno al se icio UPCommons No se au o iza la p esen ación de su con enido en una
en ana o ma co ajeno a UPCommons ( aming). Es a ese a de de echos a ec a an o al
esumen de p esen ación de la esis como a sus
con enidos. En la u ilización o ci a de pa es
de la esis es obligado indica el nomb e de la
pe sona au o a.
WARNING On ha ing consul ed his hesis you’ e accep ing he ollowing use condi ions:
Sp eading his hesis by he ins i u ional eposi o y UPCommons
(h p://upcommons.upc.edu/ esis) and he coope a i e eposi o y TDX (h p://www. dx.ca /?locale-
a ibu e=en) has been au ho ized by he
i ula o he in ellec ual p ope y igh s only o p i a e
uses placed in in es iga ion and eaching
ac i i ies. Rep oduc ion wi h luc a i e aims is no
au ho ized nei he i s sp eading no a ailabili y
om a si e o eign o he UPCommons se ice.
In oducing i s con en in a window o ame o eign o he
UPCommons se ice is no au ho ized
( aming). These igh s a ec o he p esen a ion summa y o he
hesis as well as o i s con en s.
In he using o ci a ion o pa s o he hesis i ’s obliged o indica e
he name o he au ho .
UNIVERSITAT POLITÈCNICA DE CATALUNYA
DOCTORAL THESIS
Simula ion Me hodologies o
Fu u e La ge-Scale Pa allel Sys ems
Au ho :
Thomas GRASS
Supe iso s:
D . Ma c CASAS GUIX
D . Miquel MORETÓ PLANAS
A hesis submi ed in ul illmen o he equi emen s
o he deg ee o Doc o o Philosophy
in he
Facul a d’In o mà ica de Ba celona
Depa amen d’A qui ec u a de Compu ado s
July 17, 2017
iii
Decla a ion o Au ho ship
I, Thomas GRASS, decla e ha his hesis i led “Simula ion Me hodologies o
Fu u e La ge-Scale Pa allel Sys ems” and he wo k p esen ed in i a e my own. I
con i m ha :
•This wo k was done wholly o mainly while in candida u e o a esea ch de-
g ee a his Uni e si y.
•Whe e any pa o his hesis has p e iously been submi ed o a deg ee o
any o he quali ica ion a his Uni e si y o any o he ins i u ion, his has been
clea ly s a ed.
•Whe e I ha e consul ed he published wo k o o he s, his is always clea ly
a ibu ed.
•Whe e I ha e quo ed om he wo k o o he s, he sou ce is always gi en. Wi h
he excep ion o such quo a ions, his hesis is en i ely my own wo k.
•I ha e acknowledged all main sou ces o help.
•Whe e he hesis is based on wo k done by mysel join ly wi h o he s, I ha e
made clea exac ly wha was done by o he s and wha I ha e con ibu ed my-
sel .
Signed:
Da e:
Abs ac
Since he ea ly 2000s, compu e sys ems ha e seen a ansi ion om single-co e o
mul i-co e sys ems. While single-co e sys ems included only one p ocesso co e on
a chip, cu en mul i-co e p ocesso s include up o ens o co es on a single chip,
a end which is likely o con inue in he u u e. Today, mul i-co e p ocesso s a e
ubiqui ous. They a e used in all classes o compu ing sys ems, anging om low-
cos mobile phones o high-end High-Pe o mance Compu ing (HPC) sys ems. De-
signing u u e mul i-co e sys ems is a majo challenge [12]. The p ima y design ool
used by compu e a chi ec s in academia and indus y is a chi ec u al simula ion.
Simula ing a compu e sys em execu ing a p og am is ypically se e al o de s o
magni ude slowe han unning he p og am on a eal sys em. The e o e, new ech-
niques a e needed o speed up simula ion and allow he explo a ion o la ge design
spaces in a easonable amoun o ime.
One way o inc easing simula ion speed is sampling. Sampling educes simula-
ion ime by simula ing only a ep esen a i e subse o a p og am in de ail. In his
hesis, we p esen a wo kload analysis o a se o ask-based p og ams. We hen use
he insigh s om his s udy o p opose TaskPoin , a sampled simula ion me hod-
ology o ask-based p og ams. Task-based p og amming models can educe he
synch oniza ion cos s o pa allel p og ams on mul i-co e sys ems and a e becom-
ing inc easingly impo an . Finally, we p esen MUSA, a simula ion me hodology
o simula ing applica ions unning on housands o co es on a hyb id, dis ibu ed
sha ed-memo y sys em. The simula ion ime equi ed o simula ion wi h MUSA is
compa able o he ime needed o na i e execu ion o he simula ed p og am on a
p oduc ion HPC sys em.
The echniques de eloped in he scope o his hesis pe mi esea che s and en-
ginee s wo king in compu e a chi ec u e o simula e la ge wo kloads, which we e
in easible o simula e in he pas . Ou wo k enables a chi ec u al esea ch in he
ields o u u e la ge-scale sha ed-memo y and hyb id, dis ibu ed sha ed-memo y
sys ems.

ii
Resum
Des dels p incipis dels anys 2000, els sis emes d’o dinado s han expe imen a una
ansició de sis emes d’un sol nucli a sis emes de múl iples nuclis. Men e els sis-
emes d’un sol nucli incloïen només un nucli en un xip, els sis emes ac uals de
múl iples nuclis n’inclouen desenes, una endència que p obablemen con inua à
en el u u . A ui en dia, els p ocessado s de múl iples nuclis són omnip esen s. Es
an se i en o es les classes de sis emes de compu ació, de elè ons mòbils de baix
cos ins a sis emes de compu ació d’al endimen . Dissenya els u u s sis emes de
múl iples nuclis és un ep e impo an [12]. L’eina p incipal usada pels a qui ec es
de compu ado s, an a l’acadèmia com a la indús ia, és la simulació. Simula un
o dinado execu an un p og ama ípicamen és múl iples o d es de magni u més
len que execu a el ma eix p og ama en un sis ema eal. Pe an , es necessi en
no es ècniques pe accele a la simulació i pe me e l’explo ació de g ans espais de
disseny en un emps aonable.
Una mane a d’accele a la eloci a de simulació és la simulació mos ejada. La
simulació mos ejada edueix el emps de simulació simulan en de all només un
subconjun ep esen a iu d’un p og ama. En aques a esi es p esen a una anàlisi de
endimen d’una col·lecció de p og ames basa s en asques. Com a esul a d’aque-
s a anàlisi, p oposem TaskPoin , una me odologia de simulació mos ejada pe p o-
g ames basa s en asques. Els models de p og amació basa s en asques poden e-
dui els cos os de sinc oni zació de p og ames pa al·lels execu a s en sis emes de
múl iples nuclis i ac ualmen es an guanyan impo ància. Finalmen , p esen em
MUSA, una me odologia de simulació pe simula aplicacions execu an -se en mil-
e s de nuclis d’un sis ema híb id, que consis eix en nodes de memò ia compa ida
que o men un sis ema de memò ia dis ibuïda. El emps que eque eixen les sim-
ulacions amb MUSA és compa able amb el emps que iga l’execució na i a en un
sis ema d’al endimen en p oducció.
Les ècniques desen olupades al lla g d’aques a esi pe me en simula execu-
cions de p og ames que abans no e en iables, an als in es igado s com als en-
ginye s que eballen en l’a qui ec u a de compu ado s. Pe an , aques eball ha-
bili a u u a ece ca en el camp d’a qui ec u a de sis emes de memò ia compa ida
o dis ibuïda, o bé de sis emes híb ids, a g an escala.
ix
Resumen
A p incipios de los años 2000, los sis emas de o denado es expe imen a on una an-
sición de sis emas con un núcleo a sis emas con múl iples núcleos. Mien as los
sis emas single-co e incluían un sólo núcleo, los sis emas mul i-co e incluyen dece-
nas de núcleos en el mismo chip, una endencia que p obablemen e con inua á en
el u u o. Hoy en día, los p ocesado es mul i-co e son omnip esen es. Se u ilizan
en odas las clases de sis emas de compu ación, de elé onos mó iles de bajo cos e
has a sis emas de al o endimien o. Diseña sis emas mul i-co e del u u o es un e o
impo an e. La he amien a p incipal usada po a qui ec os de compu ado es, an o
en la academia como en la indus ia, es la simulación. Simula un compu ado eje-
cu ando un p og ama ípicamen e es múl iples o denes de magni ud más len o que
ejecu a el mismo p og ama en un sis ema eal. Po ese mo i o se necesi an nue as
écnicas pa a acele a la simulación y pe mi i la explo ación de g andes espacios de
diseño den o de un iempo azonable.
Una mane a de aumen a la elocidad de simulación es la simulación mues eada.
La simulación mues eada educe el iempo de simulación simulando en de alle sólo
un subconjun o ep esen a i o de la ejecución en e a de un p og ama. En es a esis
p esen amos un análisis de endimien o de una colección de p og amas basados en
a eas. Como esul ado de es e análisis p esen amos TaskPoin , una me odología
de simulación mues eada pa a p og amas basados en a eas. Los modelos de p o-
g amación basados en a eas pueden educi los cos es de sinc onización de p o-
g amas pa alelos ejecu ados en sis emas mul i-co e y ac ualmen e es án ganando
impo ancia. Finalmen e, p esen amos MUSA, una me odología pa a simula apli-
caciones ejecu adas en miles de núcleos de un sis ema híb ido, compues o de no-
dos de memo ia compa ida que o man un sis ema de memo ia dis ibuida. El
iempo de simulación que equie en las simulaciones con MUSA es compa able con
el iempo necesa io pa a la ejecución del p og ama simulado en un sis ema de al o
endimien o en p oducción.
Las écnicas desa olladas al la go de es a esis pe mi en a los in es igado es e in-
genie os abajando en la a qui ec u a de compu ado es simula ejecuciones la gas,
que an es no se podían simula . Nues o abajo acili a nue os caminos de in es-
igación en los campos de sis emas de memo ia compa ida o dis ibuida y en sis-
emas híb idos.
x i
7 Conclusions 107
7.1 Execu ion Time P edic abili y o Task-Based P og ams ..........107
7.2 Sampled Simula ion o Task-Based P og ams ...............108
7.3 Mul i-Le el Simula ion o Hyb id P og ams ...............109
8 Fu u e Wo k 111
8.1 Scheduling Task-Based P og ams Using Execu ion Time P edic abili y 111
8.2 Sampled Simula ion o Task-Based P og ams ...............112
8.3 Mul i-Le el Simula ion o Hyb id P og ams ...............112
A Publica ions 115
A.1 Con e ence Publica ions ...........................115
A.2 Jou nal Publica ions .............................115
A.3 Wo kshop Publica ions ............................115
A.4 Pos e P esen a ions .............................115
A.5 O he Publica ions (No as Fi s Au ho ) ..................116
Bibliog aphy 117

x ii
Lis o Figu es
1.1 Co es pe socke o sys ems in he TOP 500 lis o e ime ........ 3
2.1 Illus a ion o sha ed-memo y UMA sys em ................ 8
2.2 Illus a ion o sha ed-memo y ccNUMA sys em wi h 2 socke s . . . . . 9
2.3 Illus a ion o dis ibu ed-memo y sys em ................. 9
2.4 Illus a ion o hyb id dis ibu ed sha ed-memo y sys em ........ 10
2.5 Sys ems using accele a o s o e ime .................... 11
2.6 Illus a ion o mul i- h eaded OpenMP p og am ............. 13
2.7 Illus a ion o MPI p og am execu ed wi h ou anks .......... 14
2.8 Example o unc ional pa allelism: H.264 ................. 15
2.9 Example o da a pa allelism: ma ix-ma ix mul iplica ion ....... 16
2.10 Dependency g aph o ask-based Cholesky decomposi ion ....... 18
2.11 Illus a ion o basic-block ec o s (BBVs) .................. 26
2.12 Illus a ion o he SMARTS echnique ................... 28
3.1 O e iew o he TaskSim simula ion in as uc u e ............ 41
3.2 Reo de -Bu e Occupancy Analysis acco ding o Lee e al. ....... 41
4.1 Execu ion ime p edic ion e o o single sample ............. 50
4.2 Pe o mance a ia ion on di e en pla o ms ............... 52
4.3 Pe o mance a ia ion in luidanima e and me ge-so ........... 54
4.4 Execu ion ime p edic ion e o wi h clus e ing and linea in e pola ion 55
4.5 MPKI a ia ion as a unc ion o numbe o h eads ............ 56
5.1 IPC a ia ion pe ask ype o di e en benchma ks ........... 62
5.2 O e iew o TaskPoin wi h and wi hou analy ical modeling . . . . . 63
5.3 Ini ial wa mup, sampling, as - o wa ding and esampling in TaskPoin 66
5.4 Illus a ion o pe iodic sampling and lazy sampling in TaskPoin . . . 69
5.5 Changing numbe o h eads and a e ask clus e s in TaskPoin . . . . 70
5.6 E o and speedup o di e en sizes o wa mup in e al ........ 73
5.7 E o and speedup o di e en sizes o sample his o y ......... 73
5.8 E o and speedup o di e en sizes o sampling pe iod ........ 74
5.9 Resul s pe iodic sampling, high-pe o mance a chi ec u e ....... 75
5.10 Resul s pe iodic sampling, low-powe a chi ec u e ............ 76
x iii
5.11 Resul s lazy sampling, high-pe o mance a chi ec u e .......... 77
5.12 Resul s lazy sampling, low-powe a chi ec u e .............. 78
5.13 Resul s model-based sampling, high-pe o mance a chi ec u e . . . . . 79
5.14 Resul s model-based sampling, low-powe a chi ec u e ......... 80
6.1 O e iew o MUSA’s acing and simula ion me hodology ....... 86
6.2 Ou pu o MUSA’s acing- and simula ion in as uc u e ........ 88
6.3 Valida ing MUSA wi h he NAS Mul i-Zone benchma ks ........ 94
6.4 Simula ing BT-MZ wi h inpu class E and 256 MPI anks ........ 97
6.5 Simula ing HYDRO wi h inpu class E and 256 MPI anks ........ 98
6.6 Simula ing SPECFEM3D wi h inpu class E and 256 MPI anks . . . . . 99
6.7 Simula ion ime BT-MZ ............................100
6.8 Simula ion ime HYDRO ...........................101
6.9 Simula ion ime SPECFEM3D ........................102
6.10 Case s udy: simula ing di e en a chi ec u es wi h MUSA .......103
xix
Lis o Tables
2.1 Classi ica ion o sha ed-memo y mul i-co e simula o s ......... 21
3.1 In es iga ed machines ............................ 39
3.2 Task-based pa allel benchma ks used o he e alua ion o TaskPoin . 44
5.1 Pa ame e s o he a chi ec u es simula ed wi h TaskPoin ........ 72
6.1 Cha ac e is ics o applica ions simula ed wi h MUSA .......... 92
6.2 T ace sizes o simula ions wi h MUSA .................. 92
6.3 Pa ame e s o a chi ec u es used in case s udy wi h MUSA . . . . . . . 102
xxi
Lis o Abb e ia ions
BBV Basic Block Vec o
ccNUMA cache-cohe en Non-Uni o m Memo y Access
CMP Chip Mul i-P ocesso
CPU Cen al P ocessing Uni
DRAM Dynamic Random Access Memo y
FPGA Field-P og ammable Ga e A ay
GPGPU Gene al Pu pose G aphics P ocessing Uni
ILP Ins uc ion-Le el Pa allelism
IPC Ins uc ions Pe Cycle
ISA Ins uc ion Se A chi ec u e
HPC High-Pe o mance Compu ing
LLC Las -Le el Cache
LRU Leas Recen ly Used
MLP Memo y Le el Pa allelism
NoC Ne wo k-on-Chip
NUCA Non-Uni o m Cache A chi ec u e
PMU Pe o mance Moni o ing Uni
ROB ReO de -Bu e
RTL Regis e -T ans e Le el
SIMD Single Ins uc ion, Mul iple Da a
SMT Simul aneous Mul i-Th eading
SoC Sys em-On-a-Chip
SPMD Single P og am, Mul iple Da a
TLP Th ead-Le el Pa alellism
UMA Uni o m Memo y Access

1
Chap e 1
In oduc ion
The i s comme cial mic op ocesso , he In el 4004, was in oduced in 1971 and con-
sis ed o app oxima ely 2,300 ansis o s in eg a ed on a single chip [7]. I equi ed
a a ie y o o he in eg a ed ci cui s o unc ion. The In el 4004 ope a ed a a clock
equency o 740kHz and was able o execu e one ins uc ion e e y eigh clock cycles
o a o al o up o 92,600 ins uc ions pe second. E e since he in oduc ion o he
In el 4004, pe o mance and complexi y o compu e sys ems ha e been inc easing
exponen ially o e ime.
In compa ison, he In el Xeon E5-2699 4 p ocesso [64], eleased ea ly in 2016,
in eg a es app oxima ely 7.2 billion ansis o s on a single chip. The chip con ains 22
ac i e co es1, 55MB o las -le el cache and a a ie y o ci cui y o in e ace wi h he
es o he sys em. The co es ope a e a 2.2GHz and can p ocess up o 4 ins uc ions
pe clock cycle, esul ing in a heo e ical maximum o 193.6 billion ins uc ions pe
second o he ull p ocesso . Thus, since he a i al o he In el 4004, p ocesso
pe o mance has imp o ed by a ac o o mo e han 2 million.
The massi e inc ease in p ocesso pe o mance o e ime has been possible be-
cause he manu ac u ing p ocesses o in eg a ed ci cui s ha e been con inuously
imp o ing, combined wi h a chi ec u al enhancemen s. O e ime, hese imp o e-
men s allowed o in eg a e an e e la ge numbe o ansis o s on a single chip.
Go don Moo e obse ed in 1965 ha he numbe o ansis o s had been doubling
e e y wo yea s and he p ojec ed his end in o he u u e [84]. His obse a ion
became known as Moo e’s Law.
Du ing he i s h ee decades o he mic op ocesso ’s his o y, compu e a chi-
ec s used he inc easing numbe s o ansis o s coming along wi h Moo e’s Law
p ima ily o imp o e single- h ead pe o mance. As he ea u e sizes o in eg a ed
ci cui s sh ank, i was possible o inc ease he equency o ope a ion, and hus he
ins uc ion h oughpu . Besides, he newly a ailable ansis o s allowed o employ
mo e sophis ica ed echniques o exploi ins uc ion-le el pa allelism (ILP), allowing
a single p ocesso o execu e mul iple ins uc ions pe cycle, po en ially ou o p o-
g am o de . These e o s culmina ed in he P esco mic o-a chi ec u e, used by he
1The chip con ains 24 co es, wo o which a e deac i a ed.
2
Chap e 1. In oduc ion
In el Pen ium 4 p ocesso . The P esco mic o-a chi ec u e used 31 pipeline s ages
o achie e a high clock equency. Pen ium 4 P esco p ocesso s we e able o un a
up o 3.8GHz, consuming mo e han 100W in powe . I became appa en ha u -
he inc easing he ope a ion equency would lead o unaccep able he mal powe
dissipa ion. A he same ime, deepe pipelines would exace ba e he al eady high
penal ies o pipeline lushes, e.g. in he case o b anch misspecula ion.
In he ea ly 2000’s, he majo p ocesso manu ac u e s s a ed o use he in-
c eased ansis o coun s o implemen chip mul i-p ocesso s (CMPs), i.e. p ocesso s
in eg a ing se e al p ocesso co es on a single chip. These p ocesso co es an a
a lowe ope a ion ol age and clock equency han hei single-co e p edecesso s.
CMPs achie ed highe o al pe o mance while consuming less powe . This pe o -
mance inc ease has been achie ed by exploi ing h ead-le el pa allelism (TLP). Ins ead
o elying on e e mo e sophis ica ed echniques o de ec and exploi ILP, CMPs ex-
ecu e mul iple execu ion h eads simul aneously.
Exploi ing TLP on CMPs ypically equi es suppo in p og amming languages
and un ime en i onmen s. P og amme s need o ake ca e o e icien ly exposing
TLP in a p og am. Despi e hese incon eniences, CMPs a e p e alen oday. In el’s
cu en high-end Xeon E5-2699 4 p ocesso has 22 co es, whe eas In el’s Xeon Phi
7120X sys ems e en include 61 co es. An end o he con inuously inc easing co e
coun s in his mul i-co e e a is cu en ly no in sigh .
A chi ec u al simula ion is a key ool o compu e a chi ec s and applica ion
de elope s. By elying on simula ion, compu e a chi ec s can e alua e he pe -
o mance and powe consump ion o a benchma k on a a ie y o design choices
wi hou ac ually building cos ly ha dwa e p o o ypes. Applica ion de elope s use
simula ion o de elop and op imize sys em so wa e and applica ions so ha he
so wa e is eady once a new machine hi s he ma ke .
High-pe o mance compu ing (HPC) sys ems ypically consis o a la ge num-
be o sha ed memo y nodes, each composed o mul iple p ocesso s o socke s. In
ecen yea s, he numbe o co es pe socke is con inuously inc easing. The TOP
500 lis [113] lis s he 500 as es HPC sys ems in he wo ld and is upda ed wice a
yea . Figu e 1.1 shows he pe cen age o sys ems lis ed in he TOP 500 lis o se-
lec ed numbe s o co es pe socke . The igu e clea ly demons a es ha , since he
ad en o he dual-co e p ocesso , which eached i s peak ea ly in 2007, single-co e
p ocesso s ha e p ac ically anished. Ins ead, sys ems a e buil wi h e e inc eas-
ing numbe s o co es, and cu en ly, he e is no eason o assume ha his end will
change in he nea u u e.
The impac ha he inc easing co e coun has on a chi ec u al simula ion is wo-
old. Fi s , a la ge amoun o simula ed, s a e-holding ha dwa e equi es he sim-
ula ion o la ge wo kloads o s ess he simula ed design meaning ully. Second, a
1.1. Thesis Con ibu ions
3
No 2000
No 2001
No 2002
No 2003
No 2004
No 2005
No 2006
No 2007
No 2008
No 2009
No 2010
No 2011
No 2012
No 2013
No 2014
No 2015
No 2016
Mon h/Yea
0
20
40
60
80
100
Sha eo allsys ems[%]
Co espe socke
1
2
4
6
8
10
12
16
FIGURE 1.1: E olu ion o he numbe o co es pe socke since
No embe 2000, as obse ed in he sys ems lis ed in he TOP 500 lis
o he as es HPC sys ems.
simula ion o a sys em wi h mul iple co es equi es simula ing he in e ac ions o
hese co es in sha ed sys em esou ces, e.g. las -le el caches o he on-chip in e -
connec subsys em. Bo h he la ge design complexi y and he mo e complex sys-
em beha io inc ease simula ion complexi y and hus simula ion ime. Howe e ,
he simula ion speed o con empo a y de ailed a chi ec u al simula o s has no in-
c eased o he same ex en .
The size o HPC sys ems is also inc easing in e ms o he numbe o nodes.
Consequen ly, sys em-le el simula ions need o simula e no only a la ge numbe
o o al co es, bu also inc easingly la ge in e connec ion ne wo ks. Exis ing simula-
o s o such machines ei he use high-le el models o a e p ohibi i ely slow. While
high-le el models achie e high simula ion speed, hey do so by sac i icing simula-
ion de ail. De ailed simula ion o p og ams execu ing on housands o co es in a
dis ibu ed memo y sys em is e y accu a e bu in easible due o i s excessi e sim-
ula ion ime.
1.1 Thesis Con ibu ions
In he ollowing, we lis he con ibu ions we make in he di e en chap e s o his
hesis:
10
Chap e 2. Backg ound
nodes. Wi hin a node g oup, nodes a e in e connec ed using a h ee-dimensional
mesh opology. Di e en node g oups a e in e connec ed in a h ee-dimensional
o us opology. An ad an age o his in e connec a chi ec u e is ha he e a e mul-
iple pa hs be ween any pai o nodes. As a esul , he sys em can ole a e a small
numbe o link ailu es and s ill be ope a ional.
The examples men ioned abo e illus a e ha he in e connec ne wo k has a
signi ican in luence on how applica ions a e e icien ly mapped o he nodes o a
sys em. Bo h men ioned sys ems p o ide highe communica ion bandwid h and
lowe la ency be ween p ocesses unning in he same supe node o node g oup, e-
spec i ely. Besides, he K compu e ’s mesh- o us in e connec is well-sui ed o ap-
plica ions in which p ocesses mainly communica e wi h hei immedia e neighbo s.
On he o he hand, all- o-all communica ions o communica ions be ween dis an
nodes can be cos ly in e ms o la ency. Communica ion be ween dis an nodes ad-
di ionally causes ne wo k con en ion all along he message pa h.
2.1.3 Hyb id Sys ems
Cu en HPC sys ems canno be classi ied in o ei he sha ed- o dis ibu ed-memo y
sys ems. Ins ead, hey ollow a hyb id design app oach, as illus a ed in Figu e 2.4:
each mul i-co e p ocesso is pa o a UMA socke . Mul iple UMA socke s oge he
o m a sha ed-memo y ccNUMA node. An HPC sys em consis s o mul iple cc-
NUMA nodes, po en ially housands o ens o housands. Each ccNUMA node is
connec ed o a ne wo k, o ming a (hyb id) dis ibu ed-memo y sys em comp ised
o sha ed-memo y nodes.
Ne wo k Con olle
...
Ne wo k
Node 1
Socke 1 Socke 2
Ne wo k Con olle
Node 2
Socke 1 Socke 2
Ne wo k Con olle
Socke 1 Socke 2
Node N
FIGURE 2.4: Hyb id sys em; sha ed-memo y ccNUMA nodes a -
anged in a dis ibu ed-memo y con igu a ion.
2.1.4 He e ogeneous Sys ems
To achie e highe pe o mance and be e ene gy e iciency sys ems can inco po a e
mul iple ypes o p ocesso s. The di e en p ocesso ypes can di e in a a ie y
o cha ac e is ics. They can use he same o di e en ins uc ion se a chi ec u es
(ISAs) and a y in pe o mance and powe consump ion. An example is sys ems

2.1. Pa allel Sys ems
11
consis ing o bo h mul i-co e p ocesso s and gene al-pu pose g aphics p ocessing uni s
(GPGPUs). I a p ocesso is op imized o a ce ain class o compu a ions i is also
e e ed o as an accele a o .
The TOP 500 lis [113] lis s he 500 as es HPC sys ems in he wo ld and is up-
da ed e e y six mon hs. Figu e 2.5 displays he pe cen age o di e en ypes o
accele a o s used by sys ems in he TOP 500 lis o e ime. Some accele a o ypes,
e.g. he IBM Cell p ocesso o ATI Radeon GPGPUs, had some signi icance in he
pas bu disappea ed a e wa ds. As can be seen in he igu e, oday he ma ke o
accele a o s in HPC is domina ed by NVIDIA GPGPUs and In el MIC accele a o s.
In e es ingly, la ely, he o al amoun o sys em using accele a o s is dec easing.
No 2007
No 2008
No 2009
No 2010
No 2011
No 2012
No 2013
No 2014
No 2015
No 2016
Mon h/Yea
0
2
4
6
8
10
12
14
Sha eo allsys ems[%]
IBMCell
NVIDIAGPGPUS
ATIGPGPUs
In elMIC
O he s
FIGURE 2.5: Pe cen age o sys ems in he TOP 500 lis using accele a-
o s o e ime.
Ano he example o a he e ogeneous sys em is he ARM big.LITTLE a chi ec-
u e, designed o imp o e ene gy e iciency o ba e y-powe ed mobile de ices. In
big.LITTLE, as , mo e powe -consuming ("big") co es a e combined wi h slowe ,
mo e ene gy-e icien ("li le") co es. Ea ly implemen a ions had es ic ions, such
as only allowing o use ei he all big o all li le co es. S a ing wi h he Samsung
Exynos 5420 SoC, hese limi a ions ha e been o e come. A big.LITTLE sys em can
also include a GPGPU. While big and li le co es ha e he same ISA, he GPGPU
usually has a di e en ISA. Howe e , big co es, li le co es and he GPGPU sha e he
same physical memo y add ess space, hus o ming a ccNUMA sys em.
12
Chap e 2. Backg ound
2.1.5 Implica ions on Design Techniques o Fu u e Sys ems
In he p e ious subsec ions we poin ed ou how he ha dwa e complexi y o mode n
compu e sys ems is con inuously inc easing. In HPC sys ems, complexi y inc eases
bo h a he in a-node and he in e -node le els. A he in a-node le el co e coun s
and co e he e ogenei y a e inc easing o e ime. A he in e -node le el, la ge num-
be s o nodes need o be in e connec ed, equi ing new ne wo k echnologies.
The inc ease in o e all sys em complexi y exceeds he capabili ies o exis ing
simula ion echniques. New, ad anced echniques a e needed o simula e u u e
sys ems a a good accu acy and in a easonable amoun o simula ion ime. In his
hesis, we p esen echniques o imp o ing simula ion speed a he in a-node and
in e -node le els, while main aining high simula ion accu acy.
2.2 Pa allel P og amming Models
Pa allel p og amming models can be classi ied acco ding o a a ie y o di e en c i-
e ia. In his sec ion, we p esen a classi ica ion along wo o hogonal dimensions.
The i s dimension is he way in which a p og amme manages di e en pa allel
execu ion h eads. The second dimension consis s in he way he p og amme de-
composes a p oblem in o de o make i sui able o pa allel execu ion.
2.2.1 Sha ed-Memo y P og amming Models
A pa allel p og amming model o sha ed-memo y machines p o ides a means o
c ea e se e al execu ion h eads ha sha e all o pa o hei memo y add ess space.
A p og am using mo e han one h ead is e e ed o as a mul i- h eaded p og am.
The decomposi ion o a p og am in o mul iple h eads can gene a e ace condi ions,
unde which he ou come o a p og am depends on he o de in which he di e en
h eads access sha ed da a. Undesi ed ace condi ions can be a oided wi h he aid
o synch oniza ion p imi i es, namely locks and semapho es.
In adi ional pa allel p og amming models o sha ed-memo y sys ems, like
POSIX Th eads (P h eads) [19], he p og amme explici ly decomposes an appli-
ca 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.
While P h eads gi es he applica ion de elope a la ge deg ee o con ol, he esul -
ing p og ams a e di icul o main ain. This is mainly due o he low deg ee o sim-
ila i y be ween he pa allel code and a sequen ial implemen a ion, which esul s in
low code eadabili y. Fu he mo e, P h eads p og ams can be ailo ed o a pa icula
a chi ec u e, hinde ing pe o mance po abili y.
2.2. Pa allel P og amming Models
13
The mos p e alen sha ed-memo y p og amming model oday is OpenMP [39].
OpenMP suppo s he C, C++ and Fo an p og amming languages. I allows he
p og amme o pa allelize a sequen ial e sion o a p og am by adding p ep oces-
so di ec i es. An ad an age o OpenMP is ha i allows a p og amme o w i e a
pa allel p og am in an inc emen al ashion, s a ing wi h a sequen ial implemen a-
ion. This inc eases p og amme p oduc i i y and imp o es code eadabili y.
LISTING 2.1: Dense ma ix-ma ix mul iplica ion in OpenMP
1[sequen ial code]
2
3#p agma omp pa allel o
4 o (i=0;i<n;i++){
5 o (j=0;j<n;j++){
6c[i][j] = 0.0;
7 o (k=0;k<n;k++){
8c[i][j] = c[i][j] + a[i][k] *b[k][j];
9}
10 }
11 }
12
13 [mo e sequen ial code]
OpenMP is an example o a p og amming model suppo ing he o k-join pa adigm.
The code agmen in Lis ing 2.1 shows a case o a mul iplica ion o wo ma ices o
dimension n×n, implemen ed using OpenMP. Lines 4 o 11 implemen he ac ual
ma ix mul iplica ion. The decla a ion in line 3 ul ills wo unc ions: i s , i c ea es
a h ead eam, consis ing o a use -speci ied numbe o wo ke h eads. I no h ead
coun is speci ied, he numbe o wo ke h eads is equal o he numbe o ha dwa e
h eads o he hos machine. Second, he s a emen in line 3 causes he i e a ion
space o he ou e mos o -loop o be spli in o equally-sized chunks. The numbe o
chunks is equal o he numbe o h eads, and each chunk is assigned o a di e en
h ead. Once all h eads inish he execu ion o hei espec i e chunks, he wo ke
h eads a e des oyed, and he main h ead con inues he sequen ial execu ion o he
p og am.
Time
Th ead 1
...
Th ead 2
Th ead 3
Th ead 4
Fo k Join
FIGURE 2.6: Illus a ion o pa allel execu ion in an OpenMP applica-
ion wi h ou execu ion h eads
14
Chap e 2. Backg ound
Figu e 2.6 illus a es he pa allel execu ion o he p e ious example wi h ou
h eads. In he beginning, one h ead execu es he sequen ial po ion o he p og am.
When en e ing he pa allel sec ion, h ee mo e h eads a e c ea ed. A e wa ds, all
h eads pa icipa e in he pa allel compu a ion. Th eads can communica e explici ly
by accessing he same, sha ed memo y o he applica ion. A he end o he pa allel
phase, all h eads implici ly synch onize, and he addi ionally c ea ed h eads a e
des oyed. Then, he main h ead con inues wi h he execu ion o he sequen ial
pa s o he applica ion.
The a o emen ioned mechanism o dis ibu ing wo k ac oss se e al h eads is
e e ed o as wo k sha ing. OpenMP also suppo s asking, which is in oduced in
Subsec ion 2.2.4 la e in his sec ion. O he examples o sha ed-memo y p og am-
ming models a e Cilk [15] and In el Th ead Building Blocks (TBB) [96].
2.2.2 Message Passing P og amming Models
In message passing p og amming models, h eads ha e only p i a e memo y. Com-
munica ion is achie ed by means o messages exchanged be ween h eads. Typi-
cally, message passing elies on pa alleliza ion ac oss di e en p ocesses o anks,
in con as o he h eads used by sha ed-memo y p og ams. The mos widesp ead
ep esen a i e o his class o p og amming models is he Message Passing In e ace
(MPI) [56,82]. MPI o e s a a ie y o unc ions o sending and ecei ing messages
be ween wo p ocesses (poin - o-poin communica ion). The e a e also communica-
ion p imi i es in ol ing mo e han wo p ocesses, e.g. all- o-all communica ions,
in which each p ocess communica es wi h all o he p ocesses. O he examples a e
one- o-all and all- o-one communica ions. They a e also e e ed o as sca e and
ga he ope a ions, espec i ely.
Time
Rank 1
Rank 2
Rank 3
Rank 4
...
FIGURE 2.7: Illus a ion o compu a ion phases (boxes) and messages
(a ows) in an MPI applica ion wi h ou anks
Figu e 2.7 illus a es an MPI applica ion execu ed wi h ou anks, each o which
uns on a di e en node o a clus e . In he beginning, all anks pe o m compu a-
ions. A some poin , each ank sends messages o i s immedia e neighbo s. This
communica ion scheme is e e ed o as poin - o-poin communica ion. When he
communica ion is comple e, all anks esume compu a ion. A e some ime, all
2.2. Pa allel P og amming Models
15
anks exchange messages wi h each o he , pe o ming an all- o-all communica ion,
be o e once mo e hey esume compu a ion.
In MPI, a p og am is pa allelized ac oss di e en p ocesses, each o which uns
on a di e en co e. The co es can be loca ed in di e en nodes, in di e en socke s o
he same node, o in he same socke . P ocesses ypically communica e ia a high-
bandwid h, low-la ency ne wo k. I wo communica ing p ocesses a e loca ed on
he same node, cu en MPI implemen a ions a oid using he ne wo k in e ace o
communica ion. Ins ead, communica ion is achie ed ia sha ed memo y in a way
which is anspa en o he use , managed by he MPI lib a y.
No e ha he dis inc ion be ween sha ed-memo y and message passing p o-
g amming models is based on he p og amme ’s iew o memo y. Sha ed-memo y
p og amming models map na u ally o sha ed-memo y sys ems, e.g. CMPs. On he
o he hand, message passing maps na u ally o dis ibu ed-memo y machines, such
as clus e s. Howe e , i is also possible o p og am sha ed-memo y machines using
message passing o o p og am dis ibu ed-memo y machines wi h sha ed-memo y
p og amming models. Fo example, In el’s p og amming model Clus e OpenMP
hides explici message passing om he p og amme by c ea ing he illusion o a
single add ess space encompassing he en i e sys em’s memo y [60].
2.2.3 Func ional Pa allelism s. Da a Pa allelism
In he p e ious sec ions, we classi y p og amming models in o sha ed-memo y and
message passing p og amming models, acco ding o he p og amme ’s iew o a
sys em’s memo y. In his sec ion we conside a di e en classi ica ion, acco ding
o he way in which a p og am exposes pa allelism. No e ha his classi ica ion is
o hogonal o he one p esen ed in he p e ious sec ion.
The implemen a ion o a pa allel p og am equi es he decomposi ion o a p ob-
lem so ha i s compu a ion can be accele a ed by using mul iple h eads. The wo
dominan ypes o pa allelism a e unc ional pa allelism and da a pa allelism. Exploi -
ing hese di e en kinds o pa allelism equi es di e en p og amming s a egies.
I B B P B B P B B I B B P B B P B B I
GOP 1 GOP 2
FIGURE 2.8: Example o unc ional pa allelism: Dependencies be-
ween di e en ames in an H.264 ideo s eam
A p og am is said o con ain unc ional pa allelism pe o ms se e al asks se-
quen ially, which could pa ially o en i ely be execu ed in pa allel wi hou iola ing

16
Chap e 2. Backg ound
p og am co ec ness. An example is decoding a ideo encoded in he H.264 s an-
da d [120]. As illus a ed in Figu e 2.8, a G oup-o -Pic u es (GOP) in an H.264 ideo
con ains so-called I-, P- and B-F ames. I-F ames a e independen o o he ames
and can be decoded in pa allel. P-F ames depend on he p e ious I-F ame. Once
his I-F ame is decoded, all P-F ames o he GOP can be decoded in pa allel. Finally,
B-F ames depend on he su ounding non-B-F ames. Once hose a e decoded, all
B-F ames in a subsequence can be decoded in pa allel.
A p og am con aining da a pa allelism, epea edly pe o ms he same ope a ion
on di e en elemen s o anges o i s da a, whe eas hese ope a ions could be exe-
cu ed in pa allel wi hou iola ing p og am co ec ness. Se e al pa allel execu ion
pa adigms exploi da a pa allelism.
ASingle Ins uc ion, Mul iple Da a (SIMD) machine can exploi da a pa allelism
which is known a compile ime. Special machine ins uc ions ope a e on mul iple
da a i ems a a ime. Fo example, In el’s AVX512 ins uc ion se ex ensions p o ide
ins uc ions which can ope a e on up o 64 by e-sized ope ands wi h a single in-
s uc ion. A second example is GPGPUs, in which mul iple ha dwa e h eads sha e
he same con ol logic and ope a e in locks ep on di e en da a. Finally, he ma ix
mul iplica ion example in Sec ion 2.2.1 also elies on da a pa allelism.
Da a pa allelism can also be exploi ed by independen p ocesso s execu ing he
same p og am ope a ing on di e en pa s o he da a domain, esul ing in a Single
P og am, Mul iple Da a (SPMD) execu ion scheme. An ad an age o SPMD is ha
da a pa allelism does no need o be known a compile ime. Fu he mo e, SPMD
machines show a highe ole ance o con ol low di e gence, which occu s when
di e en h eads ollow di e en con ol pa hs due o da a dependence o he con ol
low.
A B A
11
A
21
A
12
A
22
CB
11
B
21
B
12
B
22
C
11
C
21
C
12
C
22
×
=
×
=
FIGURE 2.9: Example o exploi ing da a pa allelism h ough domain
decomposi ion: blocked ma ix-ma ix mul iplica ion
One way o exploi da a pa allelism in SPMD machines is domain decomposi ion,
he decomposi ion o he p oblem domain in o blocks o iles, which can be p ocessed
independen ly. Di e en h eads can ope a e on di e en blocks simul aneously, ac-
cele a ing he o e all p og am execu ion. Figu e 2.9 illus a es h ee ma ices. The
ma ices Aand Ba e o be mul iplied, and he esul s o ed in ma ix C. A e spli -
ing he h ee ma ices in o sub-ma ices, he mul iplica ion ules o blocked ma i-
ces can be applied and he sub-ma ices o ma ix Ccan be calcula ed in pa allel,
2.2. Pa allel P og amming Models
17
acco ding o Equa ions 2.1 o 2.4.
C11 =A11 ×B11 +A12 ×B21 (2.1)
C21 =A21 ×B11 +A22 ×B21 (2.2)
C12 =A11 ×B12 +A12 ×B22 (2.3)
C22 =A21 ×B12 +A22 ×B22 (2.4)
2.2.4 Task-Based P og amming Models
A mul i- h eaded execu ion is said o be load-balanced i all h eads each a synch o-
niza ion poin a he same ime. The absence o load balance is e e ed o as load im-
balance. Load imbalance is a common p oblem wi h mul i- h eaded p og ams since
i limi s pa allel e iciency and, consequen ly, applica ion scalabili y. Task-based p o-
g amming models ha e he po en ial o alle 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. A un ime
en i onmen dynamically schedules ask ins ances o a ailable execu ion h eads,
aking in o accoun he dependencies be ween di e en ask ins ances.
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 balance he wo kload assigned o each h ead dynamically [79]. 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 [30,114].
In his wo k, we di e en ia e be ween ask ypes and ask ins ances. E e y ex-
ecu 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 o-
g am, he numbe o ask ypes is small, i.e. up o a ew ens. On he o he hand, he
numbe o ask ins ances can lie in he o de o housands o millions.
The decomposi ion o a sequen ial p og am in o se e al ask ypes can be seen as
a manne o unc ional decomposi ion, while he epea ed ins an ia ion o a ask ype
can be ega ded as domain decomposi ion. Thus, ask-based p og amming models
allow he p og amme o exploi bo h unc ional and da a pa allelism.
Figu e 2.10 shows a ask dependency g aph o a ask-based implemen a ion o a
Cholesky decomposi ion. The p og am consis s o ou ask ypes, which a e calls o
he unc ions dpo ,d sm,dsy k and dgemm o he Le el 3 Basic Linea Algeb a
Subp og ams (BLAS) [76]. In he beginning, only one ask ins ance can be execu ed,
18
Chap e 2. Backg ound
since i gi es a dependency o all o he ask ins ances. When his ins ance inishes
execu ion, mo e pa allelism becomes a ailable. No e ha he las ou ask ins ances
need o be execu ed sequen ially due o da a dependencies.
main Dependence ype:Use unc ions:
2
3
4 56
7 8
12
13
18
9
10 11
14 15 19
16
17
20
21
smpSs_dpo _ ile
smpSs_dsy k_ ile
smpSs_d sm_ ile
smpSs_dgemm_ ile T ue dependence
An i-dependence
Ou pu dependence
(A)
dpo
d sm
dsy k
dgemm
(B)
FIGURE 2.10: Dependency g aph o ask-based implemen a ion o
Cholesky decomposi ion
An example o a p og amming model suppo ing asks is OpenMP [39]. S a ing
wi h a sequen ial e sion o a p og am, he p og amme adds sou ce code anno a-
ions o indica e which pa s o he p og am a e o be conside ed as asks. These
asks a e anno a ed wi h he da a ead and w i en by each ins ance o he ask. The
esul ing pa allel p og am is ypically mo e in ui i e o p og amme s, compa ed
o low-le el pa allel p og amming models. Besides, de elopmen and debugging
echniques a e simila o he me hods o he de elopmen o single h eaded ap-
plica ions. O he pa allel p og amming models suppo ing asks a e In el Th ead
Building Blocks (TBB) [96] and OmpSs [42].
2.3. A chi ec u al Simula ion
19
2.2.5 Hyb id P og amming Models
As s a ed in Sec ion 2.1.3, cu en HPC sys ems consis o a la ge numbe o nodes,
o ming a dis ibu ed-memo y sys em. Each node i sel is a sha ed-memo y mul i-
co e sys em. One way o p og am hese machines is he use o hyb id p og am-
ming models. In a hyb id p og amming model, a dis ibu ed-memo y p og amming
model is employed o pe o m a coa se-g ain pa alleliza ion o he wo kload ac oss
he di e en nodes o he sys em. A sha ed-memo y p og amming model u he
pa allelizes he wo kload ac oss he di e en p ocesso s wi hin a node. A widely
used hyb id p og amming model is MPI+OpenMP [92].
Hyb id p og amming models seem o be a na u al i o he hyb id na u e o
cu en HPC sys ems. Howe e , hey also in oducemo e a iables which need o be
uned by sys em use s. T adi ional dis ibu ed-memo y p og ams, elying pu ely on
message passing o pa alleliza ion, a e ypically un wi h one p ocess pe p ocesso .
In a hyb id p og am, a single p ocess can un on mul iple h eads. An applica ion
migh scale well wi h he numbe o p ocesses, bu no wi h he numbe o h eads
pe p ocess and ice e sa. I is up o he use o de e mine he ideal numbe s o
p ocesses and h eads pe p ocess.
2.3 A chi ec u al Simula ion
A chi ec u al simula ion is an impo an ool o compu e a chi ec s in academic
esea ch and indus y [2]. Simula ion allows e alua ing a chi ec u al ea u es and
hei impac on pe o mance and powe consump ion wi hou ac ually building a
cos ly p o o ype o he p oposed design. Fo example, ou -o -o de execu ion, a ea-
u e used by i ually e e y mode n p ocesso om mobile o high-pe o mance
sys ems, was i s e alua ed in simula ion [63]. Also, de elope s o sys em so wa e
and applica ions eso o simula ion while eal ha dwa e is no ye a ailable.
The equi emen s o compu e a chi ec s o a simula o a e ypically di e en
om he equi emen s o so wa e de elope s. While he a chi ec is mainly in e -
es ed in accu a ely modeling he ele an ha dwa e s uc u es and hei impac on
pe o mance, he so wa e de elope wan s a simula o ha suppo s he ins uc ion
se a chi ec u e (ISA) o he u u e machine.
2.3.1 Func ional s. Pe o mance Simula ion
Acco ding o he di e en needs o compu e a chi ec s and so wa e de elope s e-
lying on simula ion, simula o s can be classi ied oughly in o wo classes, namely
26
Chap e 2. Backg ound
be ween co es and he con en ion on sha ed sys em esou ces addi ionally inc ease
simula ion complexi y.
2.4.1 Checkpoin ing
O en imes, i is desi able o simula e no he en i e execu ion o a benchma k, bu
only a egion o in e es . Howe e , especially execu ion-d i en simula o s equi e he
simula ion o a benchma k om he beginning. Consequen ly, all p og am pa s
leading o he egion o in e es , e.g. ini ializa ion o da a s uc u es, a e simula ed
ou o necessi y. A solu ion o his p oblem is checkpoin ing. When using check-
poin ing, an image o he a chi ec u al s a e o he simula ed sys em is s o ed on
he simula ion hos , oge he wi h he s a e o he simula o . This image is e e ed
o as a checkpoin . Checkpoin s can be es o ed, allowing o esume a p e iously
checkpoin ed simula ion. A chi ec u al simula ion can be accele a ed by c ea ing a
checkpoin be o e he egion o in e es . Successi e simula ions can s a om his
checkpoin . The echnique can also be applied o mul iple egions o in e es .
2.4.2 Sampling
Sampling echniques accele a e a chi ec u al simula ion by pe o ming de ailed pe -
o mance simula ion only on a subse , o sample, o a simula ed p og am. The p o-
g am pa s no belonging o he sample a e ei he simula ed in a as e , unc ional-
only simula ion mode o e en omi ed. Finally, he pe o mance me ics o he en i e
simula ion a e ex apola ed, based on he pe o mance in o ma ion ob ained du ing
de ailed simula ion o he sample.
Single-Th eaded Simula ion Sampling
In hei SimPoin me hodology [107], She wood e al. use basic block ec o s (BBVs)
o iden i y he ep esen a i e pa s o a p og am’s execu ion. A e wa ds, only hese
ep esen a i e pa s a e simula ed in de ail. Finally, he pe o mance me ics o he
en i e p og am execu ion a e ex apola ed.
(
I
BB 1
I
BB 2
)
1
(
I
BB 1
I
BB 2
)
2
(
I
BB 1
I
BB 2
)
3
(
I
BB 1
I
BB 2
)
N
.. .
0 100M 200M 300M N·100M(N-1)·100M
FIGURE 2.11: Gene a ion o basic block ec o s (BBVs) o a p og am
consis ing o wo basic blocks
The i s s ep o applying SimPoin is he gene a ion o BBVs o he p og am
which is o be simula ed. While he p og am is execu ed na i ely o in a simula o ,

2.4. Accele a ion Techniques o A chi ec u al Simula ion
27
he dynamic ins uc ion s eam is spli in o in e als o ypically 100 million ins uc-
ions, as illus a ed in Figu e 2.11. Fo each in e al, a ec o BBViwi h as many
dimensions as he o al numbe o basic blocks in he p og am is cons uc ed. The
igu e illus a es a hypo he ic example o a p og am consis ing o only wo basic
blocks. Each dimension o his ec o is indexed by a di e en basic block and con-
ains a coun e o he numbe o dynamic ins uc ions, belonging o he co espond-
ing basic block, which a e execu ed du ing each 100 million ins uc ion in e al.
The key idea behind SimPoin is ha i wo in e als ha e simila BBVs, hey
a e simila in e ms o he ins uc ions he p og am execu es du ing his in e al
and, hence, a e likely o ha e simila pe o mance. This simila i y be ween BBVs
is de ec ed by applying k-means clus e ing [81] o he se o all BBVs. The esul ing
clus e s con ain BBVs o simila pe o mance. By selec ing one ep esen a i e BBV
o each clus e , one can ob ain a se o 100 million ins uc ion in e als cap u ing he
en i e beha io o he simula ed p og am.
De ailed simula ion is pe o med only on he ep esen a i e in e als, also e-
e ed o as simula ion poin s, while he emainde o he applica ion up o he las
de ailed in e al is simula ed in a as e , unc ional simula ion mode. A e simula-
ion, he pe o mance me ics o all in e als a e used o ex apola e he pe o mance
o he ull de ailed simula ion, depending on he numbe o BBVs in each clus e .
She wood e al. epo an a e age IPC e o o 3.0% [107].
Pe elman e al. p opose a echnique o selec s a is ically alid simula ion poin s
ea ly in ime [90]. The o iginal SimPoin me hodology spends a signi ican amoun
o ime in unc ional simula ion be ween simula ion poin s. By choosing simula ion
poin s ea ly in ime, he amoun o unc ional simula ion leading up o he la es
simula ion poin is signi ican ly educed.
The Sampling Mic oa chi ec u e Simula ion (SMARTS) amewo k [121], p oposed
by Wunde lich e al., swi ches pe iodically be ween wa mup, de ailed simula ion
and simula ion in as - o wa d mode, as illus a ed in Figu e 2.12. Du ing a wa mup
phase, Wins uc ions a e simula ed in de ail, bu he simula ion s a is ics a e ig-
no ed. The eason o his is ha a he beginning o he simula ion, he simula ed
a chi ec u al s uc u es, like b anch p edic o s and caches, a e in hei ini ial, cold
s a e. Also, a e a as - o wa d phase, he mic o-a chi ec u al s a e is s ale and is
b ough up- o-da e du ing he wa mup phase.
Once he wa mup phase is comple e, he simula o s a s measu ing mic o-a chi ec u al
pe o mance me ics while simula ing Uins uc ions du ing he de ailed simula-
ion phase. A he end o he de ailed phase, he simula ion is swi ched o as -
o wa d mode, which execu es he simula ed p og am in a pu ely unc ional simu-
la ion mode wi hou upda ing he mic o-a chi ec u al s a e o he simula ion.
Wunde lich e al. epo wa mup in e als o up o W= 4000 ins uc ions
28
Chap e 2. Backg ound
.. .
.. .
U(k−1)−W
U
W
k
Wa mup De ailed Fas -Fo wa d
#Ins
FIGURE 2.12: Pe iodic swi ching be ween wa mup, de ailed and as -
o wa d simula ion modes in SMARTS
and de ailed simula ion in e als o U= 1000 ins uc ions. The leng h o he as -
o wa d in e al is se o a alue which esul s in a o al numbe o 10,000 in e -
als. Consequen ly, he o al numbe o ins uc ions simula ed in de ail, including
wa mup and de ailed simula ion, amoun s o 500,000 ins uc ions pe benchma k,
o less han 0.1% o he o al ins uc ion coun ac oss all benchma ks o he SPEC2000
benchma k sui e [59]. Simula ions using SMARTS a e 60 imes as e han ull de-
ailed simula ions, which shows ha simula ion speedup is mainly limi ed by he
speed o unc ional simula ion du ing he as - o wa d phases.
Wi h Tu boSMARTS [118], he same g oup p oposes an ex ension o SMARTS.
Tu boSMARTS elimina es he unc ional simula ion phases du ing he as - o wa d
in e als. In an ap io i s ep, Tu boSMARTS gene a es a checkpoin lib a y o he
simula ed p og am, which can a e wa ds be used o all simula ions o he p o-
g am. Be o e each wa mup in e al, he co ec a chi ec u al s a e is es o ed om
his checkpoin lib a y. The au ho s epo simula ion imes o less han 2 minu es
ac oss all SPEC2000 benchma ks.
Mul i-Th eaded Simula ion Sampling
The p e iously in oduced sampling echniques o simula ions o single- h eaded
a chi ec u es can no be di ec ly applied o simula ions o mul i- h eaded sys ems.
In a single- h eaded p og am, p og ess can be measu ed in e ms o commi ed in-
s uc ions. Howe e , his is gene ally no alid in mul i- h eaded p og ams. Di e -
en h eads o a mul i- h eaded p og am can p og ess a di e en a es, e.g. due o
he inhomogeneous na u e o he wo kload. Ano he example is he lack o ai ness
accessing sha ed sys em esou ces, e.g. when one h ead monopolizes he las -le el
cache. Finally, a h ead can be execu ing ins uc ions ha do no con ibu e o he
p og ess o he p og am, e.g. while spinning on a lock.
Fo he easons men ioned abo e, a any poin in ime, he di e en h eads ha e
ypically execu ed di e en numbe s o use ul ins uc ions in he pas . Hence, he
ins uc ion coun can no se e as a me ic o measu ing p og ess and iden i ying
common poin s in ime ac oss mul iple h eads. The sampled simula ion echniques
2.4. Accele a ion Techniques o A chi ec u al Simula ion
29
in oduced in Sec ion 2.4.2 ely on ins uc ion coun o measu e p og ess and de-
e mine phase bounda ies in simula ed p og ams. Ins ead, a echnique a ge ing
simula ion o mul i- h eaded p og ams mus measu e p og ess in e ms o cycles,
i.e. ime, which is he only common me ic ac oss all h eads. In he ollowing, we
p esen se e al echniques which a e based on his insigh .
Ca lson e al. [24] apply pe iodic ime-based sampling [5,29] o pa allel p o-
g ams. Sho , de ailed simula ion phases ake u ns wi h longe as - o wa d phases,
esul ing in an o e all educ ion o simula ion ime. The du a ion o de ailed- and
as - o wa d in e als is de e mined based on he pe iodici ies o he simula ed ap-
plica ion and a e measu ed in e ms o cycles.
Du ing de ailed simula ion, he pe o mance me ics o in e es a e measu ed
in a iming simula ion o he di e en h eads and hei in e ac ions wi h one an-
o he . Du ing as - o wa d phases, Ca lson e al. employ unc ional simula ion. All
memo y accesses a e simula ed by simula ion models o he memo y hie a chy, en-
su ing ha he simula ed caches a e always in a ep esen a i e s a e a he ansi ion
o de ailed simula ion. As he au ho s igh ully poin ou , i is possible o employ
mo e elabo a e wa mup echniques be o e de ailed simula ion and hus elimina e
he need o unc ional cache wa mup du ing as - o wa ding.
As s a ed ea lie , di e en h eads o a mul i- h eaded p og am can p og ess
a di e en a es. De ailed simula ion is used o model each h ead’s in e ac ion
wi h he sys em esou ces and also i s in e ac ion wi h o he h eads. The e o e, he
p og ess o each h ead is modeled co ec ly. Fas - o wa ding he simula ion using
unc ional simula ion a a cons an IPC, as i is ypical in a chi ec u al simula o s,
would esul in inco ec h ead p og ess. A he beginning o he nex de ailed
simula ion in e al, he h ead in e lea ing would no be he same as i he en i e
simula ion would ha e been un in de ail. Ca lson e al. minimize his p oblem by
as - o wa ding each h ead a he a e age IPC o he las de ailed simula ion in e -
al. The echnique achie es an a e age simula ion speedup o 2.9 wi h an a e age
execu ion ime e o o 3.5%.
One o he p ima y ad an ages o he echnique is ha i is no ied o a pa icula
p og amming model. Howe e , i is no di ec ly applicable o ask-based p og ams.
The sampling pa am e s a e de e mined ap io i in a p o iling un. Du ing simu-
la ion, he co ec sampling pa am e s can change due o di e en decisions o he
dynamic schedule .
Ba ie Poin [23], also p oposed by Ca lson e al., i s analyzes mic o-a chi ec u e
independen pe o mance me ics o p og am sec ions be ween global ba ie s. A -
e wa ds, he SimPoin in as uc u e [107] iden i ies clus e s o hose in e -ba ie
egions wi h simila pe o mance. Simula ion ime is educed by simula ing only
one ep esen a i e ou o each clus e . Ba ie Poin exploi s he ac ha all h eads
30
Chap e 2. Backg ound
synch onize a a global ba ie and, hence, a he beginning o each in e -ba ie e-
gion a e aligned co ec ly.
Ins ead o cha ac e izing p og am phases based on BBVs, Ba ie Poin uses sig-
na u e ec o s (SVs). SVs a e a combina ion o BBVs and s ack dis ance his og ams. The
s ack dis ance is he numbe o memo y accesses o unique add esses be ween wo
accesses o he same memo y loca ion. A s ack dis ance his og am is a his og am
o he s ack dis ances obse ed be ween he beginning o he p og am and he end
o each in e -ba ie egion. Thus, s ack dis ance his og ams cap u e he his o ic be-
ha io o all p e ious in e -ba ie egions. In he case o Ba ie Poin , he bins o
he s ack dis ance his og am a e spaced acco ding o powe s o wo. This allows
o be e esolu ion o smalle s ack dis ances. Finally, o each in e -ba ie egion,
he BBV and he s ack dis ance his og am a e combined, ei he by addi ion o by
conca ena ion, o o m an SV.
Once he SVs a e gene a ed, hey a e clus e ed using he exis ing, publicly a ail-
able SimPoin ool [107]. SVs, in con as o BBVs, cap u e he his o ic s a e o he
memo y hie a chy. The e o e, hey allow de ec ing in e -ba ie egions wi h di e -
en pe o mance due o a di e en s a e o he memo y hie a chy, which would go
unde ec ed when only using BBVs.
Finally, one ep esen a i e in e -ba ie egion o each clus e is simula ed in de-
ail, and he o e all p og am pe o mance is ex apola ed by applying weigh s o
he pe - egion simula ion s a is ics. Ba ie Poin achie es an a e age simula ion
speedup o 24.7 wi h an a e age execu ion ime e o o 0.9%. In compa ison o
he a o emen ioned echnique a ge ing gene al pa allel applica ions, his shows
ha le e aging he na u e o a pa allel p og amming model can lead o signi ican ly
highe simula ion speedup.
Task-based p og ams aim a a oiding global ba ie s. Ins ead, synch oniza ion
is achie ed by dynamically scheduling di e en ask ins ances in a alid execu ion
o de . Fo his eason, he Ba ie Poin echnique is no gene ally applicable o ask-
based p og ams.
In hei Mul ile el Simula ion echnique, Gonzalez e al. [51] iden i y ep esen-
a i e phases (CPU bu s s) o p og ams implemen ed in MPI p og amming model.
These ep esen a i e CPU bu s s a e iden i ied du ing p o iling be o e simula ion
and a e a e wa ds simula ed in de ail. The ob ained pe o mance in o ma ion is
hen used o ex apola e he o e all p og am pe o mance.
2.4. Accele a ion Techniques o A chi ec u al Simula ion
31
Wa mup in Mul i-Th eaded Simula ions
Wa mup o single- h eaded simula ions has been ex ensi ely s udied [38,43,58,
107,117,121]. The echnique used by Ba ie Poin combines wo exis ing me hod-
ologies, namely unc ional wa mup [38] and checkpoin ing [117]. The esul ing ech-
nique uses dynamic ins umen a ion o ack he mos ecen memo y accesses on a
pe -cache-line basis. A e wa ds, his in o ma ion is used o es o e cache s a e a
he beginning o each de ailed simula ion in e al.
Luo e al. [124] p opose Sel -Moni o ed Adap i e Cache Wa m-Up (SMA), a ech-
nique no equi ing p o iling be o e simula ion. E e y cache in a simula ed sys em
moni o s i s ac ion o used lines o e ime. When his po ion passes a h eshold o
emains cons an du ing a ce ain ime, a cache is conside ed wa med. The au ho s
e alua e SMA o single- h eaded simula ions. Howe e , no undamen al easons
a e impeding i s applicabili y o mul i- h eaded simula ions.
2.4.3 S a is ical Simula ion
De ailed simula ion o a ull p og am execu ion can be e y ime-consuming. S a-
is ical models aim o educe simula ion ime by c ea ing a syn he ic wo kload wi h
he same s a is ical p ope ies as he dynamic ins uc ion s eam o a ull p og am
execu ion.
The HLS simula o [85] c ea es a s a is ical p o ile o an applica ion while simu-
la ing i in an a chi ec u al simula o . Fo each s a ic ins uc ion o he applica ion,
he p o ile con ains he unc ional uni equi emen s, miss- a e dis ibu ions he in-
s uc ion causes a he di e en cache le els, and he dis ance o o he ins uc ions
on which he cu en ins uc ion depends. This analysis is done on a pe -basic-block
basis. The b anch ins uc ion a he end o each basic block is assigned he p e-
dic abili y alue obse ed du ing p o iling in he a chi ec u al simula o . Finally,
he ins uc ion p o ile is simula ed epe i i ely, un il he simula ed IPC con e ges.
Nussbaum e al. p opose a s a is ical pe o mance model o supe scala p o-
cesso s [87]. Fi s , an ins uc ion ace o he applica ion o be simula ed is cap-
u ed du ing de ailed simula ion in an a chi ec u al simula o . A e wa ds, he in-
s uc ion mix, namely he pe cen ages o dynamic ins uc ions belonging o each
ou o 14 di e en ins uc ion ypes, is de e mined. A he same ime, a dis ibu-
ion o he leng hs o he dependency chains be ween dynamic ins uc ions is de-
e mined. Finally, a syn he ic ins uc ion ace wi h he same ins uc ion mix and
in e -ins uc ion dependency dis ibu ions. This ace is hen used as an inpu o an
a chi ec u al simula o .
The a o emen ioned s a is ical simula ion echniques use mic o-a chi ec u e de-
penden in o ma ion o cap u e he beha io o he simula ed b anch p edic o . I

32
Chap e 2. Backg ound
he pa ame e s o he b anch p edic o changes, he applica ion p o ile needs o be
egene a ed. Eeckhou e al. [44] imp o e on his model by using s a is ical low
g aphs. A s a is ical low g aph o o de np edic s he ou come o a b anch, de-
pending on he ou comes o he las nexecu ions o ha b anch, simila o he way
ac ual b anch p edic o s wo k.
2.4.4 Analy ical Models
Analy ical models ollow he goal o a oiding a chi ec u al simula ion and ins ead
ely on a se o analy ical exp essions o p edic he pe o mance o a sys em execu -
ing a speci ied wo kload. The wo majo classes o analy ical pe o mance models
a e mechanis ic and empi ical models. Mechanis ic models a e buil in a cons uc-
i e way wi h equa ions desc ibing how he di e en a chi ec u al s uc u es and
hei in e ac ion a ec pe o mance. Mechanis ic models, he e o e, allow easoning
abou why a pa icula design is be e o wo se han ano he . Empi ical models, on
he o he hand, a e usually models de eloped in he ield o machine lea ning e.g.
a i icial neu al ne wo ks o suppo ec o machines. These models a e ained on
a se o de ailed e e ence simula ions.
The In e al Model [16], p esen ed by B eughe e al., models a p og am’s execu-
ion on a hypo he ic sys em by assuming an execu ion a he designed s eady-s a e
IPC. The execu ion a his maximum sus ainable IPC is dis up ed by miss e en s.
B eughe e al. dis inguish be ween miss e en s occu ing in he p ocesso on -end,
e.g. b anch misp edic ions and ins uc ion cache misses, and miss e en s aking
place in he back-end, e.g. las -le el cache misses. While misses in he on -end a e
se ialized, long-la ency misses in he back-end, e.g. DRAM accesses, can pa ially
o e lap. The in e al model p edic s he o e all pe o mance o an applica ion ex-
ecu ed on he modeled sys em. I does no ake in o accoun he e ec s o single
ins uc ions.
Genb ugge e al. ex end his model o simula ions o mul i- h eaded sys ems in
hei In e al Simula ion me hodology [48]. In con as o he o iginal In e al Model,
In e al Simula ion akes in o accoun he e ec s o single ins uc ions and how hey
in e ac wi h each o he in sha ed sys em esou ces.
In e al Simula ion uses one model ins ance pe simula ed p ocesso co e. A
unc ional simula o supplies he pe -co e models wi h ins uc ions. In he absence
o miss e en s, each model p ocesses ins uc ions a a a e equal o he p ocesso
wid h. Dedica ed simula ion models simula e he occu ence o miss e en s. E.g., a
b anch p edic o model p edic s i a b anch missp edic ion occu s. I a miss e en
happens, he in e al model o he co esponding co e accoun s o he la ency in o-
duced by he e en . No e ha , since he applica ion p o ile is gene a ed on- he- ly, i
is egene a ed o each combina ion o e alua ed a chi ec u e and applica ion.
2.4. Accele a ion Techniques o A chi ec u al Simula ion
33
Van den S een e al. [115] p opose an ex ension o he In e al Simula ion model.
In e al Simula ion equi es mic o-a chi ec u e dependen inpu da a, namely he
numbe o cache misses pe cache le el, he numbe o b anch p edic o misses and
he amoun o memo y-le el pa allelism (MLP). The app oach p esen ed by Van den
S een e al. elimina es he mic o-a chi ec u e dependen pa s o he model inpu .
Ins ead, hey use a mic o-a chi ec u e independen applica ion p o ile and gene -
a e he mic o-a chi ec u e dependen elemen s o he model inpu using analy ical
models o caches, b anch p edic o s and MLP.
Caches a e modeled using S a S ack [46], a echnique o modeling a bi a ily
sized LRU caches. S a S ack’s model equi es he euse dis ances o he modeled ap-
plica ion as an inpu . The euse dis ance is he numbe o memo y accesses be ween
wo accesses o he same cache line. Based on he euse dis ance p o ile, S a S ack
p edic s an applica ion’s cache miss a e.
B anch p edic o s a e modeled using he Linea En opy model [91], p oposed by
Pes el e al. Fi s , he applica ion o be modeled is execu ed in a p o ile which, o
each s a ic b anch ins uc ion and each his o y o pas b anches, coun s he num-
be o imes he co esponding b anch is aken and no aken. This in o ma ion
is a e wa ds used o calcula e each b anch’s en opy. A linea model p edic s he
pe -b anch miss a e o se e al di e en b anch p edic o s based on he pe -b anch
en opy.
MLP is he numbe o simul aneously ou s anding LLC misses, i.e. he numbe
o memo y accesses which can be se ed by he DRAM subsys em in pa allel. Van
den S een e al. p opose an MLP model, which sepa a es MLP calcula ion in o a
ac ion s emming om LLC cold misses and a po ion a ising om capaci y and
con lic misses.
In Chap e 5, we p esen TaskPoin , a sampled simula ion me hodology o ask-
based p og ams. We show how we use a modi ied e sion o he model p oposed
by Van den S een e al. o imp o e he accu acy o TaskPoin .
Casas e al. p opose an analy ical pe o mance model o MPI applica ions [28].
Fi s , an execu ion ace o he applica ion is gene a ed which con ains ime-s amped
in o ma ion abou he occu ence o MPI calls o ha dwa e pe o mance coun e s,
e.g. he numbe o execu ed loa ing poin ope a ions pe second. This in o ma ion
is con e ed in o a ime se ies. By applying Disc e e Wa ele T ans o m o his ime
se ies, Casas e al. iden i y pe iodic beha io in he applica ion and il e he appli-
ca ion ace o size educ ion. A e wa ds, hey apply an analy ical model o p edic
he applica ion’s speedup o di e en numbe s o p ocesso s.
34
Chap e 2. Backg ound
2.4.5 Reduced Inpu Se s
A common way o educe simula ion ime is o simula e benchma k execu ions us-
ing smalle inpu se s unde he assump ion ha he pe o mance cha ac e is ics o
he benchma k a e no a ec ed. Howe e , changing he inpu se equen ly changes
impo an p ope ies o a benchma k, e.g. he ins uc ion mix o he amoun o pa -
allelism which can be exploi ed by a mul i-co e sys em.
KleinOsowski e al. p esen MinneSPEC [70,71], a modi ied inpu se o he
SPEC2000 benchma k sui e [59]. The au ho s show, ha ac oss all benchma ks ei-
he he pe cen ages o calls o he di e en unc ions wi hin a benchma k o he
ins uc ion mix do no ma ch he alues obse ed when using he e e ence inpu se .
Hsu e al. [62] con i m ha he SPEC2000 benchma ks show di e en pe o mance
o di e en inpu se s.
Sou he n e al. [110] p esen a s udy o he scalabili y o he benchma ks cons i-
u ing he PARSEC benchma k sui e [13]. All PARSEC benchma ks can be execu ed
wi h al e na i e inpu se s which a e designed o a chi ec u al simula ion. How-
e e , Sou he n e al. show ha some benchma ks, when using he la ges simula ion
inpu , achie e a scalabili y se e al imes lowe han he scalabili y obse ed o he
na i e execu ion inpu .
Fo he easons men ioned abo e, i is o en impossible o educe simula ion
ime by educing he inpu size wi hou signi ican ly a ec ing a benchma k’s pe -
o mance cha ac e is ics. The e o e, in he scope o his wo k, we de elop se e al
echniques o simula ion ime educ ion based on sampling. These echniques a e
p esen ed in Chap e s 5and 6.
2.4.6 Pa alleliza ion
On a pa allel sys em, a chi ec u al simula ions can be pa allelized in a i ial way by
execu ing mul iple ins ances o a single- h eaded simula o simul aneously. While
his echnique does no educe he ime equi ed o a single simula ion, i can signi -
ican ly inc ease simula ion h oughpu . This is especially he case du ing he ea ly
phase o design space explo a ion when ens o hund eds o housands o simula-
ions need o be execu ed.
The e a e also app oaches o pa allelizing he simula o i sel . A i s glance,
a chi ec u al simula o s used o simula e mul i-co e designs seem a na u al i o
pa alleliza ion on a mul i-co e sha ed-memo y hos . Ideally, each co e o he hos
would handle one o mo e simula ed co es. Howe e , h eads unning on di e -
en co es o he simula ed sys ems compe e o sha ed sys em esou ces. The e o e,
he di e en simula ion h eads a e equen ly o ced o synch onize, limi ing scal-
abili y. In o de o ci cum en his p oblem, pa allel simula o s equen ly employ
2.4. Accele a ion Techniques o A chi ec u al Simula ion
35
echniques o elax he synch oniza ion equi emen s be ween di e en simula o
h eads.
The Wisconsin Wind Tunnel II (WWT2) [86] execu es di e en simula ed co es
in di e en h eads on he hos sys em. En o cing cycle-by-cycle synch oniza ion
among he simula ed co es implies a signi ican synch oniza ion o e head, which
esul s in low simula ion speed imp o emen o pa allel simula ions. WWT2 spli s
simula ion ime in o quan a, du ing which p ocesso s do no a ec each o he ’s
s a e. Quan a a e execu ed in pa allel. A he end o each quan um, he simula ed
p ocesso s synch onize. WWT2’s pa alleliza ion app oach is conse a i e, i.e. i al-
ways main ains empo al causali y be ween he simula ed co es.
SlackSim [32] allows he simula ed ime o di e ge by a use -speci ied numbe o
cycles. This empo al slack educes synch oniza ion o e head and allows o be e
simula ion scalabili y. The main di e ence o WWT2 is ha di e en simula ed co es
a e only h o led i hey di e ge by mo e han he use -speci ied slack, an app oach
which is no conse a i e. The au ho s o SlackSim epo a simula ion e o o up
o 0.7% o a maximum slack o 100 cycles. Fo unlimi ed slack, he e o amoun s
o up o 4% a only sligh ly be e simula ion speedup, compa ed o a slack o 100
cycles.
2.4.7 Ha dwa e Accele a ion
The main limi o he scalabili y o a chi ec u al simula o s is synch oniza ion be-
ween simula ion models o igh ly synch onized sys em componen s, e.g. di e en
co es, cache memo ies and he on-chip in e connec . In a ha dwa e ins ance o a
sys em, synch oniza ion be ween sys em componen s happens in pa allel ia dedi-
ca ed signal lines, all o which can ope a e in pa allel. In an a chi ec u al simula o ,
synch oniza ion is achie ed wi h he help o so wa e echniques, i.e. locks and
semapho es. As a esul , many e en s which happen in pa allel in a eal sys em a e
p ocessed sequen ially by he simula o .
The e a e p oposals o using ha dwa e accele a ion o ci cum en his p oblem.
A p omising candida e is Field-P og ammable Ga e A ays (FPGAs). FPGAs consis o
gene ic logic, s o age elemen s and a con igu able in e connec ab ic. FPGA en-
do s p o ide ools o syn hesize RTL desc ip ions and gene a e a bi s eam wi h he
con igu a ion da a o he FPGA. The amoun o esou ces on a single FPGA scales
wi h Moo e’s Law, as do he sys ems modeled by compu e a chi ec s. The e o e,
FPGAs a e a p omising pla o m o a chi ec u al simula ion.
The FPGA-Accele a ed Simula ion Technologies (FAST) amewo k [34] spli s he
simula ion o a p og am execu ing on a single-co e sys em in o wo pa s, namely
unc ional and iming simula ion. Func ional simula ion o he simula ed p og am
is pe o med in so wa e using QEMU. The dynamic ins uc ion s eam execu ed by
42
Chap e 3. Expe imen al Se up
ROB, acco ding o he issue wid h o he simula ed p ocesso . When he ROB is ully
occupied, he issue s age is s alled.
When a memo y ins uc ion eaches he ail o he ROB, TaskSim c ea es a mem-
o y eques and sends i o he CPU-side po o he co esponding co e’s L1 cache.
De ailed iming models o caches, on-chip in e connec s uc u es and DRAM sim-
ula e he pa h o he memo y eques h ough he memo y hie a chy. E en ually, a
esponse message a i es a he CPU model whe e he eques o igina ed. The mem-
o y ins uc ion is commi ed and lea es he ROB. A e wa ds, non-memo y ins uc-
ions a e commi ed a he speci ied commi a e, un il he nex memo y ins uc ion
is encoun e ed o he simula ion inishes.
In con as , TaskSim’s abs ac CPU model only accoun s o he du a ion, mea-
su ed in cycles, o compu a ion phases and calls o he un ime sys em. In he ex-
is ing implemen a ion, TaskSim eads a ask ins ance’s cycle coun om he applica-
ion ace. In Chap e 5we ex end TaskSim wi h a as - o wa d mechanism capable
o simula ing execu ion a an a bi a y, use -de ined IPC. Fu he mo e, we add sup-
po o swi ch be ween di e en simula ion modes a un ime.
3.4 Benchma ks
In his sec ion, we gi e an o e iew o he benchma ks used o he e alua ion o
he simula ion me hodologies de eloped in he scope o his hesis. Fi s , we p esen
he ask-based benchma ks used in ou e alua ion o TaskPoin . A e wa ds, we
in oduce he hyb id (MPI+OpenMP and MPI+OmpSs) benchma ks used o ou
e alua ion o MUSA.
3.4.1 Task-based Benchma ks
In ou e alua ion o TaskPoin in Chap e 5, we in es iga e a se o 27 ask-based pa -
allel benchma ks implemen ed using he OmpSs p og amming model. The bench-
ma ks and hei key cha ac e is ics a e lis ed in Tab. 3.2. They co e a b oad ange
o algo i hms widely used in scien i ic HPC applica ions and include p og ams wi h
di e en compu e- o-memo y a ios, di e en memo y access pa e ns and di e en
amoun s o pa allelism and synch oniza ion. Benchma ks 1 o 11 ha e been success-
ully used in p e ious wo ks o e alua e HPC clus e s [93,94]. Benchma ks 12 o 16
a e in-house implemen a ions o algo i hms equen ly ocu ing in scien i ic com-
pu ing. Finally, benchma ks 17 o 27 a e pa o he PARSEC benchma k sui e [13],
which is widely used o e alua e he pe o mance o pa allel sys ems.
Whene e possible, we gene a e 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
use he simla ge inpu se s. Table 3.2 lis s he numbe o ask ypes and ask ins ances

3.4. Benchma ks
43
and he ime equi ed o a de ailed simula ion o he en i e benchma k o 1 and 64
simula ed h eads using he TaskSim simula o .
We classi ied he benchma ks acco ding o whe he hey a e compu e-in ensi e
o no . Because he wo king se s o all concu en ly execu ing ask ins ances i in o
he las le el cache, we conside ed he ollowing benchma ks as compu e-in ensi e:
2d-con olu ion,3d-s encil,a omic-mon e-ca lo-dynamics,me ge-so ,dense-ma ix-mul iplica ion,
luidanima e and swap ions.
We op imized compu e-in ensi e benchma ks by adjus ing he ask wo king se
o i in o he on-chip las -le el cache. This is one o he mos s aigh o wa d op-
imiza ions applied by p og amme s in blocked nume ical algo i hms. The mos
cache cons ained con igu a ion is he Co ex-A9 unning wi h ou h eads. The e-
o e, we adjus ed he ask wo king se o i in o a qua e o he las -le el cache
in he Co ex-A9 chip. We use he same con igu a ion o all pla o ms o ha e he
same basis o compa ison.
Fo he emaining benchma ks, we con igu e he ask g anula i y o he esul -
ing ask ins ances o be a leas 100,000 ins uc ions long. By doing so, we ensu e
ha he ime spen in ask execu ion is signi ican ly la ge han he ime spen in
pe o mance measu emen code o in he un ime en i onmen . The numbe o ask
ins ances pe applica ion is adjus ed o a la ge enough numbe so he e is enough
pa allelism o use all h eads a all imes.
3.4.2 Hyb id MPI+OpenMP Benchma ks
The NAS pa allel benchma ks [9] ha e been widely used o e alua e he pe o mance
o HPC sys ems. In his hesis, we use he Mul izone e sions [116] o he NAS pa -
allel benchma ks BT,SP and LU, named BT-MZ,SP-MZ and LU-MZ, espec i ely.
All h ee benchma ks compu e he solu ion o he uns eady, comp essible Na ie -
S okes equa ions o a h ee-dimensional p oblem. To his end, he di e en bench-
ma ks employ di e en ma hema ical sol e s. The benchma ks pe o m mul iple i -
e a ions, whe eas he numbe o i e a ions depends on he inpu size. Each i e a ion
ep esen s a ime s ep, a he end o which neighbo ing zones pe o m a bounda y
exchange.
All h ee NAS mul i-zone benchma ks pa i ion he global p oblem domain in o
blocks e e ed o as zones. Pa i ioning is done along he ho izon al axes. LU-MZ
and SP-MZ wo k wi h zones o equal size. In BT-MZ he sizes o adjacen zones
app oxima ely o m a geome ic se ies. In o he wo ds, mo ing along one o he
ho izon al axes, he dis ance be ween adjacen zone bounda ies g ows by an app ox-
ima ely cons an ac o . Du ing execu ion, di e en zones a e ypically p ocessed by
MPI p ocesses unning on di e en clus e nodes. Each MPI p ocess can u he
exploi pa allelism by elying on OpenMP o in a-node pa alleliza ion.
44
Chap e 3. Expe imen al Se up
TABLE 3.2: Task-based pa allel benchma ks used o he e alua ion o TaskPoin
# Benchma k # Task ypes # Task ins ances Simula ion ime [h:min]P ope ies
1 Th ead 64 Th eads
1 2d-con olu ion 1 16384 31:37 59:34 Ke nel: s ided memo y accesses
2 3d-s encil 1 16370 9:12 40:51 Ke nel: s ided memo y accesses
3 a omic-mon e-ca lo-dynamics 1 16384 8:38 15:16 Ke nel: emba assingly pa allel
4 dense-ma ix-mul iplica ion 1 17576 70:14 127:10 Ke nel: high da a euse, compu e bound
5 8 25024 31:57 110:47 Ke nel: a iable s ide memo y accesses
6 his og am 1 16384 6:02 12:13 Ke nel: a omic ope a ions
7 me ge-so 4 20480 12:39 33:23 Ke nel: ecu si e ask ins an ia ion
8 n-body 2 25000 8:15 12:31 Ke nel: i egula memo y accesses
9 educ ion 2 16384 1:51 5:15 Ke nel: pa allelism dec eases o e ime
10 spa se-ma ix- ec o -mul iplica ion 1 1024 0:33 1:26 Ke nel: load imbalance, memo y bound
11 ec o -ope a ion 1 16400 24:25 191:00 Ke nel: egula , memo y bound
12 spa seLU 11 22058 7:25 17:17 Decomposi ion o la ge, spa se ma ices
13 cholesky 4 19600 33:42 59:29 Decomposi ion o He mi ian posi i e-de ini e ma ices
14 jacobi 9 20480 19:07 19:54 Jacobi i e a i e me hod
15 kmeans 6 16337 75:21 141:02 Clus e ing based on Lloyd’s algo i hm
16 knn 2 18400 31:28 65:27 Ins ance-based machine lea ning algo i hm
17 blackscholes 2 24500 8:42 17:19 Op ion p ice calcula ion
18 body ack 7 21439 15:24 31:28 Human body acking wi h mul iple came as
19 canneal 1 16384 11:13 29:38 Cache-awa e simula ed annealing
20 dedup 4 15738 10:08 23:32 Deduplica ion: combina ion o global and local comp ession
21 acesim 12 20086 15:13 22:15 Physical modeling o human ace
22 e e 6 12288 58:34 115:22 Image simila i y sea ch
23 luidanima e 9 8225 25:15 46:03 Simula ion o incomp essible luids
24 eqmine 7 1932 23:52 34:13 F equen Pa e n G ow h me hod o F equen I em Mining
25 s eamclus e 10 14656 21:09 37:41 Online clus e ing algo i hm
26 swap ions 1 16384 29:27 70:25 Mon e-Ca lo simula ion o calcula e swap ion p ices
27 x264 3 383 121:47 122:25 Video comp ession acco ding o H.264 s anda d
3.5. Pe o mance Measu emen in Na i e Execu ion
45
Besides he NAS mul i-zone benchma ks, we use he HYDRO and SPECFEM3D
p oxy applica ions. In he ollowing, we summa ize he key p ope ies o all hyb id
benchma ks used in his hesis:
•BT-MZ employs a block idiagonal sol e based on Gaussian elimina ion.
Due o he i egula spacing be ween zones, he o al size o he la ges zone
is app oxima ely 20 imes la ge han he size o he smalles zone, esul ing in
di e en amoun s o wo k assigned o di e en MPI p ocesses. This makes i
di icul o achie e good load balance and, hus, high pa allel e iciency.
•SP-MZ decomposes he p oblem domain in o equally-sized zones, esul ing
in app oxima ely he same amoun o wo k pe MPI p ocess. The numbe o
zones inc eases wi h he inpu size. This makes i easie o balance load ac oss
di e en MPI p ocesses. SP-MZ uses a scala pen adiagonal sol e .
•LU-MZ uses a lowe -uppe symme ic Gauss-Seidel sol e [122]. In con as o
BT-MZ and SP-MZ, he numbe o zones in LU-MZ is limi ed o 16. The e o e,
in o de o scale o a la ge numbe o p ocesso s, LU-MZ needs o ely on in a-
node sha ed-memo y pa allelism.
•The HYDRO benchma k [75] is a p oxy applica ion based on he RAMSES ap-
plica ion [112]. RAMSES uses echniques om compu a ional luid dynamics
o model galaxy o ma ion. HYDRO cap u es he key pe o mance cha ac e -
is ics o RAMSES, bu a signi ican ly less code complexi y. RAMSES employs
adap i e mesh e inemen o ebalance he compu a ion as he mass dis ibu-
ion in he simula ed uni e se e ol es. HYDRO, on he o he hand, assumes a
ixed ca esian mesh.
•SPECFEM3D [72] is an applica ion o modeling seismic wa e p opaga ion.
SPECFEM3D uses he con inuous Gale kin spec al-elemen me hod o simu-
la e o wa d and adjoin seismic wa e p opaga ion on a bi a y uns uc u ed
hexahed al meshes.
3.5 Pe o mance Measu emen in Na i e Execu ion
In Chap e 4, we in es iga e he pe o mance p edic abili y o ask-based p og ams.
We show, ha pe o mance p edic abili y is ela ed o pe o mance egula i y. We
measu e pe o mance egula i y using ha dwa e pe o mance coun e s.
3.5.1 Ha dwa e Pe o mance Coun e s
Mode n p ocesso s include dedica ed ha dwa e o coun ing pe o mance- ela ed
e en s occu ing in he p ocesso . This ha dwa e is e e ed o as he pe o mance
46
Chap e 3. Expe imen al Se up
moni o ing uni (PMU). The PMU can be con igu ed by he use o coun a a ie y
o e en s, e.g. he numbe o execu ed ins uc ions, elapsed CPU cycles, o hi s and
misses in he di e en cache le els o he b anch p edic o . The e en s moni o ed
by he PMU a e accessible ia a se o egis e s. The PMU egis e s can be accessed
only in p i ileged mode. S a ing wi h ke nel e sion 2.6.31, Linux includes ke nel
suppo in o de o access he PMU om use -space ia sys em calls.
The exac se o obse able PMU e en s and he numbe o simul aneously a ail-
able coun e egis e s depend on he p ocesso model. The PMU used in In el’s
Sandy B idge a chi ec u e ea u es 11 coun e egis e s, whe eas he numbe o coun-
e s on he ARM Co ex-A9 p ocesso is limi ed o 6. Thus, ou o he hund eds o
a ailable PMU e en s on a mode n p ocesso he a o emen ioned pla o ms can si-
mul aneously moni o up o 11 o 6, espec i ely.
Accessing he PMU ia sys em calls is a edious p ocess. Since pe o mance mea-
su emen code depends on he ISA and he exac p ocesso model, i is no po able.
The Pe o mance Applica ion P og amming In e ace (PAPI) lib a y [17] p o ides a laye
o abs ac ion decoupling pe o mance measu emen code om a chi ec u al imple-
men a ion de ails. PAPI de ines a se o e en s, many o which exis on all mode n
p ocesso s. As a esul , pe o mance measu emen code can in e ace wi h PAPI in
a consis en , a chi ec u e independen way, as long as he unde lying a chi ec u e
suppo s he measu ed e en s and p o ides enough coun e egis e s.
3.5.2 Pe o mance Measu emen o Task-Based P og ams
In Chap e 4, we in es iga e pe o mance egula i y o ask-based p og ams in na-
i e execu ion. We measu e cycle coun , ins uc ion coun and numbe s o L1 (da a),
L2 (da a) and L3 cache misses using ha dwa e pe o mance coun e s. To his end we
use he Me cu ium compile , which au oma ically inse s calls o a low-o e head in-
s umen a ion lib a y a he beginning and he end o each ask ins ance. In e nally,
his lib a y in e aces o he pe o mance coun e subsys em ia he PAPI lib a y.
In OmpSs, a ask ins ance can be suspended be o e i inishes execu ion. In pa -
icula , when a ask ins ance execu es a call o he un ime sys em, i is no gua an-
eed ha con ol is immedia ely e u ned o he calling ask ins ance. Ins ead, he
un ime sys em can schedule ano he ask ins ance o execu ion i s , and a e u n
o he o iginal ask ins ance in he u u e. The ins umen a ion lib a y used in his
wo k akes his in o accoun by main aining pe - ask-ins ance s a is ics.
47
Chap e 4
Execu ion Time P edic abili y o
Task-Based P og ams
4.1 In oduc ion
Mul i-co e sys ems a e in eg a ing an inc easing numbe o p ocesso co es on a
single chip. This makes i di icul o p og amme s o exploi he a ailable on-chip
h ead-le el pa allelism.
Task-based p og amming models allow he p og amme o speci y p og am pa s
as so-called asks. Tasks may execu e concu en ly and a e ypically ins an ia ed
many imes du ing execu ion. A un ime en i onmen dynamically maps ask in-
s ances o h eads. The in ui i e p og am pa i ioning imp o es p og ammabili y.
A he same ime, dynamic ask scheduling educes he inhe en synch oniza ion
cos s o o he sha ed memo y p og amming models hanks o a be e load balanc-
ing [3].
The ac ha all ins ances o he same ask ype consis o he same s a ic code
sugges s ha hey should exhibi simila pe o mance and execu ion ime and, he e-
o e, execu ion ime should be p edic able. In his chap e , we in es iga e he exe-
cu ion ime p edic abili y o ask-based p og ams based on pe o mance egula i y.
We ca y ou a pe o mance analysis on ou di e en s a e-o - he-a mul i-co e ma-
chines. Two machines a e based on ARM Co ex-A9 MPCo e and Co ex-A15 MP-
Co e mobile CPUs. The o he wo a e based on high-end In el Sandy B idge and
IBM POWER7 CPUs, espec i ely. This allows us o in es iga e i pe o mance eg-
ula i y depends on he a chi ec u e. We expec pe o mance a iabili y o inc ease
when inc easing he numbe o execu ion h eads compe ing o sha ed esou ces.
To his end, we analyze pe o mance a iabili y on a pe - ask-ins ance basis o
h ead coun s anging om one up o he numbe o co es on each machine. We
each simila conclusions o he di e en machines, bu ind ha a chi ec u es wi h
mo e agg essi e pe o mance op imiza ions show a highe pe o mance a iabili y.
We iden i y h ee sou ces o a iabili y ac oss ins ances o he same ask ype: (i)
inpu dependence, (ii) mul iple classes o beha io , and (iii) con en ion on accessing

48
Chap e 4. Execu ion Time P edic abili y o Task-Based P og ams
sha ed esou ces. Fo p og ams su e ing om esou ce con en ion, we in es iga e
how sha ing dec eases pe o mance and inc eases pe o mance a iabili y. We also
p esen a model based on linea in e pola ion o p edic execu ion ime o inpu de-
penden ask ypes. Fu he mo e, we use a clus e ing algo i hm o iden i y di e en
beha io s in he same ask ype. Using ou in e pola ion model and clus e ing algo-
i hm, we d ama ically inc ease he accu acy o execu ion ime p edic ion. P edic-
ion e o s o e 80% a e educed o less han 12% o inpu dependen cases and less
han 2% on he p esence o mul iple beha io s.
In his chap e , we make he ollowing con ibu ions:
•An analysis o pe o mance a iabili y ac oss ins ances o he same ask ype
in ask-based p og ams execu ing on mul i-co e sys ems. This analysis shows
he a iabili y on an ins ance-by-ins ance basis.
•A classi ica ion o he di e en sou ces o execu ion ime a iabili y on in-
s ances o he same ask ype.
•A low-complexi y model based on linea in e pola ion o p edic ing he exe-
cu ion ime o a ask ins ance as a unc ion o i s ins uc ion coun .
•The use o a clus e ing algo i hm o iden i y di e en classes o beha io in he
same ask ype. In ou example, we success ully classi y ask ins ances in o
clus e s, each o which exhibi s egula pe o mance.
4.2 Execu ion Time P edic abili y o Task-Based P og ams
Many pa allel implemen a ions o nume ical algo i hms decompose he p oblem
domain in o sub-domains called blocks o iles. In ask-based p og amming mod-
els he p og amme speci ies pa s o a p og am as wo k uni s called asks, each one
o pe o m a di e en ope a ion. A ask is usually ins an ia ed many imes, each
ins ance pe o ming he common ope a ion o he ask on a sepa a e block o ile.
Task ins ances can be scheduled o h eads whene e hey ha e hei dependencies
sa is ied. Typically, a h ead execu es many ask ins ances be o e eaching a syn-
ch oniza ion poin . Task-based p og amming models a e a p og amming pa adigm
elying on he exploi a ion o unc ional- and da a pa allelism. Fo backg ound on
di e en ypes o pa allelism we would like o e e o Chap e 2.2.3. Backg ound
on pa allel p og amming o sha ed-memo y sys ems is p o ided in Chap e 2.1.1.
The ac ha ins ances o he same ask ype consis o he same code leads us
o he assump ion ha hey consis o simila numbe s o ins uc ions, exhibi sim-
ila pe o mance and he e o e hei execu ion ime is p edic able. Howe e , his
assump ion u ns ou o be w ong in some cases. Figu e 4.1 shows he o al exe-
cu ion ime p edic ion e o o a se o ask based p og ams, assuming he ime o
4.3. E alua ion
49
he i s o he second execu ed ins ance o all ins ances o a ask ype. The e o
is calcula ed acco ding o Equa ion 4.1, wi h T he se o ask ins ances o he same
ask ype, CSample he cycle coun o he sample ask ins ance and Ci he cycle coun
o ask ins ance i. We only in es iga e ime spen in ask execu ion and igno e ope -
a ing sys em and un ime sys em o e heads.
E = 1−Pi∈TCSample
Pi∈TCi!·100% (4.1)
Be o e conduc ing ou de ailed analysis, we en ision h ee po en ial sou ces o
pe o mance a iabili y ha po en ially deg ade pe o mance p edic abili y:
•Inpu dependence: The beha io o a ask ins ance depends on he ask ins ance’s
inpu da a. An example is spa se algo i hms, in which ask ins ances pe o m
di e en amoun s o compu a ion o exhibi di e en memo y access pa e ns,
due o he na u e o he spa se inpu da a.
•Se e al ypes o beha io pe ask ype: Task ins ances o he same ype pe o m
one ou o se e al possible ypes o compu a ion. An example is ecu si e
algo i hms, in which some ask ins ances c ea e mo e child asks, while o he s
pe o m he ac ual compu a ion when he ecu sion e mina es.
•Con en ion on sha ed esou ces: Mul iple h eads in e e e wi h each o he when
accessing sha ed sys em esou ces. Di e en ins ances o he same ask ype
may su e om di e en deg ees o in e e ence caused by o he h eads un-
ning in he sys em and accessing sha ed esou ces. This includes sha ed caches,
in e connec s uc u es and memo y bandwid h.
4.3 E alua ion
The esul s o he expe imen s conduc ed in he scope o his chap e show ha ,
despi e he ob ious in ui ion, pe o mance can be i egula ac oss ins ances o he
same ask ype. This di ec ly a ec s execu ion ime p edic ion (shown in Figu e 4.1).
In his sec ion, we i s show he esul s o ou pe o mance analysis on a pe - ask-
ins ance basis. A e wa ds, we p esen a case o inpu dependen ask beha io and
p esen a model o es ima e he execu ion ime o a ask ins ance as a unc ion o i s
ins uc ion coun . We also show a case o mul iple classes o beha io wi hin a single
ask ype. We use a clus e ing echnique o dis inguish hese di e en classes o be-
ha io and imp o e execu ion ime p edic abili y. Finally, we explain how esou ce
sha ing a ec s pe o mance egula i y and analyze con en ion on di e en sha ed
esou ces in he memo y hie a chy.
50
Chap e 4. Execu ion Time P edic abili y o Task-Based P og ams
1212412481248
0
20
40
60
80
100
A15 A9 S.B. P7
2dcon olu ion
i s
second
1212412481248
A15 A9 S.B. P7
3ds encil
1212412481248
A15 A9 S.B. P7
a omicmon e
ca lodynamics
1212412481248
0
20
40
60
80
100
densema ix
mul iplica ion
1212412481248
his og am
1212412481248
me geso
1212412481248
0
20
40
60
80
100
nbody
1212412481248
educ ion
1212412481248
spa se
ma ix ec o 
mul iplica ion
1212412481248
0
20
40
60
80
100
ec o 
ope a ion
1212412481248
luid
anima e
1212412481248
swap ions
Th eadcoun
Pla o m
P edic ione o [%]
FIGURE 4.1: Pe cen e o when assuming he execu ion ime o he
i s / second execu ed ask ins ance o all ask ins ances o p edic
o al execu ion ime. Resul s shown o ou di e en machines (see
Tab. 3.1) and di e en h ead coun s.
4.3. E alua ion
51
4.3.1 Pe -Task-Ins ance Pe o mance Analysis
Figu e 4.2 shows boxplo s o he measu ed ins uc ions pe cycle (IPC) pe ask ype.
Each cha co esponds o one ask ype and shows he measu ed esul s on ou di -
e en pla o ms. Only one h ead pe co e is execu ed in each expe imen , which
limi s he con igu a ions o wo h eads (Co ex-A15), ou h eads (Co ex-A9), and
eigh h eads (In el Sandy B idge and IBM POWER7). The solid box con ains he
in e qua ile ange o he measu ed IPC alues o all ins ances o he espec i e ask
ype, i.e., 50% o he obse a ions a e wi hin his ange. The ho izon al line wi hin
he box indica es he median. The whiske s ex end om he 5 h o he 95 h pe -
cen ile. The lowe and uppe 5% o he measu ed IPC alues a e ea ed as ou lie s
and a e no shown in he plo .
Mos o he in es iga ed benchma ks only ha e one ask ype, whe eas me ge-
so ,n-body and educ ion ha e wo and luidanima e has eigh . The di e en ask
ypes o luidanima e show simila pe o mance a iabili y. The e o e, we limi ou
e alua ions o he ask ype Compu eFo cesMT, which accoun s o 40% o luidan-
ima e’s o al ins uc ion coun .
In ou esul s, we obse e wo gene al classes o beha io . The i s class con-
sis s o benchma ks o which IPC does no signi ican ly deg ade when inc easing
he numbe o execu ion h eads. This beha iou is exposed by he benchma ks
2d-con olu ion,a omic-mon e-ca lo-dynamics,me ge-so (bo h ask ypes), n-body (bo h
ask ypes), educ ion (bo h ask ypes), luidanima e (all ask ypes) and swap ions. We
make he impo an obse a ion ha 2d-con olu ion,a omic-mon e-ca lo-dynamics and
n-body ( ask ype 1) p esen a nea ly cons an IPC wi h e y low a iabili y. This
beha io is pe sis en ac oss he di e en pla o ms.
The second class o beha io consis s o he benchma ks, o which IPC deg ades
when inc easing he numbe o execu ion h eads. This phenomenon is known
as wo k ime in la ion [88]. In ou benchma k sui e, his beha io is exposed by
he benchma ks 3d-s encil,his og am,spa se-ma ix- ec o -mul ipli-ca ion and ec o -
ope a ion. Fo hese benchma ks, besides wo k ime in la ion, we also obse e an
inc easing pe o mance a iabili y. No e ha he a iabili y shown in Figu e 4.2 di-
ec ly ela es o he p edic ion e o shown in Figu e 4.1.
4.3.2 P edic abili y o I egula Beha io
In his subsec ion, we iden i y h ee sou ces o i egula beha io , namely inpu de-
pendence, mul iple classes o beha io pe ask ype and esou ce sha ing. We p e-
dic execu ion ime o ask ypes wi h inpu dependen beha io using an in e pola ion-
based model. Fo ask ypes wi h se e al classes o beha io we use a clus e ing

59
Chap e 5
Sampled Simula ion o Task-Based
P og ams
5.1 In oduc ion
Compu e a chi ec u e esea ch hea ily elies on simula ion. Inc easing design com-
plexi 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 e-
qui 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 de-
sign.
One echnique o educe simula ion ime is sampling. Sampled simula ion e-
duces 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 [107] o swi ch pe iodically be ween de ailed
and as - o wa ding mode in ime-based sampling [121].
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 e-
cen 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. [24] 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. [22]
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 synch 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 [79].
A ask-based p og amming model allows he p og amme o speci y p og am pa s
60
Chap e 5. Sampled Simula ion o Task-Based P og ams
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 dy-
namically 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 chap e , 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 exe-
cu 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 dynamically 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.
•We employ basic-block ec o s (BBVs) and clus e ing o iden i y classes o be-
ha io among ask ins ances o an applica ion. We show, how we (i) iden i y
mul iple classes o beha io among ask ins ances o he same ask ype and
(ii) me ge ask ins ances wi h simila beha io belonging o di e en ypes.
•We use an analy ical pe o mance model o imp o e simula ion accu acy du -
ing simula ion in as - o wa d mode. Ou app oach combines he speed o
analy ical models wi h he accu acy o de ailed simula ion.
5.2. Backg ound and Mo i a ion
61
•We e alua e TaskPoin simula ing 27 ask-based pa allel benchma ks, includ-
ing 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 chap e is o ganized as ollows. In Sec ion 5.2, we p o ide
backg ound and mo i a ion o ou wo k. In Sec ion 5.3, we p esen ou TaskPoin
me hodology. We e alua e TaskPoin in Sec ion 5.4. Finally, we conclude in Sec-
ion 5.5.
5.2 Backg ound and Mo i a ion
This sec ion p o ides backg ound on ask-based p og amming 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
27 ask-based pa allel benchma ks.
5.2.1 Pa allel P og amming Models
In adi ional pa allel p og amming models o sha ed memo y sys ems, like POSIX
Th eads [19], he p og amme explici 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 alle ia e load imbalance
and hus inc ease pa allel e iciency. When implemen ing a pa allel p og am us-
ing a ask-based p og 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 dynam-
ically 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 [79]. 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 [30,114].
In his wo k, we di e en ia e be ween ask ypes and ask ins ances. E e y ex-
ecu 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
62
Chap e 5. Sampled Simula ion o Task-Based P og ams
2dcon olu ion
3ds encil
a omicmon eca lo
dynamics
densema ix
mul iplica ion
his og am
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
20
10
0
10
20
IPC a ia ion[%]
2838
45
59
48
FIGURE 5.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
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.
5.2.2 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 27 bench-
ma ks. The in es iga ed benchma ks a e in oduced in Sec ion 3.4.1.
Di e en benchma ks, and e en di e en ask ypes o he same benchma k, gen-
e 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 5.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 al-
ues, 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 16 ou o 27 benchma ks pe o mance a ia ion lies wi hin
±5%.
We mo i a e TaskPoin based on he insigh ha pe o mance o ask-based p o-
g ams is, in many cases, egula ac oss ins ances o he same ask ype. Fo he
emaining cases, ou imp o ed e sion o TaskPoin au oma ically de ec s classes
o ask ins ances wi h simila beha io using basic-block ec o s and clus e ing. A
po en ial simula ion e o is compensa ed wi h a co ec ion ac o de i ed om pe -
o mance p edic ions ob ained om an analy ical pe o mance model.
5.2. Backg ound and Mo i a ion
63
...
#p agma omp ask
label( ask ype 1)
do_some hing();
...
#p agma omp ask
label( ask ype 2)
do_some hing_else();
...
...
#p agma omp ask
label( ask ype 1)
do_some hing();
...
#p agma omp ask
label( ask ype 2)
do_some hing_else();
...
Gene a e
BBVs Clus e BBVs
9 clus e s
KMeans
DBSCAN
1 clus e
Assump ion: Same ask ype → same beha io
o
P oblems:
Va ying beha io wi hin a ask clus e
Tasks wi h di e en beha io in he
same clus e
Duplica e wo k o simila beha io in
di e en ask ypes
Solu ions:
I egula ly shaped clus e s a e spli in o
mul iple clus e s
Tasks wi h di e en beha io end up in
di e en clus e s
Tasks wi h simila beha io a e me ged,
independen o ask ype
I egula ly shaped clus e s emain
Tasks wi h un ela ed beha io end up
in di e en clus e s
Tasks wi h simila beha io a e me ged,
independen o ask ype
(A) TaskPoin wi hou analy ical modeling. Task ins ances o he same
ype a e assumed o ha e simila beha io .
...
#p agma omp ask
label( ask ype 1)
do_some hing();
...
#p agma omp ask
label( ask ype 2)
do_some hing_else();
...
...
#p agma omp ask
label( ask ype 1)
do_some hing();
...
#p agma omp ask
label( ask ype 2)
do_some hing_else();
...
Gene a e
BBVs Clus e BBVs
9 clus e s
KMeans
DBSCAN
1 clus e
Assump ion: Same ask ype → same beha io
o
P oblems:
Va ying beha io wi hin a ask clus e
Tasks wi h di e en beha io in he
same clus e
Duplica e wo k o simila beha io in
di e en ask ypes
Solu ions:
I egula ly shaped clus e s a e spli in o
mul iple clus e s
Tasks wi h di e en beha io end up in
di e en clus e s
Tasks wi h simila beha io a e me ged,
independen o ask ype
I egula ly shaped clus e s emain
Tasks wi h un ela ed beha io end up
in di e en clus e s
Tasks wi h simila beha io a e me ged,
independen o ask ype
(B) TaskPoin wi h analy ical modeling. Classes o beha io a e iden i ied
using clus e ing.
FIGURE 5.2: O e iew o o iginal and imp o ed TaskPoin me hod-
ology. The imp o ed me hodology uses BBVs o de e mine classes o
simila beha io .
5.2.3 Iden i ying Rep esen a i e Task Ins ances
Ou analysis o pe o mance egula i y on a pe - ask- ype basis in Figu e 5.1 shows
ha , o many applica ions, ask ins ances o he same ask ype beha e simila ly
in e ms o pe o mance. The e o e, i is easonable o assume ha , in hose cases,
ins ances o he same ask ype can se e as pe o mance samples o one ano he .
Howe e , he igu e also shows ha some benchma ks expose a signi ican pe o -
mance a ia ion among ask ins ances. Examples a e me ge-so , , eqmine and
dedup. These applica ions equi e mo e sophis ica ed echniques o iden i y classes
o ask ins ances which can se e as samples o one ano he .
Basic-block ec o s (BBVs) [107] ha e been used in he pas o cha ac e ize phases
o a wo kload and iden i y ep esen a i e wo kload egions. A BBV is a ec o wi h
as many dimensions as he e a e s a ic basic blocks in he simula ed applica ion.
Each dimension con ains he numbe o execu ed dynamic ins uc ions o he co e-
sponding basic block du ing a ce ain ime in e al. In his wo k, we de e mine one
BBV pe execu ed ask ins ance.
Figu e 5.2a illus a es ou o iginal TaskPoin me hodology. The igu e shows he
BBVs o wo ask ypes o me ge-so . We apply andom p ojec ion o wo dimen-
sions o he BBVs o isualisa ion. Each ask ype consis s o wo clea ly dis inc
clus e s o BBVs, which expose di e en beha io and pe o mance a un ime. One
o his clus e s is eccen ically shaped A , wi h he esul , ha ask ins ances which
a e in he same clus e , bu a some dis ance w. . . each o he , show di e en pe -
o mance. Fu he mo e, ea ing bo h clus e s o a ask ype as i hey showed he
same pe o mance B , as in me ge-so , leads o a simula ion e o o mo e han 40%.

64
Chap e 5. Sampled Simula ion o Task-Based P og ams
Fu he mo e, each clus e obse ed in one ask ype is simila o a clus e in he
o he ask ype C , esul ing in duplica ed wo k du ing sampled simula ion. An
ideal clus e ing would consis in wo clus e s, each o which con aining wo o he
pai wise simila clus e s shown in Figu e 5.2a. This is achie ed by he ex ension o
TaskPoin we p esen in his pape . No e ha in Figu e 5.2a BBVs a e solely used o
he pu pose illus a ion.
Figu e 5.2b illus a es how we imp o e TaskPoin by applying BBVs and clus-
e ing o he iden i ica ion o di e en classes o ask ins ances in an applica ion.
To his end, we c ea e a BBV o each ask ins ance. I wo ask ins ances beha e
simila ly, hey ypically ha e simila BBVs. On he o he hand, ask ins ances wi h
dissimila beha io a e likely o also ha e dissimila BBVs. The igu e illus a es ha
KMeans ends o spli i egula ly shaped clus e s in o many sub-clus e s. In he case
o DBSCAN, ask ins ances which a e connec ed by a dense egion o o he ask in-
s ances a e clus e ed oge he . In his wo k, we chose o ely on DBSCAN clus e ing,
because a lowe numbe o clus e s equi es less de ailed simula ion and hus allows
o a highe simula ion speedup.
5.2.4 Analy ical Pe o mance Modeling
Figu e 5.2b illus a es ha clus e s o ask ins ances, as hey a e de ec ed by DB-
SCAN, can ha e asymme ic shape and la ge diame e A . I his happens, using a
sample o p edic he pe o mance o a ask ins ance, which is u he away in he
same clus e , in oduces a simula ion e o . We le e age he ela i e accu acy o an
analy ical model o co ec his e o du ing simula ion.
Analy ical pe o mance models ha e been ex ensi ely used o sequen ial ap-
plica ions [16,44,67,91]. As explained in Sec ion 2.4.4, analy ical models can be
classi ied in o empi ical and mechanis ic models. Empi ical models aim a cap u ing a
sys em’s beha io wi h machine lea ning echniques, e.g. suppo ec o machines
o a i icial neu al ne wo ks. While hey can achie e good accu acy, hey do no p o-
ide much insigh in o why a ce ain design achie es be e o wo se pe o mance
han ano he . Mechanis ic models employ ma hema ical o mulas o model he e -
ec o he key a chi ec u al pa ame e s on pe o mance. Mechanis ic models allow
o s udy he sou ces o pa icula ly good o bad pe o mance by simply compa ing
he con ibu ion o he di e en e ms o he model’s o mula. Since hey p o ide
mo e insigh in o he sou ces o pe o mance, in his wo k we use a mechanis ic
pe o mance model.
In his wo k, we use an analy ical pe o mance model p oposed by Van den
S een e al. [115]. The model is an ex ension o In e al Simula ion [48]. In e al
Simula ion equi es mic o-a chi ec u e dependen inpu da a, namely he numbe
o cache misses pe cache le el, he numbe o b anch p edic o misses and he
5.3. Sampled Simula ion o Task-Based P og ams
65
amoun o memo y-le el pa allelism (MLP). The app oach p esen ed by Van den
S een e al. elimina es he mic o-a chi ec u e dependen pa s o he model inpu .
Ins ead, hey use a mic o-a chi ec u e independen applica ion p o ile and gene -
a e he mic o-a chi ec u e dependen elemen s o he model inpu using analy ical
models o caches, b anch p edic o s and MLP.
Caches a e modeled using S a S ack [46], a echnique o modeling a bi a ily
sized LRU caches. S a S ack’s model equi es he euse dis ances o he modeled ap-
plica ion as an inpu . The euse dis ance is he numbe o memo y accesses be ween
wo accesses o he same cache line. Based on he euse dis ance p o ile, S a S ack
p edic s an applica ion’s cache miss a e.
B anch p edic o s a e modeled using he Linea En opy model [91], p oposed by
Pes el e al. Fi s , he applica ion o be modelled is execu ed in a p o ile which, o
each s a ic b anch ins uc ion and each his o y o pas b anches, coun s he num-
be o imes he co esponding b anch is aken and no aken. This in o ma ion is
a e wa ds used o calcula e each b anches en opy. A linea model p edic s he
pe -b anch miss a e o se e al di e en b anch p edic o s based on he pe -b anch
en opy.
MLP is he numbe o simul aneously ou s anding LLC misses, i.e. he numbe
o memo y accesses which can be se ed by he DRAM subsys em in pa allel. Van
den S een e al. p opose an MLP model, which sepa a es MLP calcula ion in o a
ac ion s emming om LLC cold misses. and a ac ion s emming om capaci y-
and con lic misses.
5.3 Sampled Simula ion o Task-Based P og ams
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 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 sam-
pling mechanism and policy allows o he in eg a ion o o he sampling policies
wi h low implemen a ion e o .
5.3.1 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 hodology o ask-based p o-
g 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 hodology, a simula o needs o ul il he
ollowing wo equi emen s:
66
Chap e 5. Sampled Simula ion o Task-Based P og ams
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
FIGURE 5.3: Ini ial wa mup, sampling, as - o wa ding and esam-
pling in TaskPoin
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 [6,14,
103], 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 .
5.3.2 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 ching be ween de ailed and as mode
only occu s be ween wo consecu i e ask ins ances.
Figu e 5.3 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 sim-
ula 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,
5.3. Sampled Simula ion o Task-Based P og ams
67
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 5.3).
Simula ion Wa mup
Be o e conduc ing pe o mance measu 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 sam-
pled simula ion is well-s udied [38,58,107,117,121,124]. In his hesis, we wa m
he simula ion by simula ing an empi ically 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 5.4.
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 (ap-
p oxima ely) he same as i he whole p og am was simula ed in de ail. Be o e e-
sampling, 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.
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
74
Chap e 5. Sampled Simula ion o Task-Based P og ams
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
FIGURE 5.8: E o and speedup o di e en sizes o sampling pe iod
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 hesis, 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 5.8 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
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, e-
sul 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 in-
s 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 Task-
Poin o pe iodic sampling wi h P= 250 and o lazy sampling (pe iodic sampling
wi h P=∞).
5.4.2 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 5.1, 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 5.9 shows execu ion ime e o and simula ion speedup o all in es iga ed
benchma ks, simula ed wi h he pa ame e s W= 2,H= 4 and P= 250.

5.4. E alua ion
75
0
2
4
6
8
10
Absolu ee o [%]
36.5
15.1
36.9
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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
10
20
30
40
50
60
70
80
Speedup
FIGURE 5.9: E o and speedup o pe iodic sampling; high-
pe o mance a chi ec u e; 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 36.9% o me ge-so simula ed wi h 64 h eads.
We a ibu e his e o o he ac ha each o me ge-so ask ypes has wo dis inc
classes o beha io , as s a ed ea lie . La e on in his sec ion we show, how model-
based simula ion imp o es his e o .
The simula ion o eqmine wi h 8 h eads shows an e o o 8.9%. F eqmine con-
sis 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 in-
e 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 og 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.
We obse e an e o o 7.3% in he case o dedup wi h 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 es-
sion, 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 [53]. Pe o mance a ia ion makes
76
Chap e 5. Sampled Simula ion o Task-Based P og ams
0
2
4
6
8
10
Absolu ee o [%]
14.3
13.8
11.0
15.9
37.1
13.0
22.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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
10
20
30
40
50
60
70
80
Speedup
FIGURE 5.10: E o and speedup o pe iodic sampling; low-powe
a chi ec u e; P= 250
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 sampled 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 in-
dependen 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 simu-
la 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 5.10 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 5.1 wi h
1, 2, 4 and 8 h eads. We no ice ha , o inc easing 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 37.1% o 2 h eads, luidanima e is he benchma k wi h he high-
es e o . In he case o luidanima e, he ins uc ion coun o ask ins ances a ies
be ween 1 million and 70 million, whe eas ask ins ances wi h mo e ins uc ions
end o execu e a a highe IPC. The ins uc ion coun and IPC a ia ion is caused by
he ac ha all ask ins ances pe o m an index compu a ion ha is highly ine icien
o high indexes. The assump ion, ha ask ins ances o he same ype ha e simila
pe o mance is hus no ul illed.
x264 shows an e o o up o 22.3%. This benchma k pe o ms ideo anscoding,
which is a highly inpu -dependen ope a ion. Each ame is p ocessed by a di e en
5.4. E alua ion
77
0
2
4
6
8
10
Absolu ee o [%]
22.9
28.0
40.8
14.2
15.0
14.5
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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
100
200
300
400
500
600
Speedup
FIGURE 5.11: E o and speed-up o lazy sampling; high-
pe o mance a chi ec u e
ask ins ance. Depending on he p ope ies o a ame, pe o mance can a y in a
wide ange, esul ing in a la ge simula ion e o .
Me ge-so and eqmine a e o he benchma ks wi h signi ican e o s o up o
14.3% and 13.0%, espec i ely. 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 inconsis en beha io among ask in-
s ances belonging o he same ask ype.
In e es ingly, wi h 11.0%, spa se-ma ix- ec o -mul iplica ion shows a la ge e o
o he low-powe a chi ec u e han o he high-pe o mance a chi ec u e. Depend-
ing on he s uc u e o he inpu ma ix, memo y accesses a e mo e o less egu-
la [52]. 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 in-
pu dependence, simila o he case o dedup explained in he p e ious sec ion.
5.4.3 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 3.2 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 5.1.
High-Pe o mance A chi ec u e
Figu e 5.11 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 3.5% o all simula ed h ead coun s (including
1, 2, and 4 h eads, which a e no shown in he Figu e).
78
Chap e 5. Sampled Simula ion o Task-Based P og ams
0
2
4
6
8
10
Absolu ee o [%]
11.5
14.6
12.9
10.3
11.2
11.3
13.1
47.3
38.0
24.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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
500
1000
1500
2000
2500
3000
3500
4000
Speedup
FIGURE 5.12: E o and speed-up o lazy sampling; low-powe a chi-
ec u e
Me ge-so and eqmine a e s ill among he benchma ks showing he highes e -
o . Compa ed o pe iodic sampling, he highes obse ed e o o me ge-so in-
c eases om 36.9% o 40.8% o he simula ion wi h 64 h eads. In he case o e-
qmine, he highes obse ed e o inc eases om 8.9% o 9.6% o he simula ion
wi h 8 h eads.
Wi h up o 15.0% and 14.5%, dedup and x264 show conside ably la ge e o s
compa ed o pe iodic sampling. This indica es ha by esampling he simula ion
pe iodic sampling is able o educe he e o o benchma ks wi h i egula beha io .
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. Com-
pa ed o pe iodic sampling, we obse e he la ges inc ease om 37.8 o 197.0 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 16.0
o 22.5. Fo 1 h ead, which is no shown in he Figu e, speedup inc eases om 35.2
o 1244.5.
Low-Powe A chi ec u e
Figu e 5.12 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 me ge-so ,
spa se-ma ix- ec o -mul iplica ion and eqmine. Fo dedup and x264, he e o in-
c eases o all simula ed h ead coun s. We obse e he highes inc ease, om 22.3%
o 47.3%, o he simula ion o x264 wi h 2 h eads.
5.4. E alua ion
79
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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
100
200
300
400
500
600
Speedup
FIGURE 5.13: E o and speed-up wi h analy ical model; high-
pe o mance a chi ec u e
Limi a ions o Lazy Sampling
Ou esul s show, ha lazy sampling achie es signi ican ly highe simula ion speedup,
compa ed o pe iodic sampling. Howe e , lazy sampling can lead o simula ion e -
o s o mo e han 40%, especially i he simula ed applica ion con ains ask ypes
whose ins ances expose a ying beha io . The mos no able cases a e me ge-so ,
dedup, eqmine and x264. This mo i a es he use o sma e clus e ing echniques
o de ec classes o ask ins ances wi h ela ed beha io . As s a ed ea lie , we use
DBSCAN clus e ing in o de o a oid eccen ically shaped clus e s being spli in o
mul iple sub-clus e s. We co ec he esul ing simula ion e o using pe o mance
p edic ions ob ained om an analy ical model.
5.4.4 Analy ical modeling
Fo ou e alua ion o model-based simula ion, we assume he same sampling pa-
ame e s as o lazy sampling, i.e. W= 2,H= 4 and P=∞. The applica ion
p o iles a e gene a ed oge he wi h he applica ion aces be o e simula ion. Fo
each simula ed a chi ec u e, he model is e alua ed once pe benchma k.
High-Pe o mance A chi ec u e
Figu e 5.13 shows e o and speedup o he model-based simula ions o he high-
pe o mance a chi ec u e. The a e age e o anges om 0.09% o 8 h eads o
1.32% o 64 h eads. In compa ison, lazy sampling shows a e age e o s o almos
3% o 8 and 64 simula ed h eads.
Fo 21 ou o 27 benchma ks, we obse e e o s o less han 2% ac oss all sim-
ula ed h ead coun s. The highes e o is 8% in he case o me ge-so , which is a
signi ican imp o emen o e he 40.8% obse ed in he case o lazy sampling.

80
Chap e 5. Sampled Simula ion o Task-Based P og ams
0
2
4
6
8
10
Absolu ee o [%]
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
me geso
nbody
educ ion
spa sema ix ec o 
mul iplica ion
ec o ope a ion
checkSpa seLU
cholesky
jacobi
kmeans
knn
blackscholes
body ack
canneal
dedup
acesim
e e
luidanima e
eqmine
s eamclus e
swap ions
x264
a e age
0
500
1000
1500
2000
2500
3000
3500
4000
Speedup
FIGURE 5.14: E o and speed-up wi h analy ical model; low-powe
a chi ec u e
Fo some benchma ks, he simula ion e o inc eases o inc easing h ead coun s.
In pa icula , his happens o he benchma ks dense-ma ix-mul iplica ion, ,his-
og am,me ge-so ,checkSpa seLU and blackscholes. In ou cu en implemen a ion,
he analy ical model does no model con en ion in he sha ed LLC. Fo he a o emen-
ioned benchma ks, we ind he LLC misses pe kilo-ins uc ion (MPKI) o inc ease
o an inc easing numbe o h eads, which suppo s ou a o emen ioned hypo he-
sis.
Wi h an a e age speedup o 220 o 8 h eads, model-based simula ion is as e
han lazy sampling, which achie es a speedup o 200. A he same ime, he simu-
la ion e o is educed o less han hal , compa ed o lazy sampling. Thus, model-
based simula ion is supe io o lazy sampling bo h in e ms o e o and speedup.
Low-Powe A chi ec u e
Figu e 5.14 shows e o and speedup o he model-based simula ions o he low-
powe a chi ec u e. The a e age e o anges om 0.06% o 1 h ead o 0.49% o 4
h eads, which is a la ge imp o emen o e lazy sampling.
Fo 22 o 27 benchma ks, he maximum e o ac oss all h ead coun s is less han
2%. Fo 13 o hese benchma ks he e o is e en less han 0.1%. The la ges e o
o 3.6% occu s in he case o . As in he case o he high-pe o mance a chi ec u e,
o some benchma ks he e o inc eases when inc easing he numbe o simula ed
h eads.
The a e age simula ion speedup anges om 290 o 8 h eads o 1490 o 1
h ead. Lazy sampling achie es a e age speedups o 240 and 1300, espec i ely.
Thus, as in he case o he high-pe o mance a chi ec u e, model-based simula ion
achie es supe io simula ion accu acy and speed.
5.5. Summa y
81
Summa y
The esul s o ou e alua ion show ha TaskPoin accu a ely p edic s execu ion ime
o ask-based p og ams. Fo lazy sampling, he a e age e o is 3.2% wi h a max-
imum e o o 40.8% and a simula ion speedup o 22.5. We show ha , o mos
benchma ks, pe iodic sampling leads o a smalle simula ion e o , howe e , a he
expense o simula ion speedup. Wi h pe - ask-ins ance BBVs, DBSCAN clus e ing
and analy ical modelling, we educe he simula ion e o ac oss all benchma ks. Fo
64 simula ed h eads, model-based simula ion leads o an a e age e o o 1.3% wi h
a maximum e o o 7.9%. Wi h 22.3, he simula ion speedup is only sligh ly lowe
han he speedup o 22.5 o lazy sampling.
5.5 Summa y
P e ious sampled simula ion echniques o pa allel p og ams ely on p o iling o
iden i y he pa ame e s o he sampling mechanism. Al hough hose echniques
ha e been p o en o be accu a e o s a ically scheduled o k-join based p og ams,
hey a e no di ec ly applicable o dynamically scheduled ask-based pa allel p o-
g ams.
The p oposed me hodology enables sampled simula ion o ask-based pa allel
p og ams. Sampling uni s a e iden i ied based on he pa i ioning in o asks p o-
ided by he p og amme . Be ween de ailed simula ion phases, we employ a no el
as - o wa d mechanism, which co ec ly e lec s he di e en p og ess a es o ask
ins ances belonging o di e en ask ypes and adap s o phase changes in he simu-
la ed applica ion.
In his chap e , we ex end ou o iginal me hodology wi h BBVs and clus e ing
o au oma ically de e mine classes o simila ask ins ances. We co ec simula ion
inaccu acies by applying co ec ion ac o s ob ained om an analy ical pe o mance
model.
We assessed TaskPoin ’s gene aliza ion capabili y by using wo adically di e -
en a chi ec u es o selec sampling pa ame e s and o un simula ions. The e alua-
ion esul s a e sa is ac o y ac oss a wide ange o benchma ks, di e en numbe s o
simula ed h eads and di e en a chi ec u e models. The a e age simula ion e o
is less han 2% a an a e age speedup anging om 19× o 64 h eads o 1019× o
1 h ead.
83
Chap e 6
Mul i-Le el Simula ion o Hyb id
P og ams
6.1 In oduc ion
The p ocess o designing nex -gene a ion High Pe o mance Compu ing (HPC) ma-
chines is ex emely challenging. The inc easing amoun o compu a ional esou ces
each new gene a ion o HPC sys ems in eg a es makes his challenge e en mo e di -
icul . In addi ion, he end o use commodi y se e p ocesso s as he common
choice o designing such machines is changing, as p ocesso s wi h leane co e de-
signs ha ea u e signi ican ly di e en mic oa chi ec u al cha ac e is ics a e s a -
ing o make hei debu in he HPC ma ke [95,119,125]. Consequen ly, he design
space o nex -gene a ion HPC machines is expanding. No el solu ions a e equi ed
in o de o quickly p edic he pe o mance o cu en and u u e scien i ic applica-
ions on hose sys ems and o iden i y he bes design poin s.
Besides aking in o accoun he ha dwa e, i is also impo an o conside i s in e -
ac ions wi h he sys em so wa e (e.g. ope a ing sys em, un ime sys em) [30,114].
Hyb id p og amming models a e pe asi e nowadays, employing MPI o in e -
node communica ion and a sha ed-memo y p og amming model o node-le el pa -
allelism. Mo i a ed by la ge co e coun s wi hin he same node, sophis ica ed ways
o handling sha ed memo y pa allelism a e becoming inc easingly a ac i e o e-
duce load imbalance and hus imp o e pa allel e iciency in la ge sha ed-memo y
mul i-co e con igu a ions [42,66,79]. Fo example, OpenMP, he mos popula ap-
p oach o sha ed memo y p og amming, has signi ican ly e ol ed and cu en ly
inco po a es ad anced ea u es such as asking suppo [8,89]. Fo all hese easons,
pa allel ope a ions such as scheduling and synch oniza ion a e expec ed o become
key sys em so wa e componen s. As a esul , simula o s a ge ing nex -gene a ion
HPC sys ems mus ake in o accoun such pa allel ope a ions pe o med a he un-
ime sys em le el.
Exis ing ools make simula ion o la ge-scale HPC machines wi h housands o
co es un easible. Con en ional cycle-accu a e a chi ec u al simula o s o e a g ea
90
Chap e 6. Mul i-Le el Simula ion o Hyb id P og ams
MUSA allows he use o de ine such bounds as inpu pa ame e s, gi ing g ea lex-
ibili y in deciding which compu a ion phases a e o be simula ed in de ail, while
he pe o mance o he emaining phases is ex apola ed. Sec ion 6.3.4 de ails how
MUSA pe o ms sampling o compu a ion phases a di e en le els.
Ne wo k simula ion and inal ou pu : A e he compu a ion phases ha e been
simula ed, MUSA eplays he execu ion o he communica ion ace e en s in o de
o simula e he communica ion ne wo k and gene a e he inal ou pu ace o he
simula ion. Du ing his p ocess, he du a ions o he compu a ion phases a e e-
placed by he esul s ob ained in he simula ions (ei he in bu s o de ailed mode),
and he communica ion phases a e simula ed using a ne wo k simula o . A he end
o his p ocess he en i e simula ion is comple e and he ou pu ace is gene a ed o
isualiza ion.
Figu e 6.2b shows an ou pu simula ion ace gene a ed by MUSA when simu-
la ing wo co es pe ank. The simula ion models he OpenMP scheduling e en s by
calling he ac ual un ime sys em h ough inse ed API calls o he aced e en s,
ai h ully modeling he impac o ha ing wo co es on each node. The MPI commu-
nica ion is p ocessed by h ead T0 on each ank, while he compu a ion phase load
o each ank is dis ibu ed ac oss he wo co es.
6.3.4 Sampling - Reducing Simula ion Time
Accu a e mic oa chi ec u al simula ion is ime consuming. Con en ional simula-
o s achie e simula ion speeds o 100 o 1000 KIPS [14,99,103]. As a consequence,
de ailed simula ion o la ge sys ems o long- unning applica ions becomes in easi-
ble. While MUSA allows simula ions a di e en le els o de ail, i s ill equi es o
simula e some compu a ion phases in de ail. In an HPC applica ion, hese phases
ypically un o a ew seconds, be o e s a ing a new communica ion phase.
A common echnique o educing simula ion ime is sampling. Sampling can
be employed o allow de ailed simula ion o la ge po ions o an applica ion o
o u he educe simula ion ime. Sampling seeks o minimize he amoun o de-
ailed simula ion by only simula ing he ep esen a i e pa s o an applica ion. In
he ollowing, we poin ou how MUSA employs sampling a h ee o hogonal le -
els o g anula i y in an applica ion, namely (i) he whole applica ion, (ii) a single
MPI ank, and (iii) a compu a ion phase wi hin an MPI ank. Fo a mo e ho ough
in oduc ion o sampled simula ion we e e o Sec ion 2.4.2.
Applica ion le el: Many applica ions in HPC show i e a i e beha io , wi h each
i e a ion ep esen ing a s ep in ime o space. In many cases, di e en i e a ions
show e y simila pe o mance. Au oma ic echniques o iden i y i e a ions based
on pe o mance moni o ing coun e s o aces o logical e en s ha e been p oposed
in he pas [27,65]. Howe e , he simples app oach elies on di ec ly analyzing he

6.4. E alua ion
91
code o he applica ion, anno a ing he s a and end o an i e a ion. When sampling
a he applica ion le el, MUSA le e ages hese echniques o iden i y epe i i e be-
ha io and selec a small numbe o i e a ions o de ailed simula ion.
MPI ank le el: As desc ibed in Sec ion 6.2, a common p og amming echnique
in HPC applica ions is he di ision o he p oblem domain in o blocks. A e wa ds,
each block is p ocessed by a di e en MPI ank. O en, di e en MPI anks show
simila pe o mance ac oss all p ocesses. Consequen ly, MUSA can selec a subse o
he MPI anks o de ailed simula ion a he mic oa chi ec u e le el. MUSA adop s
a simple app oach consis ing in simula ing one ou o e e y NMPI anks (pe iodic
sampling). The e a e exis ing echniques o au oma ically selec ep esen a i e com-
pu a ion phases o an applica ion [50,106].
Compu a ion phase le el: A e selec ing a subse o i e a ions and MPI anks,
all compu a ion phases ha e o be simula ed in de ail. Iden i ying ep esen a i e
sec ions o a compu a ion phase can be done au oma ically [107,121], and applied
o pa allel applica ions wi h ba ie s [22], as is he case o ypical OpenMP p o-
g ams wi h pa allel loops. In he case o ask-based p og ams, MUSA allows o
pe o m simula ions wi h TaskPoin [54], he sampled simula ion me hodology o
ask-based p og ams p esen ed in Chap e 5o his hesis.
6.4 E alua ion
In his sec ion, we p esen ou e alua ion o MUSA. Fi s , we in oduce he appli-
ca ions we use o e alua e MUSA, and he na i e HPC sys em used o alida ion.
A e wa ds, we in oduce MUSA’s acing in as uc u e. Then, we alida e MUSA,
be o e we apply ou me hodology o de ec scalabili y bo lenecks in hyb id applica-
ions bo h a he algo i hmic le el, due o he lack o pa allelism, and a he ha dwa e
le el, due o con en ion on sha ed esou ces. Finally, we also p esen simula ion ime
esul s and a design space explo a ion analysis.
6.4.1 Applica ions
To alida e MUSA we use he NAS mul i-zone benchma ks [116]: BT-MZ,SP-MZ
and LU-MZ. The benchma ks a e in oduced in Sec ion 3.4.2. Fo his alida ion
s ep we use 16 MPI anks wi h a mapping o one ank pe node. Simula ions a e
pe o med wi h 1 o 8 co es pe node. We un he benchma ks wi h he inpu class
D, o which we obse e enough pa allelism o he 16 MPI anks employed.
In o de o illus a e he po en ial o MUSA, we e alua e la ge-scale machines
using HYDRO [75], BT-MZ wi h he la ge inpu class E, and SPECFEM3D [72]. The
benchma ks HYDRO and SPECFEM3D a e also in oduced in Sec ion 3.4.2. Fo he
92
Chap e 6. Mul i-Le el Simula ion o Hyb id P og ams
TABLE 6.1: Applica ion cha ac e is ics.
Benchma k Cha ac e is ics
Name Inpu Ranks Tasks/ ank I e a ions Regions/i e a ion
BT-MZ Class D 16 2.3M 250 1
SP-MZ Class D 16 131K 500 1
LU-MZ Class D 16 1.3M 300 1
HYDRO big 256 1.0M 200 2
BT-MZ Class E 256 1.3M 250 1
SPECFEM3D n/a 256 1.9M 10700 1
TABLE 6.2: Applica ion acing s a is ics.
Benchma k T acing
Name Inpu O e head Bu s T ace De ailed T ace
BT-MZ Class D 3.4% 5.6 GB 53.3 GB
SP-MZ Class D 1.2% 0.4 GB 13.7 GB
LU-MZ Class D 1.0% 3.2 GB 12.5 GB
HYDRO big 6.0% 16.1 GB 16.9 GB
BT-MZ Class E 8.5% 57.4 GB 120.0 GB
SPECFEM3D n/a 9.3% 101.4 GB 106.4 GB
la ge-scale simula ions we employ 256 MPI anks, one pe node, and up o 64 co es
pe node, esul ing in simula ions o up o 16,384 co es.
All applica ions use a hyb id p og amming model based on MPI [56,82] o
in e -node pa alleliza ion and a ask-based p og amming model, OmpSs [42], o
in a-node pa alleliza ion. MPI and OmpSs a e in oduced in Sec ions 2.2.2 and 2.2.4,
espec i ely.
Table 6.1 summa izes he main cha ac e is ics o each applica ion. I includes
he numbe o MPI anks, he o al numbe o asks pe MPI ank, he numbe o
i e a ions o he applica ion and he numbe o pa allel egions wi hin an i e a ion.
Fo example, in he case o BT-MZ wi h inpu class E he e is an a e age o 5,200
asks pe pa allel egion ( asks/ ank
i e a ions × egions ).
Table 6.2 lis s he ace sizes o he in es iga ed applica ions. Bu s aces con ain
only MPI and OpenMP un ime sys em e en s, bu no de ailed ins uc ion ace. The
able clea ly shows, ha de ailed aces can be up o an o de o magni ude la ge
han bu s aces. The able also lis s he acing o e head o gene a ing bu s aces,
i.e. he applica ion slowdown caused by he ins umen a ion ool. Gene a ing a
de ailed ace in oduces an o e head o up o h ee o de s o magni ude, which is
no shown in he able.
6.4.2 Na i e HPC In as uc u e
We alida e MUSA agains he Ma eNos um 3 supe compu e . Each node has wo
socke s wi h an In el Xeon E5-2670 ea u ing eigh co es unning a 2.6GHz. The
6.4. E alua ion
93
co es implemen agg essi e supe scala capabili ies, ha e p i a e L1 and L2 caches,
and a sha ed 20MB L3 cache. The nodes a e connec ed ia a high-bandwid h In ini-
Band FDR10 ne wo k. To alida e MUSA, we simula e he same HPC in as uc u e.
Fo he na i e execu ions, we p esen esul s wi h up o eigh co es pe node,
making use o a single socke . This a oids ac o ing in non-uni o m memo y access
imings ha may bias he esul s. In addi ion, we un each na i e expe imen i e
imes and selec he measu emen ha p esen s he lowes amoun o in e e ence
due o cu en sys em load.
6.4.3 T acing and Simula ion In as uc u e
Ou mul i-le el simula ion in as uc u e is based on wo main componen s:
1. Dimemas, a high-le el simula o able o model MPI communica ion phases us-
ing analy ical models [49] (in oduced in Sec ion 2.3.3)
2. TaskSim, a de ailed mul i-co e simula o wi h accu a e memo y models [99,
100] (in oduced in Sec ion 3.3)
Pe o ming applica ion simula ions equi es wo s eps. In he i s s ep we gene -
a e aces ha allow execu ion eplay e en i he cha ac e is ics o he simula ed
compu a ional node change, e.g. he numbe o co es o he memo y hie a chy de-
sc ip ion. Hence we can pe o m design space a chi ec u al analysis using he same
se o aces, educing ace s o age equi emen s.
T aces a e ob ained using di e en ligh weigh acing ools based on ex ae [10]
and PIN [80]. To ob ain he aces o an applica ion, we ins umen a na i e execu-
ion ha uns only a single h ead pe node, i.e. pe MPI ank. Ex ae gene a es he
high-le el ace (bu s ace) using coa se-g ain ins umen a ion. The ace ins u-
men s he en i e applica ion, i.e. all anks and i e a ions. Howe e , o he de ailed
ace, such an app oach would be imp ac ical and equi e oo much s o age. Fo he
e alua ed se o applica ions, we obse e ha acing he second i e a ion o a sin-
gle MPI ank is enough o la e econs uc an applica ion’s en i e execu ion using
his in o ma ion and he bu s ace. This allows o manageable acing imes and
s o age equi emen s.
Table 6.2 de ails he o e head o gene a ing aces a bu s le el, and he sizes o
he bu s and de ailed aces o each applica ion. The o e heads include he ace
disk I/O cos s, which ac ually do no a ec he applica ion beha io , as I/O is pe -
o med a poin s whe e he applica ion is hal ed by he ace . In e ms o ace sizes,
bu s aces a e ela i ely small, while co e ing he en i e execu ion o applica ions
unning o se e al minu es on he eal machine. On he o he hand, de ailed aces
a e bigge , e en hough hey only co e he second i e a ion o a single MPI ank.
No e ha a de ailed ace o he en i e BT-MZ applica ion wi h inpu class D would
94
Chap e 6. Mul i-Le el Simula ion o Hyb id P og ams
16 32 64 128
To al co es
0
2
4
6
8
Speedup
BT-MZ
Na i e
MUSA (bu s )
MUSA (de ailed)
MUSA (de ailed + sampled)
16 32 64 128
To al co es
0
2
4
6
8
Speedup
SP-MZ
16 32 64 128
To al co es
0
2
4
6
8
Speedup
LU-MZ
(a) A single i e a ion o he benchma k
16 32 64 128
To al co es
0
2
4
6
8
Speedup
BT-MZ
Na i e
MUSA (bu s )
MUSA (de ailed)
MUSA (de ailed + sampled)
16 32 64 128
To al co es
0
2
4
6
8
Speedup
SP-MZ
16 32 64 128
To al co es
0
2
4
6
8
Speedup
LU-MZ
(b) En i e execu ion o he benchma k
FIGURE 6.3: MUSA alida ion using he NAS Mul i-Zone Pa al-
lel Benchma ks: BT-MZ (le ), SP-MZ (middle) and LU-MZ ( igh ).
Benchma ks a e un na i ely and simula ed using MUSA wi h 16 MPI
anks and up o eigh co es pe node.
equi e mo e han 200 e aby es o s o age. The ob ained de ailed aces a e manage-
able while s ill allowing MUSA o pe o m meaning ul de ailed mic oa chi ec u al
simula ions.
Ou me hodology equi es bo h an a chi ec u al and a communica ion ne wo k
6.4. E alua ion
95
simula o . To simula e he compu a ion phases we use TaskSim, a de ailed mul i-
co e simula o wi h wo ope a ion modes, a as explo a ion mode based on p e-
calcula ed compu a ion phase execu ion imes (bu s ) and a de ailed mode wi h ac-
cu a e mic oa chi ec u e and memo y models [99,100]. Fo he ne wo k we employ
Dimemas, which is able o model MPI communica ion p imi i es using analy ical
models [49]. Howe e , we s ongly belie e ha he MUSA me hodology can be ap-
plied o nea ly any simula o cu en ly a ailable in he communi y.
6.4.4 Valida ion
We alida e MUSA by pe o ming se e al expe imen s wi h he NAS Mul i-Zone
benchma ks. As desc ibed in Sec ion 6.4.1, all alida ion expe imen s a e done wi h
16 MPI anks and he class D inpu se , always assuming a single MPI ank pe node.
Figu e 6.3 shows he speedup o a single i e a ion (Figu e 6.3a), and o he en i e
applica ion (Figu e 6.3b) when inc easing he numbe o co es pe MPI ank. Ha ing
bo h igu es is e y use ul, as he o e all execu ion ime o he whole applica ion o a
single i e a ion can be biased by he sequen ial execu ion o a pa icula phase o he
applica ion, such as eading inpu iles, ini ializing da a s uc u es o w i ing ou pu
iles.
Na i e execu ions a e pe o med wi h up o eigh co es pe ank, as his is he
numbe o co es pe socke on he a ailable machine. Consequen ly, in ou alida-
ion we use up o 128 co es, wi h pa allel e iciencies ha ange om 48% (LU-MZ) o
92% (BT-MZ). Using a pe o mance isualiza ion ool, we obse e ha in all bench-
ma ks he i s i e a ion is less ep esen a i e han he o he s. We he e o e chose o
ace he second i e a ion in de ail o a oid cap u ing he impac o cold ha dwa e
s uc u es in he p ocesso . Figu e 6.3 shows ha scalabili y in na i e and simula ed
execu ions closely ma ch when compa ing a single i e a ion and he en i e applica-
ion.
Fi s , we e alua e he accu acy o MUSA wi h bu s simula ions, deno ed MUSA
(bu s ) in he igu e. A i s obse a ion is ha bu s simula ions accu a ely model he
sys em o BT-MZ, wi h negligible ela i e e o s. This is due o he ac ha BT-MZ
is compu e bound and con en ion on sha ed esou ces does no inc ease signi ican ly
wi h la ge co e coun s, leading o a speedup o 7.3×on an 8 co e node. Howe e ,
SP-MZ and LU-MZ ha e highe memo y con en ion and pe o mance p edic ions
s a o di e om he na i e execu ion as he numbe o co es pe node inc eases.
Fo SP-LU and LU-MZ,MUSA (bu s ) p edic s speedups o 6.9×and 7.5×wi h ela-
i e e o s o 33% and 88% wi h espec o na i e uns.
The esul s ob ained in bu s simula ion clea ly indica e ha , as we scale he
numbe o co es in he sys em, cycle-accu a e memo y simula ions a e necessa y o
cap u e con en ion on sha ed esou ces. We pe o m a second se o simula ions

96
Chap e 6. Mul i-Le el Simula ion o Hyb id P og ams
wi h MUSA using de ailed mic oa chi ec u al and memo y models, deno ed MUSA
(de ailed) in he igu e. In his case, MUSA simula es one i e a ion o a single MPI
ank and ex apola es he esul s o he emaining MPI anks and i e a ions.
MUSA (de ailed) imp o es accu acy wi h espec o MUSA (bu s ) o bo h SP-
MZ and LU-MZ when simula ing a sys em wi h 128 co es. In he case o SP-MZ, he
ela i e e o is educed om 33% o 10%, cap u ing he end obse ed in na i e
execu ion. Fo LU-MZ he e o is educed om 88% o 25%. Howe e , he end is
no cap u ed as accu a ely as in he o he wo benchma ks due o modeling inaccu-
acies in he simula ed DRAM subsys em. LU-MZ has poo ow-bu e locali y and
in e nal bank con lic s, and hus needs a de ailed componen -speci ic simula o o
cap u e hese beha io . The e o e, o his applica ion we would sugges o use ools
like DRAMSim2 [102] o Ramula o [69]. In he case o BT-MZ, he e o is negligi-
ble as happens in he bu s simula ion and, as expec ed, he pe o mance is again
accu a ely p edic ed.
Nex , we e alua e he accu acy o MUSA using TaskPoin [54] o speed up de-
ailed simula ion, deno ed MUSA (de ailed+sampling) in he igu e. In his case, we
only pe o m de ailed mic oa chi ec u al simula ion on a ac ion o he ask in-
s ances o he applica ion. We apply TaskPoin ’s de aul pa ame e s: i s , we sim-
ula e 2 ask ins ances in each h ead in o de o wa m up mic oa chi ec u al s a e.
A e wa ds, we simula e a o al o 4 ask ins ances o each ask ype as samples.
This educes he o al simula ion ime by a ac o o 2.5×in BT-MZ, 1.9×in SP-MZ,
and 3.0×in LU-MZ. As shown in Figu e 6.3b, MUSA (de ailed+sampling) p edic s
nea ly he same speedups as MUSA (de ailed). The a e age di e ence be ween hese
app oaches is less han 3%. These esul s a e consis en wi h p e iously published
esul s wi h TaskPoin [54].
Ou alida ion shows ha MUSA p o ides accu a e pe o mance p edic ions by
combining in o ma ion a di e en le els o g anula i y. When compa ing na i e
execu ions o he en i e applica ion wi h MUSA simula ions, we can see ha he
ela i e e o s a e low and ha he de ailed models a e able o cap u e mic oa chi-
ec u al de ails such as memo y con en ion. In addi ion, we can do his in an a o d-
able amoun o ime, as e en de ailed simula ions comple e wi hin a ew hou s. A
mo e comp ehensi e s udy in e ms o simula ion ime is shown o ou la ge-scale
simula ions in Sec ion 6.4.6.
6.4.5 La ge-scale Simula ions
We p esen la ge-scale simula ions o BT-MZ wi h inpu class E, HYDRO and SPECFEM3D
o he en i e applica ion. Table 6.1 lis s he ele an applica ion cha ac e is ics. We
employ 256 MPI anks, one pe node, wi h up o 8 co es pe node (2,048 co es)
o na i e execu ions and up o 64 co es o simula ions wi h MUSA (16,386 co es).
6.4. E alua ion
97
256 512 1K 2K 4K 8K 16K
To al co es
0
10
20
Speedup
BT-MZ
Na i e
MUSA (bu s )
MUSA (de ailed)
MUSA (de ailed + sampled)
FIGURE 6.4: Pe o mance es ima ions o BT-MZ wi h inpu class E
o he en i e applica ion on 256 MPI anks. Na i e uns wi h up o
8 co es pe node (2,048 co es), and simula ed uns wi h MUSA on up
o 64 co es pe node (16,384 co es).
These simula ions allow us o iden i y scalabili y bo lenecks occu ing o la ge co e
coun s pe node, a end ha con inues o mani es .
Figu e 6.4 shows speedup es ima ions o BT-MZ. Resul s wi h up o 8 co es pe
node (2,048 o al) a e alida ed agains he na i e execu ion o he applica ion, show-
ing a good le el o accu acy. Wi h 8 co es pe node, he pa allel e iciency eaches
82% o he o e all execu ion o he na i e applica ion, and MUSA p edic s he pa -
allel e iciency wi h an e o o less han 5% o all simula ion modes.
When pe o ming bu s simula ions wi h la ge co e coun s, he pa allel e i-
ciency signi ican ly deg ades, eaching 26% o 64 co es (16×speedup). We ana-
lyze i ask managemen is he limi ing ac o o scalabili y. To his end, we un he
mas e h ead wi h a signi ican ly highe speed and obse e no signi ican change
in scalabili y. F om his expe imen we conclude ha BT-MZ does no expose su i-
cien ask pa allelism o achie e a highe pa allel e iciency a la ge co e coun s. One
possible solu ion is o educe ask g anula i y and hus inc ease he numbe o ask
ins ances. As his app oach also inc eases he ask managemen o e head, i poses
an in e es ing op imiza ion p oblem. MUSA p edic s simila scalabili y ends wi h
all simula ion modes because his applica ion is no memo y in ensi e, as s a ed in
he p e ious subsec ion.
In conclusion, we iden i y ha BT-MZ lacks ask pa allelism and hus shows
limi ed scalabili y in execu ions wi h la ge co e coun s pe MPI ank. Scalabili y
can be imp o ed by educing ask g anula i y, bu only i his does no inc ease he
e o o ask managemen o a poin whe e i becomes he new limi ing ac o o
98
Chap e 6. Mul i-Le el Simula ion o Hyb id P og ams
256 512 1K 2K 4K 8K 16K
To al co es
0
5
10
15
Speedup
HYDRO
Na i e
MUSA (bu s )
MUSA (de ailed)
MUSA (de ailed + sampled)
FIGURE 6.5: Pe o mance es ima ions o HYDRO o he en i e ap-
plica ion on 256 MPI anks. Na i e uns wi h up o 8 co es pe node
(2,048 co es), and simula ed uns wi h MUSA on up o 64 co es pe
node (16,384 co es).
scalabili y.
Figu e 6.5 shows speedup es ima ions o HYDRO. Resul s wi h up o 8 co es pe
node (2,048 o al) a e alida ed agains he na i e execu ion o he applica ion. Fo
up o 8 co es, de ailed simula ion modes p edic pa allel e iciency wi h an e o o
less han 8%. Fo highe co e coun s, all simula ion modes p edic simila esul s.
We a ibu e his o HYDRO’s low memo y in ensi y.
As we inc ease he numbe o co es, pa allel e iciency signi ican ly deg ades,
eaching a alue o only 17% a 64 co es pe node. A signi ican pe cen age o pa al-
lel e iciency is los due o communica ion (MPI) o e heads. We ind he pa allel e i-
ciency o he compu a ion phases o be 31% when communica ion is igno ed. The e-
o e, he compu a ional pa o he applica ion has oom o imp o emen . Wi h he
help o con en ional pe o mance analysis ools o MPI applica ions, we obse e
ha he sequen ial pa in each i e a ion is limi ing he scalabili y o he applica ion
o co e coun s la ge han 8. To a oid his limi a ion, he applica ion needs o be
es uc u ed o educe he amoun o sequen ial compu a ion.
Fu he mo e, o 32 and 64 co es pe node he ime de o ed o ask c ea ion and
scheduling limi s he scalabili y o he applica ion. The e a e mul iple solu ions o
alle ia e his p oblem. The i s solu ion consis s in inc easing he g anula i y o he
execu ed asks, as his educes he o al numbe o ask ins ances and hus he man-
agemen e o . A second op ion is ha ing mul iple h eads c ea ing and scheduling
asks using nes ed pa allelism. Finally, a hi d al e na i e consis s in using ha dwa e
suppo o he un ime sys em [47].
6.4. E alua ion
99
256 512 1K 2K 4K 8K 16K
To al co es
0
5
10
15
Speedup
SPECFEM3D
Na i e
MUSA (bu s )
MUSA (de ailed)
MUSA (de ailed + sampled)
FIGURE 6.6: Pe o mance es ima ions o SPECFEM3D o he en i e
applica ion on 256 MPI anks. Na i e uns wi h up o 8 co es pe
node (2,048 co es), and simula ed uns wi h MUSA on up o 64 co es
pe node (16,384 co es).
Figu e 6.6 shows speedup es ima ions o SPECFEM3D. Resul s o up o 8 co es
pe node (2,048 o al) a e compa ed o he na i e execu ion o he applica ion. Fo
2 and 4 co es pe node, we obse e no able ela i e e o s when compa ing MUSA
simula ion modes and na i e execu ion. Howe e , o 8 co es pe node he de ailed
simula ion modes p edic pa allel e iciency wi h an e o o less han 3%. In ad-
di ion, we obse e ha o co e coun s pe node o 8 and mo e, pe o mance es i-
ma ions wi h bu s and de ailed mode di e signi ican ly due o inc easing o -chip
memo y con en ion, leading o pe o mance o e es ima ions in bu s mode.
As we inc ease he co e coun in bu s simula ion mode, we obse e ha he
applica ion’s scalabili y suddenly sa u a es om 32 o 64 co es pe node. We ind
ha his is because he numbe o ask ins ances o his applica ion is small, less
han 200 pe pa allel egion (see Table 6.1). Mo eo e , he e a e se e al ask ypes
ha ea u e signi ican ly di e en execu ion imes, which e en ually leads o se e e
load imbalance, limi ing scalabili y. Since MUSA ai h ully models ask scheduling
in bu s mode, we co ec ly iden i y his bo leneck.
Howe e , o de ailed simula ions we see ha he pe o mance ac ually sa u a es
when mo ing om 16 o 32 co es pe node. This is due o he combined e ec o load
imbalance and signi ican o -chip memo y con en ion, which especially penalizes
long unning asks ha now execu e o an e en longe pe iod o ime, exace ba ing
load imbalance. Wi h MUSA we a e able o iden i y a bo leneck ha mani es s due
o he combina ion o wo ac o s, and gain insigh on he pe o mance penal y each
ac o imposes.

107
Chap e 7
Conclusions
In his hesis, we p esen a s udy o execu ion ime p edic abili y o ask-based p o-
g ams. The esul s o his s udy a e he mo i a ion o de elop TaskPoin , ou sam-
pled simula ion me hodology o ask-based p og ams execu ed on sha ed-memo y
mul i-co e sys ems. Finally, we p esen MUSA, ou mul i-le el simula ion app oach
o hyb id applica ions. MUSA includes TaskPoin o speed up simula ions a he
sha ed-memo y node le el.
7.1 Execu ion Time P edic abili y o Task-Based P og ams
Task-based p og amming models a e a p omising way o e icien ly p og am u-
u e sha ed-memo y sys ems wi h la ge co e coun s. In a ask-based p og amming
model, he p og amme decla es p og am pa s as asks, which a e ins an ia ed
many imes du ing he execu ion o he p og am. A un ime sys em calcula es da a
dependencies be ween ask ins ances. Task ins ances which ha e hei dependencies
ul illed a e scheduled o a ailable execu ion h eads.
In Chap e 4we p esen an analysis o execu ion ime p edic abili y o ask-
based p og ams. To his end, we e alua e pe o mance a iabili y ac oss di e en
ins ances o he same ask ype and ind ha he nai e assump ion o egula pe o -
mance ac oss ins ances o he same ask ype is no always alid.
We show ha accu a e pe o mance p edic ions can be de i ed om de ailed
pe o mance in o ma ion o a ela i ely small numbe o ask ins ances. We p esen
echniques o imp o e he accu acy o execu ion ime p edic ions o ask ypes wi h
i egula pe o mance. These echniques a e based on linea in e pola ion and clus-
e ing. The execu ion ime p edic ion e o is educed om mo e han 80% o less
han 12% o inpu dependen cases and o less han 2% o ask ypes exposing
mul iple classes o beha io .
108
Chap e 7. Conclusions
7.2 Sampled Simula ion o Task-Based P og ams
A chi ec u al simula ion o u u e mul i-co e sys ems is becoming inc easingly chal-
lenging. Due o he inc easing o al size o on-chip caches, la ge wo kloads need o
be simula ed in o de o meaning ully s ess a design. Fu he mo e, he inc easing
co e coun s in mul i-co e designs equi e longe simula ions in o de o s ess sha ed
sys em esou ces and simula e in e ac ions o di e en h eads in a meaning ul way.
P e ious sampled simula ion echniques o pa allel p og ams ely on he as-
sump ion, ha he sequence o use ul ins uc ions, i.e. he applica ion’s ins uc ions
excluding un ime sys em ac i i y and synch oniza ion, does no change ac oss di -
e en execu ions o he applica ion. Al hough hose exis ing echniques ha e been
p o en o be accu a e o s a ically scheduled o k-join based p og ams, hey a e
no di ec ly applicable o dynamically scheduled ask-based pa allel p og ams. In
ask-based p og ams, he execu ion o de o ask ins ances can change due o he
dynamic schedule o he un ime sys em.
In Chap e 5we p esen TaskPoin , a me hodology o sampled simula ion o
ask-based pa allel p og ams. Sampling uni s a e iden i ied based on he pa i ion-
ing in o asks p o ided by he p og amme . Be ween de ailed simula ion phases,
we employ a no el as - o wa d mechanism, which co ec ly e lec s he di e en
p og ess a es o ask ins ances belonging o di e en ask ypes and adap s o phase
changes in he simula ed applica ion.
We imp o e he o iginal TaskPoin me hodology by au oma ically clus e ing ask
ins ances using BBVs and DBSCAN clus e ing. A e c ea ing a BBV o each ask
ins ance, DBSCAN clus e ing iden i ies clus e s o ask ins ances wi h simila beha -
io . This has wo ad an ages: i s , di e en ask ypes can ha e ask ins ances wi h
simila beha io . Ou imp o ed app oach me ges hese ask ins ances in o a single
clus e , educing he amoun o de ailed simula ion equi ed o sampled simula ion.
Second, a ask ype can ha e ask ins ances wi h di e en classes o beha io . Ou
new app oach also iden i ies hese cases and clus e s he ask ins ances acco dingly.
Fo some applica ions, clus e ing wi h DBSCAN esul s in clus e s wi h la ge di-
ame e s, i.e. clus e s con aining ask ins ances which a e dissimila , bu connec ed
by a chain o ask ins ances simila o hei espec i e neighbo s. Ou imp o ed
e sion o TaskPoin uses an analy ical pe o mance model o achie e accu a e pe -
o mance p edic ions in he a o emen ioned cases.
We assess TaskPoin s gene aliza ion capabili y by using wo adically di e en
a chi ec u es o selec sampling pa ame e s and o un simula ions. The e alua ion
esul s a e sa is ac o y ac oss a wide ange o benchma ks, di e en numbe s o sim-
ula ed h eads and di e en a chi ec u e models. The a e age simula ion e o o
ou model-based simula ion mode anges om 0.1% o 1 simula ed h ead o 1.3%
7.3. Mul i-Le el Simula ion o Hyb id P og ams
109
o 64 simula ed h eads. The simula ion speedup anges om 22.3× o 1,490× o
h ead coun s o 64 and 1, espec i ely.
7.3 Mul i-Le el Simula ion o Hyb id P og ams
The p ocess o designing u u e HPC sys ems is ex emely challenging. The e e
inc easing sys em complexi y, in e ms o p ocesso s pe node and nodes pe sys-
em, makes a chi ec u al simula ion o en i e sys ems p ohibi i ely ime consum-
ing. Fu he mo e, p og am execu ion on u u e sys ems is likely o be managed
by sys em so wa e, e.g. a un ime en i onmen . A simula ion me hodology o
u u e HPC sys ems ideally allows o pe o m de ailed la ge-scale a chi ec u al sim-
ula ions, while aking he e ec s o he sys em so wa e in o accoun .
In Chap e 6o his hesis we in oduce MUSA, a mul i-le el simula ion ap-
p oach o u u e HPC sys ems p og ammed wi h hyb id p og amming models
which enables as and accu a e pe o mance es ima ions o la ge-scale nex -gene a ion
HPC machines. MUSA can model mic oa chi ec u al and un ime sys em e ec s by
le e aging mul i-le el aces. These aces also allow o di e en simula ion modes
and execu ion eplay o quickly ex apola e esul s o en i e hyb id applica ions un-
ning on ens o housands o co es.
MUSA has been alida ed using a p oduc ion supe compu e wi h up o 2,048
co es showing high accu acy, wi h ela i e e o s below 10% in he common case.
Fo na i e codes ha un o se e al minu es, MUSA allows de ailed simula ion o
sys ems wi h mo e han en housand co es wi hin a ew hou s o o al agg ega ed
CPU ime. Ou 16,384-co e simula ions e ealed scalabili y bo lenecks in he e alu-
a ed applica ions ha we e easily iden i iable using he simula ion ou pu ace and
con en ional pe o mance analysis ools.
The main ad an age o MUSA is ha i p o ides esul s no only ac oss known
sys ems, bu also o u u e sys ems no ye a ailable on he ma ke . Ou design
space explo a ion analysis p o ides use ul insigh s on he di e en mic oa chi ec-
u al equi emen s o h ee applica ions o achie e good scalabili y, showing he po-
en ial MUSA o e s in p edic ing he pe o mance o applica ions on nex -gene a ion
HPC machines.
111
Chap e 8
Fu u e Wo k
8.1 Scheduling Task-Based P og ams Using Execu ion Time
P edic abili y
In ou e alua ion o execu ion ime p edic abili y o ask-based p og ams in Chap-
e 4we showed ha execu ion ime o ask-based p og ams is p edic able. In Chap-
e 5, we le e age his insigh and p opose TaskPoin , ou sampled simula ion me hod-
ology o ask-based p og ams execu ed on mul i-co e sys ems.
We en ision ano he po en ial applica ion o he insigh s o his wo k in he ield
o dynamic scheduling o ask ins ances in ask-based p og amming models. In a
ask-based p og amming model, a un ime sys em schedules ask ins ances which
a e eady o execu ion o a ailable execu ion h eads. The pe o mance o each
ask ins ance, and hus he o e all p og am pe o mance, can depend on he exac
schedule.
Scheduling ask ins ances which sha e da a closely a e each o he is ypically
bene i ial in o de o achie e maximum pe o mance. I a consume ask ins ance is
no ye eady, he op imal scheduling decision can be o schedule o he ask ins ances
in he meanwhile, as long as his does no cause he da a accessed by he consume o
be e ic ed om he sha ed las le el cache [20,31]. A he same ime, i is desi able
o no inc ease he leng h o he c i ical pa h o an applica ion’s ask dependency
g aph [35,36].
Knowing a ask ins ance’s execu ion ime in ad ance has he po en ial o enable
a schedule o make in o med scheduling decisions. We belie e ha i is wo hwhile
o in es iga e he po en ial o execu ion ime p edic abili y o imp o ing dynamic
ask scheduling policies.

112
Chap e 8. Fu u e Wo k
8.2 Sampled Simula ion o Task-Based P og ams
In Chap e 5we p esen TaskPoin , a sampled simula ion me hodology o dynam-
ically scheduled ask-based p og ams. TaskPoin op ionally uses clus e ing and an-
aly ical pe o mance modeling o imp o e simula ion e o and speedup, especially
o i egula applica ions.
As we show in ou e alua ion, ou model-based simula ion app oach does no
ake in o accoun he con en ion on he sha ed LLC o a simula ed, mul i- h eaded
sys em. In he u u e, we plan o ully in eg a e he analy ical model wi h ou simu-
la ion en i onmen , allowing o ge mo e accu a e pe o mance p edic ion by aking
LLC con en ion in o accoun .
Cu en ly, model-based simula ions wi h TaskPoin equi e de ailed simula ion
o a small numbe o sample ask ins ances. Fo he u u e, we plan o elimina e
he need o de ailed simula ion. While we would s ill use a simula o o model he
e ec s o he un ime en i onmen , pe o mance es ima ions would ely pu ely on
analy ical modeling. We a e con iden ha his app oach will achie e la ge sim-
ula ion speeds and, equally impo an , imp o e he scalabili y o simula ion speed
when inc easing he numbe o simula ed h eads.
8.3 Mul i-Le el Simula ion o Hyb id P og ams
In Chap e 6o his hesis we p esen MUSA, ou mul i-le el simula ion app oach
o hyb id sys ems. We alida e MUSA and pe o m la ge-scale a chi ec u al sim-
ula ions wi h up o 16,384 simula ed co es. We also conduc a case s udy, in which
we simula e he pe o mance o se e al la ge-scale hyb id applica ions on di e en
a chi ec u es, namely a s a e-o - he-a high-pe o mance a chi ec u e, a low-powe
a chi ec u e and an a chi ec u e ea u ing die-s acked DRAM. We ind ha some
applica ions, e.g. BT-MZ, bene i om being un on a sys em wi h agg essi e ou -
o -o de p ocesso s and a e no e y sensi i e o he pe o mance o he DRAM sub-
sys em. O he applica ions, e.g. SPECFEM3D, clea ly bene i om being un on
a sys em wi h high-bandwid h, die-s acked DRAM. The design space explo a ion
p esen ed in his hesis is only an example o show he use ulness o MUSA. We
en ision a mo e ho ough s udy o u u e a chi ec u es using MUSA.
Cu en ly, MUSA can only simula e sys ems consis ing o single-socke nodes.
Howe e , many cu en HPC sys ems consis o nodes con aining wo o mo e sock-
e s. We see po en ial o u u e wo k in ex ending MUSA o i o suppo mul i-
socke nodes. This would allow o use MUSA o s udy he impac o how p ocesso
co es a e dis ibu ed ac oss di e en socke s on pe o mance.
8.3. Mul i-Le el Simula ion o Hyb id P og ams
113
Ou cu en implemen a ion o MUSA canno simula e communica ions o e -
lapped wi h compu a ion, i.e., be o e sending o ecei ing an MPI message, all h eads
o a ank need o synch onize. Due o he e e inc easing numbe o p ocesso co es
in a single HPC sys em, his can be a limi ing ac o o pe o mance. In he u u e, we
would like o add suppo o simula ing communica ions o e lapped wi h compu-
a ion. This would allow o s udy he pe o mance bene i s o a mo e asynch onous
execu ion model allowed by less synch oniza ions o he simula ed applica ion.
115
Appendix A
Publica ions
A.1 Con e ence Publica ions
•“MUSA: A Mul i-Le el Simula ion App oach o Nex -Gene a ion HPC Machines”.
Thomas G ass, Césa Allande, Ad iàA mejach, Alejand oRico, Edua dAyguadé,
Jesús Laba a, Ma eo Vale o, Ma c Casas, Miquel Mo e o. Published in P o-
ceedings o he In e na ional Con e ence o High Pe o mance Compu ing,
Ne wo king, S o age and Analysis 2016 (SC16). Sal Lake Ci y, U ah, Uni ed
S a es o Ame ica. No embe 2016.
•“TaskPoin : Sampled Simula ion o Task-Based P og ams”.Thomas G ass, Alejan-
d o Rico, Ma c Casas, Miquel Mo e o, Edua d Ayguadé. Published in P oceed-
ings o he 2016 In e na ional Symposium on Pe o mance Analysis o Sys ems
and So wa e (ISPASS 2016). Uppsala, Sweden. Ma ch 2016.
A.2 Jou nal Publica ions
•“Sampled Simula ion o Task-Based P og ams”.Thomas G ass, Ge mán Ceballos,
T e o Ca lson, Alejand o Rico, Edua d Ayguadé, Miquel Mo e ó, Ma c Casas.
Unde submission a IEEE T ansac ions on Compu e s (TC).
A.3 Wo kshop Publica ions
•“E alua ing Execu ion Time P edic abili y o Task-Based P og ams on Mul i-Co e
P ocesso s”.Thomas G ass, Alejand o Rico, Ma c Casas, Miquel Mo e o, Alex
Rami ez. Published in P oceedings o Eu o-Pa 2014: Pa allel P ocessing Wo k-
shops (MuCoCoS 2014). Po o, Po ugal. Augus 2014.
A.4 Pos e P esen a ions
•“E alua ing Execu ion Time P edic abili y o Task-Based P og ams”.Thomas G ass,
Alejand o Rico, Miquel Mo e o, Ma c Casas, Alex Rami ez. P esen ed a Ten h
122
BIBLIOGRAPHY
[51] J. Gonzalez, M. Casas, M. Mo e o, A. Rami ez, J. Laba a, and M. Vale o.
“Simula ing whole supe compu e applica ions”. In: IEEE Mic o 31.3 (2011),
pp. 32–45.
[52] G. Goumas, K. Kou is, N. Anas opoulos, V. Ka akasis, and N. Kozi is. “Un-
de s anding he pe o mance o spa se ma ix- ec o mul iplica ion”. In: 16 h
Eu omic o Con e ence on Pa allel, Dis ibu ed and Ne wo k-Based P ocessing (2008),
pp. 283–292.
[53] T. G ass, A. Rico, M. Casas, M. Mo e o, and A. Rami ez. “E alua ing Execu-
ion Time P edic abili y o Task-Based P og ams on Mul i-Co e P ocesso s”.
In: Eu o-Pa 2014: Pa allel P ocessing Wo kshops. 2014, pp. 218–229.
[54] T. G ass, A. Rico, M. Casas, M. Mo e o, and E. Ayguad?? “TaskPoin : Sam-
pled simula ion o ask-based p og ams”. In: In e na ional Symposium on Pe -
o mance Analysis o Sys ems and So wa e. 2016, pp. 296–306.
[55] E. G obelny, D. Bueno, I. T oxel, a. D. Geo ge, and J. S. Ve e . “FASE: A
F amewo k o Scalable Pe o mance P edic ion o HPC Sys ems and Ap-
plica ions”. In: Simula ion 83.10 (2007), pp. 721–745.
[56] W. G opp, E. Lusk, and A. Skjellum. Using MPI: po able pa allel p og amming
wi h he message-passing in e ace. Vol. 1. MIT p ess, 1999.
[57] T. R. Hal hill. “ARM’s 64-Bi Makeo e ”. In: The Linley G oup Newsle e s
(2012).
[58] J. Haskins and K. Skad on. “Memo y e e ence euse la ency: Accele a ed
wa mup o sampled mic oa chi ec u e simula ion”. In: In e na ional Sympo-
sium on Pe o mance Analysis o Sys ems and So wa e. IEEE, 2003, pp. 195–203.
[59] J. L. Henning. “SPEC CPU2000: Measu ing CPU pe o mance in he new mil-
lenium”. In: IEEE Compu e 33.7 (2000), pp. 28–35.
[60] J. P. Hoe linge . “Ex ending OpenMP o Clus e s”. In: In el Co po a ion whi e
pape (2006).
[61] M. Hsieh, J. Meng, M. Le enhagen, K. Ped e i, A. Coskun, and A. Rod igues.
“SST + gem5 = A scalable simula ion in as uc u e o high pe o mance
compu ing”. In: P oceedings o he Fi h In e na ional Con e ence on Simula ion
Tools and Techniques. 2012, pp. 196–201.
[62] W. C. Hsu, H. Chen, P. C. Yew, and D.-y. Chen. “On he p edic abili y o p o-
g am beha io using di e en inpu da a se s”. In: P oceedings Six h Annual
Wo kshop on In e ac ion be ween Compile s and Compu e A chi ec u es. 2002,
pp. 45–53.

BIBLIOGRAPHY
123
[63] W.-m. Hwu and Y. N. Pa . “HPSm, a high pe o mance es ic ed da a low
a chi ec u e ha ing minimal unc ionali y”. In: ACM SIGARCH Compu e A -
chi ec u e News 14.2 (1986), pp. 297–306.
[64] In el Xeon P ocesso E5-2699 4.h ps://a k.in el.com/p oduc s/
91317/In el-Xeon-P ocesso -E5-2699- 4-55M-Cache-2_20-
GHz. Accessed: 2017-05-22.
[65] K. E. Isaacs, A. Bha ele, J. Li lande , D. Böhme, T. Gamblin, M. Schulz, B.
Hamann, and P.-T. B eme . “Reco e ing logical s uc u e om Cha m++ e en
aces”. In: P oceedings o he In e na ional Con e ence o High Pe o mance Com-
pu ing, Ne wo king, S o age and Analysis (2015), 49:1–49:12.
[66] L. V. Kale and S. K ishnan. “CHARM++: A po able concu en objec o i-
en ed sys em based on C++”. In: ACM SIGPLAN No ices 28.10 (1993), pp. 91–
108.
[67] T. Ka khanis and J. Smi h. “A i s -o de supe scala p ocesso model”. In:
P oceedings o he 31s Annual In e na ional Symposium on Compu e A chi ec-
u e. 2004, pp. 338–349.
[68] D. J. Ke byson, H. J. Alme, A. Hoisie, F. Pe ini, H. J. Wasse man, and M. Gi -
ings. “P edic i e pe o mance and scalabili y modeling o a la ge-scale ap-
plica ion”. In: P oceedings o he 2001 ACM/IEEE con e ence on Supe compu ing.
2001, pp. 37–37.
[69] Y. Kim, W. Yang, and O. Mu lu. “Ramula o : A as and ex ensible DRAM
simula o ”. In: IEEE Compu e A chi ec u e Le e s 15.1 (2016), pp. 45–49.
[70] A. J. KleinOsowski and D. J. Lilja. “MinneSPEC: A new SPEC benchma k
wo kload o simula ion-based compu e a chi ec u e esea ch”. In: IEEE Com-
pu e A chi ec u e Le e s 1.1 (2002), p. 7.
[71] A. J. KleinOsowski, J Flynn, N Mea es, and D. J. Lilja. “Adap ing he SPEC
2000 benchma k sui e o simula ion-based compu e a chi ec u e esea ch”.
In: Wo kload cha ac e iza ion o eme ging compu e applica ions (2001), pp. 83–
100.
[72] D. Koma i sch and J. T omp. “In oduc ion o he spec al elemen me hod
o h ee-dimensional seismic wa e p opaga ion”. In: Geophysical Jou nal In-
e na ional 139.3 (1999), pp. 806–822.
[73] J. Laba a, S. Gi ona, V. Pille , T. Co es, and L. G ego is. “DiP: A pa allel p o-
g am de elopmen en i onmen ”. In: P oceedings o he Second In e na ional
Eu o-Pa Con e ence on Pa allel P ocessing. Ap il. 1996, pp. 665–674.
124
BIBLIOGRAPHY
[74] T. La age and A. Seznec. “Choosing Rep esen a i e Slices o P og am Exe-
cu ion o Mic oa chi ec u e Simula ions: A P elimina y Applica ion o he
Da a S eam”. In: Wo kload cha ac e iza ion o eme ging compu e applica ions.
Sp inge US, 2001, pp. 145–163.
[75] P.-F. La allée, G. C. de Ve diè e, P. Wau ele , D. Lecas, and J.-M. Dupays. Po -
ing and op imizing HYDRO o new pla o ms and p og amming pa adigms-lessons
lea n . 2012.
[76] C. L. Lawson, R. J. Hanson, D. R. Kincaid, and F. T. K ogh. “Basic linea al-
geb a subp og ams o o an usage”. In: ACM T ansac ions on Ma hema ical
So wa e 5.3 (1979), pp. 308–323.
[77] K. Lee, S. E ans, and S. Cho. “Accu a ely app oxima ing supe scala p o-
cesso pe o mance om aces”. In: In e na ional Symposium on Pe o mance
Analysis o Sys ems and So wa e. IEEE, 2009, pp. 238–248.
[78] E. A. León, R. Riesen, A. B. Maccabe, and P. G. B idges. “Ins uc ion-le el
simula ion o a clus e a scale”. In: P oceedings o he Con e ence on High Pe -
o mance Compu ing Ne wo king, S o age and Analysis. 2009, p. 1.
[79] J. Li lande , S. K ishnamoo hy, and L. V. Kale. “Wo k s ealing and pe sis ence-
based load balance s o i e a i e o e decomposed applica ions”. In: P oceed-
ings o he 21s in e na ional symposium on High-Pe o mance Pa allel and Dis-
ibu ed Compu ing. 2012, pp. 137–148.
[80] C.-K. Luk, B. C. Ed, F. C. G. Hi, E. D. Q. Rs, A Tu, R. Cohn, R. Mu h, H.
Pa il, A. Klause , G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. “Pin:
Building cus omized p og am analysis ools wi h dynamic ins umen a ion”.
In: P oceedings o he 2005 ACM SIGPLAN con e ence on P og amming language
design and implemen a ion. Vol. 40. 6. 2005, p. 190.
[81] J. Macqueen. “Some me hods o classi ica ion and analysis o mul i a ia e
obse a ions”. In: P oceedings o he Fi h Be keley Symposium on Ma hema ical
S a is ics and P obabili y. 1967, pp. 281–297.
[82] Message Passing In e ace Fo um. MPI: A message-passing in e ace s anda d.
2012.
[83] J. E. Mille , H. Kas u e, G. Ku ian, C. G uenwald, N. Beckmann, C. Celio,
J. Eas ep, and A. Aga wal. “G aphi e: A dis ibu ed pa allel simula o o
mul ico es”. In: P oceedings o he Six een h In e na ional Symposium on High-
Pe o mance Compu e A chi ec u e. 2010, pp. 1–12.
[84] G. E. Moo e. “C amming mo e componen s on o in eg a ed ci cui s”. In: P o-
ceedings O The IEEE 86.1 (1965), pp. 82–85.
BIBLIOGRAPHY
125
[85] M.Oskin, F. T. Chong, and M Fa ens. “HLS: Combining S a is ical and Sym-
bolic Simula ion o Guide Mic op ocesso Designs”. In: P oceedings o he 27 h
annual in e na ional symposium on Compu e a chi ec u e. 2000, pp. 71–82.
[86] S. S. Mukhe jee, S. K. Reinha d , B. Falsa i, M. Li zkow, M. D. Hill, D. A.
Wood, S. Huss-Lede man, and J. R. La us. “Wisconsin Wind Tunnel II: a
as , po able pa allel a chi ec u e simula o ”. In: IEEE Concu ency 8.4 (2000),
pp. 12–20.
[87] S. Nussbaum and J. Smi h. “Modeling supe scala p ocesso s ia s a is ical
simula ion”. In: P oceedings o he 2001 In e na ional Con e ence on Pa allel A -
chi ec u es and Compila ion Techniques. 2001, pp. 15–24.
[88] S. L. Oli ie , B. R. De Supinski, M. Schulz, and J. F. P ins. “Cha ac e izing
and mi iga ing wo k ime in la ion in ask pa allel p og ams”. In: Scien i ic
P og amming 21.3-4 (2013), pp. 123–136.
[89] OpenMP A chi ec u e Re iew Boa d. OpenMP applica ion p og am in e ace
e sion 4.0. Tech. ep. 2013.
[90] E. Pe elman, G. Hame ly, and B. Calde . “Picking s a is ically alid and ea ly
simula ion poin s”. In: P oceedings o he In e na ional Con e ence on Pa allel A -
chi ec u es and Compila ion Techniques. 2003, pp. 244–255.
[91] S. D. Pes el, S. Eye man, and L. Eeckhou . “Mic o-A chi ec u e Independen
B anch Beha io Cha ac e iza ion”. In: IEEE In e na ional Symposium on Pe -
o mance Analysis o Sys ems and So wa e. 2015, pp. 135–144.
[92] R. Rabensei ne , G. Hage , and G. Jos . “Hyb id MPI/OpenMP pa allel p o-
g amming on clus e s o mul i-co e SMP nodes”. In: P oceedings o he 17 h Eu-
omic o In e na ional Con e ence on Pa allel, Dis ibu ed and Ne wo k-Based P o-
cessing. 2009, pp. 427–436.
[93] N. Rajo ic, A. Rico, J. Vipond, I. Gelado, N. Puzo ic, and A. Rami ez. “Ex-
pe iences Wi h Mobile P ocesso s o Ene gy E icien HPC”. In: P oceedings
o he Con e ence on Design, Au oma ion and Tes in Eu ope. No embe . 2013,
pp. 464–468.
[94] N. Rajo ic, P. M. Ca pen e , I. Gelado, N. Puzo ic, A. Rami ez, and M. Vale o.
“Supe compu ing wi h commodi y CPUs: A e Mobile SoCs Ready o HPC?”
In: In e na ional Con e ence o High Pe o mance Compu ing, Ne wo king, S o age
and Analysis. 2013, pp. 1–12.
[95] N. Rajo ic, L. Vilano a, C. Villa ieja, N. Puzo ic, and A. Rami ez. “The low
powe a chi ec u e app oach owa ds exascale compu ing”. In: Jou nal o Com-
pu a ional Science 4.6 (2013), pp. 439–443.
126
BIBLIOGRAPHY
[96] J. Reinde s. In el Th ead Building Blocks: Ou i ing C++ o Mul i-Co e P ocesso
Pa allelism. O eilly Media, Inc., 2007.
[97] P. Ren, M. Lis, M. H. Cho, K. S. Shim, C. W. Fle che , O. Khan, N. Zheng, and
S. De adas. “HORNET: A cycle-le el mul ico e simula o ”. In: IEEE T ansac-
ions on Compu e -Aided Design o In eg a ed Ci cui s and Sys ems 31.6 (2012),
pp. 890–903.
[98] A. Rico, A. Rami ez, and M. Vale o. “A ailable ask-le el pa allelism on he
Cell BE”. In: Scien i ic P og amming 17.1-2 (2009), pp. 59–76.
[99] A. Rico, F. Caba cas, C. Villa ieja, M. Pa lo ic, A. Vega, Y. E sion, A. Rami ez,
and M. Vale o. “On he simula ion o la ge-scale a chi ec u es using mul iple
applica ion abs ac ion le els”. In: ACM T ansac ions on A chi ec u e and Code
Op imiza ion 8.4 (2012), pp. 1–20.
[100] A. Rico, A. Du an, F. Caba cas, Y. E sion, A. Rami ez, and M. Vale o. “T ace-
d i en simula ion o mul i h eaded applica ions”. In: IEEE In e na ional Sym-
posium on Pe o mance Analysis o Sys ems and So wa e. IEEE, 2011, pp. 87–96.
[101] A. F. Rod igues, K. S. Hemme , B. W. Ba e , C. Ke sey, R. Old ield, M. We-
s on, R Risen, J. Cook, P. Rosen eld, E. Coope -Balls, e al. “The s uc u al
simula ion oolki ”. In: ACM SIGMETRICS Pe o mance E alua ion Re iew 38.4
(2011), p. 37.
[102] P. Rosen eld, E. Coope -Balis, and B. Jacob. “DRAMSim2: A cycle accu a e
memo y sys em simula o ”. In: IEEE Compu e A chi ec u e Le e s 10.1 (2011),
pp. 16–19.
[103] D. Sanchez and C. Kozy akis. “ZSim: Fas and accu a e mic oa chi ec u al
simula ion o housand-co e sys ems”. In: P oceedings o he In e na ional Sym-
posium on Compu e A chi ec u e. 2013, pp. 475–486.
[104] A. Sandbe g, N. Nikole is, T. E. Ca lson, E. Hage s en, S. Kaxi as, and D.
Black-Scha e . “Full Speed Ahead: De ailed A chi ec u al Simula ion a Nea -
Na i e Speed”. In: 2015 IEEE In e na ional Symposium on Wo kload Cha ac e i-
za ion. IEEE, 2015, pp. 183–192.
[105] D. Schmidl, P. Philippen, D. Lo enz, C. Rössel, M. Geime , D. An Mey, B.
Moh , and F. Wol . “Pe o mance analysis echniques o ask-based OpenMP
applica ions”. In: Lec u e No es in Compu e Science (including subse ies Lec u e
No es in A i icial In elligence and Lec u e No es in Bioin o ma ics) 7312 LNCS.01
(2012), pp. 196–209.
BIBLIOGRAPHY
127
[106] T. She wood, E. Pe elman, and B. Calde . “Basic block dis ibu ion analysis
o ind pe iodic beha io and simula ion poin s in applica ions”. In: P oceed-
ings o he In e na ional Con e ence on Pa allel A chi ec u es and Compila ion Tech-
niques. 2001, pp. 3–14.
[107] T. She wood, E. Pe elman, G. Hame ly, and B. Calde . “Au oma ically cha -
ac e izing la ge scale p og am beha io ”. In: ACM SIGOPS Ope a ing Sys ems
Re iew 36.5 (2002), pp. 45–57.
[108] A. Sna ely, L. Ca ing on, N. Wol e , J. Laba a, R. Badia, and A. Pu kayas ha.
“A amewo k o pe o mance modeling and p edic ion”. In: P oceedings o
he ACM/IEEE Con e ence on Supe compu ing. 2002, pp. 1–17.
[109] A. Sodani, R. G amun , J. Co bal, H. S. Kim, K. Vinod, S. Chin hamani, S.
Hu sell, R. Aga wal, and Y. C. Liu. “Knigh s Landing: Second-Gene a ion
In el Xeon Phi P oduc ”. In: IEEE Mic o 36.2 (2016), pp. 34–46.
[110] G. Sou he n and J. Renau. “Analysis o PARSEC wo kload scalabili y”. In:
P oceedings o he In e na ional Symposium on Pe o mance Analysis o Sys ems
and So wa e. 2016, pp. 133–142.
[111] Z. Tan, A Wa e man, R A izienis, Y. Lee, H Cook, D Pa e son, and K Asano ic.
“RAMP gold: An FPGA-based a chi ec u e simula o o mul ip ocesso s”.
In: P oceedings o he 47 h ACM/IEEE Design Au oma ion Con e ence. 2010, pp. 463–
468.
[112] R. Tessie . “Cosmological hyd odynamics wi h adap i e mesh e inemen -A
new high esolu ion code called RAMSES”. In: As onomy & As ophysics 385.1
(2002), pp. 337–364.
[113] TOP500 Supe compu e Si es.URL:h ps://www. op500.o g/ ( isi ed on
03/02/2017).
[114] M. Vale o, M. Mo e o, M. Casas, E. Ayguade, and J. Laba a. “Run ime-Awa e
A chi ec u es: A Fi s App oach”. In: Supe compu ing on ie s and inno a ions
1.1 (2014), pp. 29–44.
[115] S. Van Den S een, S. Eye man, S. De Pes el, M. Mech i, T. E. Ca lson, D.
Black-Scha e , E. Hage s en, and L. Eeckhou . “Analy ical P ocesso Pe o -
mance and Powe Modeling Using Mic o-A chi ec u e Independen Cha ac-
e is ics”. In: IEEE T ansac ions on Compu e s 65.12 (2016), pp. 3537–3551.
[116] R. F. Van de Wijngaa and H. Jin. NAS Pa allel Benchma ks, Mul i-Zone Ve -
sions. Tech. ep. 2003.
[117] T. F. Wenisch, R. E. Wunde lich, M. Fe dman, A. Ailamaki, B. Falsa i, and J.
C. Hoe. “SimFlex: S a is ical Sampling o Compu e Sys em Simula ion”. In:
IEEE Mic o 26.4 (2006), pp. 18–31.

128
BIBLIOGRAPHY
[118] T. F. Wenisch, R. E. Wunde lich, B. Falsa i, and J. C. Hoe. “Tu boSMARTS: Ac-
cu a e mic oa chi ec u e simula ion sampling in minu es”. In: P oceedings o
he 2005 ACM SIGMETRICS In e na ional Con e ence on Measu emen and Mod-
eling o Compu e Sys ems. Vol. 33. 1. 2005, pp. 408–409.
[119] S. Whi e. “The AMD Op e on Sea le: A 64b ARM Dense Se e P ocesso ”.
In: Ho Chips (2014).
[120] T. Wiegand. “O e iew o he H. 264/AVC ideo coding s anda d”. In: IEEE
T ansac ions on Ci cui s and Sys ems o Video Technology 13.7 (2003), pp. 560 –
576.
[121] R. E. Wunde lich, T. F. Wenisch, B. Falsa i, and J. C. Hoe. “SMARTS: accele -
a ing mic oa chi ec u e simula ion ia igo ous s a is ical sampling”. In: P o-
ceedings o he 30 h Annual In e na ional Symposium on Compu e A chi ec u e.
2003, pp. 84–95.
[122] S. Yoon and A. Jameson. “Lowe -uppe symme ic-Gauss-Seidel me hod o
he Eule and Na ie -S okes equa ions”. In: AIAA jou nal 26.9 (1988), pp. 1025–
1026.
[123] M. T. You s . “PTLsim: A cycle accu a e ull sys em x86-64 mic oa chi ec u al
simula o ”. In: IEEE In e na ional Symposium on Pe o mance Analysis o Sys-
ems and So wa e. 2007, pp. 23–34.
[124] Yue Luo, L. John, and L. Eeckhou . “Sel -Moni o ed Adap i e Cache Wa m-
Up o Mic op ocesso Simula ion”. In: 16 h Symposium on Compu e A chi ec-
u e and High Pe o mance Compu ing. IEEE, 2004, pp. 10–17.
[125] C. Zhang. “Ma s: A 64-co e ARM 8 p ocesso ”. In: P oceedings o he 2015
IEEE Ho Chips Symposium. 2016.
[126] G. Zheng, G. Gup a, E. Bohm, I. Dooley, and L. V. Kale. “Simula ing la ge
scale pa allel applica ions using s a is ical models o sequen ial execu ion
blocks”. In: P oceedings o he In e na ional Con e ence on Pa allel and Dis ibu ed
Sys ems. 2010, pp. 221–228.