CSC 320 Chapter #5, Spring 2015

Chapter 5 Large and Fast: Exploiting Memory Hierarchy Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 2 Memory Technology � Static RAM (SRAM) � 0.5ns – 2.5ns, $2000 – $5000 per GB � Dynamic RAM (DRAM) � 50ns – 70ns, $20 – $75 per GB � Magnetic disk � 5ms – 20ms, $0.20 – $2 per GB � Ideal memory � Access time of SRAM � Capacity and cost/GB of disk §5.1 Introduction Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 3 Principle of Locality � Programs access a small proportion of their address space at any time � Temporal locality � Items accessed recently are likely to be accessed again soon � e.g., instructions in a loop, induction variables � Spatial locality � Items near those accessed recently are likely to be accessed soon � E.g., sequential instruction access, array data Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 4 Taking Advantage of Locality � Memory hierarchy � Store everything on disk � Copy recently accessed (and nearby) items from disk to smaller DRAM memory � Main memory � Copy more recently accessed (and nearby) items from DRAM to smaller SRAM memory � Cache memory attached to CPU Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 5 Memory Hierarchy Levels � Block (aka line): unit of copying � May be multiple words � If accessed data is present in upper level � Hit: access satisfied by upper level � Hit ratio: hits/accesses � If accessed data is absent � Miss: block copied from lower level � Time taken: miss penalty � Miss ratio: misses/accesses = 1 – hit ratio � Then accessed data supplied from upper level Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 6 Cache Memory � Cache memory � The level of the memory hierarchy closest to the CPU � Given accesses X1, …, Xn–1, Xn §5.2 The Basics of Caches � How do we know if the data is present? � Where do we look? Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 7 Direct Mapped Cache � Location determined by address � Direct mapped: only one choice � (Block address) modulo (#Blocks in cache) � #Blocks is a power of 2 � Use low-order address bits Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 8 Tags and Valid Bits � How do we know which particular block is stored in a cache location? � Store block address as well as the data � Actually, only need the high-order bits � Called the tag � What if there is no data in a location? � Valid bit: 1 = present, 0 = not present � Initially 0 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 9 Cache Example � 8-blocks, 1 word/block, direct mapped � Initial state Index V Tag Data 000 N 001 N 010 N 011 N 100 N 101 N 110 N 111 N Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 10 Cache Example Index V Tag Data 000 N 001 N 010 N 011 N 100 N 101 N 110 Y 10 Mem[10110] 111 N Word addr Binary addr Hit/miss Cache block 22 10 110 Miss 110 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 11 Cache Example Index V Tag Data 000 N 001 N 010 Y 11 Mem[11010] 011 N 100 N 101 N 110 Y 10 Mem[10110] 111 N Word addr Binary addr Hit/miss Cache block 26 11 010 Miss 010 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 12 Cache Example Index V Tag Data 000 N 001 N 010 Y 11 Mem[11010] 011 N 100 N 101 N 110 Y 10 Mem[10110] 111 N Word addr Binary addr Hit/miss Cache block 22 10 110 Hit 110 26 11 010 Hit 010 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 13 Cache Example Index V Tag Data 000 Y 10 Mem[10000] 001 N 010 Y 11 Mem[11010] 011 Y 00 Mem[00011] 100 N 101 N 110 Y 10 Mem[10110] 111 N Word addr Binary addr Hit/miss Cache block 16 10 000 Miss 000 3 00 011 Miss 011 16 10 000 Hit 000 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 14 Cache Example Index V Tag Data 000 Y 10 Mem[10000] 001 N 010 Y 10 Mem[10010] 011 Y 00 Mem[00011] 100 N 101 N 110 Y 10 Mem[10110] 111 N Word addr Binary addr Hit/miss Cache block 18 10 010 Miss 010 Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 15 Address Subdivision Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 16 Example: Larger Block Size � 64 blocks, 16 bytes/block � To what block number does address 1200 map? � Block address = 1200/16 = 75 � Block number = 75 modulo 64 = 11 Tag Index Offset 0 3 4 10 9 31 4 bits 6 bits 22 bits Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 17 Block Size Considerations � Larger blocks should reduce miss rate � Due to spatial locality � But in a fixed-sized cache � Larger blocks ⇒ fewer of them � More competition ⇒ increased miss rate � Larger blocks ⇒ pollution � Larger miss penalty � Can override benefit of reduced miss rate � Early restart and critical-word-first can help Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 18 Cache Misses � On cache hit, CPU proceeds normally � On cache miss � Stall the CPU pipeline � Fetch block from next level of hierarchy � Instruction cache miss � Restart instruction fetch � Data cache miss � Complete data access Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 19 Write-Through � On data-write hit, could just update the block in cache � But then cache and memory would be inconsistent � Write through: also update memory � But makes writes take longer � e.g., if base CPI = 1, 10% of instructions are stores, write to memory takes 100 cycles � Effective CPI = 1 + 0.1×100 = 11 � Solution: write buffer � Holds data waiting to be written to memory � CPU continues immediately � Only stalls on write if write buffer is already full Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 20 Write-Back � Alternative: On data-write hit, just update the block in cache � Keep track of whether each block is dirty � When a dirty block is replaced � Write it back to memory � Can use a write buffer to allow replacing block to be read first Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 28 Measuring Cache Performance � Components of CPU time � Program execution cycles � Includes cache hit time � Memory stall cycles � Mainly from cache misses � With simplifying assumptions: §5.3 Measuring and Improving Cache Performance Instruction Miss penalty Misses Program ns Instructio Miss rate Miss penalty Program accesses Memory stall cycles Memory × × = × × = Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 29 Cache Performance Example � Given � I-cache miss rate = 2% � D-cache miss rate = 4% � Miss penalty = 100 cycles � Base CPI (ideal cache) = 2 � Load & stores are 36% of instructions � Miss cycles per instruction � I-cache: 0.02 × 100 = 2 � D-cache: 0.36 × 0.04 × 100 = 1.44 � Actual CPI = 2 + 2 + 1.44 = 5.44 � Ideal CPU is 5.44/2 =2.72 times faster Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 30 Average Access Time � Hit time is also important for performance � Average memory access time (AMAT) � AMAT = Hit time + Miss rate × Miss penalty � Example � CPU with 1ns clock, hit time = 1 cycle, miss penalty = 20 cycles, I-cache miss rate = 5% � AMAT = 1 + 0.05 × 20 = 2ns � 2 cycles per instruction Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 31 Performance Summary � When CPU performance increased � Miss penalty becomes more significant � Decreasing base CPI � Greater proportion of time spent on memory stalls � Increasing clock rate � Memory stalls account for more CPU cycles � Can’t neglect cache behavior when evaluating system performance Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 46 Virtual Memory � Use main memory as a “cache” for secondary (disk) storage � Managed jointly by CPU hardware and the operating system (OS) � Programs share main memory � Each gets a private virtual address space holding its frequently used code and data � Protected from other programs � CPU and OS translate virtual addresses to physical addresses � VM “block” is called a page � VM translation “miss” is called a page fault §5.4 Virtual Memory Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 47 Address Translation � Fixed-size pages (e.g., 4K) Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 60 The Memory Hierarchy � Common principles apply at all levels of the memory hierarchy � Based on notions of caching � At each level in the hierarchy � Block placement � Finding a block � Replacement on a miss � Write policy §5.5 A Common Framework for Memory Hierarchies The BIG Picture Chapter 5 — Large and Fast: Exploiting Memory Hierarchy — 87 Concluding Remarks � Fast memories are small, large memories are slow � We really want fast, large memories � � Caching gives this illusion ☺ � Principle of locality � Programs use a small part of their memory space frequently � Memory hierarchy � L1 cache ↔ L2 cache ↔ … ↔ DRAM memory ↔ disk � Memory system design is critical for multiprocessors §5.12 Concluding Remarks