CacheBasics Two questions to answer (in hardware):Q1: Howdo weknowif a data itemis inthe cache?Q2: Ifit is, how do we find it?DirectmappedEach memory block is mapped to exactly one block in thecachelotsoflowerlevelblocksmustshareblocksinthecacheAddressmapping (toanswerQ2):(block address) modulo (# of blocks in the cache)Haveatagassociatedwitheachcacheblockthat containsthe address information (the upper portion of the address)requiredto identifythe block (to answerQ1)CS314Chapter5A.12HaojinZhu, SJTU, 2017
CS314 Chapter 5A.12 Haojin Zhu, SJTU, 2017 ❑ Two questions to answer (in hardware): Q1: How do we know if a data item is in the cache? Q2: If it is, how do we find it? ❑ Direct mapped Each memory block is mapped to exactly one block in the cache - lots of lower level blocks must share blocks in the cache Address mapping (to answer Q2): (block address) modulo (# of blocks in the cache) Have a tag associated with each cache block that contains the address information (the upper portion of the address) required to identify the block (to answer Q1) Cache Basics
Caching:ASimpleFirstExampleMainMemory0000xXOnewordblocksCache0001xxTwoloworderbits0010xXDataIndexValidTagdefine the byte in the0011xXword (32b words)000100xx010101xx口10D1j0xx110111xxQ2:Howdowefind it?1000xx1001xxUse next 2 low order国oxxQ1: Is it there?memoryaddressbits1011xx- the index - to1100xxComparethecachedetermine which1101xxtag to the high order 2cache block (i.e.,oxxmodulo the number ofmemoryaddressbitsto1111xxtell ifthememory blockblocksinthecache)is inthe cache(blockaddress)modulo (#ofblocksinthecache)CS314Chapter5A.14Haojin Zhu, SJTU, 2017
CS314 Chapter 5A.14 Haojin Zhu, SJTU, 2017 Caching: A Simple First Example 00 01 10 11 Cache Main Memory Q2: How do we find it? Use next 2 low order memory address bits – the index – to determine which cache block (i.e., modulo the number of blocks in the cache) Tag Data Q1: Is it there? Compare the cache tag to the high order 2 memory address bits to tell if the memory block is in the cache Valid 0000xx 0001xx 0010xx 0011xx 0100xx 0101xx 0110xx 0111xx 1000xx 1001xx 1010xx 1011xx 1100xx 1101xx 1110xx 1111xx One word blocks Two low order bits define the byte in the word (32b words) (block address) modulo (# of blocks in the cache) Index