inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 20 Caches 2 2005 07 26 Andy Carle CS61C L32 Caches II 1 A Carle Summer 2005 UCB Review Direct Mapped Cache Memory Address Memory 0 1 2 3 4 5 6 7 8 9 A B C D E F Cache Index 0 1 2 3 4 Byte Direct Mapped Cache Cache Location 0 can be occupied by data from Memory location 0 4 8 4 blocks any memory location that is multiple of 4 CS61C L32 Caches II 2 A Carle Summer 2005 UCB Issues with Direct Mapped Tag Index Offset Since multiple memory addresses map to same cache index how do we tell which one is in there What if we have a block size 1 byte Answer divide memory address into three fields HEIGHT WIDTH ttttttttttttttttt iiiiiiiiii oooo tag to check if have correct block CS61C L32 Caches II 3 index to select block byte offset within block A Carle Summer 2005 UCB Direct Mapped Cache Terminology All fields are read as unsigned integers Index specifies the cache index which row of the cache we should look in Offset once we ve found correct block specifies which byte within the block we want I e which column Tag the remaining bits after offset and index are determined these are used to distinguish between all the memory addresses that map to the same location CS61C L32 Caches II 4 A Carle Summer 2005 UCB Direct Mapped Cache Example 1 3 Suppose we have a 16KB of data in a direct mapped cache with 4 word blocks Determine the size of the tag index and offset fields if we re using a 32 bit architecture Offset need to specify correct byte within a block block contains 4 words 16 bytes 24 bytes need 4 bits to specify correct byte CS61C L32 Caches II 5 A Carle Summer 2005 UCB Direct Mapped Cache Example 2 3 Index index into an array of blocks need to specify correct row in cache cache contains 16 KB 214 bytes block contains 24 bytes 4 words blocks cache bytes cache bytes block 214 bytes cache 24 bytes block 210 blocks cache need 10 bits to specify this many rows CS61C L32 Caches II 6 A Carle Summer 2005 UCB Direct Mapped Cache Example 3 3 Tag use remaining bits as tag tag length addr length offset index 32 4 10 bits 18 bits so tag is leftmost 18 bits of memory address Why not full 32 bit address as tag All bytes within block need same address 4b Index must be same for every address within a block so its redundant in tag check thus can leave off to save memory 10 bits in this example CS61C L32 Caches II 7 A Carle Summer 2005 UCB TIO 2 H W 2H 2W AREA cache size B HEIGHT of blocks WIDTH size of one block B block Tag Index Offset HEIGHT of blocks CS61C L32 Caches II 8 WIDTH size of one block B block AREA cache size B A Carle Summer 2005 UCB Caching Terminology When we try to read memory 3 things can happen 1 cache hit cache block is valid and contains proper address so read desired word 2 cache miss nothing in cache in appropriate block so fetch from memory 3 cache miss block replacement wrong data is in cache at appropriate block so discard it and fetch desired data from memory cache always copy CS61C L32 Caches II 9 A Carle Summer 2005 UCB Accessing data in a direct mapped cache Memory Ex 16KB of data Address hex Value of Word direct mapped 4 word blocks Read 4 addresses 1 2 3 4 0x00000014 0x0000001C 0x00000034 0x00008014 Memory values on right only cache memory level of hierarchy 00000010 00000014 00000018 0000001C 00000030 00000034 00000038 0000003C 00008010 00008014 00008018 0000801C CS61C L32 Caches II 10 a b c d e f g h i j k l A Carle Summer 2005 UCB Accessing data in a direct mapped cache 4 Addresses 0x00000014 0x0000001C 0x00000034 0x00008014 4 Addresses divided for convenience into Tag Index Byte Offset fields 000000000000000000 0000000001 0100 000000000000000000 0000000001 1100 000000000000000000 0000000011 0100 000000000000000010 0000000001 0100 Tag CS61C L32 Caches II 11 Index Offset A Carle Summer 2005 UCB 16 KB Direct Mapped Cache 16B blocks Valid bit determines whether anything is stored in that row when computer initially turned on all entries invalid Valid Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 0x4 7 0x0 3 0x8 b 0xc f 1022 0 1023 0 CS61C L32 Caches II 12 A Carle Summer 2005 UCB 1 Read 0x00000014 000000000000000000 0000000001 0100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 13 A Carle Summer 2005 UCB So we read block 1 0000000001 000000000000000000 0000000001 0100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 14 A Carle Summer 2005 UCB No valid data 000000000000000000 0000000001 0100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 15 A Carle Summer 2005 UCB So load that data into cache setting tag valid 000000000000000000 0000000001 0100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 a b c d 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 16 A Carle Summer 2005 UCB Read from cache at offset return word b 000000000000000000 0000000001 0100 Tag field Index field Offset Valid 0x8 b 0xc f 0x4 7 0x0 3 Index Tag 0 0 a b c d 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 17 A Carle Summer 2005 UCB 2 Read 0x0000001C 0 00 0 001 1100 000000000000000000 0000000001 1100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 a b c d 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 18 A Carle Summer 2005 UCB Index is Valid 000000000000000000 0000000001 1100 Tag field Index field Offset Valid 0x4 7 0x8 b 0xc f 0x0 3 Index Tag 0 0 a b c d 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1022 0 1023 0 CS61C L32 Caches II 19 A Carle Summer 2005 UCB Index valid Tag Matches 000000000000000000 0000000001 1100 Tag field Index …
View Full Document
Unlocking...