Virtual Memory 1!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)P)&)H)Chapter)5.4)(up)to)TLBs))2)Announcements!HW3)available)due)today)Tuesday))• HW3)has)been)updated.)Use)updated)version.)• Work)with)alone)• Be)responsible)with)new)knowledge)PA3)available)later)today)or)by)tomorrow)• Work)in)pairs)))Next)five)weeks)• One)homeworks)and)two)projects)• Prelim2)will)be)Thursday,)April)28th))• PA4)will)be)final)project)(no)final)exam)))3)Goals for Today!Title)says)Virtual)Memory,)but)really)finish)caches:)writes))Introduce)idea)of)Virtual)Memory)))))4)Cache Design!Need)to)determine)parameters:)• Cache)size)• Block)size)(aka)line)size))• Number)of)ways)of)setVassociaWvity)(1,)N,)∞))• EvicWon)policy))• Number)of)levels)of)caching,)parameters)for)each)• Separate)IVcache)from)DVcache,)or)Unified)cache)• Prefetching)policies)/)instrucWons)• Write)policy)5)A Real Example!>"dmidecode")t"cache"Cache"Information"""""""""Configuration:"Enabled,"Not"Socketed,"Level"1"""""""""Operational"Mode:"Write"Back"""""""""Installed"Size:"128"KB"""""""""Error"Correction"Type:"None"Cache"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:1"cache/index0/type:Data"cache/index0/ways_of_associativity:8"cache/index0/number_of_sets:64"cache/index0/coherency_line_size:64"cache/index0/size:32K"cache/index1/level:1"cache/index1/type:Instruction"cache/index1/ways_of_associativity:8"cache/index1/number_of_sets:64"cache/index1/coherency_line_size:64"cache/index1/size:32K"cache/index2/level:2"cache/index2/type:Unified"cache/index2/shared_cpu_list:0)1"cache/index2/ways_of_associativity:24"cache/index2/number_of_sets:4096"cache/index2/coherency_line_size:64"cache/index2/size:6144K"DualVcore)3.16GHz)Intel))(purchased)in)2009))6)A Real Example!Dual)32K)L1)InstrucWon)caches)• 8Vway)set)associaWve)• 64)sets)• 64)byte)line)size)Dual)32K)L1)Data)caches)• Same)as)above)Single)6M)L2)Unified)cache)• 24Vway)set)associaWve)(!!!))• 4096)sets)• 64)byte)line)size)4GB)Main)memory)1TB)Disk))DualVcore)3.16GHz)Intel))(purchased)in)2009))7)Basic Cache Organization!Q:)How)to)decide)block)size?)A:)Try)it)and)see)But:)depends)on)cache)size,)workload,))associaWvity,)…))Experimental)approach!)8)Experimental Results!9)Tradeoffs!For)a)given)total)cache)size,)larger)block)sizes)mean….))• fewer)lines)• so)fewer)tags)(and)smaller)tags)for)associaWve)caches))• so)less)overhead)• and)fewer)cold)misses)(withinVblock)“prefetching”))But)also…)• fewer)blocks)available)(for)scaiered)accesses!))• so)more)conflicts)• and)larger)miss)penalty)(Wme)to)fetch)block))10)WriWng)with)Caches)11)Cached Write Policies!Q:)How)to)write)data?))CPU))Cache)SRAM))Memory)DRAM))addr)data)If)data)is)already)in)the)cache…)NoVWrite)• writes)invalidate)the)cache)and)go)directly)to)memory)WriteVThrough)• writes)go)to)main)memory)and)cache)WriteVBack)• CPU)writes)only)to)cache)• cache)writes)to)main)memory)later)(when)block)is)evicted))12)Write Allocation Policies!Q:)How)to)write)data?))CPU))Cache)SRAM))Memory)DRAM))addr)data)If)data)is)not)in)the)cache…)WriteVAllocate)• allocate)a)cache)line)for)new)data)(and)maybe)writeVthrough))NoVWriteVAllocate)• ignore)cache,)just)go)to)main)memory)13)Memory)Direct)Mapped)Cache)+)WriteVthrough)+)WriteVallocate)Processor)A Simple Direct Mapped Cache!lb))$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)$4)Using)byte&addresses&in)this)example!)Ad d r)Bus )=)5)bi ts)0) 101)1) 103)2) 107)3) 109)4) 113)5) 127)6) 131)7) 137)8) 139)9) 149)10) 151)11) 157)12) 163)13) 167)14) 173)15) 179)16) 181)Hits:)))))))))))))Misses:)0) 101&1) 103&2) 107&3) 109&4) 113&5) 127&6) 131&7) 137&8) 139&9) 149&10) 151&11) 157&12) 163&13) 167&14) 173&15) 179&16) 181&14)How Many Memory References?!WriteVthrough)performance))Each)miss)(read)or)write))reads)a)block)from)mem)• 5)misses))10)mem)reads)Each)store)writes)an)item)to)mem)• 4)mem)writes)EvicWons)don’t)need)to)write)to)mem)• no)need)for)dirty)bit)15)Memory)Direct)Mapped)Cache)+)WriteVback)+)WriteVallocate)Processor)A Simple Direct Mapped Cache!V) )))tag)))) ))))data)$1)$2)$3)$4)Using)byte&addresses&in)this)example!)Ad d r)Bus )=)5)bi ts)0) 101)1) 103)2) 107)3) 109)4) 113)5) 127)6) 131)7) 137)8) 139)9) 149)10) 151)11) 157)12) 163)13) 167)14) 173)15) 179)16) 181)0) 101&1) 103&2) 107&3) 109&4) 113&5) 127&6) 131&7) 137&8) 139&9) 149&10) 151&11) 157&12) 163&13) 167&14) 173&15) 179&16) 181&Hits:)))))))))))))Misses:)D)lb))$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&]&16)How Many Memory References?!WriteVback)performance))Each)miss)(read)or)write))reads)a)block)from)mem)• 5)misses))10)mem)reads)Some)evicWons)write)a)block)to)mem)• 1)dirty)evicWon))2)mem)writes)• (+)2)dirty)evicWons)later))+4)mem)writes))• need)a)dirty)bit)17)Write-Back Meta-Data!V)=)1)means)the)line)has)valid)data)D)=)1)means)the)bytes)are)newer)than)main)memory)When)allocaWng)line:)• Set)V)=)1,)D)=)0,)fill)in)Tag)and)Data)When)wriWng)li n e:)• Set)D)=)1)When)evicWng)li n e:)• If)D)=)0:)just)set)V)=)0)• If)D)=)1:)writeVback)Data,)then)set)D)=)0,)V)=)0)V) D) Tag) Byte)1) Byte)2) …)Byte)N)18)Performance: An Example!Performance:)WriteVback)versus)WriteVthrough)Assume:)large)associaWve)cache,)16Vbyte)lines)for"(i=1;"i<n;"i++)"" "A[0]"+="A[i];""""for"(i=0;"i<n;"i++)"" "B[i]"="A[i]"19)Performance Tradeoffs!Q:)Hit)Wme:)writeVthrough)vs.)writeVback?)A:)WriteVthrough)slower)on)writes.)Q:)Miss)penalty:)writeVthrough)vs.)writeVback?)A:)WriteVback)slower)on)evicWons.))20)Write Buffering!Q:)Writes)to)main)memory)are)slow!)A:)Use)a)writeVback)buffer)• A)small)queue)holding)dirty)lines)• Add)to)end)upon)evicWon)• Remove)from)front)upon)compleWon)Q:)What)does)it)help?)A:)short)bursts)of)writes)(but)not)sustained)writes))A:)fast)evicWon)reduces)miss)penalty)21)Write-through vs. Write-back!WriteVthrough)is)slower)•
View Full Document