inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 35 Caches IV VM I 2004 11 19 Andy Carle inst eecs berkeley edu cs61c ta Google strikes back against recent encroachments into the Search world with the launch of two new services Keyhole Scholar CS 61C L35 Caches IV VM I 1 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 2 Garcia Fall 2004 UCB Review Direct Mapped 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 CS 61C L35 Caches IV VM I 3 Garcia Fall 2004 UCB Review 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 CS 61C L35 Caches IV VM I 4 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 5 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 6 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 7 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 8 Garcia Fall 2004 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 0 set 1 set 0 lru set 1 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 1 lru set 0 CS 61C L35 Caches IV VM I 9 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 10 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 11 Garcia Fall 2004 UCB Administrivia Do your reading VM is hard Project 3 Due Next Wednesday No Labs Next Week CS 61C L35 Caches IV VM I 12 Garcia Fall 2004 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 k way set associated k places for each block direct map k 1 CS 61C L35 Caches IV VM I 13 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 14 Garcia Fall 2004 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 CS 61C L35 Caches IV VM I 15 Garcia Fall 2004 UCB Typical Scale L1 size tens of KB hit time complete in one clock cycle miss rates 1 5 L2 size hundreds of KB hit time few clock cycles miss rates 10 20 L2 miss rate is fraction of L1 misses that also miss in L2 why so high CS 61C L35 Caches IV VM I 16 Garcia Fall 2004 UCB Example with L2 cache Assume L1 Hit Time 1 cycle L1 Miss rate 5 L2 Hit Time 5 cycles L2 Miss rate 15 L1 misses that miss L2 Miss Penalty 200 cycles L1 miss penalty 5 0 15 200 35 Avg mem access time 1 0 05 x 35 2 75 cycles CS 61C L35 Caches IV VM I 17 Garcia Fall 2004 UCB Example without L2 cache Assume L1 Hit Time 1 cycle L1 Miss rate 5 L1 Miss Penalty 200 cycles Avg mem access time 1 0 05 x 200 11 cycles 4x faster with L2 cache 2 75 vs 11 CS 61C L35 Caches IV VM I 18 Garcia Fall 2004 UCB An Actual CPU Pentium M CS 61C L35 Caches IV VM I 19 Garcia Fall 2004 UCB What to do on a write hit Write through update the word in cache block and corresponding word in memory …
View Full Document
Unlocking...