15-213 Recitation 6: 10/14/02Amdahl’s LawAmdahl’s Law: ExampleCache Performance MetricsLocalityPractice Problem 6.4Array Organization in MemorySolutionCache Organization (review)Cache Access PatternsPractice Problem 6.15–17PowerPoint PresentationSlide 13Slide 14Slide 15Slide 16Answer to Problem 6.15Slide 18Slide 19Answer to Problem 6.16Slide 21Slide 22Slide 23Slide 24Answer to Problem 6.1715-213 Recitation 6: 10/14/02Outline•Optimization–Amdahl’s Law•Cache –Performance Metrics–Access PatternsAnnie Luoe-mail: [email protected] Hours: Thursday 6:00 – 7:00 Wean 8402Reminder•L4 due: Thursday 10/24, 11:59pmAmdahl’s Law•Amdahl’s Law describes a general principle for improving any process, not only for speeding up computer systems. T1T2Old program T1 = time that can NOT be improved.T2 = time that can be improved.T2’ = time after the improvement. Old time: T = T1 + T2T1’ = T1T2’ <= T2New program (improved)New time: T’ = T1’ + T2’Speedup = T / T’•Planning a trip PGH –>NY –> Paris –> Metz •Suppose both PGH –>NY and Paris –> Metz take 4 hours•For NY –> Paris take 8.5 hours by a Boeing 747•Total travel time: Amdahl’s Law: ExampleNY->Paris Total time Speedup over 747747 8.5 hours 16.5 hours 1What if we choose faster methods? SST 3.75 hours 11.75 hours 1.4rocket 0.25 hours 8.25 hours 2.0rip 0.0 hours 8.0 hours 2.1•It’s hard to gain significant improvement. •Larger speedup comes from improving larger fraction of the whole system.Cache Performance Metrics•Miss Rate–Fraction of memory references not found in cache (misses/references)•Hit Time–Time to deliver a line in the cache to the processor (including determining time)•Miss Penalty –Additional time required because of a missLocality•Temporal locality: –a memory location that is referenced once is likely to be reference again multiple times in the near future•Spatial locality: –if a memory location is referenced once, then the program is likely to reference a nearby memory location in the near futurePractice Problem 6.4•Permute the loops so that it scans the 3-dimensional array a with a stride-1 reference pattern:int summary3d(int a[N][N][N]){ int i, j, k, sum = 0; for (i = 0; i < N; i++) { for (j = 0; k < N; j++ ) { for (k = 0; k < N; k++ ) { sum += a[k][i][j]; } } } return sum;}Array Organization in Memorya[0][0][0], a[0][0][1], … …, a[0][0][N-1], a[0][1][0], a[0][1][1], … …, a[0][1][N-1], a[0][2][0], a[0][2][1], … …, a[0][2][N], … … a[1][0][0], a[1][0][1], … …, a[1][0][N], … …a[N-1][N-1][0],a[N-1][N-1][1],……,a[N-1][N-1][N-1]Solutionint summary3d(int a[N][N][N]){ int i, j, k, sum = 0; for (k = 0; k < N; k++) { for (i = 0; i < N; i++ ) { for (j = 0; j < N; j++ ) { sum += a[k][i][j]; } } } return sum;}Cache Organization (review)••• B–110••• B–110validvalidtagtagset 0:B = 2b bytesper cache blockE lines per setS = 2s setst tag bitsper line1 valid bitper line•••••• B–110••• B–110validvalidtagtagset 1:•••••• B–110••• B–110validvalidtagtagset S-1:••••••Cache is an arrayof sets.Each set containsone or more lines.Each line holds ablock of data.Cache Access Patterns•Now it’s your turn to spend 15 minutes working on Practice Problems 6.15-6.17 •Handout is a photocopy from the text book•Note that: –The size of struct algae_position is 8 bytes–Each cache block (16 bytes) holds two algae_position structs–The 16×16 array requires 2048 bytes of memory–Twice the size of the 1024 byte cachex y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yPractice Problem 6.15–17•Each row: 16 struct items, 8 cache blocks, 128 bytes•Each column: 16 struct items•Yellow area: 1024 bytes, green area: 1024 bytesx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x y6.15 – Row Major Access Patterngrid[0][0].xgrid[0][2].ygrid[8][0].xgrid[8][2].yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y x y x y x y x y x yx y x y x y …
View Full Document