15 213 The course that gives CMU its Zip Cache Memories October 6 2006 Topics Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance The memory mountain class12 ppt 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 2 L1 L2 tags cache bus interface memory bus ALU system bus I O bridge main memory 15 213 F 06 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 transfer unit between the cache and main memory is a 4 word block 16 bytes 3 line 0 line 1 block 10 The small fast L1 cache has room for two 4 word blocks abcd block 21 pqrs block 30 wxyz The big slow main memory has room for many 4 word blocks 15 213 F 06 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 4 valid tag valid tag 0 0 Cache size C B x E x S data bytes 15 213 F 06 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 06 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 6 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 15 213 F 06 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 06 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 8 tag s bits 00 001 set index cache block tag b bits block offset 0 15 213 F 06 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 9 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 15 213 F 06 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 7 w1 w2 w3 3 If cache hit block offset selects starting byte m 1 10 t bits 0110 tag s bits b bits i 100 set index block offset 0 15 213 F 06 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 11 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 15 213 F 06 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 06 Accessing Set Associative Caches Set selection identical to direct mapped cache valid tag set 0 valid tag selected set set 1 valid tag valid tag cache block cache block cache block cache block set S 1 t bits m 1 13 tag valid tag valid tag s bits 00 001 set index cache block cache block b bits block offset 0 15 213 F 06 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 14 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 15 213 F 06 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 15 t bits 0110 tag 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 …
View Full Document
Unlocking...