Recitation 6 Cache Access Patterns Andrew Faulring 15213 Section A 14 October 2002 Andrew Faulring faulring cs cmu edu Office hours NSH 2504 lab 2507 conference room Wednesday 5 6 Lab 4 due Thursday 24 Oct 11 59pm Today s Plan Optimization Amdahl s law Cache Access Patterns Practice problems 6 4 6 15 17 Lab 4 Horner s Rule including na ve code Amdahl s law Old program unenhanced T1 T2 Old time T T1 T2 New program enhanced T 1 T 1 T2 T2 New time T T1 T2 T1 time that can NOT be enhanced T2 time that can be enhanced T2 time after the enhancement 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 747 8 5 hours 16 5 hours SST 3 75 hours 11 75 hours speedup over 747 1 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 747 8 5 hours SST 3 75 hours rocket 0 25 hours rip 0 0 hours total trip time 16 5 hours 11 75 hours 8 25 hours 8 hours speedup over 747 1 1 4 2 0 2 1 Moral 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 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 future Practice Problem 6 4 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 Answer int 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 text Practice 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 cache Practice Problem 6 15 17 Rows 16 items 8 blocks 128 bytes Columns 16 items Yellow block 1k Orange block 1k x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y 6 15 Row major access pattern x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y 6 15 Stride of 2 words First loop accessing just x s x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x x x x y y y y y y y y x x x x x …
View Full Document
Unlocking...