Memory HierarchiesSRAM vs. DRAMTerminologyCache Design 101Cache design issuesA Simple Fully Associative Cache1st AccessSlide 82nd AccessSlide 103rd AccessSlide 124th AccessSlide 145th AccessSlide 16Block sizeWrite strategyHandling Stores (Write-Through)Write-Through (REF 1)Slide 21Write-Through (REF 2)Slide 23Write-Through (REF 3)Slide 25Write-Through (REF 4)Slide 27Write-Through (REF 5)Slide 29How Many Memory References?Write-Through vs. Write-BackHandling Stores (Write-Back)Write-Back (REF 1)Slide 34Write-Back (REF 2)Slide 36Write-Back (REF 3)Slide 38Write-Back (REF 4)Slide 40Write-Back (REF 5)Slide 42Slide 43How many memory references?Direct-Mapped CacheTwo-Way Set Associative CacheSources of cache missesProgramming for cachesEffects of Varying Cache ParametersSlide 50Slide 51Slide 52Other Cache Design DecisionsSlide 54PrefetchingCalculating the Effects of LatencySlide 57Copyright Gary S. Tyson 2003Copyright Sally A. McKee 2005Memory Memory HierarchiesHierarchiesAdapted from slides byAdapted from slides bySally McKeeSally McKeeCornell UniversityCornell UniversityCopyright Gary S. Tyson 2003, Copyright Sally A. McKee 20052SRAM vs. DRAMSRAM vs. DRAMSRAM (static random access memory)SRAM (static random access memory)Faster than DRAMFaster than DRAMEach storage cell is larger, so smaller capacity Each storage cell is larger, so smaller capacity for same areafor same area2-10ns access time2-10ns access timeDRAM (dynamic random access memory)DRAM (dynamic random access memory)Each storage cell tiny (capacitance on wire)Each storage cell tiny (capacitance on wire)Can get 2Gb chips todayCan get 2Gb chips today50-70ns access time50-70ns access timeLeaky–need to periodically refresh dataLeaky–need to periodically refresh dataWhat happens on a read?What happens on a read?CPU clock rates ~0.2ns-2ns (5GHz-500MHz)CPU clock rates ~0.2ns-2ns (5GHz-500MHz)Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 20053TerminologyTerminologyTemporal locality:Temporal locality:If memory location X is accessed, then it is more likely If memory location X is accessed, then it is more likely to be re-accessed in the near future than some random to be re-accessed in the near future than some random location Ylocation YCaches exploit temporal locality by placing a memory Caches exploit temporal locality by placing a memory element that has been referenced into the cacheelement that has been referenced into the cacheSpatial locality:Spatial locality:If memory location X is accessed, then locations near X If memory location X is accessed, then locations near X are more likely to be accessed in the near future than are more likely to be accessed in the near future than some random location Ysome random location YCaches exploit spatial locality by allocating a Caches exploit spatial locality by allocating a cache linecache line of data (including data near the referenced location)of data (including data near the referenced location)Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 20054Memory pyramidDisk (Many GB)Memory (128MB – few GB)L2 Cache (½-32MB)L1 Cache(several KB)Reg100s bytesCache Design 101Cache Design 101part of pipeline1-3 cycle access6-15 cycle access50-300 cycle accessL3 becoming more common(sometimes VERYLARGE)These are rough numbers: mileage may vary for These are rough numbers: mileage may vary for latest/greatestlatest/greatestCaches USUALLY made of SRAMCaches USUALLY made of SRAMMillions cycle access!Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 20055Cache design issuesCache design issuesBlock placementBlock placement: where can block be placed in : where can block be placed in higher memory level?higher memory level?Fully-associative: anywhereFully-associative: anywhereDirect-mapped: exactly one placeDirect-mapped: exactly one placeSet-associative: some small number of placesSet-associative: some small number of placesBlock identificationBlock identification: how does processor find the : how does processor find the block if it is there at higher memory level?block if it is there at higher memory level?Block replacementBlock replacement: which block should be replaced : which block should be replaced from higher level to make room for a new blockfrom higher level to make room for a new blockWrite strategyWrite strategy: are lower levels updated when : are lower levels updated when block in higher level is written?block in higher level is written?Write-through: yesWrite-through: yesWrite-back: no, update lower level only when block is Write-back: no, update lower level only when block is evicted from higher levelevicted from higher levelCopyright Gary S. Tyson 2003, Copyright Sally A. McKee 20056A Simple Fully A Simple Fully Associative CacheAssociative Cache1101301501601802002202400123456789101112131415Ld R1 M[ 1 ]Ld R2 M[ 5 ]Ld R3 M[ 1 ]Ld R3 M[ 4 ]Ld R2 M[ 0 ]CacheProcessortag dataR0R1R2R3Memory1001201401701902102302502 cache lines3 bit tag field2 byte blockVVHow many address bits?Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 2005711stst Access Access1101301501601802002202400123456789101112131415Ld R1 M[ 1 ]Ld R2 M[ 5 ]Ld R3 M[ 1 ]Ld R3 M[ 4 ]Ld R2 M[ 0 ]CacheProcessortag dataR0R1R2R3Memory10012014017019021023025000Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 2005811stst Access Access1101301501601802002202400123456789101112131415Ld R1 M[ 1 ]Ld R2 M[ 5 ]Ld R3 M[ 1 ]Ld R3 M[ 4 ]Ld R2 M[ 0 ]CacheProcessor0tag dataR0R1R2R3Memory100120140170190210230250100110110Misses: 1Hits: 0lruAddr: 0001block offset10Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 2005922ndnd Access Access1101301501601802002202400123456789101112131415Ld R1 M[ 1 ]Ld R2 M[ 5 ]Ld R3 M[ 1 ]Ld R3 M[ 4 ]Ld R2 M[ 0 ]CacheProcessor0tag dataR0R1R2R3Memory100120140170190210230250100110110Misses: 1Hits: 0lru10Copyright Gary S. Tyson 2003, Copyright Sally A. McKee 20051022ndnd Access Access1101301501601802002202400123456789101112131415Ld R1 M[ 1 ]Ld R2 M[ 5 ]Ld R3 M[ 1 ]Ld R3 M[ 4 ]Ld R2 M[ 0 ]CacheProcessor0tag dataR0R1R2R3Memory2100120140170190210230250100110110Misses: 2Hits: 0lru150140150Addr: 0101block offset11Copyright Gary S. Tyson 2003,
View Full Document
Unlocking...