Review We would like to have the capacity of disk at the speed of the processor unfortunately this is not feasible CS61C Machine Structures So we create a memory hierarchy Lecture 18 Caches Part II each successively lower level contains most used data from next higher level November 1 2000 exploits temporal locality do the common case fast worry less about the exceptions design principle of MIPS David Patterson http www inst eecs berkeley edu cs61c Locality of reference is a Big Idea 1 CS61C L18 Cache2 UC Regents Big Idea Review 1 2 Block Size Tradeoff Types of Cache Misses set of address value bindngs address index to set of candidates compare desired address with tag service hit or miss Fully Associative Cache Course Advice load new block and binding on miss tag index N Way Associative Cache offset 000000000000000000 0000000001 1100 Valid Tag 0 1 2 3 1 0 0x0 3 a 2 Outline Mechanism for transparent movement of data among levels of a storage hierarchy address CS61C L18 Cache2 UC Regents 0x4 7 b 0x8 b Block Replacement Policy 0xc f c Multilevel Caches if time d CS61C L18 Cache2 UC Regents Cache write policy if time 3 CS61C L18 Cache2 UC Regents Block Size Tradeoff 1 3 Block Size Tradeoff 2 3 Benefits of Larger Block Size Drawbacks of Larger Block Size 4 L a r g e r b l o c k s i z e m e a n s larger miss penalty Spatial Locality if we access a given word we re likely to access other nearby words soon Another Big Idea on a miss takes longer time to load a new block from next level Very applicable with Stored Program Concept if we execute a given instruction it s likely that we ll execute the next few as well If block size is too big relative to cache size then there are too few blocks Result miss rate goes up Works nicely in sequential array accesses too In general minimize Average Access Time Hit Time x Hit Rate Miss Penalty x Miss Rate CS61C L18 Cache2 UC Regents 5 CS61C L18 Cache2 UC Regents 6 Extreme Example One Big Block Block Size Tradeoff 3 3 Valid Bit Hit Time time to find and retrieve data from current level cache Cache Size 4 bytes M iss Penalty average time to retrieve data on a current level miss includes the possibility of misses on successive levels of memory hierarchy If item accessed likely accessed again soon But unlikely will be accessed again immediately The next access will likely to be a miss again Continually loading data into the cache but discard data force out before use it again M iss Rate 1 Hit Rate Nightmare for cache designer Ping Pong Effect 7 CS61C L18 Cache2 UC Regents Miss Rate Exploits Spatial Locality 8 Compulsory Misses Fewer blocks compromises temporal locality Average Access Time CS61C L18 Cache2 UC Regents Types of Cache Misses 1 2 Block Size Tradeoff Conclusions Block Size Block Size 4 bytes Only O N E entry in the cache Hit Rate of requests that are found in current level cache Miss Penalty Cache Data B3 B2 B1 B0 Tag Block Size occur when a program is first started cache does not contain any of that program s data yet so misses are bound to occur can t be avoided easily so won t focus on these in this course Increased Miss Penalty Miss Rate Block Size CS61C L18 Cache2 UC Regents 9 CS61C L18 Cache2 UC Regents 10 Dealing with Conflict Misses Types of Cache Misses 2 2 Solution 1 Make the cache size bigger Conflict Misses fails at some point miss that occurs because two distinct memory addresses map to the same cache location Solution 2 Multiple distinct blocks can fit in the same Cache Index 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 CS61C L18 Cache2 UC Regents 11 CS61C L18 Cache2 UC Regents 12 Fully Associative Cache 1 3 Fully Associative Cache 2 3 Fully Associative Cache e g 32 B block Memory address fields compare tags in parallel Tag same as before Offset same as before 31 Cache Tag 27 bits long Index non existent What does this mean Cache Tag must compare with all tags in entire cache to see if data is there CS61C L18 Cache2 UC Regents 13 Valid Cache Data B 31 B1 B 0 no rows any block can go anywhere in the cache 14 Third Type of Cache Miss Benefit of Fully Assoc Cache Capacity Misses miss that occurs because the cache has a limited size miss that would not occur if we increase the size of the cache 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 CS61C L18 Cache2 UC Regents sketchy definition so just get the general idea This is the primary type of miss for Fully Associate caches 15 Administrivia General Course Philosophy 16 CS61C L18 Cache2 UC Regents Administrivia Courses for Telebears General Philosophy Take courses from great teachers HKN ratings 6 very good 5 not good w w w h k n eecs student coursesurveys s h t m l Take variety of u n d e r g r a d c o u r s e s now to get introduction to areas Can learn advanced material on own later once know vocabulary Top Faculty CS Course may teach soon Who knows what you will work on over a 40 year career CS61C L18 Cache2 UC Regents CS61C L18 Cache2 UC Regents Fully Associative Cache 3 3 no Conflict Misses since data can go anywhere 4 0 Byte Offset 17 CS 70 Discrete Math CS 150 Logic design CS 152 Computer CS 160 User Interface CS 164 Compilers C S 1 6 9 S W engin C S 1 7 4 Combinatori CS 184 Graphics C S 1 8 8 Artfic Intel CS61C L18 Cache2 UC Regents Papadami K a t z D T A Kubiatowicz Rowe Aiken Brewer Sinclair Sequin Rusell 6 3 6 3 6 7 6 0 6 1 6 3 6 0 6 1 6 0 S00 F92 F99 F99 S00 F99 F97 S99 F97 18 If many good teachers M y r e c o m m e n d a t i o n s Administrivia Courses for Telebears CS169 Software Engineering General Philosophy Everyone writes programs even HW designers Take courses from great teachers Often programs are written in groups learn skill now in school before it counts Top Faculty EE Course may teach soon EE EE EE EE EE EE EE EE EE 105 120 121 130 140 141 142 143 192 Micro Devices Signal System Noise Analysis I C Devices Linear I C s Digital I C s I C for Comm Process I C s Mechatronics Howe Kahn Tse H u D T A Brodersen Rabaey Meyer Cheung Fearing 6 2 …
View Full Document
Unlocking...