TaskPoint: sampled simulation of task-based programs

TaskPoin : Sampled Simula ion o Task-Based P og ams Thomas G ass∗†, Alejand o Rico‡, Ma c Casas†, Miquel Mo e o∗†, Edua d Ayguad´ e∗† ∗Uni e si a Poli ` ecnica de Ca alunya, †Ba celona Supe compu ing Cen e , ‡ARM Inc. Abs ac —Sampled simula ion is a ma u e echnique o e- ducing simula ion ime o single- h eaded p og ams, bu i is no di ec ly applicable o simula ion o mul i- h eaded a chi ec u es. Recen mul i- h eaded sampling echniques assume ha he wo kload assigned o each h ead does no change ac oss mul iple execu ions o a p og am. This assump ion does no hold o dynamically scheduled ask-based p og amming models. Task- based p og amming models allow he p og amme o speci y p og am segmen s as asks which a e ins an ia ed many imes and scheduled dynamically o a ailable h eads. Due o sys em noise and a ia ion in scheduling decisions, wo consecu i e execu ions on he same machine ypically esul in di e en ins uc ion s eams p ocessed by each h ead. In his pape , we p opose TaskPoin , a sampled simula ion echnique o dynamically scheduled ask-based p og ams. We le e age ask ins ances as sampling uni s and simula e only a ac ion o all ask ins ances in de ail. Be ween de ailed simula ion in e als we employ a no el as - o wa d mechanism o dynamically scheduled p og ams. We e alua e he p oposed echnique on a se o 19 ask-based pa allel benchma ks and wo di e en a chi ec u es. Compa ed o de ailed simula ion, TaskPoin accele a es a chi ec u al simula ion wi h 64 simula ed h eads by an a e age ac o o 19.1 a an a e age e o o 1.8% and a maximum e o o 15.0%. I. INTRODUCTION Compu e a chi ec u e esea ch hea ily elies on simula ion. Inc easing design complexi y and inc easing co e coun s in mode n mul i-co e p ocesso s p esen new challenges o a chi- ec u al simula ion. Fi s , simula ing a mo e complex design equi es mo e ime o a gi en wo kload. Second, he mo e complex a design, he la ge he simula ed wo kload needs o be in o de o meaning ully s ess he design. One echnique o educe simula ion ime is sampling. Sam- pled simula ion educes simula ion ime by only simula ing a ac ion o a wo kload. Sampling is a well-es ablished echnique o simula ion o single- h eaded a chi ec u es. The p e alen echniques pe o m de ailed simula ion o ei he only he ep esen a i e p og am pa s iden i ied in p o iling [1] o pe iodically ia ime-based sampling [2]. While sampled simula ion is a well-es ablished echnique o single- h eaded a chi ec u es, echniques a ge ing mul i- h eaded a chi ec u es ha e only been ecen ly p oposed. The main challenge in sampling mul i- h eaded simula ions is o ensu e ha a he beginning o each de ailed simula ion in e al all h eads ha e made he same amoun o p og ess as in a ull de ailed simula ion. A echnique p oposed by Ca lson e al. [3] achie es his by selec ing a pe iodic sampling in e al du ing o line p o iling and, du ing simula ion, es ima ing he a e a which o as - o wa d each h ead be ween in e als o de ailed simula ion. Ca lson e al. [4] also p opose a echnique based on he insigh ha a e a global ba ie all h eads a e synch onized and esume execu ion simul aneously. The echnique le e ages he in e -ba ie egions in ba ie syn- ch onized p og ams as sampling uni s. Task-based p og amming models ha e been p oposed o educe load imbalance and hus inc ease pa allel e iciency o u u e la ge-scale mul i-co e machines [5]. A ask-based p og amming model allows he p og amme o speci y p o- g am pa s as asks and o speci y dependencies be ween hose asks. Tasks a e ypically ins an ia ed many imes du ing he execu ion o a p og am. O e -decomposi ion ensu es ha he e a e many mo e ask ins ances han he e a e execu ion h eads. The o e -decomposi ion o a pa allel p og am in o asks, oge he wi h dynamic scheduling o ask ins ances o h eads, dynamically balances he amoun o wo k assigned o each h ead. In e - ask dependencies en o ce synch oniza ion only when necessa y. The lack o global ba ie s and he dynamically scheduled execu ion o ask-based p og ams make hem unsui able o exis ing sampled simula ion echniques. In his wo k we p esen TaskPoin , a sampled simula ion me hodology o dynamically scheduled ask-based p og ams execu ed on sha ed memo y mul i-co e machines. TaskPoin le e ages ask ins ances as sampling uni s and only simula es a small numbe o hem in de ail. The emaining ask ins ances a e simula ed in a as e simula ion mode, ensu ing ha p og ess in di e en h eads is modelled co ec ly. In his pape , we make he ollowing con ibu ions: •We compa e he pe o mance a ia ion o ask-based p og ams in na i e execu ion and a chi ec u al simula ion. This mo i a es he design o ou TaskPoin me hodology, i s sampling policies and i s as - o wa ding me hodology. •We p esen TaskPoin , a sampled simula ion echnique o mul i-co e a chi ec u es p og ammed wi h a dynami- cally scheduled, ask-based p og amming model. In his con ex , we in oduce wo sampling policies, pe iodic sampling and lazy sampling. Lazy sampling simula es ask ins ances in de ail based on hei ype while pe iodic sampling conside s hei ype and dis ibu ion o e ime. •We p opose a mechanism o accu a ely as - o wa d an a chi ec u al simula ion o a ask-based p og am. Du ing as - o wa d, we model he pe o mance o a gi en ask ins ance based on p e ious ins ances o he same ask ype. We accoun o di e en ask inpu sizes ac oss he applica ion execu ion by ac o ing in he numbe o ins uc ions o he gi en ask ins ance acco dingly. © 2016 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any cu en o u u e media, including ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses,c ea ing new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse o any copy igh ed componen o his wo k in o he wo ks. 2dcon olu ion 3ds encil a omicmon eca lo dynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions 20 15 10 5 0 5 10 15 20 IPC a ia ion[%] 28 24 Fig. 1: IPC a ia ion ac oss all ask ins ances o na i e execu ion wi h 8 h eads, no malized pe ask ype •We e alua e TaskPoin simula ing 19 ask-based pa al- lel benchma ks, including 6 ask-based e sions o he PARSEC benchma k sui e. We e alua e he sensi i i y o TaskPoin o di e en a chi ec u es by es ing di e en numbe s o simula ed h eads on wo di e en con igu- a ions co e ing he opposi e ex emes o he mul i-co e design space: high-pe o mance and low powe . The emainde o his pape is o ganized as ollows. In Sec ion II, we p o ide backg ound and mo i a ion o ou wo k. In Sec ion III, we p esen ou TaskPoin me hodology. Nex , we in oduce ou expe imen al se up in Sec ion IV. We e alua e TaskPoin in Sec ion V. Finally, we p esen ela ed wo k in Sec ion VI, be o e we conclude in Sec ion VII. II. BACKGROUND AND MOTIVATION This sec ion p o ides backg ound on ask-based p og am- ming models. We hen mo i a e ou wo k wi h an analysis o pe o mance a ia ion in na i e execu ion o 19 ask-based pa allel benchma ks. A. Pa allel P og amming Models In adi ional pa allel p og amming models o sha ed mem- o y sys ems, like POSIX Th eads [6], he p og amme ex- plici ly decomposes an applica ion in o concu en ins uc ion s eams and manages synch oniza ion be ween hose. These ins uc ion s eams a e p ocessed simul aneously by di e en h eads. A common p oblem wi h mul i- h eaded p og ams is load imbalance. Load imbalance occu s when di e en h eads each a synch oniza ion poin a di e en poin s in ime. Task-based p og amming models ha e he po en ial o al- le ia e load imbalance and hus inc ease pa allel e iciency. When implemen ing a pa allel p og am using a ask-based p o- g amming model, he p og amme speci ies p og am pa s as asks and, op ionally, da a dependencies be ween hese asks. Tasks a e ins an ia ed many imes du ing he execu ion o a p og am, esul ing in a la ge numbe o ask ins ances, each o which ope a es on di e en da a. A un ime en i onmen dynamically schedules ask ins ances o execu ion h eads. Due o a ine-g ained o e -decomposi ion o he applica ion, he e a e ideally mo e ask ins ances eady o execu ion han he e a e h eads. This allows he un ime en i onmen o dynamically balance he wo kload assigned o each h ead [5]. Fu he op imiza ions a e possible i he a chi ec u e in e aces di ec ly wi h he un ime en i onmen [7, 8]. In his wo k, we di e en ia e be ween ask ypes and ask ins ances. E e y execu ion o a ask decla a ion s a emen a un ime esul s in he c ea ion o a ask ins ance. All ask ins ances esul ing om he same ask decla a ion s a emen in he sou ce code a e said o be o he same ask ype. In a ypical ask-based p og am, he numbe o ask ypes is small, whe eas he numbe o ask ins ances lies in he o de o housands. B. Pe o mance Va ia ion o Task-Based P og ams In o de o mo i a e TaskPoin , ou sampled simula ion echnique o ask-based pa allel p og ams, we analyze pe - o mance a ia ion in na i e execu ion o 19 benchma ks. The in es iga ed benchma ks a e in oduced in Sec ion IV. Di e en benchma ks, and e en di e en ask ypes o he same benchma k, gene ally show di e en a e age ins uc ions pe cycle (IPC). Fo an easy compa ison o pe o mance a ia ion ac oss benchma ks, we no malize he IPC o all ask ins ances o he a e age IPC o hei espec i e ask ype. Fo each benchma k, we use one box plo o hese no malized IPC alues o isualize pe o mance a ia ion ac oss ask ins ances. Figu e 1 shows IPC a ia ion ac oss ask ins ances obse ed in a na i e execu ion wi h 8 h eads on a sys em wi h an In el SandyB idge-EP E5-2670 CPU unning a 2.6 GHz and 128 GB o DDR3-1600 as main memo y. The solid box o each box plo indica es he ange om he i s o he hi d qua ile o he no malized IPC alues, while he whiske s ex end om he i h o he 95 h pe cen ile. IPC alues o ask ins ances below he i h and abo e he 95 h pe cen ile a e ea ed as ou lie s. The Figu e shows ha o 15 ou o 19 benchma ks pe o mance a ia ion lies wi hin ±5%. We show ha pe o mance a ia ion is closely e lec ed in simula ion when we in oduce he TaskSim simula o in Sec ion IV. We mo i a e TaskPoin based on he insigh ha pe o - mance o ask-based p og ams is gene ally egula ac oss ins ances o he same ask ype. A no el y o TaskPoin is ha i le e ages he concep o asks decla ed by he p og amme o iden i y ask ins ances o he same ask ype as sampling uni s o simila pe o mance. III. SAMPLED SIMULATION OF TASK-BASED PROGRAMS In his sec ion, we p esen ou TaskPoin me hodology. Fi s , we in oduce he p e equisi es which need o be ul illed by an a chi ec u al simula o in o de o se e as an implemen a- ion pla o m o TaskPoin . Nex , we p esen he di e en 2 A1 Th ead 1 Th ead 2 Time B1 ... wa mup ... 1 2 3 4 A2B2 A3B3 A4B4 A5 A6 B5 B6 A7 An-1 Bn Bn+1 ... An An+1 Bn+3 An+2 Bn+4 An+3 Bn+5 5 An+4 An+5 Bn+6 Bn+7 An+6 ... measu e sample as - o wa d wa mup measu e sample 0 Bn+2 de ailed simula ion as - o wa d Xi i- h ins ance o ask- ype X Fig. 2: Ini ial wa mup, sampling, as - o wa ding and esampling in TaskPoin phases o TaskPoin ’s sampling mechanism, namely wa m- up, sampling and as - o wa ding. A e wa ds, we in oduce ou pe iodic sampling policy. The sepa a ion in o sampling mechanism and policy allows o he in eg a ion o o he sampling policies wi h low implemen a ion e o . A. Requi emen s o he A chi ec u al Simula o Ou objec i e is o p o ide a sampled simula ion me hod- ology o ask-based p og ams which does no depend on a speci ic a chi ec u al simula o . The e o e, we keep he equi emen s o he a ge simula o o a minimum. In o de o se e as a sui able pla o m o implemen ing ou me hodol- ogy, a simula o needs o ul il he ollowing wo equi emen s: 1) The simula o needs o ea u e a de ailed and a as simula ion mode. 2) The as mode has o be capable o ope a ing a a use - speci ied IPC. Mos con empo a y a chi ec u al simula o s ea u e se e al le els o de ail [9, 10, 11], allowing o ade o speed o accu acy. Thus, we assume he i s equi emen o be i ially ul illed. Rega ding he second equi emen , i a simula o does no suppo ixed-IPC simula ion by de aul , we conside he implemen a ion o his unc ionali y o be a mino e o . B. Sampling Mechanism TaskPoin ope a es on he le el o g anula i y o ask ins ances. A ask ins ance is simula ed ei he in de ailed o in as mode. Simula ion in de ailed mode se es o wa ming a chi ec u al s a e o o measu e samples, whe eas simula ion in as mode accu a ely as - o wa ds simula ion ime. Swi ch- ing be ween de ailed and as mode only occu s be ween wo consecu i e ask ins ances. Figu e 2 illus a es he di e en phases o TaskPoin . Fo each ask ype, we main ain wo ec o s holding he IPC his o ies o he mos ecen ly simula ed ask ins ances. The size Ho hese ec o s is a pa ame e e e ed o as he his o y size. Bo h ec o s a e FIFO bu e s in which a newly added elemen eplaces he oldes one. The i s ec o con ains he his o y o ask ins ances which a e alid samples, i.e. which a e simula ed a e wa ming up a chi ec u al s a e. We e e o i as he his o y o alid samples. The second ec o holds he his o y o all ask ins ances simula ed in de ailed mode, ega dless o he simula ion being p ope ly wa med. We e e o i as he his o y o all samples. While he o me is he sample his o y we usually use o de e mine which IPC o use in as mode, he la e is needed i he e a e ask ypes ha occu in equen ly and can no be sampled in a single sampling in e al. We e e o hese ask ypes as a e ask ypes. In mul i- h eaded applica ions, co-exis ing h eads in e e e wi h each o he , e.g. by compe ing o sha ed esou ces, h ough in e - h ead synch oniza ion o by in alida ing da a esiding in emo e caches. In o de o co ec ly model h ead in e e ence, we simula e all h eads ei he in de ailed mode o in as mode. Since we assume ha mode swi ching only occu s be ween wo consecu i e ask ins ances, he e a e sho phases du ing which some h eads a e simula ed in as - o wa d mode, while o he s a e simula ed in de ailed mode (see 2, 3and 5in Figu e 2). Simula ion Wa mup:Be o e conduc ing pe o mance mea- su emen s, a simula ion needs o be wa med, i.e. i needs o be pu in a ep esen a i e s a e. Wa ming mic o-a chi ec u al s a e in sampled simula ion is well-s udied [1, 2, 12, 13, 14, 15]. In his pape , we wa m he simula ion by simula ing an empi i- cally de e mined numbe o ask ins ances in de ail and a oid complex wa mup schemes. Ins ead, we ocus on he sampling me hodology i sel . Howe e , we dis inguish be ween wa ming a simula ion s a and wa ming be o e esampling a e a simula ion phase in as mode. When a ask ins ance simula ed o wa mup inishes execu ion, i s IPC is added o he his o y o all samples. A simula ion s a , all simula ed mic o-a chi ec u al s uc- u es a e in hei ini ial (cold) s a e. Du ing de ailed simula ion, s a e-holding elemen s begin o ill un il occupancy eaches a s eady s a e. In his wo k, we assume ha simula ing W ask ins ances pe h ead a simula ion s a is su icien o pu ing he simula o in o a ep esen a i e (wa m) s a e. We e e o Was he size o he wa m-up in e al and e alua e di e en alues o Win Sec ion V. A e a simula ion phase in as mode, mic o-a chi ec u al s a e is s ale. Be o e esampling he simula ion, wa mup makes su e ha mic o-a chi ec u al s a e is (app oxima ely) he same as i he whole p og am was simula ed in de ail. Be o e esampling, we pe o m de ailed simula ion un il e e y h ead has simula ed one ask ins ance in de ail. Sampling:Like simula ion wa mup, sampling is pe o med in de ailed simula ion mode. When wa mup is inished, we s a ea ing he simula ed ask ins ances as alid samples. When a alid sample ask ins ance inishes simula ion, i s a e age IPC is added o he his o y o alid samples and o he his o y o all samples. We igge he ansi ion o as mode when one o he ollowing wo condi ions is ul illed: 1) The his o y o alid samples is ully popula ed. 3 Th ead 1 Th ead 2 Time Time 1 1 2 2 P-1 P-1 P P 1 1 2 2 ... ... ... ... ... Th ead 1 Th ead 2 1 1 2 2 P-1 P-1 P P sampling as - o wa d (a) Pe iodic sampling (b) Lazy sampling wa mup Fig. 3: Illus a ion o pe iodic sampling (a) and lazy sampling (b) as a special case o pe iodic sampling wi h in ini e sampling pe iod P 2) A ce ain numbe o ask ins ances has been simula ed wi hou encoun e ing any ins ance o a a e ask ype whose his o y o alid samples is no ye ully popula ed. The i s condi ion means ha all ask ypes a e ully sampled. The second condi ion is needed o a oid spending an excessi e amoun o ime on de ailed simula ion in he p esence o a e ask ypes. In his pape , we cu o sampling when all h eads ha e simula ed 5 ask ins ances wi hou encoun e ing an ins ance o a p e iously obse ed a e ask ype. Accu a e Fas -Fo wa ding:When he ansi ion o as mode is igge ed, all ask ins ances s a ing in he u u e a e simula ed in as mode. Howe e , ask ins ances which s a ed in he pas a e simula ed in de ailed mode un il hey comple e. Task ins ances inishing simula ion a e he ansi ion o as mode a e only added o he his o y o all samples. A ask ins ance simula ed in as mode is simula ed wi h he a e age IPC o he his o y o alid samples o i s ask ype. I a ask ins ance belongs o a a e ask ype whose his o y o alid samples is emp y, we use he a e age IPC o he his o y o all samples ins ead. I he his o y o all samples o he co esponding ask ype is also emp y, we igge esampling. Ra e ask ypes end o occu in equen ly du ing he execu ion o an applica ion. They accoun only o a small pe cen age o he o al ins uc ion coun o an applica ion and a e used o in equen asks, e.g. se ing up and dele ing da a s uc u es. We ind he impac o using non- ep esen a i e samples o as simula ion o a e ask ypes o be negligible. One con ibu ion o his pape is he p esen ed as - o wa ding mechanism o a chi ec u al simula ion o ask- based pa allel p og ams. Ou echnique as - o wa ds each h ead a a a e depending on he ask ype o he ask ins ance cu en ly being simula ed. C. Pe iodic Sampling Policy A sampling policy decides when o esample a simula ion unning in as - o wa d mode. The pe iodic sampling policy, illus a ed in Figu e 3a, wa ms and samples a simula ion a simula ion s a . A e wa ds, i swi ches he simula ion o as - o wa d mode. When a h ead has execu ed a numbe Po ask ins ances o any ask ype in as - o wa d mode, he simula ion is esampled. We e e o he pa ame e Pas he sampling pe iod. When a simula ion is esampled, he en ies o he his o y o alid samples a e disca ded. When esampling is comple e, he simula ion e u ns o as - o wa d mode and he p ocess epea s. Th ead 1 Th ead 2 Time ... Th ead 3 Th ead 4 ... Task ype B Task ype A (a) Change in numbe o execu ion h eads a ime , hus al e ing a e age pe o mance due o esou ce con en ion Th ead 1 Th ead 2 Time ... Th ead 3 Th ead 4 ... (b) Ins ance o a e ask ype s a ing execu ion a ime Fig. 4: Illus a ion o changing numbe o execu ion h eads (a) and a e ask ype (b) Simula ion speedup is de e mined by he size o he sam- pling pe iod. The la ge he sampling pe iod, he mo e ask ins ances a e simula ed in as mode. In he special case o an in ini e sampling pe iod, esampling is ne e igge ed by he sampling policy. We e e o his case as lazy sampling. Lazy sampling is illus a ed in Figu e 3b. I he numbe o ask ins ances o a p og am is oo small o he sampling pe iod is oo la ge, a simula ion inishes du ing he i s as - o wa d in e al, be o e any h ead has simula ed P ask ins ances. In his case, pe iodic sampling is equi alen o lazy sampling. Besides he a o emen ioned case o a h ead ha ing sim- ula ed P ask ins ances in as mode, esampling is also igge ed when i is impossible o accu a ely simula e a ask ins ance in as mode. This happens in he ollowing wo cases. Figu e 4a shows a case whe e he numbe o h eads pa icipa ing in ask execu ion changes a un ime, e.g. when he simula ed applica ion en e s a phase exposing mo e pa - allelism. When he numbe o execu ion h eads changes, so does he con en ion on sha ed esou ces, like sha ed caches and main memo y. This a ec s pe - h ead pe o mance and in alida es p e iously measu ed samples. Resampling a oids p edic ion e o s due o non- ep esen a i e samples. Figu e 4b shows a case whe e he i s ins ance o a new ask ype is encoun e ed while simula ing in as mode. When encoun e ing an ins ance o a p e iously unknown ask ype, he ask ype’s sample his o y is emp y. The e o e, i is impossible o simula e his ask ins ance in as mode. We ci cum en his p oblem by igge ing esampling. 4 Wi h his esampling s a egy, bo h pe iodic sampling and lazy sampling accoun o phase changes in he applica ion. I a new phase is implemen ed wi h di e en ask ypes, he simula ion is esampled. The same holds o changes in he a ailable compu a ion esou ces o he a ailable pa allelism. IV. EXPERIMENTAL SETUP In his sec ion, we in oduce he expe imen al se up we use o implemen and e alua e TaskPoin . Fi s , we in oduce he ask-based p og amming model OmpSs. Subsequen ly, we p esen he 19 benchma ks and he wo a chi ec u es we use in ou e alua ion. Finally, we elabo a e on he TaskSim simula o and ou implemen a ion o as simula ion a a bi a y IPC and show an analysis o pe o mance a ia ion obse ed in simula ion o ask-based p og ams. The OmpSs P og amming Model:Fo ou e alua ions we choose he OmpSs p og amming model [16]. The OmpSs com- pile and un ime en i onmen a e a ailable as open sou ce. OmpSs allows o decla e asks and anno a e hem wi h da a inpu s and ou pu s. Using his in o ma ion, he OmpSs un ime sys em schedules ask ins ances aking da a dependencies in o accoun and pe o ms synch oniza ion only when necessa y. These OmpSs ea u es we e included in o he speci ica ions o OpenMP 3.0 and 4.0. Benchma ks:Table I lis s he benchma ks used in ou e alua ion. They ep esen a a ie y o wo kloads and a e implemen ed using he OmpSs p og amming model. While he majo i y o benchma ks ep esen wo kloads common o high- pe o mance compu ing (HPC), blackscholes,body ack,can- neal,dedup, eqmine and swap ions a e pa o he PARSEC benchma k sui e [17]. Whene e possible, we gene a ed aces equi alen o a leas en seconds o single- h eaded execu ion on a s a e-o - he-a machine. Fo he PARSEC benchma ks we used he simla ge inpu se s. Table I lis s he numbe o ask ins ances and he ime equi ed o a de ailed simula ion o he en i e benchma k o 1 and 64 execu ion h eads using he TaskSim simula o . TaskSim is in oduced la e in his sec ion. Simula ed A chi ec u es:We e alua e he ideli y o ou me hodology by in es iga ing simula ion speedup and execu- ion ime e o o mul i- h eaded simula ions o wo adically di e en mul i-co e a chi ec u es. One esembles a se e - class sys em, while he o he esembles a low-powe mobile pla o m. Table II lis s he key cha ac e is ics o he simula ed a chi ec u es. The high pe o mance a chi ec u e ea u es a la ge eo de bu e and a h ee-le el cache hie a chy, as ound in HPC sys ems. The low-powe a chi ec u e has a smalle eo de bu e and wo le els o cache memo ies, as is ypical o ba e y powe ed mobile sys ems. Recen ly, low-powe sys ems a e gaining in e es o applica ions in HPC [18]. The TaskSim Simula o :We e alua e ou me hodology using he TaskSim simula o [19, 20]. TaskSim is a cycle- accu a e, ace-d i en pe o mance simula o o mul i-co e a chi ec u es. I in e aces wi h an unmodi ied e sion o he OmpSs un ime sys em. The un ime sys em schedules he ask ins ances o he simula ed applica ion o execu ion on he simula ed p ocesso co es. TaskSim has a de ailed and a as simula ion mode. The de ailed mode is based on he Reo de -Bu e Occupancy Analysis model p oposed by Lee e al. [21]. When unning in de ailed mode, TaskSim models a use -de ined memo y hie a - chy including p i a e and sha ed cache memo ies, in e connec s uc u es and DRAM. In he as mode, called bu s mode, TaskSim only accoun s o he numbe o CPU cycles be ween e en s, in ou case be ween he beginning and he end o he execu ion o a ask ins ance. In he exis ing implemen a ion, TaskSim eads a ask ins ance’s cycle coun om he applica ion ace. In he implemen a ion o ou as - o wa d mechanism, he du a ion o a ask ins ance is calcula ed a he beginning o i s execu ion. Using he mean IPC o he sample his o y o a ask ins ance i’s ask ype Tand i s dynamic ins uc ion coun Ii, we es ima e i s numbe o execu ion cycles Ciacco ding o Ci=Ii IP CT . The esul is he numbe o cycles i akes o execu e he ask ins ance a an IPC o IP CT, he a e age IPC o he ins ance’s ask ype. The dynamic ins uc ion coun is ead om he applica ion ace. In he scope o his wo k, we ex ended TaskSim wi h he capabili y o swi ch be ween de ailed and as - o wa d mode a un ime. We also ex ended i s as simula ion mode. Ins ead o using p e iously eco ded cycle coun s om a ace, ou implemen a ion o as mode uses cycle coun s p edic ed by ou as - o wa d mechanism. To he bes o ou knowledge, his is he i s as - o wa d mechanism applying di e en IPCs o di e en pa s o a p og am. Ou mechanism allows as - o wa ding dynamically scheduled pa allel p og ams in which he pe - h ead ins uc ion s eam is a-p io i unknown. Nex , we e alua e pe o mance a ia ion o ask-based p og ams obse ed in simula ion wi h TaskSim. Figu e 5 shows IPC a ia ion ac oss ask ins ances in an a chi ec u al simula ion wi h 8 execu ion h eads. The pa am- e e s o he simula ed a chi ec u e ma ch he machine used o na i e execu ion, as a as hey a e publicly a ailable. All benchma ks showing a pe o mance a ia ion o less hen ±5% in na i e execu ion (see Figu e 1) also do so in simula ion. Con e sely, h ee ou o he ou benchma ks showing a a ia ion la ge han ±5% in na i e execu ion also do so in simula ion. The excep ion is spa se-ma ix- ec o - mul iplica ion, which in na i e execu ion exhibi s a a ia ion o nea ly ±10%, compa ed o less han ±5% in simula ion. The h ee benchma ks wi h he la ges deg ee o pe o mance a ia ion in na i e execu ion, namely checkSpa seLU,dedup and eqmine, also show he la ges a ia ion in simula ion. Due o modelling inaccu acies in TaskSim’s de ailed simu- la ion mode, he magni udes o pe o mance a ia ion in na i e execu ion and simula ion do no ma ch exac ly. Howe e , o 18 ou o 19 benchma ks we co ec ly iden i y i a benchma k exposes a pe o mance a ia ion o mo e o less han 5%. V. EVALUATION In his sec ion, we conduc a sensi i i y analysis o Task- Poin ’s model pa ame e s. Then, we e alua e execu ion ime e o and simula ion speedup o pe iodic sampling and lazy 5 TABLE I: Task-based pa allel benchma ks used o he e alua ion o TaskPoin Benchma k # Task # Task Simula ion ime [h:min]P ope ies Types Ins ances 1 Th ead 64 Th eads 2d-con olu ion 1 16384 31:37 59:34 Ke nel: s ided memo y accesses 3d-s encil 1 16370 9:12 40:51 Ke nel: s ided memo y accesses a omic-mon e-ca lo-dynamics 1 16384 8:38 15:16 Ke nel: emba assingly pa allel dense-ma ix-mul iplica ion 1 17576 70:14 127:10 Ke nel: high da a euse, compu e bound his og am 1 16384 6:02 12:13 Ke nel: a omic ope a ions n-body 2 25000 8:15 12:31 Ke nel: i egula memo y accesses educ ion 2 16384 1:51 5:15 Ke nel: pa allelism dec eases o e ime spa se-ma ix- ec o -mul iplica ion 1 1024 0:33 1:26 Ke nel: load imbalance, memo y bound ec o -ope a ion 1 16400 24:25 191:00 Ke nel: egula , memo y bound checkSpa seLU 11 22058 7:25 17:17 Decomposi ion o la ge, spa se ma ices cholesky 4 19600 33:42 59:29 Decomposi ion o He mi ian posi i e-de ini e ma ices kmeans 6 16337 75:21 141:02 Clus e ing based on Lloyd’s algo i hm knn 2 18400 31:28 65:27 Ins ance-based machine lea ning algo i hm blackscholes 2 24500 8:42 17:19 Op ion p ice calcula ion body ack 7 21439 15:24 31:28 Human body acking wi h mul iple came as canneal 1 16384 11:13 29:38 Cache-awa e simula ed annealing dedup 4 15738 10:08 23:32 Deduplica ion: combina ion o global and local comp ession eqmine 7 1932 23:52 34:13 F equen Pa e n G ow h me hod o F equen I em Mining swap ions 1 16384 29:27 70:25 Mon e-Ca lo simula ion o calcula e swap ion p ices 2dcon olu ion 3ds encil a omicmon eca lo dynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions 20 15 10 5 0 5 10 15 20 IPC a ia ion[%] 26 39 21 Fig. 5: IPC a ia ion ac oss all ask ins ances o simula ion o high-pe o mance a chi ec u e wi h 8 h eads, no malized pe ask ype TABLE II: A chi ec u al pa ame e s o high pe o mance and mobile con igu a ions used o model alida ion Pa ame e High-pe . Low-powe Reo de -bu e size 168 40 Issue wid h 4 3 Commi a e 4 3 Cache line size 64 B 64 B L1 cache 32 kB p i a e 4 cycles la ency 8-way associa i e 32 kB p i a e 4 cycles la ency 2-way associa i e L2 cache 2 MB p i a e 11 cycles la ency 8-way associa i e 1 MB sha ed 21 cycles la ency 16-way associa i e L3 cache 20 MB sha ed 28 cycles la ency 20-way associa i e none sampling. Finally, we es he obus ness o ou model by using he same pa ame e s o simula e a low-powe a chi ec u e. A. Adjus ing he Model Pa ame e s We de e mine he op imal model pa ame e s ollowing an inc emen al app oach. Fi s , we de e mine he op imal numbe Wo ask ins ances needed o wa mup a simula ion s a . A e wa ds, we conside di e en numbe s o ask ins ances Hcons i u ing he sample his o y. Finally, we explo e a ange o alues o he sampling pe iod P. In o de o de e mine he op imal alue o Wwe se H= 10 and P=∞and e alua e di e en alues anging om W= 0 (no wa mup) o W= 10. Figu e 6a shows e o and speedup, a e aged o e simula ions wi h 32 and 64 h eads. The epo ed alues a e a e aged o e he benchma ks and ke nels wi h an e o >5% o a leas one alue o H, namely 2d-con olu ion,3d-s encil,a omic-mon e-ca lo-dynamics,knn and blackscholes. We ound ha W= 2 yields an a e age e o o less han 2%. La ge alues o Wdo no signi ican ly educe he a e age e o , bu hey educe simula ion speedup. The e o e, o he emainde o his pape , we se W= 2. Nex , we e alua e di e en alues o H, he size o he sample his o y. Fo his pu pose, we se P=∞. No e ha we al eady se W= 2. Figu e 6b shows e o and speedup o di e en sizes Ho he sample his o y, a e aged o e simula ions wi h 32 and 64 h eads o he a o emen ioned benchma ks. We ound ha H= 4 minimizes he a e age e o . This alue also minimizes he s anda d de ia ion o he a e age e o , which is no shown in he Figu e. La ge alues o Hdo no only esul in a la ge a e age e o , bu also in lowe simula ion speedup. The e o e, o he emainde o his pape , we se H= 4. Finally, we explo e di e en sizes o he sampling pe iod P. Wi h W= 2 and H= 4 al eady ixed, Pis he only emaining pa ame e . Figu e 6c shows he a e age e o o alues o P anging om 10 o 1,000. We ind ha a e age e o 6 0 2 4 6 8 10 Numbe  W o  askins ances o wa mup 0 2 4 6 8 10 A e agee o [%] 0 50 100 150 200 A e agespeedup E o Speedup (a) E o and speedup o di e en sizes Wo wa mup in e al, a e age o 32 and 64 h eads 1 2 3 4 5 6 7 8 9 10 Size H o samplehis o y 0 2 4 6 8 A e agee o [%] 0 10 20 30 40 A e agespeedup E o Speedup (b) E o and speedup o di e en sizes Ho ask ins ance his o y, a e age o 32 and 64 h eads 101102103 Size P o samplingpe iod 0.0 0.5 1.0 1.5 2.0 2.5 A e agee o [%] 0 5 10 15 20 25 A e agespeedup E o Speedup (c) E o and speedup o di e en sizes Po sampling pe iod, a e age o 32 and 64 h eads Fig. 6: E o and speedup o di e en sizes o wa mup in e al (a), sample his o y (b) and sampling pe iod (c) and speedup inc ease wi h he size o he sampling pe iod. The la ge he alue o P, mo e ask ins ances a e simula ed in as mode. Since he o al numbe o ask ins ances o a p og am is cons an , he ac ion o de ailed simula ion dec eases, esul ing in inc easing speedup. Fo P≥1000 e o and speedup emain cons an . A his poin , none o he in es iga ed p og ams has a su icien numbe o ask ins ances o esampling he simula ion a leas once and pe iodic sampling becomes equi alen o lazy sampling. We aim o a simula ion e o o less han 1%. A sampling pe iod P= 250 yields an e o o 0.8% and a simula ion speedup o 15.1x, a e aged o e he benchma ks used in ou sensi i i y analysis. In he emainde o his sec ion, we e alua e TaskPoin o pe iodic sampling wi h P= 250 and o lazy sampling (pe iodic sampling wi h P=∞). B. Pe iodic Sampling Fi s , we e alua e pe iodic sampling, simula ing he high- pe o mance a chi ec u e in Table II, which we also use o ind he sampling pa ame e s. A e wa ds, we simula e he low- powe a chi ec u e using he same sampling pa ame e s. High-Pe o mance A chi ec u e:Figu e 7 shows execu ion ime e o and simula ion speedup o all in es iga ed bench- ma ks, simula ed wi h he pa ame e s W= 2,H= 4 and P= 250. The a e age execu ion ime e o is less han 2% o 8, 16, 32 and 64 simula ed h eads. The e o o 1, 2 and 4 simula ed h eads is less han 1% and no shown in he Figu e. We obse e he la ges simula ion speedup o 76.2 o spa se-ma ix- ec o -mul iplica ion execu ed wi h 8 h eads. We obse e he highes e o o 8.9% in he simula ion o eqmine wi h 8 h eads. F eqmine consis s o 7 di e en ask ypes, one o which accoun s o 93% o he o al numbe o dynamic ins uc ions. The dynamic ins uc ion coun o he ins ances o his ask ype anges om 490 o 11,000,000. Inspec ing he sou ce code e eals a cons uc o nes ed i - s a emen s in a ask decla a ion. This causes di e en ins ances o he same ask ype o ollow comple ely un ela ed con ol low pa hs. The unbalanced size ac oss ask ins ances makes sampling he simula ions wi h 32 and 64 h eads ine ec i e. Since hese con igu a ions a e simula ed almos en i ely in de ail, he e o is negligible and speedup is close o 1. F om his inding, we de i e a ecommenda ion o p o- g amme s o imp o ing pe o mance p edic abili y o ask- based p og ams: One should a oid la ge-scale con ol low di e gence among ins ances o he same ask ype. In p ac ice, his is achie ed by decla ing code pe o ming un ela ed wo k as di e en ask ypes. The second la ges e o o 7.3% is shown by dedup o 64 h eads. Dedup consis s o 4 ask ypes, one o which accoun s o 99.9% o he dynamic ins uc ion coun . The dynamic ins uc ion coun o he ins ances o his ask ype anges om 3,500,000 o 25,100,000. The domina ing ask ype pe o ms de-duplica ion as well as comp ession, which a e highly inpu dependen ope a ions. P e ious wo k iden i ied inpu dependence as a sou ce o pe o mance a ia ion [22]. Pe o mance a ia ion makes i di icul o de e mine a ask ype’s a e age pe o mance du ing sampling. We ecognize ha , in ce ain cases, inpu dependence can no be a oided. One way o imp o e he accu acy o sam- pled simula ion o p og ams showing inpu dependence is o classi y ask ins ances in o classes o simila pe o mance. We en ision clus e ing o ins ances o he same ask ype based on mic o-a chi ec u e independen me ics, e.g. ins uc ion coun o ins uc ion mix. We lea e his o u u e wo k. Nex , we e alua e he gene aliza ion capabili y o pe iodic sampling. We simula e a low-powe a chi ec u e which is adically di e en om he high-pe o mance a chi ec u e we used o de e mine he sampling pa ame e s. Low-Powe A chi ec u e:Figu e 8 shows execu ion ime e o and simula ion speedup o simula ions o all benchma ks execu ed on he low-powe a chi ec u e in oduced in Table II wi h 1, 2, 4 and 8 h eads. We no ice ha , o inc easing 7 0 2 4 6 8 10 Absolu ee o [%] 8 h eads 16 h eads 32 h eads 64 h eads 2dcon olu ion 3ds encil a omicmon e ca lodynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions a e age 100 101 102 Speedup Fig. 7: E o and speedup o pe iodic sampling; high-pe o mance a chi ec u e; P= 250 0 2 4 6 8 10 Absolu ee o [%] 11.0 13.0 1 h ead 2 h eads 4 h eads 8 h eads 2dcon olu ion 3ds encil a omicmon e ca lodynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions a e age 100 101 102 Speedup Fig. 8: E o and speedup o pe iodic sampling; low-powe a chi ec u e; P= 250 h ead coun s, speedup deg ades less han in he case o he high-pe o mance a chi ec u e. Since we simula e smalle h ead coun s, he simula ion is esampled mo e o en and he pe cen age o ask ins ances simula ed in as mode is mo e simila ac oss di e en h ead coun s. Wi h an e o o 13.0% o 4 h eads, eqmine is he benchma k wi h he highes e o . This is consis en wi h he simula ion o he high-pe o mance a chi ec u e. We a ibu e his e o o he same eason as in he case o he high- pe o mance a chi ec u e, namely he highly imbalanced size o he ins ances o he dominan ask ype. We obse ed he second la ges e o o 8.4% o spa se- ma ix- ec o -mul iplica ion wi h 8 h eads. Depending on he s uc u e o he inpu ma ix, memo y accesses a e mo e o less egula [23]. We conclude ha , due o he wo-le el cache hie a chy, he smalle las -le el cache and he lowe memo y bandwid h, his has a highe impac on pe o mance a ia ion han in he high-pe o mance a chi ec u e. This is ano he example o inpu dependence, simila o he case o dedup explained in he p e ious sec ion. C. Lazy Sampling Fo ou e alua ion o lazy sampling, we se W= 2,H= 4 and P=∞. We simula e he benchma ks lis ed in Table I execu ing on he high pe o mance a chi ec u e and he low- powe a chi ec u e lis ed in Table II. High-Pe o mance A chi ec u e:Figu e 9 shows execu- ion ime e o and simula ion speedup o he lazy sampling policy o he in es iga ed benchma ks execu ed on he high- pe o mance a chi ec u e. The a e age e o is less han 2% o all simula ed h ead coun s (including 1, 2, and 4 h eads, which a e no shown in he Figu e). Dedup and eqmine a e s ill he benchma ks showing he highes e o . Compa ed o pe iodic sampling, he highes obse ed e o o dedup inc eases om 7.3% o 15.0% o he simula ion wi h 64 h eads. In he case o eqmine, he highes obse ed e o inc eases om 8.9% o 9.6% o he simula ion wi h 8 h eads. While he a e age e o o lazy sampling is compa able o he e o o pe iodic sampling, we obse e a signi ican inc ease o a e age simula ion speedup. Compa ed o pe iodic sampling, we obse e he la ges inc ease om 44.4 o 178.5 o he a e age speedup o he simula ions wi h 8 h eads. The smalles gain in speedup is obse ed o he simula ions wi h 64 h eads, in which speedup inc eases om 15.8 o 19.1. Fo 1 h ead, which is no shown in he Figu e, speedup inc eases om 43.2 o 1019. Low-Powe A chi ec u e:Figu e 10 shows execu ion ime e o and simula ion speedup o he low-powe a chi ec u e. We obse e a ma ginal inc ease o he maximum e o o spa se-ma ix- ec o -mul iplica ion and eqmine, he bench- 8 0 2 4 6 8 10 Absolu ee o [%] 14.2 15.0 8 h eads 16 h eads 32 h eads 64 h eads 2dcon olu ion 3ds encil a omicmon e ca lodynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions a e age 101 102 103 104 Speedup Fig. 9: E o and speed-up o lazy sampling; high-pe o mance a chi ec u e 0 2 4 6 8 10 Absolu ee o [%] 10.3 11.2 13.1 11.3 1 h ead 2 h eads 4 h eads 8 h eads 2dcon olu ion 3ds encil a omicmon e ca lodynamics densema ix mul iplica ion his og am nbody educ ion spa sema ix ec o  mul iplica ion ec o ope a ion checkSpa seLU cholesky kmeans knn blackscholes body ack canneal dedup eqmine swap ions a e age 101 102 103 104 Speedup Fig. 10: E o and speed-up o lazy sampling; low-powe a chi ec u e ma ks wi h he la ges e o s in he simula ions o he low- powe a chi ec u e employing pe iodic sampling. Howe e , in he case o dedup, he e o inc eases o all simula ed h ead coun s. We obse e he highes inc ease, om 3.2% o 11.3%, o he simula ion wi h 8 h eads. Summa y:The esul s o ou e alua ion show ha Task- Poin accu a ely p edic s execu ion ime o ask-based p o- g ams. Fo lazy sampling, he a e age e o is 1.8% wi h a maximum e o o 15% and a simula ion speedup o 19.1. We show ha lazy sampling achie es much g ea e speedup han pe iodic sampling a a compa able e o . The e o e, we ad oca e he use o lazy sampling o e alua ions equi ing a la ge numbe o simula ions, e.g. du ing he ea ly phase o design space explo a ion. We ecommend o employ pe iodic sampling in la e phases o design space explo a ion when he size o he design space has al eady been signi ican ly educed. VI. RELATED WORK In his sec ion, we i s in oduce di e en simula o s o mul i-co e sys ems. Then, we p esen he p e alen ech- niques o sampled simula ion o single- h eaded a chi ec u es. A e wa ds, we e iew ecen wo k on sampled simula ion o mul i- h eaded a chi ec u es. Finally, we p esen wo k on pe o mance analysis o ask-based p og ams. Mul i-Th eaded A chi ec u al Simula ion: COTSon [10] is a ull-sys em simula o decoupling unc ional and iming simula ion. Func ional simula ion elies on jus -in- ime com- pila ion o he simula ed p og am. COTSon ea u es se e al le els o de ail and suppo s sampling. In addi ion o pe o mance, ESESC [24] also simula es a u u e design’s powe consump ion and he mal beha iou . ESESC is he i s simula o applying ime-based sampling o simula ion o mul i- h eaded applica ions. The ull-sys em simula o gem5 [11] ea u es CPU models a se e al le els o de ail, anging om a model employing na i e execu ion o a de ailed model o a supe scala ou -o - o de CPU. Besides o he s, gem5 suppo s he x86 and ARM a chi ec u es, which a e he mos p e alen a chi ec u es oday. In con as o he a o emen ioned simula o s, Snipe [25] ea u es a pu ely analy ic CPU model. Ins ead o modelling mic o-a chi ec u al s uc u es wi hin he CPU, i employs he mechanis ic In e al Simula ion model [26]. The highe le el o abs ac ion o in e al simula ion is di ec ly e lec ed in a highe simula ion speed, compa ed o mo e de ailed models. Single-Th eaded Simula ion Sampling:In hei SimPoin me hodology [1], She wood e al. use basic block ec o s o iden i y he mos ep esen a i e code sec ions. The majo simula ion e o is spen on hese sec ions SimPoin s equi es a-p io i p o iling o he applica ion o be simula ed in o de o 9