Recitation 6:Cache Access PatternsAndrew FaulringToday’s PlanAmdahl’s lawExample: Amdahl’s lawAmdahl’s law (cont)LocalityPractice Problem 6.4AnswerCache Access PatternsPractice Problem 6.15–17Practice Problem 6.15–176.15: Row major access pattern6.15: Stride of 2 words6.15: Stride of 2 words6.15: Stride of 2 words6.15: Stride of 2 wordsAnswers to 6.15Column major access patternColumn major access patternAnswers to 6.16Column major access patternAnswers to 6.16Stride of 1 wordStride of 1 wordAnswers to 6.17Lab 4: Horner’s RuleNaïve code for Horner’s RuleRecitation 6:Cache Access PatternsAndrew Faulring15213 Section A14 October 2002Andrew Faulring• [email protected]• Office hours:– NSH 2504 (lab) / 2507 (conference room)– Wednesday 5–6•Lab 4– due Thursday, 24 Oct @ 11:59pmToday’s Plan• Optimization– Amdahl’s law• Cache Access Patterns– Practice problems 6.4, 6.15–17•Lab 4– Horner’s Rule, including naïve codeAmdahl’s lawT1Old program (unenhanced)T1= time that can NOTbe enhanced.T2Old time: T = T1+ T2T2= time that can beenhanced.T2’ = time after theenhancement. T2’ <= T2T1’ = T1New program (enhanced)New time: T’ = T1’ + T2’Speedup: Soverall= T / T’Key idea: Amdahl’s law quantifies the general notion of diminishing returns. It applies to any activity, not just computer programs.Example: Amdahl’s law• You plan to visit a friend in Normandy France and must decide whether it is worth it to take the Concorde SST ($3,100) or a 747 ($1,021) from NY to Paris, assuming it will take 4 hours Pgh to NY and 4 hours Paris to Normandy.time NY->Paris total trip time speedup over 747747 8.5 hours 16.5 hours 1SST 3.75 hours 11.75 hours 1.4• Taking the SST (which is 2.2 times faster) speeds up the overall trip by only a factor of 1.4!Amdahl’s law (cont)• Trip example: Suppose that for the New York to Paris leg, we now consider the possibility of taking a rocket ship (15 minutes) or a handy rip in the fabric of space-time (0 minutes):time NY->Paris total trip time speedup over 747747 8.5 hours 16.5 hours 1SST 3.75 hours 11.75 hours 1.4rocket 0.25 hours 8.25 hours 2.0rip 0.0 hours 8 hours 2.1Moral: It is hard to speed up a program.Moral++ : It is easy to make premature optimizations.Locality• Temporal locality: a memory location that is referenced once is likely to be reference again multiple timesin the near future• Spatial locality: if a memory location is referenced once, then the program is likely to reference a nearby memory locationin the near futurePractice Problem 6.4int 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;}Answerint 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 Access Patterns• Spend the next fifteen minutes working on Practice Problems 6.15–17• Handout is a photocopy from the textPractice Problem 6.15–17• sizeof(algae_position) = 8• Each block (16 bytes) holds two algae_position structures• The 16×16 array requires 2048 bytes of memory– Twice the size of the 1024 byte cachePractice Problem 6.15–17• Rows: 16 items (8 blocks, 128 bytes)• Columns: 16 items• Yellow block: 1k; Orange block 1kx 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 patternx 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: Stride of 2 words• First loop, accessing just x’sx 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 …
View Full Document
Unlocking...