Slide 1AnnouncementsGoals for TodayCache DesignA Real ExampleA Real ExampleBasic Cache OrganizationExperimental ResultsTradeoffsSlide 10Cached Write PoliciesWrite Allocation PoliciesA Simple Direct Mapped CacheHow Many Memory References?A Simple Direct Mapped CacheHow Many Memory References?Write-Back Meta-DataPerformance: An ExamplePerformance TradeoffsWrite BufferingWrite-through vs. Write-backCache-coherencySlide 23Cache Conscious ProgrammingCache Conscious ProgrammingSummarySummaryVirtual MemoryProcessor & MemoryMultiple ProcessesMultiple ProcessesSolution? Multiple processes/processorsSlide 33Virtual MemoryAddress SpacesAddress SpaceVirtual Memory AdvantagesSlide 38Address TranslationAddress TranslationSimple PageTableSummaryPage Size ExampleInvalid PagesBeyond Flat Page TablesPage PermissionsAliasingSlide 48PagingPagingSlide 51sbrkContext SwitchShared MemoryMultiplexingPaging Assumption 1Reasons for ThrashingThrashingPaging Assumption 2More ThrashingPreventing ThrashingVirtual Memory 1Hakim WeatherspoonCS 3410, Spring 2011Computer ScienceCornell UniversityP & H Chapter 5.4 (up to TLBs)2AnnouncementsHW3 available due today Tuesday •HW3 has been updated. Use updated version.•Work with alone•Be responsible with new knowledgePA3 available later today or by tomorrow•Work in pairsNext five weeks•One homeworks and two projects•Prelim2 will be Thursday, April 28th •PA4 will be final project (no final exam)3Goals for TodayTitle says Virtual Memory, but really finish caches: writesIntroduce idea of Virtual Memory4Cache DesignNeed to determine parameters:•Cache size•Block size (aka line size)•Number of ways of set-associativity (1, N, )•Eviction policy •Number of levels of caching, parameters for each•Separate I-cache from D-cache, or Unified cache•Prefetching policies / instructions•Write policy5A Real Example> dmidecode -t cacheCache Information Configuration: Enabled, Not Socketed, Level 1 Operational Mode: Write Back Installed Size: 128 KB Error Correction Type: NoneCache Information Configuration: Enabled, Not Socketed, Level 2 Operational Mode: Varies With Memory Address Installed Size: 6144 KB Error Correction Type: Single-bit ECC> cd /sys/devices/system/cpu/cpu0; grep cache/*/*cache/index0/level:1cache/index0/type:Datacache/index0/ways_of_associativity:8cache/index0/number_of_sets:64cache/index0/coherency_line_size:64cache/index0/size:32Kcache/index1/level:1cache/index1/type:Instructioncache/index1/ways_of_associativity:8cache/index1/number_of_sets:64cache/index1/coherency_line_size:64cache/index1/size:32Kcache/index2/level:2cache/index2/type:Unifiedcache/index2/shared_cpu_list:0-1cache/index2/ways_of_associativity:24cache/index2/number_of_sets:4096cache/index2/coherency_line_size:64cache/index2/size:6144KDual-core 3.16GHz Intel (purchased in 2009)6A Real ExampleDual 32K L1 Instruction caches•8-way set associative•64 sets•64 byte line sizeDual 32K L1 Data caches•Same as aboveSingle 6M L2 Unified cache•24-way set associative (!!!)•4096 sets•64 byte line size4GB Main memory1TB DiskDual-core 3.16GHz Intel (purchased in 2009)7Basic Cache OrganizationQ: How to decide block size?A: Try it and seeBut: depends on cache size, workload, associativity, …Experimental approach!8Experimental Results9TradeoffsFor a given total cache size,larger block sizes mean…. •fewer lines•so fewer tags (and smaller tags for associative caches)•so less overhead•and fewer cold misses (within-block “prefetching”)But also…•fewer blocks available (for scattered accesses!)•so more conflicts•and larger miss penalty (time to fetch block)10Writing with Caches11Cached Write PoliciesQ: How to write data?CPUCacheSRAMMemoryDRAMaddrdataIf data is already in the cache…No-Write•writes invalidate the cache and go directly to memoryWrite-Through•writes go to main memory and cacheWrite-Back•CPU writes only to cache•cache writes to main memory later (when block is evicted)12Write Allocation PoliciesQ: How to write data?CPUCacheSRAMMemoryDRAMaddrdataIf data is not in the cache…Write-Allocate•allocate a cache line for new data (and maybe write-through)No-Write-Allocate•ignore cache, just go to main memory13MemoryDirect Mapped Cache+ Write-through+ Write-allocateProcessorA Simple Direct Mapped Cachelb $1 M[ 1 ]lb $2 M[ 7 ]sb $2 M[ 0 ]sb $1 M[ 5 ]lb $2 M[ 9 ]sb $1 M[ 5 ]sb $1 M[ 0 ]V tag data$1$2$3$4Using byte addresses in this example! Addr Bus = 5 bits0 1011 1032 1073 1094 1135 1276 1317 1378 1399 14910 15111 15712 16313 16714 17315 17916 181Hits: Misses:0 1011 1032 1073 1094 1135 1276 1317 1378 1399 14910 15111 15712 16313 16714 17315 17916 18114How Many Memory References?Write-through performanceEach miss (read or write) reads a block from mem•5 misses 10 mem readsEach store writes an item to mem•4 mem writesEvictions don’t need to write to mem•no need for dirty bit15MemoryDirect Mapped Cache+ Write-back+ Write-allocateProcessorA Simple Direct Mapped CacheV tag data$1$2$3$4Using byte addresses in this example! Addr Bus = 5 bits0 1011 1032 1073 1094 1135 1276 1317 1378 1399 14910 15111 15712 16313 16714 17315 17916 1810 1011 1032 1073 1094 1135 1276 1317 1378 1399 14910 15111 15712 16313 16714 17315 17916 181Hits: Misses:Dlb $1 M[ 1 ]lb $2 M[ 7 ]sb $2 M[ 0 ]sb $1 M[ 5 ]lb $2 M[ 9 ]sb $1 M[ 5 ]sb $1 M[ 0 ]16How Many Memory References?Write-back performanceEach miss (read or write) reads a block from mem•5 misses 10 mem readsSome evictions write a block to mem•1 dirty eviction 2 mem writes•(+ 2 dirty evictions later +4 mem writes)•need a dirty bit17Write-Back Meta-DataV = 1 means the line has valid dataD = 1 means the bytes are newer than main memoryWhen allocating line:•Set V = 1, D = 0, fill in Tag and DataWhen writing line:•Set D = 1When evicting line:•If D = 0: just set V = 0•If D = 1: write-back Data, then set D = 0, V = 0V D Tag Byte 1 Byte 2 … Byte N18Performance: An ExamplePerformance: Write-back versus Write-throughAssume: large associative cache, 16-byte linesfor (i=1; i<n; i++)A[0] += A[i];for (i=0; i<n; i++)B[i] = A[i]19Performance TradeoffsQ: Hit time: write-through vs. write-back?A: Write-through slower on writes.Q: Miss penalty: write-through vs. write-back?A: Write-back slower on evictions.20Write BufferingQ: Writes to
View Full Document
Unlocking...