15 213 Recitation 6 10 14 02 Outline Optimization Amdahl s Law Cache Performance Metrics Access Patterns Annie Luo e mail luluo cs cmu edu Office Hours Thursday 6 00 7 00 Wean 8402 Reminder L4 due Thursday 10 24 11 59pm Amdahl s Law Old program T1 T2 Old time T T1 T2 New program improved T1 T1 T2 T2 New time T T1 T2 T1 time that can NOT be improved T2 time that can be improved T2 time after the improvement Speedup T T Amdahl s Law describes a general principle for improving any process not only for speeding up computer systems Amdahl s Law Example 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 What if we choose faster methods 747 NY Paris 8 5 hours SST 3 75 hours rocket 0 25 hours rip 0 0 hours Total time 16 5 hours Speedup over 747 1 11 75 hours 8 25 hours 8 0 hours 1 4 2 0 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 miss 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 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 Memory a 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 Solution 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 Organization review Cache is an array of sets 1 valid bit t tag bits per line per line valid Each set contains one or more lines 0 1 B 1 E lines per set set 0 Each line holds a block of data S 2s sets tag B 2b bytes per cache block valid tag 0 1 B 1 valid tag 0 1 B 1 1 B 1 1 B 1 1 B 1 set 1 valid tag 0 valid tag 0 set S 1 valid tag 0 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 cache Practice 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 bytes 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 grid 0 0 x grid 0 2 y grid 8 0 x grid 8 2 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 x x x x x x x x y y y y y y y y 6 15 Stride of two words First loop accessing all x s When a cache miss happens load …
View Full Document
Unlocking...