Systems I Cache Organization Topics Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on programming Cache Vocabulary Capacity Cache block aka cache line Associativity Cache set Index Tag Hit rate Miss rate Replacement policy 2 General Org 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 3 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 0 0 m 1 s bits b bits 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 4 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 valid tag cache block 5 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 set S 1 valid tag cache block 6 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 0110 1 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 t bits 0110 tag 6 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 7 Direct Mapped Cache Simulation t 1 s 2 x xx M 16 byte addresses B 2 bytes block S 4 sets E 1 entry set b 1 x v 11 Address trace reads 0 00002 1 00012 13 11012 8 10002 0 00002 0 00002 miss tag data 0 m 1 m 0 M 0 1 1 3 v 4 13 11012 miss v tag data 8 10002 miss tag data 11 1 m 9 M 8 9 m 8 1 1 M 12 13 11 0 m 1 m 0 M 0 1 11 1 m 13 m 12 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 8 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 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 9 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 10 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 valid tag cache block valid tag cache block 11 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 1 2 3 4 w0 m 1 6 w1 w2 7 w3 3 If 1 and 2 then cache hit and block offset selects starting byte t bits 0110 tag 5 s bits b bits i 100 set index block offset0 12 Cache Performance Metrics Miss Rate Fraction of memory references not found in cache misses references Typical numbers 3 10 for L1 can be quite small e g 1 for L2 depending on size etc Hit Time Time to deliver a line in the cache to the processor includes time to determine whether the line is in the cache Typical numbers 1 3 clock cycle for L1 5 12 clock cycles for L2 Miss Penalty Additional time required because of a miss Typically 100 300 cycles for main memory 13 Memory System Performance Average Memory Access Time AMAT Taccess 1 pmiss t hit pmisst miss t miss t hit t penalty Assume 1 level cache 90 hit rate 1 cycle hit time 200 cycle miss penalty AMAT 21 cycles even though 90 only take one cycle 14 Memory System Performance II How does AMAT affect overall performance Recall the CPI equation pipeline efficiency CPI 1 0 lp mp rp load use penalty lp assumed memory access of 1 cycle Further we assumed that all load instructions were 1 cycle More realistic AMAT 20 cycles really hurts CPI and overall performance Cause Name Instruction Condition Frequency Frequency Stalls Product Load lp 0 30 0 7 21 4 41 Load Use lp 0 30 0 3 21 1 1 98 Mispredict mp 0 20 0 4 2 0 16 Return rp 0 02 1 0 3 0 06 Total penalty 6 61 15 Memory System Performance III Taccess 1 pmiss t hit pmisst miss t miss t hit t penalty How to reduce AMAT Reduce miss rate Reduce miss penalty Reduce hit time There have been numerous inventions targeting each of these 16 Writing Cache Friendly Code Can write code to improve miss rate Repeated references to variables are good temporal locality Stride 1 reference patterns are good spatial locality Examples cold cache 4 byte words 4 word cache blocks int sumarrayrows int a M N int i j sum 0 int sumarraycols …