15-213 Recitation 6: 10/14/02Outline• Optimization– Amdahl’s Law• Cache – Performance Metrics– Access PatternsAnnie Luoe-mail:[email protected] Hours:Thursday 6:00 – 7:00Wean 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 NOTbe improved.T2= time that can beimproved.T2’ = time after theimprovement. 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 = 2bbytesper cache blockE lines per setS = 2ssetst 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 J• 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].x grid[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 x y x y x y x y x yx y x y x y …
View Full Document