15740 Caches Oct 8 1998 Topics Memory Hierarchy Cache Design Optimizing Program Performance Computer System Processor Processor interrupts Cache Cache Memory I O Memory I Obus bus Memory Memory I O I O controller controller disk Disk 2 disk Disk I O I O controller controller I O I O controller controller Display Display Network Network CS 740 F 98 Levels in a typical memory hierarchy cache CPU CPU regs regs register reference size speed Mbyte block size 200 B 5 ns 4B 4B C a c h e 32 B cache reference 32KB 4MB 6 ns 256 MB 16 B virtual memory Memory Memory memory reference 128 MB 100 ns 2 MB 4 KB 4 KB disk disk disk memory reference 10GB 10 ms 0 10 MB larger slower cheaper 3 CS 740 F 98 Alpha 21164 Chip Photo Microprocessor Report 9 12 94 Caches L1 data L1 instruction L2 unified TLB Branch history 4 CS 740 F 98 Alpha 21164 Chip Caches Right Half L2 Microprocessor Report 9 12 94 L2 3 Control Caches L1 data L1 instruction L2 unified TLB Branch history L1 Data L1 I n s t r Right Half L2 5 L2 Tags CS 740 F 98 High Level Low Level Acc essi Between any two levels memory divided into blocks Data moves between levels onng demand in block sized chunks Upper level blocks a subset of lower level blocks dat Access word w in block a hit a in Access word v in block b miss a w v me a a a mor b y b hier b b b a a arc a hy 6 CS 740 F 98 Locality of Principle of Locality reference Programs tend to reuse data and instructions near those they have used recently Temporal locality recently referenced items are likely to be referenced in the near future Spatial locality items with nearby addresses tend to be referenced close together in time Locality in Example sum 0 for i 0 i n i sum a i v sum Data Reference array elements in succession spatial Instruction Reference instructions in sequence spatial Cycle through loop repeatedly temporal 7 CS 740 F 98 Key que Q1 Where should a block be placed in the cache stio block placement ns Q2 How is a block found in the cache block for identification cac hes Q3 Which block should be replaced on a miss block replacement Q4 What happens on a write write strategy 8 CS 740 F 98 Address spaces An n bit address defines an address space of 2n items 0 2n 1 9 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 Address space for n 5 CS 740 F 98 Partitioning address spaces Key idea partitioning the address bits partitions the address space In general an address partitioned into sets of t tag s set index and b block offset bits e g address t tag s set index b offset belongs to one of 2s equivalence classes sets where each set consists of 2t blocks of addresses and each block consists of 2b addresses The s bits uniquely identify an equivalence class The t bits uniquely identify each block in the equivalence class The b bits define the offset of an address within a block block offset 10 CS 740 F 98 Partitioning address spaces t 1 s 3 1 011 b 1 0 2s 8 sets of blocks 2t 2 blocks set 2b 2 addresses block block 1 11 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 set 011 offset 0 CS 740 F 98 Partitioning address spaces t 1 s 3 0 110 b 1 1 2s 8 sets of blocks 2t 2 blocks set 2b 2 addresses block 12 block 0 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 set 110 offset 1 CS 740 F 98 Partitioning address spaces t 2 s 2 10 11 b 1 0 2s 4 sets of blocks 2t 4 blocks set 2b 2 addresses block block 10 13 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 set 11 offset 0 CS 740 F 98 Partitioning address spaces t 2 s 2 01 10 b 1 1 2s 4 sets of blocks 2t 4 blocks set 2b 2 addresses block 14 block 01 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 set 10 offset 1 CS 740 F 98 Partitioning address spaces t 3 s 1 101 1 b 1 0 2s 2 sets of blocks 2t 8 blocks set 2b 2 addresses block offset 0 block 101 15 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 set 1 CS 740 F 98 Partitioning address spaces t 4 s 0 1011 b 1 0 set 2s 1 set of blocks 2t 16 blocks set 2b 2 addresses block block 1011 16 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 offset 0 CS 740 F 98 Basic cache organization Address space N 2n bytes Cache C S x E x B bytes E blocks set Address n t s b bits t Valid bit tag 1 bit t bits s b data B 2b bytes block size S 2s sets Cache block cache line E Describes associativity how many blocks in set can reside in cache simultaneously Assume E 2t 17 CS 740 F 98 Direct mapped cache E 1 N 16 byte addresses n 4 t 1 s 2 x xx 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 18 cache size C 8 data bytes line size B 2b 2 bytes line b 1 x direct mapped cache E 1 entry set 00 01 S 2s 4 sets 10 11 1 Determine set from middle bits 2 If something already there knock it out 3 Put new block in cache CS 740 F 98 t 1 s 2 x xx 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 19 b 1 x Direct Mapped Cache Simulation N 16 byte addresses B 2 bytes block S 4 sets E 1 entry set Address trace reads 0 0000 1 0001 13 1101 8 1000 0 …
View Full Document
Unlocking...