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.)2OutlineOutlineCache OrganizationCache OrganizationCache Read/Write PoliciesCache Read/Write PoliciesBlock replacement policiesBlock replacement policiesWrite-back vs. write-through cachesWrite-back vs. write-through cachesWrite buffersWrite buffersCache PerformanceCache PerformanceMeans 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 HierarchyHierarchyWhere 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 BlocksBlocksFor a 1024 (2For a 1024 (21010) byte cache with 32-byte blocks) byte cache with 32-byte blocksThe uppermost 22 = (32 - 10) address bits are the tagThe uppermost 22 = (32 - 10) address bits are the tagThe 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 TradeoffIn 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 penaltyTakes longer time to fill up the blockTakes longer time to fill up the blockIf 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 upToo few cache blocksToo few cache blocksAverage Access TimeAverage Access TimeHit Time + Miss Penalty x Miss RateHit Time + Miss Penalty x Miss Rate13 Sources of Cache MissesSources of Cache MissesCompulsory (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 itConflict/Collision/InterferenceConflict/Collision/InterferenceMultiple mem locations mapped to the same cache Multiple mem locations mapped to the same cache locationlocationSolution 1: Increase cache sizeSolution 1: Increase cache sizeSolution 2: Increase associativitySolution 2: Increase associativityCapacityCapacityCache cannot contain all blocks access by the programCache cannot contain all blocks access by the programSolution 1: Increase cache sizeSolution 1: Increase cache sizeSolution 2: Restructure programSolution 2: Restructure
View Full Document