HPCA07-TUTORIAL

Solihin

Description

‰‰‰„„„‰‰‰‰„„„‰„„„„„„„‰‰„„‰‰„„„‰‰‰Computer Performance ModelingGoal: Estimating and understanding the performance of computer systemsPractical Cache Performance Low-Level ModelsModeling for Computer ArchitectsVarious levels of details: functional, trace, cycle-accurate, etc.ProsVersatile: adaptable to new architectures and workloadDetails: can embed very detailed statistics Yan Solihin, NCSU, [e-mail]: SimpleScalar, SIMICS widely usedFei Guo, NCSU, [e-mail] Puzak, IBM, [e-mail](n) overhead, scales with workload size: each instruction/event is simulated to capture its effectPhil Emma, IBM, [e-mail]: realistic workload has many billions of instructions2Modeling MethodsComputer Performance ModelingHigh-Level Models White Box Purpose: Evaluating gross trade-offs of designsModel incorporates knowledge about the system (e.g. relationships of parameters are known a priori)ProsAnalytical or heuristics-basedShort execution time, and sometimes O(1)Requires little coding Pros: models reveal insights &explain “why”, no training requiredReveal basic relationships of variablesMay reveal non-obvious trends and insightsCons: problem-specific solutionConsBlack BoxLess versatileModel learns knowledge about the systemRequires performance modeling expertise AI-based: neural networks, decision tree, curve fitting, etc.Uses: Pros: can model complex problem ...

Informations

• Publié par: Vufuk
• Nombre de lectures: 15
• Langue: English

Extrait

Practical Cache Performance Modeling for Computer Architects

Yan Solihin, NCSU,[e-mail] Fei Guo, NCSU,[e-mail] Thomas Puzak, IBM,[e-mail] Phil Emma, IBM,[e-mail]

Computer Performance Modeling „ High-Level Models ‰ Purpose: Evaluating gross trade-offs of designs ‰ Pros „ Short execution time, and sometimes O(1) „ Requires little coding „ Reveal basic relationships of variables „ May reveal non-obvious trends and insights ‰ Cons „ Less versatile „ Requires performance modeling expertise ‰ Uses: „ Early design cycle: for pruning design search space „ Entire design cycle: to re-evaluate design search space if requirements change 3

Computer Performance Modeling „ Goal: Estimating and understanding the performance of computer systems „ Low-Level Models ‰ Various levels of details: functional, trace, cycle-accurate, etc. ‰ Pros „ Versatile: adaptable to new architectures and workload „ Details: can embed very detailed statistics „ Popular: SimpleScalar, SIMICS widely used ‰ Cons „ O(n) overhead, scales with workload size: each instruction/event is simulated to capture its effect „ Slow: realistic workload has many billions of instructions

Modeling Methods „ White Box ‰ Model incorporates knowledge about the system (e.g. relationships of parameters are known a priori) ‰ Analytical or heuristics-based ‰ Pros: models reveal insights &explain why, no training required ‰ Cons: problem-specific solution „ Black Box ‰ Model learns knowledge about the system ‰ AI-based: neural networks, decision tree, curve fitting, etc. ‰ Pros: can model complex problem/system ‰ Cons: prediction without insights, requires training

2

4

1

Focus of this tutorial „ Types: ‰ High Level, Hybrid High/Low level „ A priori knowledge: ‰ White Box „ Socep: ‰ Miss count & rate ‰ Miss cost ‰ Bandwidth usage

Capturing Temporal Locality Behavior

5

Program 8:30  8:45: Introduction 8:45  9:00: Capturing temporal locality behavior 9:00  9:30: Modeling cache sharing 9:30  10:00: Modeling cache replacement policy 10:00  10:30: Coffee Break 10:30  11:30: Analysis of the effects of miss clustering on the cost of a cache miss 11:30  12:30: Interaction of Caching and Bandwidth Pressure

6

Temporal Locality Behavior „ Programs exhibit locality of references „ Spatial locality: the neighbor of recently-accessed data tends to be accessed in the near future „ Temporal locality: recently-accessed data tends to be accessed again (orreused) in the near future „ Snceficaigni:temporal reuse & cache parameters determine all non-cold misses ‰ If each memory block is accessed exactly once, we only have cold misses ‰ Cold misses affected by block size „ How can we capture temporal locality?

8

2

Stack Distance Profiling [ Mattson  70 ] „ Early attempt to capture temporal reuse behavior „ Models LRU stack with a counter for each stack position „ Example: fully associative cache with 8-entry stack ‰ C1: incremented whenever the MRU block is accessed ‰ C2: incremented whenever the 2 nd MRU block is accessed ‰ C3: incremented whenever the 3 rd MRU block is accessed ‰  ‰ C8: incremented whenever the 8 th MRU (or LRU) block is accessed ‰ C>8: incremented whenever the 9 th , 10 th ,  block is accessed

Stack Distance Properties „ For fully-associative LRU ∞ cache with A blocks, the number of misses of the Misses= ∑ C A cache is i=A+1 „ For A-way set associative LRU cache, we can collect ∞ set-specific stack distance profile, and the number of Misses= ∑ C A misses of the set is: i=A+1 „ Alternatively, keep per-set stacks, but use global set of counters

9

11

Typical Shape „ Empirical observation⇒Geometric or exponential sequence „ Due to temporal locality „ C i+1 = C i x r, where 0<r<1 is the common ratio Incremented on access to MRU line 30% Incremented on access to 2 nd MRU line 25% Incremented on access to 3 rd MRU line 20% Incremented on a miss 15% 10% 5% 0%

C1 C2 C3 C4 C5 C6 C7 C8 C>8 Stack Distance Counters 10

Where to Profile P For capturing temporal reuse patterns at the L1 cache levels ⇒Predict cache misses for various L1 cache L1 Instruction  L1 Data  configurations For capturing temporal reuse patterns at the L2 cache levels ⇒cache misses for various L2 cachePredict L2 Cache  configurations

Mem

12

3

Limitations of Stack Distance Profile „ Useful only for predicting cache misses across different cache associativities „ For other purposes, we need to capture temporal reuse patterns in greater details „ So, useCircular Sequence Profilenhdar[aC05] ‰ Extends stack distance profiling ‰ Counts the occurrence of cseq(d,n)

13

Relationship with Stack Distance Profile „ Cx = number of circular sequences cseq(d=x,n=any value), or ∞ C x = ∑ cseq(x,n) n=x „ Hence, stack distance profile is a subset of circular sequence profile

15

Definitions „ seq(d,n)=quseceenofnaccesses toddistinct addresses (in a cache set) „ cseq(d,n)(circular sequence) = a sequence in which the firstand thelast accessesare to the same address seq(5,8) cseq(5,7) A B C D A E E B cseq(4,5) cseq(1,2)

14

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack Access Counter Access Stream for 1 Set d A  B C B A 1 2 3 4 1 n 2 3 4 5 

16

4

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack A Access Counter 1 Access Stream for 1 Set 1 2  d  3 4  A B C B A 1 n 2 3 4 5 

17

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack C B A Access Counter 1 2 3 Access Stream for 1 Set d A  B C B A 1 2 3 4 1 n 2 3 4 5 

19

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack B A Access Counter 1 2 Access Stream for 1 Set d 1 2 3 4  A B C B A 1 n 2 3 4 5 

18

Collecting Circular Sequence Profile MRU LRU 1 3 4 LRU Stack C B A Found a Circular Sequence! Access Counter 2 4 Access Stream for 1 Set d A  B C B A 1 2 3 4 1 n 2 3 1 4 5 

20

5

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack B C A Access Counter 1 2 4 Access Stream for 1 Set 1 2  d  3 4  A B C B A 1 n 2 3 1 4 5 

21

Collecting Circular Sequence Profile MRU LRU 1 2 3 4 LRU Stack A B C Access Counter 1 2 3 Access Stream for 1 Set d A  B C B A 1 2 3 4 1 n 2 3 1 4 5 1 

23

Collecting Circular Sequence Profile MRU LRU 1 2 4 LRU Stack B C A Found a Access Counter 3 Circular Sequence! 2 Access Stream for 1 Set 1 2  d  3 4  A B C B A         1 n 2 3 1 4 5 1 

22

Predicting Contention Across Cache

6

Shared Cache Challenge CMP P P L1 L1 L2 Cache „ In todays CMP, L2 cache is shared by multiple cores „ on different core compete for L2 cacheApplications space

Modeling Goal „ Given n applications, predict the miss rates of any pair of applications „ Input: ‰ Behavior of each application ‰ Cache parameter ‰ Relative speed when the pair runs together „ pttuuO:  ‰ Number of cache misses for each application in the pair

25

27

Impact of Cache Space Contention 400% 100% 350% 300% 80% 250% 60% 200% 150% 40% 100% 20% 50% 0% 0%

„  cifs-noicepAacitppil „ soCecspicifedche-ul „ actn :SgiinifUp to 4X cache misses, 65% IPC reduction How to model the impact of cache sharing?

Assumptions „ LRU Replacement Algorithm „ Applications share nothing ‰ Mostly true for sequential apps (except for library and OS code) „ Applications not similar ‰ Parallel apps: threads likely to show uniform behavior, so predicting their miss rates is trivial

26

28

7

Circular Sequence Properties „ X runs alone in the system:Thread ‰ Given a circular sequencecseq X (d X ,n X ),the last access is a cache miss iffd X > Assoc „ Thread X shares the cache with thread Y: ‰ Duringcseq X (d X ,n X )s lifetime if there is a sequence of intervening accessesseq Y (d Y ,n Y ), the last access of thread X is a miss iffd X +d Y > Assoc

29

Example „ Assume a 4-way associative cache: Xs circular sequence  Ys intervening cseq X (2,3) access sequence A B AU V V W AUBV VAWAUBV V WA Cache Hit Cache Miss seq Y (2,3) intervening in seq Y (3,4) intervening in cseq X s lifetime cseq X s lifetime 31

Example „ Assume a 4-way associative cache: Xs circular sequence  Ys intervening cseq X (2,3) access sequence A B AU V V W lifetime No cache sharing: A is a cache hit Cache sharing: is A a cache hit or miss?

30

Inductive Probability Model „ Define P miss (cseq X probability of the last access is) = a cache miss „ For each cseq X (d X ,n X ) of thread X ‰ Compute the number of intervening accesses from thread Y duringcseq X s lifetime⇒denote asn Y ‰ It is possible to haved Y = 1, 2,  , n Y ⇒compute the probability of eachd Y , denoted as P(seq(d Y ,n Y )). ‰ For eachd Y = 1, 2,  , n Y „ Ifd Y +d X >Assoc, P miss (cseq X ) = P miss (cseq X ) + P(seq(d Y ,n Y )) „ Ifd Y +d X ≤Assoc, P miss (cseq X ) is kept the same _ ‰  misses +Misses = old∑P miss (cseq X ) x F(cseq X ) 32

8

Computing P(seq(d Y , n Y )) „ Basic Idea: seq(d,n) + 1 access to an already-seen address + 1 access to a A B  sequence a cminglar ir s cuf ro.i.e new address  with 1..d distinct addresse seq(d-1,n-1) seq(d,n-1) „ This is a Markov process with 3 states, and 2 edges „ P(seq(d,n)) =A* P(seq(d-1,n-1)) +B*P(seq(d-1,n)) d ∑ C i B= i=1 andA=1−B ∞ ∑ Ci i=1 33

Example seq(2,3) P(1 + ) seq(1,2) P(1 − ) seq(1,1) 1

P(2 − ) seq(2,2) P(1 + ) seq(1,1) 1

35

Overall Formula d „ ni:eDfe ∑ C i P d − =i=1P d + = −P d − ( ) ∞  and ( ) 1 ( ) ∑ C i i=1 „ P(seq(d,n)) is computed by: 1 = =    P((d−1) + )×P(seq(d−1,n−1) d d = n n> 1 1 ( ( , ))  (1 ) ( (1, 1)) > = P seq d n    = P P (d − − ) × ×P P (qes qes ( n d,n − −1)) n n > d d> 1 1   +P((d−1) + )×P(seq(d−1,n−1)) 34

Final prediction „ After we obtain P miss (cseq X (d X ,n X )) for all cseq X (d X ,n X ), „ Predict the total misses for thread X: A miss X =oldmiss X + ∑ P miss (cseq X (d X ,n X ))×C d X d X =1

36

9

Observations 

„ Based on how vulnerable to cache sharing impact: ‰ Some are highly vulnerable ‰ Some are not vulnerable ‰ Many are somewhat / sometimes vulnerable „ :sthgisnI ‰ Traditional characterizations: not indicative of impact of sharing „ Low vs. High IPC „ Int vs. Floating-Point „ High Miss Rate vs. Low Miss Rate ‰ Rather, interaction of temporal reuse behavior determine impact of cache sharing

Motivation „ Cache design critical to performance ‰ Memory wall: cache miss cost hundreds of processor cycles ‰ Capacity pressure: Multi-core design, Virtual Machine

37

„ Important parameters: size, associativity, block size, andreplacement policy

39

Modeling Replacement Policy Performance

Motivation „ Performance variation due to replacement policy is significant L2 Miss Rates Normalized Exec Time 100% 18% 32% 100% 3%1 %19 80% 80% 67% 60% 47% 60% 40% 40% 20% 20% 0% art ammp cg  ammp cg 0% art LRU Rand-MRUskw LRU Rand-MRUskw „ No agreement on the best implementation ‰ Intel Pentium: LRU ‰ Intel XScale: FIFO ‰ IBM Power 4: tree-based pseudo-LRU ‰ Others: round robin, random, replacement hints, etc.

40

01

Motivation „ No analytical model, past models assume ‰ LRU [Cascaval03, Chandra05, Ghosh97, Quong94, Sen02, Singh92, and Suh01] ‰ or Random [Agarwal89, Berg04, Ladner99] „ LRU/Random simplifies modeling, but ‰ Ignores performance variation due to replacement policy ‰ Inaccurate for highly associative caches

Outline „ Input of the Model „ Replacement Policy Model „ Case Study „ oCsonsilunc

41

43

Would be useful to model replacement policies App 1  Circular Seq Profiling . . . a App N  Circular Seq cidenoitrP tnp ecempealhcr n ea pp o ach or ef etar ssim detcdireP lociy Profiling Model MissRate  NApp 1 App . . . RP 1sRpe emtnalec RP 1 Probability Function(RPF) . . . . . . RP MsacplRet enem RP M Probability Function(RPF)

Outline „ Input of the Model ‰ Replacement Probability Function (RPF) ‰ Circular Sequence Profiles „ Replacement Policy Model „ Validation „ lusionsoCcn

42

44

11