Cache Memories 15 213 Cache memories are small fast SRAM based memories managed automatically in hardware The course that gives CMU its Zip Cache Memories October 6 2006 Hold frequently accessed blocks of main memory CPU looks first for data in L1 then in L2 then in main memory Typical system structure Topics CPU chip Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance The memory mountain SRAM Port L2 data 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 3 memory bus system bus main memory I O bridge bus interface 15 213 F 06 2 class12 ppt The transfer unit between the cache and main memory is a 4 word block 16 bytes register file L1 L2 ALU tags cache line 0 line 1 The small fast L1 cache has room for two 4 word blocks General Organization of a Cache t tag bits per line Cache is an array of sets Each set contains one or more lines valid set 0 Each line holds a block of data S 2s sets block 10 abcd block 21 pqrs block 30 wxyz 15 213 F 06 tag 0 1 B 1 valid tag 0 1 B 1 valid tag 1 B 1 valid tag 1 B 1 1 B 1 1 B 1 0 0 E lines per set The big slow main memory has room for many 4 word blocks set 1 B 2b bytes per cache block set S 1 1 valid bit per line 4 valid tag valid tag 0 0 Cache size C B x E x S data bytes 15 213 F 06 Addressing Caches Addressing Caches Address A t bits set 0 set 1 v tag v tag v tag v tag v tag v tag 0 1 B 1 0 1 B 1 b bits m 1 t bits 0 tag set index block offset 0 1 B 1 0 1 B 1 set S 1 s bits Address A 0 1 B 1 0 1 B 1 set 0 set 1 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 tag v tag v tag v tag v tag v tag 0 1 B 1 0 1 B 1 0 1 B 1 0 1 B 1 The word contents begin at offset block offset bytes from the beginning of the block 15 213 F 06 5 b bits m 1 0 tag set index block offset 0 1 B 1 0 1 B 1 set S 1 s bits 1 Locate the set based on set index 2 Locate the line in the set based on tag 3 Check that the line is valid 4 Locate the data in the line based on block offset 15 213 F 06 6 Direct Mapped Cache Accessing Direct Mapped Caches Simplest kind of cache easy to build only 1 tag compare required per access Set selection Use the set index bits to determine the set of interest Characterized by exactly one line per set set 0 valid set 1 valid tag cache block tag cache block E 1 lines per set selected set tag cache block set 1 valid tag cache block set S 1 valid cache block t bits Cache size C B x S data bytes 7 tag set S 1 valid set 0 valid 15 213 F 06 m 1 8 tag s bits 00 001 set index cache block tag b bits block offset 0 15 213 F 06 Accessing Direct Mapped Caches Accessing Direct Mapped Caches Line matching and word selection Line matching and word selection Line matching Find a valid line in the selected set with a matching tag Word selection Then extract the word Line matching Find a valid line in the selected set with a matching tag Word selection Then extract the word 1 1 The valid bit must be set 0 selected set i 1 2 The tag bits in the cache line must match the tag bits in the address m 1 1 2 3 4 5 6 7 0110 w0 If 1 and 2 then cache hit t bits 0110 tag w1 w2 w3 15 213 F 06 M 16 byte addresses B 2 bytes block S 4 sets E 1 entry set Address trace reads 0 1 7 8 0 00002 00012 01112 10002 00002 v tag data 0 1 1 0 M 8 9 M 0 1 1 0 M 6 7 1 1 2 0110 3 4 w0 5 6 7 w1 w2 w3 3 If cache hit block offset selects starting byte m 1 Direct Mapped Cache Simulation 11 selected set i s bits b bits i 100 set index block offset 0 9 t 1 s 2 b 1 x xx x 0 t bits 0110 tag s bits b bits i 100 set index block offset 0 15 213 F 06 10 Set Associative Caches Characterized by more than one line per set miss hit miss miss set 0 set 1 miss valid tag cache block valid tag cache block valid tag cache block valid tag cache block E 2 lines per set set S 1 valid tag cache block valid tag cache block E way associative cache 15 213 F 06 12 15 213 F 06 Accessing Set Associative Caches Accessing Set Associative Caches Set selection Line matching and word selection identical to direct mapped cache valid tag set 0 valid tag selected set set 1 valid tag valid tag cache block cache block set S 1 t bits m 1 13 valid tag valid tag s bits cache block cache block block offset 15 213 F 06 Line matching and word selection Word selection is the same as in a direct mapped cache 0 selected set i 1 1001 1 0110 1 1 The valid bit must be set 0 selected set i m 1 15 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 5 6 w1 w2 3 4 5 6 w1 w2 7 w3 If 1 and 2 then cache hit s bits b bits i 100 set index block offset 0 15 213 F 06 2 Way Associative Cache Simulation t 2 s 1 b 1 xx x x M 16 byte addresses B 2 bytes block S 2 sets E 2 entry set Address trace reads 00002 miss 00012 hit 01112 miss 10002 miss hit 00002 0 1 7 8 0 7 w3 s bits b bits i 100 set index block offset 0 15 213 F 06 2 w0 t bits 0110 tag 1 14 3 If cache hit block offset selects starting byte t bits 0110 tag 1 m 1 0 Accessing Set Associative Caches must compare the tag in each valid line in the selected …
View Full Document
Unlocking...