15 213 The course that gives CMU its Zip Cache Memories Oct 11 2001 Topics class14 ppt Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance Cache memories Cache memories are small fast SRAM based memories managed automatically in hardware Hold frequently accessed blocks of main memory CPU looks first for data in L1 then in L2 then in main memory Typical bus structure CPU chip register file L1 cache ALU cache bus L2 cache class14 ppt system bus memory bus main memory I O bridge bus interface 2 CS 213 F 01 Inserting an L1 cache between the CPU and main memory The tiny very fast CPU register file has room for four 4 byte words The transfer unit between the CPU register file and the cache is a 4 byte block line 0 line 1 The transfer unit between the cache and main memory is a 4 word block 16 bytes block 10 The small fast L1 cache has room for two 4 word blocks abcd block 21 The big slow main memory has room for many 4 word blocks pqrs block 30 wxyz class14 ppt 3 CS 213 F 01 General organization of a cache memory Cache is an array of sets Each set contains one or more lines 1 valid bit t tag bits per line per line valid S sets 0 1 B 1 E lines per set set 0 Each line holds a block of data 2s tag B 2b bytes per cache block valid tag 0 1 B 1 valid tag 0 1 B 1 1 B 1 1 B 1 1 B 1 set 1 valid tag 0 valid tag 0 set S 1 valid tag 0 Cache size C B x E x S data bytes class14 ppt 4 CS 213 F 01 Addressing caches Address A t bits v tag v tag v tag v tag set 0 set 1 0 0 1 B 1 1 B 1 0 0 1 B 1 1 B 1 1 B 1 1 B 1 v tag v tag set S 1 class14 ppt 0 0 s bits b bits m 1 0 tag set index block offset The word at address A is in the cache if the tag bits in one of the valid lines in set set index match tag The word contents begin at offset block offset bytes from the beginning of the block 5 CS 213 F 01 Direct mapped cache Simplest kind of cache Characterized by exactly one line per set set 0 valid tag cache block set 1 valid tag cache block E 1 lines per set set S 1 class14 ppt valid tag cache block 6 CS 213 F 01 Accessing direct mapped caches Set selection Use the set index bits to determine the set of interest selected set set 0 valid tag cache block set 1 valid tag cache block t bits m 1 tag s bits b bits 00 001 set index block offset0 class14 ppt set S 1 valid 7 tag cache block CS 213 F 01 Accessing direct mapped caches Line matching and word selection find a valid line in the selected set with a matching tag line matching then extract the word word selection 1 1 The valid bit must be set 0 selected set i 1 1 0110 2 3 4 w0 5 w1 w2 2 The tag bits in the cache line must match the tag bits in the address m 1 class14 ppt t bits 0110 tag s bits b bits i 100 set index block offset0 8 6 7 w3 3 If 1 and 2 then cache hit and block offset selects starting byte CS 213 F 01 Direct mapped cache simulation t 1 s 2 x xx b 1 x M 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 0000 v 1 0 0000 miss tag data 0 m 1 m 0 1 2 v 1 8 1000 miss tag data 1 4 9 1 0 m 1 m 0 1 1 m 13 m 12 v m 9 m 8 3 class14 ppt 13 1101 miss v tag data 0 0000 miss tag data 1 0 m 1 m 0 1 1 m 13 m 12 CS 213 F 01 Why use middle bits as index High Order Bit Indexing 4 line Cache 00 01 10 11 High Order Bit Indexing Adjacent memory lines would map to same cache entry Poor use of spatial locality Middle Order Bit Indexing Consecutive memory lines map to different cache lines Can hold C byte region of address space in cache at one time class14 ppt 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10 Middle Order Bit Indexing 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 CS 213 F 01 Set associative caches Characterized by more than one line per set set 0 set 1 valid tag cache block valid tag cache block valid tag cache block valid tag cache block E 2 lines per set set S 1 class14 ppt valid tag cache block valid tag cache block 11 CS 213 F 01 Accessing set associative caches Set selection identical to direct mapped cache set 0 Selected set set 1 valid tag cache block valid tag cache block valid tag cache block valid tag cache block t bits m 1 tag set S 1 s bits b bits 00 001 set index block offset0 class14 ppt valid tag cache block valid tag cache block 12 CS 213 F 01 Accessing set associative caches Line matching and word selection must compare the tag in each valid line in the selected set 1 1 The valid bit must be set 0 selected set i 1 1001 1 0110 2 The tag bits in one of the cache lines must match the tag bits in the address 2 3 4 w0 t bits 0110 tag 5 6 w1 w2 7 w3 3 If 1 and 2 then cache hit and block offset selects starting byte m 1 class14 ppt 1 s bits b bits i 100 set index block offset0 13 CS 213 F 01 Multi level caches Options separate data and instruction caches or a unified cache Processor TLB regs L1 Dcache L1 Icache size speed Mbyte line size 200 B 3 ns 8 64 KB 3 ns 8B 32 B larger slower cheaper L2 Cache 1 4MB SRAM 6 ns 100 MB 32 B Memory Memory disk disk 128 MB DRAM 60 ns 1 50 MB 8 KB 30 GB 8 ms 0 05 MB larger line size higher associativity more likely to write back class14 ppt 14 CS 213 F 01 Intel Pentium cache hierarchy Regs L1 Data 1 cycle latency 16KB 4 way assoc Write through 32B lines L2 Unified 128KB 2 MB 4 way assoc Write back Write allocate 32B lines L1 Instruction 16KB 4 way 32B lines Main Memory Up to 4GB Processor …
View Full Document
Unlocking...