inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 34 Caches IV Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia Thumb based interfaces Microsoft and U Maryland are investigating the use of a one hand thumbdriven interface for controlling PDAs and cell phones normally one needs 2 hands one to hold the device one for a stylus brighthand com article Microsoft is All Thumbs CS61C L34 Caches IV 1 Garcia UCB Review Why We Use Caches CPU Moore s Law 2000 1999 1998 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 10 1 Proc 60 yr Processor Memory Performance Gap grows 50 year DRAM DRAM 7 yr 100 1997 Performance 1000 1989 first Intel CPU with cache on chip 1998 Pentium III has two levels of cache on chip CS61C L34 Caches IV 2 Garcia UCB N Way Set Associative Cache 1 4 Memory address fields Tag same as before Offset same as before Index points us to the correct row called a set in this case So what s the difference each set contains multiple blocks once we ve found correct set must compare with all tags in that set to find our data CS61C L34 Caches IV 3 Garcia UCB N Way Set Associative Cache 2 4 Summary cache is direct mapped w respect to sets each set is fully associative basically N direct mapped caches working in parallel each has its own valid bit and data CS61C L34 Caches IV 4 Garcia UCB N Way Set Associative Cache 3 4 Given memory address Find correct set using Index value Compare Tag with all Tag values in the determined set If a match occurs hit otherwise a miss Finally use the offset field as usual to find the desired data within the block CS61C L34 Caches IV 5 Garcia UCB N Way Set Associative Cache 4 4 What s so great about this 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 CS61C L34 Caches IV 6 Garcia UCB 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 1 2 3 4 Byte Direct Mapped Cache Recall this is how a simple direct mapped cache looked CS61C L34 Caches IV 7 This is also a 1 way setassociative cache Garcia UCB 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 Here s a simple 2 way set associative cache CS61C L34 Caches IV 8 Garcia UCB Block Replacement Policy 1 2 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 a miss Fully Associative block can be written into any position Question if we have the choice where should we write an incoming block CS61C L34 Caches IV 9 Garcia UCB Block Replacement Policy 2 2 If there are any locations with valid bit off empty then usually write the new block into the first one If all possible locations already have a valid block we must pick a replacement policy rule by which we determine which block gets cached out on a miss CS61C L34 Caches IV 10 Garcia UCB Block Replacement Policy LRU LRU Least Recently Used Idea cache out block which has been accessed read or write least recently Pro temporal locality recent past use implies likely future use in fact this is a very effective policy Con with 2 way set assoc easy to keep track one LRU bit with 4 way or greater requires complicated hardware and much time to keep track of this CS61C L34 Caches IV 11 Garcia UCB Block Replacement Example We have a 2 way set associative cache with a four word total capacity and one word blocks We perform the following word accesses ignore bytes for this problem 0 2 0 1 4 0 2 3 5 4 How many hits and how many misses will there be for the LRU block replacement policy CS61C L34 Caches IV 12 Garcia UCB Block Replacement Example LRU Addresses 0 2 0 1 4 0 0 miss bring into set 0 loc 0 2 miss bring into set 0 loc 1 0 hit loc 0 loc 1 lru set 0 set 1 set 0 lru set 1 0 0 lru 2 set 0 lru 0 lru2 set 1 lru 0 2 1 miss bring into set 1 loc 0 set 1 1 lru set 0 lru0 lru4 2 4 miss bring into set 0 loc 1 replace 2 set 1 1 lru set 0 lru0 lru4 0 hit set 1 lru 1 set 0 CS61C L34 Caches IV 13 Garcia UCB Big Idea How to choose between associativity block size replacement policy Design against a performance model Minimize Average Memory Access Time Hit Time Miss Penalty x Miss Rate influenced by technology program behavior Note Hit Time encompasses Hit Rate Create the illusion of a memory that is large cheap and fast on average CS61C L34 Caches IV 14 Garcia UCB Example Assume Hit Time 1 cycle Miss rate 5 Miss penalty 20 cycles Calculate AMAT Avg mem access time 1 0 05 x 20 1 1 cycles 2 cycles CS61C L34 Caches IV 15 Garcia UCB Administrivia Do your reading VM is coming up and it s shown to be hard for students Project 3 out today due Next Wed CS61C L34 Caches IV 16 Garcia UCB Ways to reduce miss rate Larger cache limited by cost and technology hit time of first level cache cycle time More places in the cache to put each block of memory associativity fully associative any block any line N way set associated N places for each block direct map N 1 CS61C L34 Caches IV 17 Garcia UCB Improving Miss Penalty When caches first became popular Miss Penalty 10 processor clock cycles Today 2400 MHz Processor 0 4 ns per clock cycle and 80 ns to go to DRAM 200 processor clock cycles MEM 2 DRAM Proc Solution another cache between memory and the processor cache Second Level L2 Cache CS61C L34 Caches IV 18 Garcia UCB Analyzing Multi level cache hierarchy L1 hit time 2 DRAM Proc L2 hit time L2 Miss Rate L2 Miss Penalty L1 Miss Rate L1 Miss Penalty Avg Mem Access Time L1 Hit Time L1 Miss Rate L1 Miss Penalty L1 Miss Penalty L2 Hit Time L2 Miss Rate L2 Miss Penalty Avg Mem Access Time L1 Hit Time L1 Miss Rate L2 Hit Time L2 Miss Rate L2 Miss Penalty CS61C L34 Caches IV 19 Garcia UCB …
View Full Document
Unlocking...