October 25, 2007 More cache organizations 1How big is the cache?For a byte-addressable machine with 16-bit addresses with a cache with thefollowing characteristics: It is direct-mapped (as discussed last time) Each block holds one byte The cache index is the four least significant bitsTwo questions: How many blocks does the cache hold? How many bits of storage are required to build the cache (e.g., for thedata array, tags, etc.)?October 25, 2007 More cache organizations 2How big is the cache?For a byte-addressable machine with 16-bit addresses with a cache with thefollowing characteristics: It is direct-mapped (as discussed last time) Each block holds one byte The cache index is the four least significant bitsTwo questions: How many blocks does the cache hold?4-bit index -> 24 = 16 blocks How many bits of storage are required to build the cache (e.g., for the dataarray, tags, etc.)?tag size = 12 bits (16 bit address - 4 bit index)(12 tag bits + 1 valid bit + 8 data bits) x 16 blocks = 21 bits x 16 = 336 bitsOctober 25, 2007 More cache organizations 3Direct-mapped caches If the cache contains 2kblocks, then the k leastsignificant bits (LSBs) areused as the index.— data from address iwould be stored inblock i mod 2k. For example, data frommemory address 11 mapsto cache block 3 on theright, since 11 mod 4 = 3and since the lowest twobits of 1011 are 11.0123Index0123456789101112131415MemoryAddressOctober 25, 2007 More cache organizations 4Tags & Valid bits To find data stored in the cache, we need to add tags to distinguishbetween different memory locations that map to the same cache block. We include a single valid bit per block to distinguish full and emptyblocks.00011011Index0000000100100011010001010110011110001001101010111100110111101111Tag Data00110101Valid1111October 25, 2007 ©2003 Craig Zilles (derived fromslides by Howard Huang)5More cache organizations Today, we’ll explore some cache organizations to improve hit rate— How can we take advantage of spatial locality too?— How can we reduce the number of potential conflicts?October 25, 2007 More cache organizations 6 One-byte cache blocks don’t take advantage of spatial locality, whichpredicts that an access to one address will be followed by an access to anearby address. What can we do?Spatial localityOctober 25, 2007 More cache organizations 7 What we can do is make the cache block size larger than one byte. Here we use two-byte blocks, sowe can load thecache with twobytes at a time. If we read fromaddress 12, thedata in addresses12 and 13 wouldboth be copied tocache block 2.Spatial locality0123456789101112131415MemoryAddress0123IndexOctober 25, 2007 More cache organizations 8 Now how can we figure out where data should be placed in the cache? It’s time for block addresses! If the cache block size is 2n bytes, we canconceptually split the main memory into 2n-byte chunks too. To determine the block address of a byteaddress i, you can do the integer divisioni / 2n Our example has two-byte cache blocks, sowe can think of a 16-byte main memory asan “8-block” main memory instead. For instance, memory addresses 12 and 13both correspond to block address 6, since12 / 2 = 6 and 13 / 2 = 6.Block addresses0123456789101112131415ByteAddress01234567BlockAddressOctober 25, 2007 More cache organizations 9 Once you know the block address, you can map it to the cache as before:find the remainder when the block address is divided by the number ofcache blocks. In our example,memory block 6belongs in cacheblock 2, since6 mod 4 = 2. This correspondsto placing datafrom memorybyte addresses12 and 13 intocache block 2.Cache mapping0123456789101112131415ByteAddress0123Index01234567BlockAddressOctober 25, 2007 More cache organizations 10 When we access one byte of data in memory, we’ll copy its entire blockinto the cache, to hopefully take advantage of spatial locality. In our example, if a program reads from byte address 12 we’ll load all ofmemory block 6 (both addresses 12 and 13) into cache block 2. Note byte address 13 corresponds to the same memory block address! Soa read from address 13 will also cause memory block 6 (addresses 12 and13) to be loaded into cache block 2. To make things simpler, byte i of a memory block is always stored in bytei of the corresponding cache block.Data placement within a block1213ByteAddress2CacheBlockByte 1Byte 0October 25, 2007 More cache organizations 11Locating data in the cache Let’s say we have a cache with 2k blocks, each containing 2n bytes. We can determine where a byte of data belongs in this cache by lookingat its address in main memory.— k bits of the address will select one of the 2k cache blocks.— The lowest n bits are now a block offset that decides which of the 2nbytes in the cache block will store the data. Our example used a 22-block cache with 21 bytes per block. Thus, memoryaddress 13 (1101) would be stored in byte 1 of cache block 2.m-bit Addressk bits(m-k-n) bitsn-bit BlockOffset Tag Index4-bit Address2 bits1 bit1-bit BlockOffset 1 10 1October 25, 2007 More cache organizations 12A picture 10123Index Tag DataValidAddress (4 bits)=Hit2Block offsetMuxData8 881 10Tag Index (2 bits)1 0October 25, 2007 More cache organizations 13An exercisen0123Index Tag DataValidAddress (4 bits)=Hit2Block offsetMuxData888n nnTag Index (2 bits)111101010xCA 0xFE0xDE 0xAD0xBE 0xEF0xFE 0xED00For the addresses below,what byte is read from thecache (or is there a miss)? 1010 1110 0001 1101October 25, 2007 More cache organizations 14An exercisen0123Index Tag DataValidAddress (4 bits)=Hit2Block offsetMuxData888n nnTag Index (2 bits)111101010xCA 0xFE0xDE 0xAD0xBE 0xEF0xFE 0xED00For the addresses below,what byte is read from thecache (or is there a miss)? 1010 (0xDE) 1110 (miss, invalid) 0001 (0xFE) 1101 (miss, bad tag)October 25, 2007 More cache organizations 15Using arithmetic An equivalent way to find the right location within the cache is to usearithmetic again. We can find the index in two steps, as outlined earlier.— Do integer division of the address by 2n to find the block address.— Then mod the block address with 2k to find the index. The block offset is just the memory address mod 2n. For example, we can find address 13 in a 4-block, 2-byte per block cache.— The block address is 13 / 2 = 6, so the index is then 6 mod 4 = 2.— The block offset
View Full Document
Unlocking...