PowerPoint PresentationReview: Direct-Mapped CacheIssues with Direct-MappedDirect-Mapped Cache TerminologyDirect-Mapped Cache Example (1/3)Direct-Mapped Cache Example (2/3)Direct-Mapped Cache Example (3/3)TIO Dan’s great cache mnemonicCaching TerminologyAccessing data in a direct mapped cacheSlide 1116 KB Direct Mapped Cache, 16B blocks1. Read 0x00000014So we read block 1 (0000000001)No valid dataSo load that data into cache, setting tag, validRead from cache at offset, return word b2. Read 0x0000001C = 0…00 0..001 1100Index is ValidIndex valid, Tag MatchesIndex Valid, Tag Matches, return d3. Read 0x00000034 = 0…00 0..011 0100So read block 3Slide 24Load that cache block, return word f4. Read 0x00008014 = 0…10 0..001 0100So read Cache Block 1, Data is ValidCache Block 1 Tag does not match (0 != 2)Miss, so replace block 1 with new data & tagAnd return word jDo an example yourself. What happens?AdministriviaAnswersPeer InstructionPeer InstructionsAnd in Conclusion…CS61C L32 Caches II (1)Garcia, 2005 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61c CS61C : Machine StructuresLecture 32 Caches IIACM Programming contest Shanghai Jiaotong Univ took tophonors this year. The highest-ranked US team was U of Illinois at 17th place. Recall UC Berkeley won in 1996 (there’s a plaque on the 3rd floor of Soda Hall). Will US/UCB rule again? news.com.com/U.S.+slips+lower+in+coding+contest/2100-1022_3-5659116.htmlCS61C L32 Caches II (2)Garcia, 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)Garcia, 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)Garcia, 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)Garcia, 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 = 24 bytes•need 4 bits to specify correct byteCS61C L32 Caches II (6)Garcia, 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 = 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 rowsCS61C L32 Caches II (7)Garcia, 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 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 (8)Garcia, 2005 © UCBTIO Dan’s great cache mnemonicAREA (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)Garcia, 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)Garcia, 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)Garcia, 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 0100 Tag Index OffsetCS61C L32 Caches II (12)Garcia, 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)Garcia, 2005 © UCB1. Read 0x00000014...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...•000000000000000000 0000000001 0100IndexTag field Index field Offset0000000000CS61C L32 Caches II (14)Garcia, 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)Garcia, 2005 © UCBNo valid data...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...•000000000000000000 0000000001 0100IndexTag field Index field Offset0000000000CS61C L32 Caches II (16)Garcia, 2005 © UCBSo load that data into cache, setting tag, valid...ValidTag0x0-30x4-7 0x8-b 0xc-f0123456710221023...10 a b c d•000000000000000000 0000000001 0100IndexTag field Index field Offset000000000CS61C L32 Caches
View Full Document
Unlocking...