COMP 206: Computer Architecture and ImplementationOutlineReview: 4 Questions for Mem HierarchyReview: Cache ShapesExample 1: 1KB, Direct-Mapped, 32B BlocksExample 1a: Cache Miss; Empty BlockExample 1b: … Read in DataExample 1c: Cache HitExample 1d: Cache Miss; Incorrect BlockExample 1e: … Replace BlockCache PerformanceBlock Size TradeoffSources of Cache MissesThe 3C Model of Cache MissesSources of Cache Misses3Cs Absolute Miss Rate3Cs Relative Miss RateHow to Improve Cache Performance1. Reduce Misses via Larger Block Size2. Reduce Misses via Higher AssociativityExample: Ave Mem Access Time vs. Miss Rate3. Reduce Conflict Misses via Victim Cache4. Reduce Conflict Misses via Pseudo-Assoc.5. Reduce Misses by Hardware Prefetching6. Reducing Misses by Software Prefetching7. Reduce Misses by Compiler Optzns.Merging Arrays ExampleLoop Interchange ExampleLoop Fusion ExampleBlocking ExampleBlocking Example (contd.)Slide 32Slide 331COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghWed., Nov. 5, 2002Wed., Nov. 5, 2002Topic: Topic: Caches (contd.)Caches (contd.)2OutlineOutlineCache OrganizationCache OrganizationCache Read/Write PoliciesCache Read/Write PoliciesBlock replacement policiesBlock replacement policiesWrite-back vs. write-through cachesWrite-back vs. write-through cachesWrite buffersWrite buffersCache PerformanceCache PerformanceMeans of improving performanceMeans of improving performanceReading: HP3 Sections 5.3-5.7Reading: HP3 Sections 5.3-5.73Review: 4 Questions for Mem Review: 4 Questions for Mem HierarchyHierarchyWhere can a block be placed in the upper Where can a block be placed in the upper level? level? (Block placement)(Block placement)How is a block found if it is in the upper level?How is a block found if it is in the upper level?(Block identification)(Block identification)Which block should be replaced on a miss?Which block should be replaced on a miss?(Block replacement)(Block replacement)What happens on a write?What happens on a write?(Write strategy)(Write strategy)4Review: Cache ShapesReview: Cache ShapesDirect-mapped(A = 1, S = 16)2-way set-associative(A = 2, S = 8)4-way set-associative(A = 4, S = 4)8-way set-associative(A = 8, S = 2)Fully associative(A = 16, S = 1)50431 9Cache Index:Cache Tag Example: 0x50Ex: 0x010x50Stored as partof the cache “state”Valid Bit:0123: Cache DataByte 031Byte 1Byte 31:Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte SelectEx: 0x00Byte SelectExample 1: 1KB, Direct-Mapped, 32B Example 1: 1KB, Direct-Mapped, 32B BlocksBlocksFor a 1024 (2For a 1024 (21010) byte cache with 32-byte blocks) byte cache with 32-byte blocksThe uppermost 22 = (32 - 10) address bits are the tagThe uppermost 22 = (32 - 10) address bits are the tagThe lowest 5 address bits are the Byte Select (Block Size = The lowest 5 address bits are the Byte Select (Block Size = 2255))The next 5 address bits (bit5 - bit9) are the Cache IndexThe next 5 address bits (bit5 - bit9) are the Cache Index60431 9 Cache Index:Cache Tag0x0002fe 0x000x000050Valid Bit:0123: Cache DataByte 031Byte 1Byte 31:Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte Select 0x00Byte Select=Cache Miss1010xxxxxxx0x004440Example 1a: Cache Miss; Empty Example 1a: Cache Miss; Empty BlockBlock70431 9 Cache Index:Cache Tag0x0002fe 0x000x000050Valid Bit:0123: Cache Data31Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte Select 0x00Byte Select=1110x0002fe0x004440New Block of dataExample 1b: … Read in DataExample 1b: … Read in Data80431 9 Cache Index:Cache Tag0x000050 0x010x000050Valid Bit:0123: Cache DataByte 031Byte 1Byte 31:Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte Select 0x08Byte Select=Cache Hit1110x0002fe0x004440Example 1c: Cache HitExample 1c: Cache Hit90431 9 Cache Index:Cache Tag0x002450 0x020x000050Valid Bit:0123: Cache DataByte 031Byte 1Byte 31:Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte Select 0x04Byte Select=Cache Miss1110x0002fe0x004440Example 1d: Cache Miss; Incorrect Example 1d: Cache Miss; Incorrect BlockBlock100431 9 Cache Index:Cache Tag0x002450 0x020x000050Valid Bit:0123: Cache DataByte 031Byte 1Byte 31:Byte 32Byte 33Byte 63:Byte 992Byte 1023: Cache TagByte Select 0x04Byte Select=1110x0002fe0x002450 New Block of dataExample 1e: … Replace BlockExample 1e: … Replace Block11Cache PerformanceCache Performancepenalty Miss rate Miss Hit time timeaccessmemory Average timeCycle penalty Missref MMMissesnInstructiorefs MM CPI PipelineIC timeCPU cache without trafficBuscache with trafficBus ratio trafficBus 12MissPenaltyBlock SizeMissRateExploits spatial localityFewer blocks: compromisestemporal localityBlock SizeIncreased Miss Penalty& Miss RateAverageAccessTimeBlock SizeBlock Size TradeoffBlock Size TradeoffIn general, larger block size take advantage of spatial In general, larger block size take advantage of spatial locality, locality, BUT:BUT:Larger block size means larger miss penaltyLarger block size means larger miss penaltyTakes longer time to fill up the blockTakes longer time to fill up the blockIf block size is too big relative to cache size, miss rate will go upIf block size is too big relative to cache size, miss rate will go upToo few cache blocksToo few cache blocksAverage Access TimeAverage Access TimeHit Time + Miss Penalty x Miss RateHit Time + Miss Penalty x Miss Rate13 Sources of Cache MissesSources of Cache MissesCompulsory (cold start or process migration, first Compulsory (cold start or process migration, first reference): first access to a blockreference): first access to a block““Cold” fact of life: not a whole lot you can do about itCold” fact of life: not a whole lot you can do about itConflict/Collision/InterferenceConflict/Collision/InterferenceMultiple mem locations mapped to the same cache Multiple mem locations mapped to the same cache locationlocationSolution 1: Increase cache sizeSolution 1: Increase cache sizeSolution 2: Increase associativitySolution 2: Increase associativityCapacityCapacityCache cannot contain all blocks access by the programCache cannot contain all blocks access by the programSolution 1: Increase cache sizeSolution 1: Increase cache sizeSolution 2: Restructure programSolution 2: Restructure