15 213 Cache Memories October 8 2007 Topics Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance The memory mountain class12 ppt 15 213 F 07 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 system structure CPU chip register file SRAM Port L2 data L1 L2 tags cache bus interface memory bus ALU system bus main memory I O bridge 2 15 213 F 07 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 The transfer unit between the cache and main memory is a 4 word block 16 bytes The small fast L1 cache has room for two 4 word blocks line 1 block 10 a b c d block 21 pqrs The big slow main memory has room for many 4 word blocks block 30 w x y z 3 15 213 F 07 General Organization of a Cache t tag bits per line Cache is an array of sets Each set contains one or more lines set 0 Each line holds a block of data S 2s sets set 1 valid tag valid tag valid tag valid tag B 2b bytes per cache block 0 0 1 B 1 1 B 1 0 0 1 B 1 1 B 1 1 B 1 1 B 1 E lines per set set S 1 1 valid bit per line valid tag valid tag 0 0 Cache size C B x E x S data bytes 4 15 213 F 07 Addressing Caches Address A t bits set 0 set 1 v tag v tag v tag v tag 0 1 B 1 0 1 B 1 set S 1 tag v tag b bits m 1 0 tag set index block offset 0 1 B 1 0 1 B 1 v s bits 0 1 B 1 0 1 B 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 The word contents begin at offset block offset bytes from the beginning of the block 5 15 213 F 07 Addressing Caches Address A t bits set 0 set 1 v tag v tag v tag v tag 0 1 B 1 0 1 B 1 set S 1 tag v tag b bits m 1 0 tag set index block offset 0 1 B 1 0 1 B 1 v s bits 0 1 B 1 0 1 B 1 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 6 15 213 F 07 Direct Mapped Cache Simplest kind of cache easy to build only 1 tag compare required per access 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 valid tag cache block Cache size C B x S data bytes 7 15 213 F 07 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 set S 1 valid t bits m 1 tag s bits 00 001 set index cache block tag b bits block offset 0 8 15 213 F 07 Accessing Direct Mapped Caches 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 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 s bits b bits i 100 set index block offset 0 9 15 213 F 07 Accessing Direct Mapped Caches 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 0 selected set i 1 0110 1 2 3 4 w0 5 6 w1 w2 w3 3 If cache hit block offset selects starting byte m 1 t bits 0110 tag 7 s bits b bits i 100 set index block offset 0 10 15 213 F 07 Direct Mapped Cache Simulation t 1 s 2 b 1 x xx x 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 miss hit miss miss miss 11 15 213 F 07 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 valid tag cache block valid tag cache block E way associative cache 12 15 213 F 07 Accessing Set Associative Caches Set selection identical to direct mapped cache valid tag set 0 valid tag selected set set 1 cache block cache block valid tag cache block valid tag cache block set S 1 t bits m 1 13 tag valid tag cache block valid tag cache block s bits 00 001 set index b bits block offset 0 15 213 F 07 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 m 1 t bits 0110 tag 1 2 3 4 w0 5 6 w1 w2 7 w3 If 1 and 2 then cache hit s bits b bits i 100 set index block offset 0 14 15 213 F 07 Accessing Set Associative Caches 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 2 3 4 w0 5 6 w1 w2 7 w3 3 If cache hit block offset selects starting byte m 1 t bits 0110 tag s bits b bits i 100 set index block offset 0 15 15 213 F 07 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 …
View Full Document
Unlocking...