Transcription
Computer Science 61C Spring 2022McMahon and WeaverCaches1
Components of a ComputerComputer Science 61C Spring 2022McMahon and WeaverComputer Science 61C Spring 2020Kolb and thmetic & Logic Unit(ALU)ReadDataProcessor-Memory InterfaceDataOutputI/O-Memory Interfaces2
Processor-DRAM Latency GapComputer Science 61C Spring 2022McMahon and WeaverComputer Science 61C Spring 2020Kolb and Weaver1980 microprocessor executes one instruction in same time as DRAM access2020 microprocessor executes 1000 instructions in same time as DRAM accessSlow DRAM access could have disastrous impact on CPU performance!3
Library AnalogyComputer Science 61C Spring 2022 Time to nd a book in a largelibraryComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverSearch a large card catalog –(mapping title/author to indexnumber)Round-trip time to walk to thestacks and retrieve the desired book Larger libraries worsen bothdelays Electronic memories havesame issue, plus thetechnologies used to store abit slow down as densityincreases (e.g., SRAM vs.DRAM vs. Disk)fi4
What to do: Library AnalogyComputer Science 61C Spring 2022 Write a report using library booksComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Go to library, look up books, fetch from stacks, and place ondesk in library If need more, check out, keep on desk But don’t return earlier books since might need them You hope this collection of 10 books on desk enough towrite report, despite 10 being only 0.00001% of books in UCBerkeley libraries5
Memory CachingComputer Science 61C Spring 2022McMahon and Weaver Mismatch between processor and memory speeds leads usto add a new level Computer Science 61C Spring 2020 Kolb and WeaverIntroducing a “memory cache” Usually on the same chip as the CPU Faster but more expensive than DRAM memory. Cache is a copy of a subset of main memory Most processors have separate caches for instructions anddata.6
Memory HierarchyComputer Science 61C Spring 2022McMahon and Weaver If level closer to Processor, it is:Computer Science 61C Spring 2020 SmallerFasterMore expensivesubset of lower levels (contains mostrecently used data) Lowest Level (usuallydisk HDD/SSD) contains allavailable data Memory Hierarchy presents theprocessor with the illusion of avery large & fast memoryKolb and WeaverRegistersCacheMain memoryDisk7
Memory HierarchyComputer Science 61C Spring 2022McMahon and Weaver Programmer-invisible hardware mechanismComputer Science 61C Spring 2020Kolb and Weaver Gives illusion of the speed of the fastest memory with thesize of the largest memory How do we make it fast? Hierarchy How do we make it appear large? Keep the right data in the cache8
Memory Hierarchy BasisComputer Science 61C Spring 2022 Cache contains copies of data that are being usedComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Caches work on the principles of temporal and spatiallocality. Temporal locality (locality in time): If we use it now, chances are that we’ll wantto use it again soon. Spatial locality (locality in space): If we use a piece of memory, chances arewe’ll use the neighboring pieces soon.9
Taking Advantage of LocalityComputer Science 61C Spring 2022 Temporal LocalityComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverIf a memory location is referenced then it will tend to be referenced again soonKeep most recently accessed data items closer to the processor Spatial Locality If a memory location is referenced, the locations with nearby addresses willtend to be referenced soon Move blocks consisting of contiguous words closer to the processor10
Adding Cache to the ComputerComputer Science 61C Spring 2022McMahon and WeaverComputer Science 61C Spring tapathAddressPCKolb and c & Logic Unit(ALU)ReadDataProcessor-Memory InterfaceDataOutputI/O-Memory Interfaces11
Memory Reference PatternsMcMahon and WeaverComputer Science 61C Spring 2020Kolb and WeaverMemory Address(one dot per access)Computer Science 61C Spring 2022TemporalLocalitySpatialLocalityDonald J. Hatfield, Jeanette Gerald: Program Restructuring for Virtual Memory.IBM Systems Journal 10(3): 168-192 (1971)12
Good Memory Reference PatternsComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverAddressKolb and Weavern loop ecarayrAscalar accessesTime13
Memory Access without CacheComputer Science 61C Spring 2022 Load word instruction: lw t0 0(t1)Computer Science 61C Spring 2020McMahon and WeaverKolb and Weaver t1 contains 0x12F0, Memory[0x12F0] 991.2.3.4.Processor issues address 0x12F0 to MemoryMemory reads word at address 0x12F0 (99)Memory sends 99 to ProcessorProcessor loads 99 into register t014
Memory Access with CacheComputer Science 61C Spring 2022McMahon and Weaver Load word instruction: lw t0,0(t1) t1 contains 0x12F0, Memory[0x12F0] 99 With cache: Processor issues address 0x12F0 to CacheComputer Science 61C Spring 20201.Kolb and WeaverCache checks to see if has copy of data at address 0x12F02a. If nds a match (Hit): cache reads 99, sends to processor2b. No match (Miss): cache sends address 0x12F0 to Memory2.I.II.III.IV.Memory reads 99 at address 0x12F0Memory sends 99 to CacheCache replaces word which can store 0x12F0 with new 99Cache sends 99 to processorProcessor loads 99 into register t0fi15
Cache Hit vs Cache MissComputer Science 61C Spring 2022McMahon and Weaver Cache HitComputer Science 61C Spring 2020 Kolb and WeaverThe data you were looking for is in the cacheRetrieve the data from the cache and bring it to the processor Cache MissThe data you were looking for is not in the cacheGo to the memory to nd the data, put the data in the cache, and bring it tothe processor16fi
How is our data stored in the cache?Computer Science 61C Spring 2022 Fully AssociativeComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Direct Mapped Set-Associative17
Computer Science 61C Spring 2022McMahon and WeaverFully Associative Cache18
Fully Associative CacheComputer Science 61C Spring 2022McMahon and WeaverUsed to identifythe dataComputer Science 61C Spring 2020TagFull AddressServes asthe tagKolb and WeaverDataIdentifiesthe byteoffsetThe data can be stored anywhere inthe cachecache line/cache block4 Bytes19
Valid BitComputer Science 61C Spring 2022 When start a new program, cache does not have validinformation for this programComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Need an indicator whether this tag entry is valid for thisprogram Add a “valid bit” to the cache tag entry 0 cache miss, even if by chance, address tag 1 cache hit, if processor address tag20
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverUsed to identifythe dataUsed to identify ifthe data is validValid TagFull AddressServes asthe tagKolb and WeaverDataIdentifiesthe byteoffsetThe data can be stored anywhere inthe cachecache line/cache block4 Bytes21
TerminologyComputer Science 61C Spring 2022 Cache line/blockComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverA single entry in the cache Line size / block size The number of bytes in each cache line Tag Identi es the data stored at a given cache line Valid bit Tells you if the data stored at a given cache line is valid Capacityfi The total number of data bytes that can be stored in a cache22
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverUsed to identifythe dataUsed to identify ifthe data is validValid TagKolb and WeaverDataline size 4 bytescapacity 16 bytescache line/cache block4 Bytes23
Fully Associative Cache Address BreakdownComputer Science 61C Spring 2022McMahon and WeaverFull Address: ex 12 bitsComputer Science 61C Spring 202011Kolb and Weaver2 1Tag0Valid TagDataByte offset# byte offset bits log2(line size) log2(4) 2# tag bits # address bits - # offset bits 12 - 2 10cache line/cache block4 Bytes2
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid TagFull AddressTagByte OffsetEx: load byte at 0x43FTag 10 bitsData111001Kolb and Weaver000 0 0 0 Byte offset 2 bits4 Bytes25
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid TagFull AddressTagByte OffsetEx: load byte at 0x43F0100 0011 1111Tag 10 bitsByte offset 2 bitsTag 0x10FByte offset 0x3DataKolb and Weaver1110010010x10F 0 0 0 Cache Miss4 BytesWhen you load the value from memory, you’llload an entire block (in this case a block is 4bytes) even if you are only reading one byte 26
LocalityComputer Science 61C Spring 2022 Temporal localityComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverThe data we access is saved in the cache for potential future use Spatial locality We bring in a chunk of data at a time because there is a good chance that wewill want to access other data within the chunk27
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagByte OffsetEx: load byte at 0x5E2Tag 10 bitsValidTag1DataKolb and Weaver111001000x10F 0 0 0 Byte offset 2 bits4 Bytes28
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagValidTag1Byte OffsetEx: load byte at 0x5E20101 1110 0010Tag 10 bitsByte offset 2 bitsTag 0x178Byte offset 0x2DataKolb and Weaver111001000x10F 10x178 0 0 Cache Miss4 BytesWe are only reading one byte, but we bring inan entire line (in this case the line is 4 bytes)29
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagByte OffsetEx: load word at 0x824Tag 10 bitsValidTag1DataKolb and Weaver111001000x10F 10x178 0 0 Byte offset 2 bits4 Bytes30
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagValidTag1Byte OffsetEx: load word at 0x8241000 0010 0100Tag 10 bitsByte offset 2 bitsTag 0x209Byte offset 0x0DataKolb and Weaver111001000x10F 10x178 10x209 0 Cache Miss4 BytesWe are reading 4 bytes and bringing in oneline (4 bytes)31
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagByte OffsetEx: load word at 0x5E0Tag 10 bitsValidTag1DataKolb and Weaver111001000x10F 10x178 10x209 0 Byte offset 2 bits4 Bytes32
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagValidTag1Byte OffsetEx: load word at 0x5E00101 1110 0000Tag 10 bitsByte offset 2 bitsTag 0x178Byte offset 0x0DataKolb and Weaver111001000x10F 10x178 10x209 0 Cache Hit4 Bytes33
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagByte OffsetEx: load word at 0x524Tag 10 bitsValidTag1DataKolb and Weaver111001000x10F 10x178 10x209 0 Byte offset 2 bits4 Bytes34
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagValidTag1Byte OffsetEx: load word at 0x524DataKolb and Weaver111001000x10F 10x178 10x209 10x149 0101 0010 0100Tag 10 bitsByte offset 2 bitsTag 0x149Byte offset 0x04 Bytes35
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagByte OffsetEx: load byte at 0x972Tag 10 bitsValidTag1DataKolb and Weaver111001000x10F 10x178 10x209 10x149 Byte offset 2 bits4 Bytes36
Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressTagValidTag1Byte OffsetEx: load byte at 0x9721001 0111 0010Tag 10 bitsTag 0x25CByte offset 2 bitsDataKolb and Weaver111001000x10F 10x178 10x209 10x149 Cache Miss4 BytesByte offset 0x237
Eviction PoliciesComputer Science 61C Spring 2022 Least-Recently UsedComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverHardware keeps track of access historyReplace the entry that has not been used for the longest time38
0 Most recently used (MRU)3 Least recently used (LRU)Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid LRUFull AddressTagByte OffsetEx: load byte at 0x972Tag 0x25CKolb and Weaver11100100130x10F 110x178 120x209 100x149 1001 0111 0010Tag 10 bitsDataTagByte offset 2 bitsCache Miss4 BytesByte offset 0x239
0 Most recently used (MRU)1 Least recently used (LRU)Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid LRUFull AddressTagByte OffsetEx: load byte at 0x972Tag 0x25CDataKolb and Weaver11100100100x25C 120x178 130x209 110x149 1001 0111 0010Tag 10 bitsTagByte offset 2 bitsCache Miss4 BytesByte offset 0x240
0 Most recently used (MRU)1 Least recently used (LRU)Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid LRUFull AddressTagByte OffsetEx: store byte at 0x524Tag 10 bitsTagDataKolb and Weaver11100100100x25C 120x178 130x209 110x149 Byte offset 2 bits4 Bytes41
0 Most recently used (MRU)1 Least recently used (LRU)Fully Associative CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverValid LRUFull AddressByte OffsetTagEx: store byte at 0x5240101 0010 0100Tag 10 bitsByte offset 2 bitsTag 0x149Byte offset 0x0TagDataKolb and Weaver11100100110x25C 120x178 130x209 100x149 Cache Hit4 Bytes42
Handling StoresComputer Science 61C Spring 2022 Store instructions write to memory, changing valuesComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Need to make sure cache and memory have consistentinformation43
Write-through vs Write-back PoliciesComputer Science 61C Spring 2022 Write-throughComputer Science 61C Spring 2020 McMahon and WeaverKolb and WeaverWrite to the cache and the memory at the same timeThe write to memory will take longer Write-back Write data in cache and set the dirty bit to 1When this line gets evicted from the cache, write it to memory44
Write-through vs Write-back PoliciesComputer Science 61C Spring 2022McMahon and Weaver Write-throughComputer Science 61C Spring 2020 Kolb and WeaverVery simple to implement Write-backtypically lowers tra c to the memory because you might write to somethingmultiple times before you evict it from the cache45ffi
0 Most recently used (MRU)1 Least recently used (LRU)Fully Associative Cache (write-back)Computer Science 61C Spring 2022McMahon and WeaverValid Dirty LRUFull AddressComputer Science 61C Spring 2020TagByte OffsetEx: store byte at 0x524TagDataKolb and Weaver111001001010x25C 1020x178 1030x209 1100x149 0101 0010 0100Tag 10 bitsByte offset 2 bitsTag 0x149Byte offset 0x0Cache Hit4 Bytes46
Fully Associative CacheComputer Science 61C Spring 2022McMahon and WeaverComputer Science 61C Spring 2020Kolb and WeaverTagData8 Bytes47
Hardware Required for Fully Associative CacheComputer Science 61C Spring 2022McMahon and Weaver Need a comparator for each row in the cache to check thetagValid TagDataComputer Science 61C Spring 2020Kolb and WeaverFull AddressServes asthe tagIdentifiesthe byteoffsetThe data can be stored anywhere inthe cachecache line/cache block4 Bytes48
Computer Science 61C Spring 2022McMahon and WeaverDirect Mapped Caches49
Direct Mapped CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverMemory4-Byte Direct Mapped CacheKolb and WeaverBlock size 1 byte50
Direct Mapped CacheComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and Weaver8-Byte Direct Mapped CacheMemoryKolb and WeaverBlock size 2 bytesNote that this memory andcache are twice as large as theprevious slide51
Direct Mapped (write-back)Computer Science 61C Spring 2022McMahon and Weaver The data can only be stored in one locationComputer Science 61C Spring 2020Valid DirtyFull AddressTagKolb and WeaverData111001000TagIndexTIOByteOffset1234 Bytes52
Direct Mapped Cache Address BreakdownComputer Science 61C Spring 2022Computer Science 61C Spring 202011McMahon and WeaverFull Address: ex 12 bits4 32 1TagKolb and Weaver0Valid TagDataByte offset# byte offset bits log2(line size) log2(4) 2# index bits log2(# lines) log2(4) 2# tag bits # address bits - # index bits - # offset bits4 Bytes 12 - 2 - 2 8cache line/cache block53
Direct-Mapped Cache Hardware: 1 word blocks, 4KB dataComputer Science 61C Spring 2022McMahon and WeaverComputer Science 61C Spring 202031 30Hit.13 12 11TagIndex Valid20IndexTag.2 1 0Byte offset10Kolb and WeaverDataData012.1021102210232032Comparator54
Multiword-Block Direct-Mapped Cache: 16B block size, 4 kB dataComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and Weaver31 30 . . .HitTagIndex Valid012.25325425513 12 1120Index.84 3 2 1 0Byte offset2DataKolb and WeaverWord offsetDataTag203255
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020TagMcMahon and WeaverFull AddressIndexValid DirtyByteOffsetRead byte 0xFE2T 8 bits I 2 bits O 2 bitsTagDataKolb and Weaver1110010000 10 20 30 4 Bytes56
Direct MappedComputer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagValid DirtyIndex ByteOffsetRead byte 0xFE2T 8 bits I 2 bits O 2 bits0b 1111 1110 0010T 0xFEI 0x0O 0x2TagDataKolb and Weaver111001000100xFE 10 20 30 Cache Miss bring in entire line4 Bytes57
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xFE8T 8 bits I 2 bits O 2 bits30 0 TagIndexByteOffset4 Bytes58
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020TagMcMahon and WeaverFull AddressIndexValid DirtyByteOffsetRead byte 0xFE8T 8 bits I 2 bits O 2 bits0b 1111 1110 1000T 0xFEI 0x2O 0x0TagDataKolb and Weaver111001000100xFE 10 2100xFE 30 Cache Miss bring in entire line4 Bytes59
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xFE9T 8 bits I 2 bits O 2 bits3100xFE 0 TagIndexByteOffset4 Bytes60
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xFE9T 8 bits I 2 bits O 2 bits30b 1111 1110 1001100xFE 0 TagIndexT 0xFEI 0x2O 0x1ByteOffsetCache Hit!4 Bytes61
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xDF9T 8 bits I 2 bits O 2 bits3100xFE 0 TagIndexByteOffset4 Bytes62
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xDF9T 8 bits I 2 bits O 2 bits30b 1101 1111 1001100xFE 0 TagIndexT 0xDFI 0x2O 0x1ByteOffsetCache Miss bring in entire line4 Bytes63
Direct Mapped Cache ReplacementComputer Science 61C Spring 2022McMahon and Weaver Every address can only be stored at one location in the cacheComputer Science 61C Spring 2020Kolb and Weaver If there is already something else stored at our index, wemust evict it64
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xDF9T 8 bits I 2 bits O 2 bits30b 1101 1111 1001100xDF 0 TagIndexT 0xDFI 0x2O 0x1ByteOffsetCache Miss bring in entire line4 Bytes65
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020McMahon and WeaverFull AddressValid DirtyTagDataKolb and Weaver111001000100xFE 10 2Read byte 0xFE8T 8 bits I 2 bits O 2 bits3100xDF 0 TagIndexByteOffset4 Bytes66
Direct MappedComputer Science 61C Spring 2022Computer Science 61C Spring 2020TagMcMahon and WeaverFull AddressIndexValid DirtyByteOffsetTagDataKolb and Weaver111001000100xFE 10 02 10xFERead byte 0xFE8T 8 bits I 2 bits O 2 bits 3 00b 1111 1110 1000T 0xFEI 0x2Cache Miss bring in entire lineO 0x04 Bytes67
Direct MappedComputer Science 61C Spring 2022McMahon and Weaver If we had used a fully associative cache, the previous accesswould have been a hit!Computer Science 61C Spring 2020Kolb and Weaver Direct Mapped leads to more con icts than fully associative Compromise: Set Associativefl68
Computer Science 61C Spring 2022McMahon and WeaverSet Associative Caches69
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and Weaver The data can only be stored at one index, but there are multiple slots to store it inComputer Science 61C Spring 2020Kolb and WeaverValid Dirty LRUFull AddressTagData111001000TagIndexByteOffset14 Bytes70
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and Weaver The data can only be stored at one index, but there are multiple slots to store it inFull Address: ex: 12 bitsComputer Science 61C Spring 202011Kolb and Weaver3Tag2Index10Valid Dirty LRUTagData11100100Byte 0Offset# byte offset bits log2(line size) log2(4) 2# index bits log2(# sets) log2(2) 11# tag bits # address bits - # index bits - # offset bits 12 - 1 - 2 94 Bytes71
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexRead Byte 0x8E2Valid Dirty LRUByteOffset010 TagDataKolb and Weaver11100100 0 0 0 4 Bytes72
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexValid Dirty LRUByteOffsetRead Byte 0x8E2T 9 bitsI 1 bitO 2 bits0110TagDataKolb and Weaver111001000x11C 10 0 0 0b 1000 1110 0010T 0x11CI 0x0O 0x2Cache Miss bring in entire line4 Bytes73
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexValid Dirty LRUByteOffset0Read Byte 0x8E8110TagDataKolb and Weaver111001000x11C 10 0 0 4 Bytes74
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagValid Dirty LRUByte 0OffsetIndexRead Byte 0x8E8T 9 bits I 1 bitO 2 bits0b 1000 1110 1000T 0x11DI 0x0O 0x01TagDataKolb and Weaver111001000x11C 10100x11D 0 0 0 Cache Miss bring in entire line4 Bytes75
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexValid Dirty LRUByte 0OffsetRead Byte 0x8E91TagDataKolb and Weaver111001000x11C 10100x11D 0 0 0 4 Bytes76
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagValid Dirty LRUByte 0OffsetIndexRead Byte 0x8E9T 9 bits I 1 bitO 2 bits0b 1000 1110 1001T 0x11DI 0x0O 0x11TagDataKolb and Weaver111001000x11C 10100x11D 0 0 Cache Hit!0 4 Bytes77
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexValid Dirty LRUByte 0OffsetRead Byte 0xDF71TagDataKolb and Weaver111001000x11C 10100x11D 0 0 0 4 Bytes78
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagValid Dirty LRUByte 0OffsetIndexRead Byte 0xDF7T 9 bits I 1 bitO 2 bits0b 1101 1111 0111T 0x1BEI 0x1O 0x31TagDataKolb and Weaver111001000x11C 10100x11D 100x1BE 0 01Cache Miss bring in entire line4 Bytes79
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagIndexValid Dirty LRUByte 0OffsetRead Byte 0xAB81TagDataKolb and Weaver111001000x11C 10100x11D 100x1BE 0 014 Bytes80
Set Associative (write-back)Computer Science 61C Spring 2022McMahon and WeaverFull AddressComputer Science 61C Spring 2020TagValid Dirty LRUByte 0OffsetIndexRead Byte 0xAB8T 9 bits I 1 bitO 2 bits0b 1010 1011 1000T 0x157I 0x0O 0x01TagDataKolb and Weaver111001000x157 10100x11D 100x1BE 0 11Cache Miss bring in entire line4 Bytes81
Next LectureComputer Science 61C Spring 2022 Cache PerformanceComputer Science 61C Spring 2020McMahon and WeaverKolb and Weaver Multilevel Caches82
Computer Science 61C Spring 2022 McMahon and Weaver Locality Temporal locality The data we access is saved in the cache for potential future use Spatial locality We bring in a chunk of data at a time because there is a good chance that we will want to access other data within the chunk 27
