Cache Memories 15 213 Cache memories are small fast SRAM based memories managed automatically in hardware The course that gives CMU its Zip n Cache Memories Oct 10 2002 Hold frequently accessed blocks of main memory CPU looks first for data in L1 then in L2 then in main memory Typical bus structure Topics n n n n CPU chip Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance register file L1 cache system bus memory bus cache bus L2 cache main memory I O bridge bus interface 15 213 F 02 2 class14 ppt 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 The small fast L1 cache has room for two 4 word blocks line 1 The transfer unit between the cache and main memory is a 4 word block 16 bytes block 10 1 valid bit t tag bits per line per line valid tag 0 1 B 1 E lines per set set 0 Each line holds a block of data B 2b bytes per cache block valid tag 0 1 B 1 valid tag 0 1 B 1 valid tag 1 B 1 1 B 1 1 B 1 set 1 0 abcd pqrs block 30 Cache is an array of sets S 2s sets block 21 General Org of a Cache Memory Each set contains one or more lines line 0 The big slow main memory has room for many 4 word blocks valid 4 0 valid 15 213 F 02 tag set S 1 wxyz 3 ALU tag 0 Cache size C B x E x S data bytes 15 213 F 02 Addressing Caches Direct Mapped Cache 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 tag v tag set S 1 0 0 1 B 1 1 B 1 Simplest kind of cache b bits m 1 0 Characterized by exactly one line per set 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 v s bits set 0 valid tag cache block set 1 valid tag cache block E 1 lines per set set S 1 valid cache block tag The word contents begin at offset block offset bytes from the beginning of the block 15 213 F 02 5 15 213 F 02 6 Accessing Direct Mapped Caches Accessing Direct Mapped Caches Set selection Line matching and word selection n Use the set index bits to determine the set of interest set 0 valid tag cache block set 1 valid tag cache block n Line matching Find a valid line in the selected set with a matching tag n Word selection Then extract the word 1 1 The valid bit must be set selected set t bits m 1 tag s bits b bits 00 001 set index block offset0 set S 1 valid tag 0 selected set i cache block 1 0110 15 213 F 02 2 3 4 w0 5 8 t bits 0110 tag 6 w1 w2 2 The tag bits in the cache line must match the tag bits in the address m 1 7 1 s bits b bits i 100 set index block offset0 7 w3 3 If 1 and 2 then cache hit and block offset selects starting byte 15 213 F 02 Direct Mapped Cache Simulation t 1 s 2 x xx 11 00 01 10 11 Address trace reads 0 00002 1 00012 13 11012 8 10002 0 00002 0 00002 miss tag data 0 v m 1 m 0 M 0 1 1 3 High Order Bit Indexing 4 line Cache M 16 byte addresses B 2 bytes block S 4 sets E 1 entry set b 1 x v Why Use Middle Bits as Index 13 11012 miss tag data High Order Bit Indexing 11 0 m 1 m 0 M 0 1 n 11 1 m 13 m 12 M 12 13 n 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 n v 4 8 10002 miss tag data 11 1 m 9 m 8 M 8 9 1 1 M 12 13 v 5 0 00002 miss tag data 11 0 m 1 m 0 M 0 1 11 1 m 13 m 12 M 12 13 n 15 213 F 02 9 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Middle Order Bit Indexing 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10 15 213 F 02 Set Associative Caches Accessing Set Associative Caches Characterized by more than one line per set Set selection n set 0 set 1 valid tag identical to direct mapped cache cache block valid tag cache block valid tag cache block valid tag cache block set 0 E 2 lines per set Selected set set 1 valid tag cache block valid tag cache block valid tag cache block valid tag cache block set S 1 valid tag cache block valid tag cache block t bits m 1 11 15 213 F 02 tag 12 set S 1 s bits b bits 00 001 set index block offset0 valid tag cache block valid tag cache block 15 213 F 02 Accessing Set Associative Caches Multi Level Caches Line matching and word selection Options separate data and instruction caches caches or a unified cache n must compare the tag in each valid line in the selected set 1 1 The valid bit must be set Processor 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 1 2 3 4 w0 m 1 6 w1 w2 Regs 7 w3 s bits b bits i 100 set index block offset0 15 213 F 02 13 L1 d cache L1 i cache 3 If 1 and 2 then cache hit and block offset selects starting byte t bits 0110 tag 5 Intel Pentium Cache Hierarchy 200 B 3 ns size speed Mbyte line size 8 64 KB 3 ns 8B 32 B larger slower cheaper Unified Unified L2 L2 Cache Cache 1 4MB SRAM 6 ns 100 MB 32 B Memory Memory 128 MB DRAM 60 ns 1 50 MB 8 KB disk disk 30 GB 8 ms 0 05 MB 15 213 F 02 14 Cache Performance Metrics Miss Rate Regs L1 Data 1 cycle latency 16 KB 4 way assoc Write through 32B lines L1 Instruction 16 KB 4 way 32B lines n L2 L2Unified Unified 128KB 2 …
View Full Document