inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 20 Caches 1 2005 07 25 Andy Carle CS61C L31 Caches I 1 A Carle Summer 2005 UCB Review Pipelining Pipeline challenge is hazards Forwarding helps w many data hazards Delayed branch helps with control hazard in our 5 stage pipeline Data hazards w Loads Load Delay Slot Interlock smart CPU has HW to detect if conflict with inst following load if so it stalls More aggressive performance Superscalar parallelism Out of order execution CS61C L31 Caches I 2 A Carle Summer 2005 UCB Big Ideas so far 15 weeks to learn big ideas in CS E Principle of abstraction used to build systems as layers Pliable Data a program determines what it is Stored program concept instructions just data Compilation v interpretation to move down layers of system Greater performance by exploiting parallelism pipeline Principle of Locality exploited via a memory hierarchy cache Principles Pitfalls of Performance Measurement CS61C L31 Caches I 3 A Carle Summer 2005 UCB Where are we now in 61C Architecture aka Systems CPU Organization Pipelining Caches Virtual Memory I O Networks Performance CS61C L31 Caches I 4 A Carle Summer 2005 UCB The Big Picture Computer Processor Memory Devices active passive Input Control where brain programs Output Datapath data live brawn when running CS61C L31 Caches I 5 Keyboard Mouse Disk Network Display Printer A Carle Summer 2005 UCB What s the Problem CPU Moore s Law Proc 60 yr 2000 1999 1996 1995 1994 1993 1992 1991 1990 1988 1987 1986 1985 1984 1983 1982 1981 1980 1 1989 10 1998 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 L31 Caches I 6 A Carle Summer 2005 UCB Memory Hierarchy 1 3 Processor executes instructions on order of nanoseconds to picoseconds holds a small amount of code and data in registers Memory More capacity than registers still limited Access time 50 100 ns Disk HUGE capacity virtually limitless VERY slow runs milliseconds CS61C L31 Caches I 7 A Carle Summer 2005 UCB Memory Hierarchy 2 3 Processor Higher Levels in memory hierarchy Level 1 Level 2 Increasing Distance from Proc Decreasing speed Level 3 Level n Lower Size of memory at each level As we move to deeper levels the latency goes up and price per bit goes down Q Can bit go up as move deeper A Carle Summer 2005 UCB CS61C L31 Caches I 8 Memory Hierarchy 3 3 If level closer to Processor it must be smaller faster subset of lower levels contains most recently used data Lowest Level usually disk contains all available data Other levels CS61C L31 Caches I 9 A Carle Summer 2005 UCB Memory Caching We ve discussed three levels in the hierarchy processor memory disk Mismatch between processor and memory speeds leads us to add a new level a memory cache Implemented with SRAM technology faster but more expensive than DRAM memory S Static no need to refresh 10ns D Dynamic need to refresh 60ns arstechnica com paedia r ram guide ram guide part1 1 html CS61C L31 Caches I 10 A Carle Summer 2005 UCB Memory Hierarchy Analogy Library 1 2 You re writing a term paper Processor at a table in Doe Doe Library is equivalent to disk essentially limitless capacity very slow to retrieve a book Table is memory smaller capacity means you must return book when table fills up easier and faster to find a book there once you ve already retrieved it CS61C L31 Caches I 11 A Carle Summer 2005 UCB Memory Hierarchy Analogy Library 2 2 Open books on table are cache smaller capacity can have very few open books fit on table again when table fills up you must close a book much much faster to retrieve data Illusion created whole library open on the tabletop Keep as many recently used books open on table as possible since likely to use again Also keep as many books on table as possible since faster than going to library CS61C L31 Caches I 12 A Carle Summer 2005 UCB Memory Hierarchy Basis Disk contains everything When Processor needs something bring it into to all higher levels of memory Cache contains copies of data in memory that are being used Memory contains copies of data on disk that are being used Entire idea is based on Temporal Locality if we use it now we ll want to use it again soon a Big Idea CS61C L31 Caches I 13 A Carle Summer 2005 UCB Cache Design How do we organize cache Where does each memory address map to Remember that cache is subset of memory so multiple memory addresses map to the same cache location How do we know which elements are in cache How do we quickly locate them CS61C L31 Caches I 14 A Carle Summer 2005 UCB Pre Exam Exercise 1 We are now going to stop for 5 minutes During this time your goal is to by yourself come up with a potential exam exercise covering the topic of MIPS Pseudo Instructions or CALL Make it as much like a real exam question as possible After this five minutes you will explain your question to a small group and work through how you would go about solving it I ll call on some random samples for the full class CS61C L31 Caches I 15 A Carle Summer 2005 UCB Administrivia HW6 Due Tuesday HW7 Out Tomorrow Due Sunday Midterm 2 Friday 11 00am 2 00pm 306 Soda HP Auditorium Conflicts DSP terrified about the drop deadline Contact Andy ASAP CS61C L31 Caches I 16 A Carle Summer 2005 UCB Direct Mapped Cache 1 2 In a direct mapped cache each memory address is associated with one possible block within the cache Therefore we only need to look in a single location in the cache for the data if it exists in the cache Block is the unit of transfer between cache and memory CS61C L31 Caches I 17 A Carle Summer 2005 UCB Direct Mapped Cache 2 2 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 Cache Location 0 can be occupied by data from Memory location 0 4 8 4 blocks any memory location that is multiple of 4 CS61C L31 Caches I 18 A Carle Summer 2005 UCB Issues with Direct Mapped Since multiple memory addresses map to same cache index how do we tell which one is in there What if we have a block size 1 byte Answer divide memory address into three fields ttttttttttttttttt iiiiiiiiii oooo tag to check if have correct block CS61C L31 Caches I 19 index to select block byte offset within block A Carle Summer 2005 UCB Direct Mapped Cache Terminology All fields are read as unsigned integers Index specifies the cache index which row of the cache we should look in Offset once we ve found
View Full Document
Unlocking...