CS61C L32 Caches II (1)A Carle, Summer 2005 © UCBinst.eecs.berkeley.edu/~cs61c/su05CS61C : Machine StructuresLecture #20: Caches 22005-07-26Andy CarleCS61C L32 Caches II (2)A Carle, Summer 2005 © UCBReview: 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 4MemoryMemory Address0123456789ABCDEF4 Byte Direct Mapped CacheCache Index0123CS61C L32 Caches II (3)A Carle, Summer 2005 © UCBIssues with Direct-Mapped•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 fieldsttttttttttttttttt iiiiiiiiii ooootag index byteto check to offsetif have select withincorrect block block blockWIDTHHEIGHTTag Index OffsetCS61C L32 Caches II (4)A Carle, Summer 2005 © UCBDirect-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 locationCS61C L32 Caches II (5)A Carle, Summer 2005 © UCBDirect-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= 24bytes• need 4 bits to specify correct byteCS61C L32 Caches II (6)A Carle, Summer 2005 © UCBDirect-Mapped Cache Example (2/3)•Index: (~index into an “array of blocks”)• need to specify correct row in cache• cache contains 16 KB = 214bytes• block contains 24bytes (4 words)• # blocks/cache= bytes/cachebytes/block=214bytes/cache24bytes/block=210blocks/cache• need 10 bits to specify this many rowsCS61C L32 Caches II (7)A Carle, Summer 2005 © UCBDirect-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 bitsof 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 (8)A Carle, Summer 2005 © UCBTIOAREA (cache size, B)= HEIGHT (# of blocks)* WIDTH (size of one block, B/block)WIDTH (size of one block, B/block)HEIGHT(# of blocks)AREA(cache size, B)2(H+W)= 2H* 2WTag Index OffsetCS61C L32 Caches II (9)A Carle, Summer 2005 © UCBCaching 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 word2. cache miss: nothing in cache in appropriate block, so fetch from memory3. 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 (10)A Carle, Summer 2005 © UCBAccessing data in a direct mapped cache• Ex.: 16KB of data, direct-mapped, 4 word blocks• Read 4 addresses1. 0x000000142. 0x0000001C3. 0x000000344. 0x00008014• Memory values on right:• only cache/ memory level of hierarchy Address (hex)Value of WordMemory0000001000000014000000180000001Cabcd... ...0000003000000034000000380000003Cefgh0000801000008014000080180000801Cijkl... ...... ...... ...CS61C L32 Caches II (11)A Carle, Summer 2005 © UCBAccessing data in a direct mapped cache•4 Addresses:•0x00000014, 0x0000001C, 0x00000034, 0x00008014•4 Addresses divided (for convenience) into Tag, Index, Byte Offset fields000000000000000000 0000000001 0100000000000000000000 0000000001 1100000000000000000000 0000000011 0100000000000000000010 0000000001 0100Tag Index OffsetCS61C L32 Caches II (12)A Carle, Summer 2005 © UCB16 KB Direct Mapped Cache, 16B blocks• Valid bit:determines whether anything is stored in that row (when computer initially turned on, all entries invalid)...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...Index0000000000CS61C L32 Caches II (13)A Carle, Summer 2005 © UCB1. Read 0x00000014...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...• 000000000000000000 0000000001 0100IndexTag field Index field Offset0000000000CS61C L32 Caches II (14)A Carle, Summer 2005 © UCBSo we read block 1 (0000000001)...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...• 000000000000000000 0000000001 0100IndexTag field Index field Offset0000000000CS61C L32 Caches II (15)A Carle, Summer 2005 © UCBNo valid data...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...• 000000000000000000 0000000001 0100IndexTag field Index field Offset0000000000CS61C L32 Caches II (16)A Carle, Summer 2005 © UCBSo load that data into cache, setting tag, valid...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10a b c d• 000000000000000000 0000000001 0100IndexTag field Index field Offset000000000CS61C L32 Caches II (17)A Carle, Summer 2005 © UCBRead from cache at offset, return word b• 000000000000000000 0000000001 0100...ValidTag0x0-30x4-70x8-b 0xc-f0123456710221023...10a b cdIndexTag field Index field Offset000000000CS61C L32 Caches II (18)A Carle, Summer 2005 © UCB2. Read 0x0000001C = 0…00 0..001 1100...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10a b c d• 000000000000000000 0000000001 1100IndexTag field Index field Offset000000000CS61C L32 Caches II (19)A Carle, Summer 2005 © UCBIndex is Valid...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10a b c d• 000000000000000000 0000000001 1100IndexTag field Index field Offset000000000CS61C L32 Caches II (20)A Carle, Summer 2005 © UCBIndex valid, Tag Matches...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10 abcd• 000000000000000000 0000000001 1100IndexTag field Index field Offset000000000CS61C L32 Caches II (21)A Carle, Summer 2005 © UCBIndex Valid, Tag Matches, return d...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10 abcd• 000000000000000000 0000000001 1100IndexTag field Index field Offset000000000CS61C L32 Caches II (22)A Carle, Summer 2005 © UCB3. Read 0x00000034 = 0…00 0..011 0100...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10a b c d• 000000000000000000
View Full Document