Memory Subsystem and CacheThe Big PictureTechnology TrendsTechnology Trends [contd…]The Goal: Large, Fast, Cheap Memory !!!Slide 6Today’s SituationMemory Hierarchy (1/4)Memory Hierarchy (2/4)Memory Hierarchy (3/4)Memory Hierarchy (4/4)Analogy: LibraryAnalogy : Library [contd…]Memory Hierarchy BasicsCaches : Why does it Work ?Cache Design IssuesDirect Mapped CacheDirect Mapped Cache [contd…]Issues with Direct Mapped CacheExample of a direct mapped cacheTerminologyTerminology [contd…]How is the hierarchy managed ?ExampleExample [contd…]Slide 26Accessing data in cacheAccessing data in cache [contd…]Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Things to RememberMemory Subsystem and CacheAdapted from lectures notes of Dr. Patterson and Dr. Kubiatowicz of UC BerkeleyThe Big PictureControlDatapathMemoryProcessorInputOutputTechnology Trends DRAMYear Size Cycle Time1980 64 Kb 250 ns1983 256 Kb 220 ns1986 1 Mb 190 ns1989 4 Mb 165 ns1992 16 Mb 145 ns1995 64 Mb 120 ns Capacity Speed (latency)Logic: 2x in 3 years 2x in 3 yearsDRAM: 4x in 3 years 2x in 10 yearsDisk: 4x in 3 years 2x in 10 years1000:1! 2:1!Technology Trends [contd…]µProc60%/yr.(2X/1.5yr)DRAM9%/yr.(2X/10 yrs)110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982Processor-MemoryPerformance Gap:(grows 50% / year)Time“Moore’s Law”Processor-DRAM Memory Gap (latency)“Less’ Law?”The Goal: Large, Fast, Cheap Memory !!!•Fact–Large memories are slow–Fast memories are small•How do we create a memory that is large, cheap and fast (most of the time) ?–Hierarchy–Parallelism•By taking advantage of the principle of locality:–Present the user with as much memory as is available in the cheapest technology.–Provide access at the speed offered by the fastest technology.ControlDatapathSecondaryStorage(Disk)ProcessorRegistersMainMemory(DRAM)SecondLevelCache(SRAM)On-ChipCache1s10,000,000ns (10 ms)Speed (ns): 10ns 100ns100s GsSize (bytes): Ks MsTertiaryStorage(Tape)10,000,000,000ns (10 sec)TsToday’s Situation•Rely on caches to bridge gap•Microprocessor-DRAM performance gap–time of a full cache miss in instructions executed1st Alpha (7000): 340 ns/5.0 ns = 68 clks x 2 or 136 instructions2nd Alpha (8400): 266 ns/3.3 ns = 80 clks x 4 or 320 instructionsMemory Hierarchy (1/4)•Processor–executes programs–runs on order of nanoseconds to picoseconds–needs to access code and data for programs: where are these?•Disk–HUGE capacity (virtually limitless)–VERY slow: runs on order of milliseconds–so how do we account for this gap?Memory Hierarchy (2/4)•Memory (DRAM)–smaller than disk (not limitless capacity)–contains subset of data on disk: basically portions of programs that are currently being run–much faster than disk: memory accesses don’t slow down processor quite as much–Problem: memory is still too slow(hundreds of nanoseconds)–Solution: add more layers (caches)Memory Hierarchy (3/4)ProcessorSize of memory at each levelIncreasing Distance from Proc.,Decreasing cost / MBLevel 1Level 2Level nLevel 3. . .HigherLowerLevels in memory hierarchyMemory Hierarchy (4/4)•If level is closer to Processor, it must be:–smaller–faster–subset of all higher levels (contains most recently used data)–contain at least all the data in all lower levels•Lowest Level (usually disk) contains all available dataAnalogy: Library•You’re writing a term paper (Processor) at a table in Evans•Evans 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 itAnalogy : Library [contd…]•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 libraryMemory Hierarchy Basics•Disk contains everything.•When Processor needs something, bring it into to all lower 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)Caches : Why does it Work ? •Temporal Locality (Locality in Time):=> Keep most recently accessed data items closer to the processor•Spatial Locality (Locality in Space):=> Move blocks consists of contiguous words to the upper levels Lower LevelMemoryUpper LevelMemoryTo ProcessorFrom ProcessorBlk XBlk YAddress Space0 2^n - 1Probabilityof referenceCache Design Issues•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?Direct Mapped Cache•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 memoryDirect Mapped Cache [contd…]MemoryMemory Address0123456789ABCDEF4 Byte Direct Mapped CacheCache Index0123•Cache Location 0 can be occupied by data from:–Memory location 0, 4, 8, ... –In general: any memory location that is multiple of 4Issues with Direct Mapped Cache•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?•Result: divide memory address into three fieldsttttttttttttttttt iiiiiiiiii ooootag to check if you index to byte have correct block select block offsetExample of a direct mapped cache•For a 2^N byte cache:–The uppermost (32 - N) bits are always the Cache Tag–The lowest M bits are the Byte Select (Block Size = 2^M)Cache Index0123: Cache DataByte 00431:Cache Tag Example: 0x50Ex: 0x010x50Stored as partof the cache