CS61C Machine Structures Review Why We Use Caches 1000 CPU Moore s Law Proc 60 yr 1999 1996 1995 1992 1994 1993 1989 1990 1988 1987 1986 1985 1984 1983 1981 1982 1980 1 1991 10 1998 Processor Memory Performance Gap grows 50 year DRAM DRAM 7 yr 100 1997 Performance Lecture 21 Caches 3 2000 inst eecs berkeley edu cs61c su05 1989 first Intel CPU with cache on chip 1998 Pentium III has two levels of cache on chip 2005 07 27 Andy Carle A Carle Summer 2005 UCB CS61C L22 Caches III 1 CS61C L22 Caches III 2 Review Block Size Tradeoff 1 3 Mechanism for transparent movement of data among levels of a storage hierarchy Benefits of Larger Block Size set of address value bindings address index to set of candidates compare desired address with tag service hit or miss load new block and binding on miss address tag index offset 000000000000000000 0000000001 1100 Valid 0x4 7 0x8 b 0xc f 0x0 3 Tag 0 1 1 2 3 0 a b c A Carle Summer 2005 UCB Spatial Locality if we access a given word we re likely to access other nearby words soon Very applicable with Stored Program Concept if we execute a given instruction it s likely that we ll execute the next few as well Works nicely in sequential array accesses too d CS61C L22 Caches III 3 A Carle Summer 2005 UCB CS61C L22 Caches III 4 A Carle Summer 2005 UCB Block Size Tradeoff 2 3 Block Size Tradeoff 3 3 Drawbacks of Larger Block Size Hit Time time to find and retrieve data from current level cache Larger block size means larger miss penalty on a miss takes longer time to load a new block from next level If block size is too big relative to cache size then there are too few blocks Result miss rate goes up In general minimize Average Memory Access Time AMAT Hit Time Miss Penalty x Miss Rate Miss Penalty average time to retrieve data on a current level miss includes the possibility of misses on successive levels of memory hierarchy Hit Rate of requests that are found in current level cache Miss Rate 1 Hit Rate CS61C L22 Caches III 5 A Carle Summer 2005 UCB CS61C L22 Caches III 6 A Carle Summer 2005 UCB Types of Cache Misses 1 2 Block Size Tradeoff Conclusions Miss Rate Exploits Spatial Locality Miss Penalty Fewer blocks compromises temporal locality Block Size Average Access Time Three Cs Model of Misses 1st C Compulsory Misses occur when a program is first started cache does not contain any of that program s data yet so misses are bound to occur Block Size Increased Miss Penalty Miss Rate can t be avoided easily so won t focus on these in this course Block Size A Carle Summer 2005 UCB CS61C L22 Caches III 7 CS61C L22 Caches III 8 Types of Cache Misses 2 2 Fully Associative Cache 1 3 2nd C Conflict Misses Memory address fields miss that occurs because two distinct memory addresses map to the same cache location two blocks which happen to map to the same location can keep overwriting each other big problem in direct mapped caches how do we lessen the effect of these Fails at some point Solution 2 Multiple distinct blocks can fit in the same cache Index A Carle Summer 2005 UCB CS61C L22 Caches III 9 Fully Associative Cache 2 3 compare tags in parallel 4 0 Byte Offset Cache Tag Valid Cache Data B 31 B1 B 0 CS61C L22 Caches III 11 Index non existant must compare with all tags in entire cache to see if data is there CS61C L22 Caches III 10 A Carle Summer 2005 UCB Fully Associative Cache 3 3 Fully Associative Cache e g 32 B block Cache Tag 27 bits long Offset same as before no rows any block can go anywhere in the cache Solution 1 Make the cache size bigger 31 Tag same as before What does this mean Dealing with Conflict Misses A Carle Summer 2005 UCB Benefit of Fully Assoc Cache No Conflict Misses since data can go anywhere Drawbacks of Fully Assoc Cache Need hardware comparator for every single entry if we have a 64KB of data in cache with 4B entries we need 16K comparators infeasible A Carle Summer 2005 UCB CS61C L22 Caches III 12 A Carle Summer 2005 UCB Third Type of Cache Miss N Way Set Associative Cache 1 4 Capacity Misses Memory address fields miss that occurs because the cache has a limited size Tag same as before miss that would not occur if we increase the size of the cache Index points us to the correct row called a set in this case sketchy definition so just get the general idea Offset same as before So what s the difference each set contains multiple blocks This is the primary type of miss for Fully Associative caches CS61C L22 Caches III 13 once we ve found correct set must compare with all tags in that set to find our data A Carle Summer 2005 UCB A Carle Summer 2005 UCB CS61C L22 Caches III 14 N Way Set Associative Cache 2 4 N Way Set Associative Cache 3 4 Summary Given memory address cache is direct mapped w respect to sets Find correct set using Index value each set is fully associative Compare Tag with all Tag values in the determined set basically N direct mapped caches working in parallel each has its own valid bit and data CS61C L22 Caches III 15 Finally use the offset field as usual to find the desired data within the block A Carle Summer 2005 UCB N Way Set Associative Cache 4 4 even a 2 way set assoc cache avoids a lot of conflict misses hardware cost isn t that bad only need N comparators In fact for a cache with M blocks it s Direct Mapped if it s 1 way set assoc it s Fully Assoc if it s M way set assoc so these two are just special cases of the more general set associative design A Carle Summer 2005 UCB A Carle Summer 2005 UCB CS61C L22 Caches III 16 Associative Cache Example Memory Address Memory What s so great about this CS61C L22 Caches III 17 If a match occurs hit otherwise a miss 0 1 2 3 4 5 6 7 8 9 A B C D E F Cache Index 0 1 2 3 4 Byte Direct Mapped Cache Recall this is how a simple direct mapped cache looked This is also a 1 way setassociative cache CS61C L22 Caches III 18 A Carle Summer 2005 UCB Block Replacement Policy 1 2 Associative Cache Example Memory Address Memory 0 1 2 3 4 5 6 7 8 9 A B C D E F Cache Index 0 0 1 1 Direct Mapped Cache index completely specifies position which position a block can go in on a miss N Way Set Assoc index specifies a set but block can occupy any position within the set on …
View Full Document
Unlocking...