Advanced Computer Architecture CSE 8383Contents (Memory)Memory HierarchySequence of eventsCache MemoryPlacement PoliciesSlide 7Direct MappingAddress FormatExampleExample (cont.)Fully AssociativeSlide 13Slide 14Slide 15Set AssociativeSlide 17Slide 18Slide 19ComparisonGroup ExerciseGroup Exercise (Cont.)Replacement TechniquesComputer Science and EngineeringCopyright by Hesham El-RewiniAdvanced Computer Advanced Computer ArchitectureArchitectureCSE 8383CSE 8383January 19 2006January 19 2006Session 2Session 2Computer Science and EngineeringCopyright by Hesham El-RewiniContents (Memory)Memory HierarchyCache MemoryPlacement PoliciesDirect MappingFully AssociativeSet AssociativeReplacement PoliciesComputer Science and EngineeringCopyright by Hesham El-RewiniMemory HierarchyCPU RegistersCacheMain MemorySecondary StorageLatencyBandwidthSpeedCost per bitComputer Science and EngineeringCopyright by Hesham El-RewiniSequence of events1. Processor makes a request for X2. X is sought in the cache 3. If it exists  hit (hit ratio h)4. Otherwise  miss (miss ratio m = 1-h)5. If miss  X is sought in main memory6. It can be generalized to more levelsComputer Science and EngineeringCopyright by Hesham El-RewiniCache MemoryThe idea is to keep the information expected to be used more frequently in the cache.Locality of ReferenceTemporal LocalitySpatial LocalityPlacement PoliciesReplacement PoliciesComputer Science and EngineeringCopyright by Hesham El-RewiniPlacement PoliciesHow to Map memory blocks (lines) to Cache block frames (line frames)Blocks(lines)Block Frames(Line Frames)MemoryCacheComputer Science and EngineeringCopyright by Hesham El-RewiniPlacement PoliciesDirect MappingFully AssociativeSet AssociativeComputer Science and EngineeringCopyright by Hesham El-RewiniDirect MappingSimplestA memory block is mapped to a fixed cache block frame (many to one mapping)J = I mod NJ  Cache block frame numberI  Memory block numberN  number of cache block framesComputer Science and EngineeringCopyright by Hesham El-RewiniAddress FormatMemory  M blocksBlock size  B wordsCache  N blocksAddress size log2 (M * B)Tag Block frame Wordlog2 Blog2 NRemaining bits log2 M/NComputer Science and EngineeringCopyright by Hesham El-RewiniExampleMemory  4K blocksBlock size  16 wordsAddress size log2 (4K * 16) = 16Cache  128 blocksTag Block frame Word475Computer Science and EngineeringCopyright by Hesham El-RewiniExample (cont.)1281292550112739684095012127MemoryTag cache0 1 315 bitsComputer Science and EngineeringCopyright by Hesham El-RewiniFully AssociativeMost flexibleA memory block is mapped to any available cache block frame(many to many mapping)Associative SearchComputer Science and EngineeringCopyright by Hesham El-RewiniAddress FormatMemory  M blocksBlock size  B wordsCache  N blocksAddress size log2 (M * B)Tag Wordlog2 BRemaining bits log2 MComputer Science and EngineeringCopyright by Hesham El-RewiniExampleMemory  4K blocksBlock size  16 wordsAddress size log2 (4K * 16) = 16Cache  128 blocksTag Word412Computer Science and EngineeringCopyright by Hesham El-RewiniExample (cont.)0140944095012127MemoryTag cache12 bitsComputer Science and EngineeringCopyright by Hesham El-RewiniSet AssociativeCompromise between the other twoCache  number of setsSet  number of blocksA memory block is mapped to any available cache block frame within a specific setAssociative Search within a setComputer Science and EngineeringCopyright by Hesham El-RewiniAddress FormatMemory  M blocksBlock size  B wordsCache  N blocksNumber of sets S  N/num of blocks per setAddress size log2 (M * B)log2 BTag Set Wordlog2 SRemaining bitslog2 M/SComputer Science and EngineeringCopyright by Hesham El-RewiniExampleMemory  4K blocksBlock size  16 wordsAddress size log2 (4K * 16) = 16Cache  128 blocksNum of blocks per set = 4Number of sets = 324Tag Set Word57Computer Science and EngineeringCopyright by Hesham El-RewiniExample (cont.)0123126127Set 0Tagcache7 bitsSet 313233630131 4095Memory0 1127124125Computer Science and EngineeringCopyright by Hesham El-RewiniComparisonSimplicityAssociative SearchCache UtilizationReplacementComputer Science and EngineeringCopyright by Hesham El-RewiniGroup ExerciseThe instruction set for your architecture has 40-bit addresses, with each addressable item being a byte. You elect to design a four-way set-associative cache with each of the four blocks in a set containing 64 bytes. Assume that you have 256 sets in the cache. Show the Format of the addressComputer Science and EngineeringCopyright by Hesham El-RewiniGroup Exercise (Cont.)Consider the following sequence of addresses. (All are hex numbers)0E1B01AA05 0E1B01AA07 0E1B2FE305 0E1B4FFD8F 0E1B01AA0EIn your cache, what will be the tags in the sets(s) that contain these references at the end of the sequence? Assume that the cache is initially flushed (empty).Computer Science and EngineeringCopyright by Hesham El-RewiniReplacement