Cache MemoriesOctober 6, 2006Cache MemoriesOctober 6, 2006TopicsTopics Generic cache memory organization Direct mapped caches Set associative caches Impact of caches on performance The memory mountainclass12.ppt15-213“The course that gives CMU its Zip!”–2–15-213, F’06Cache MemoriesCache MemoriesCache memories are small, fast SRAMCache memories are small, fast SRAM--based memories based memories managed automatically in hardware. managed automatically in hardware. Hold frequently accessed blocks of main memoryCPU looks first for data in L1, then in L2, then in main CPU looks first for data in L1, then in L2, then in main memory.memory.Typical system structure:Typical system structure:mainmemoryI/Obridgebus interfaceL2 dataALUregister fileCPU chipSRAM Portsystem busmemory busL1 cacheL2tags–3–15-213, F’06Inserting an L1 Cache Between the CPU and Main MemoryInserting an L1 Cache Between the CPU and Main Memorya b c dblock 10p q r sblock 21......w x y zblock 30...The big slow main memory has room for many 4-word blocks.The small fast L1 cache has room for two 4-word blocks.The tiny, very fast CPU register file has room for four 4-byte words.The transfer unit between the cacheand main memoryis a 4-word block (16 bytes).The transfer unit between the CPU register file and the cache is a 4-byte block.line 0line 1–4–15-213, F’06General Organization of a CacheGeneral Organization of a Cache••• B–110••• B–110validvalidtagtagset 0:B = 2bbytesper cache blockE lines per setS = 2ssetst tag bitsper lineCache size: C = B x E x S data bytes•••••• B–110••• B–110validvalidtagtagset 1:•••••• B–110••• B–110validvalidtagtagset S-1:••••••Cache is an arrayof sets.Each set containsone or more lines.Each line holds ablock of data.1 valid bit per line–5–15-213, F’06Addressing CachesAddressing Cachest bits s bitsb bits<tag> <set index> <block offset>0m-1Address A:•••B–110•••B–110vvtagtagset 0:••••••B–110•••B–110vvtagtagset 1:••••••B–110•••B–110vvtagtagset S-1:••••••The word at address A is in the cache ifthe tag bits in one of the <valid> lines in set <set index> match <tag>.The word contents begin at offset <block offset> bytes from the beginning of the block.–6–15-213, F’06Addressing CachesAddressing Cachest bits s bitsb bits<tag> <set index> <block offset>0m-1Address A:•••B–110•••B–110vvtagtagset 0:••••••B–110•••B–110vvtagtagset 1:••••••B–110•••B–110vvtagtagset S-1:••••••1. Locate the set based on <set index>2. Locate the line in the set based on <tag>3. Check that the line is valid4. Locate the data in the line based on<block offset>–7–15-213, F’06Direct-Mapped CacheDirect-Mapped CacheSimplest kind of cache, easy to buildSimplest kind of cache, easy to build(only 1 tag compare required per access)(only 1 tag compare required per access)Characterized by exactly one line per set.Characterized by exactly one line per set.validvalidvalidtagtagtag•••set 0:set 1:set S-1:E=1 lines per setcache blockcache blockcache blockCache size: C = B x S data bytes–8–15-213, F’06Accessing Direct-Mapped CachesAccessing Direct-Mapped CachesSet selectionSet selection Use the set index bits to determine the set of interest.t bits s bits0 0 0 0 10m-1b bitstag set index block offsetselected setvalidvalidvalidtagtagtag•••set 0:set 1:set S-1:cache blockcache blockcache block–9–15-213, F’06Accessing Direct-Mapped CachesAccessing Direct-Mapped CachesLine matching and word selectionLine matching and word selection Line matching: Find a valid line in the selected set with a matching tag Word selection: Then extract the wordt bits s bits100i01100m-1b bitstag set index block offsetselected set (i):1 0110 w3w0w1w23012 7456=1?(1) The valid bit must be set= ?(2) The tag bits in the cache line must match the tag bits in the addressIf (1) and (2), then cache hit–10–15-213, F’06Accessing Direct-Mapped CachesAccessing Direct-Mapped CachesLine matching and word selectionLine matching and word selection Line matching: Find a valid line in the selected set with a matching tag Word selection: Then extract the wordt bits s bits100i01100m-1b bitstag set index block offsetselected set (i):1 0110 w3w0w1w23012 7456(3) If cache hit,block offset selects starting byte.–11–15-213, F’06Direct-Mapped Cache SimulationDirect-Mapped Cache SimulationM=16 byte addresses, B=2 bytes/block, S=4 sets, E=1 entry/setAddress trace (reads):0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]xt=1 s=2 b=1xx x0 ? ?vtag datamiss1 0 M[0-1]hitmiss1 0 M[6-7]miss1 1 M[8-9]miss1 0 M[0-1]–12–15-213, F’06Set Associative CachesSet Associative CachesCharacterized by more than one line per setCharacterized by more than one line per setE=2lines per setvalid tagset 0:set 1:set S-1:•••cache blockvalid tag cache blockvalid tag cache blockvalid tag cache blockvalid tag cache blockvalid tag cache blockE-way associative cache–13–15-213, F’06Accessing Set Associative CachesAccessing Set Associative CachesSet selectionSet selection identical to direct-mapped cachevalidvalidtagtagset 0:validvalidtagtagset 1:validvalidtagtagset S-1:•••cache blockcache blockcache blockcache blockcache blockcache blockt bits s bits0 0 0 0 10m-1b bitstag set index block offsetselected set–14–15-213, F’06Accessing Set Associative CachesAccessing Set Associative CachesLine matching and word selectionLine matching and word selection must compare the tag in each valid line in the selected set.1 0110 w3w0w1w21 1001selected set (i):3012 7456t bits s bits100i01100m-1b bitstag set index block offset=1?(1) The valid bit must be set= ?(2) The tag bits in one of the cache lines must match the tag bits in the addressIf (1) and (2), then cache hit–15–15-213, F’06Accessing Set Associative CachesAccessing Set Associative CachesLine matching and word selectionLine matching and word selection Word selection is the same as in a direct mapped cache1 0110 w3w0w1w21 1001selected set (i):3012 7456t bits s bits100i01100m-1b bitstag set index block offset(3) If cache hit,block offset selects starting byte.–16–15-213, F’062-Way Associative Cache Simulation2-Way Associative Cache SimulationM=16 byte addresses, B=2 bytes/block, S=2 sets, E=2
View Full Document
Unlocking...