Caches!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)See)P&H)5.1,)5.2)(except)writes))2)Announcements!HW3)available)due)next)Tuesday))• Work)with)alone)partner)• Be)responsible)with)new)knowledge)Use)your)resou rces )• FAQ,)class)notes,)book,)SecLons,)office)hours,)newsgroup,)CSUGLab)Next)six)weeks)• Two)homeworks)and)two)projects)• Op'onal)prelim1)tomorrow,)Wednesday,)in)Philips)101)• Prelim2)will)be)Thursday,)April)28th))• PA4)will)be)final)project)(no)final)exam)))3)Goals for Today: caches!Caches)vs)memory)vs)terLary)storage)• Tradeoffs:)big)&)slow)vs)small)&)fast)– Best)of)both)worlds)• working)set:)90/10)rule)• How)to)predict)future:)temporal)&)spacial)locality))Cache)organizaLon,)parameters)and)tradeoffs)associaLvity,)line)size,)hit)cost,)miss)penalty,)hit)rate)• Fully)AssociaLve))higher)hit)cost,)higher)hit)rate)• Larger)block)size))lower)hit)cost,)higher)miss)penalty)))))4)Performance!CPU)clock)rates)~0.2ns)–)2ns)(5GHz^500MHz))Technology) )Capacity )$/GB )Latency)Tape )1)TB )$.17 )100s)of)seconds)Disk )2)TB )$.03 )Millions)of)cycles)(ms))SSD)(Flash) )128)GB )$2 )Thousands)of)cycles)(us))DRAM) )8)GB )$10 )))))))))))))))))))))))))))(10s)of)ns))SRAM)off^chip )8)MB )$4000))5^15)cycles)(few)ns))SRAM)on^chip )256)KB )??? )1^3)cycles)(ns)))Others:)eDRAM)aka)1^T)SRAM,)FeRAM,)CD,)DVD,)…)Q:)Can)we)create)illusion)of)cheap)+)large)+)fast?)50^300)cycles)5)Memory)Pyramid)Disk)(Many)GB)–)few)TB))Memory)(128MB)–)few)GB))L2)Cache))(½^32MB))RegFile)100s)bytes)Memory Pyramid!<)1)cycle)access)1^3)cycle)access)5^15)cycle)access)50^300)cycle)access)L3)becoming)more)common)(eDRAM)?))These)are)rough)numbers:)mileage)may)vary)for)latest/greatest)Caches)usually)made)of)SRAM)(or)eDRAM))L1)Cache)(several)KB))1000000+)))))cycle)access)6)Memory Hierarchy!Memory)closer)to)processor))• small)&)fast)• stores)acLve)data)Memory)farther)from)processor))• big)&)slow)• stores)inacLve)data)))7)Active vs Inactive Data!AssumpLon:)Most)data)is)not)acLve.)Q:)How)to)decide)what)is)acLve?)A:)Some)commimee)deci des))A:)Programmer)decides))A:)Compiler)decid es))A:)OS)decides)at)run^Lme))A:)Hardware)decides)at)run^Lme)8)Insight of Caches!Q:)What)is)“acLve”)data?)+If)Mem[x])is)was)accessed)recently...)…)then)Mem[x])is)likely)to)be)accessed+soon)• Exploit)temporal)locality:)…)then)Mem[x)±+ε])is)likely)to)be)accessed)soon+• Exploit)spaLal)locality:)))9)Locality!Memory)trace)0x7c9a2b18+0x7c9a2b19+0x7c9a2b1a+0x7c9a2b1b+0x7c9a2b1c+0x7c9a2b1d+0x7c9a2b1e+0x7c9a2b1f+0x7c9a2b20+0x7c9a2b21+0x7c9a2b22+0x7c9a2b23+0x7c9a2b28+0x7c9a2b2c+0x0040030c+0x00400310+0x7c9a2b04+0x00400314+0x7c9a2b00+0x00400318+0x0040031c+...+int+n+=+4;+int+k[]+=+{+3,+14,+0,+10+};++int+fib(int+i)+{+if+(i+<=+2)+return+i;+else+return+fib(iD1)+fib(iD2);+}++int+main(int+ac,+char+**av)+{++for+(int+i+=+0;+i+<+n;+i++)+{++ +printi(fib(k[i]));++ +prints("\n");++++}+}++10)Locality!0x00000000)0x7c9a2b1f)0x00400318)11)Memory Hierarchy!Memory)closer)to)processor)is)fast)but)small)• usually)stores)subset)of)memory)farther)away)– “strictly)inclusive”)• alternaLves:)– strictly)exclusive)– mostly)inclusive)• Transfer)whole)blocks)(cache)lines):))4kb:)disk)↔)ram))256b:)ram)↔)L2))64b:)L2)↔)L1))12)Cache Lookups (Read)!Processor)tries)to)access)Mem[x])Check:)is)block)containing)Mem[x])in)the)cache?)• Yes:)cache)hit)– return)requested)data)from)cache)line)• No:)cache)miss)– read)block)from)memory)(or)lower)level)cache))– (evict)an)exisLng)cache)line)to)make)room))– place)new)block)in)cache)– return)requested)data))and)stall)the)pipeline)while)all)of)this)happens)13)Cache Organization!Cache)has)to)be)fast)and)dense)• Gain)speed)by)performing)lookups)in)parallel)– but)requires)die)real)estate)for)lookup)logic)• Reduce)lookup)logic)by)limiLng)where)in)the)cache)a)block)might)be)placed)– but)might)reduce)cache)effecLveness))Cache)Controller)CPU)14)Three common designs!A)given)data)block)can)be)placed…)• …)in)any)cache)line))Fully)AssociaLve)• …)in)exactly)one)cache)line))Direct)Mapped)• …)in)a)small)set)of)cache)lines))Set)AssociaLve)15)Direct Mapped Cache!Direct)Mapped)Cache)• Each)block)number)mapped)to)a)single)cache)line)index)• Simplest)hardware)line)0)line)1)0x000000)0x000004)0x000008)0x00000c)0x000010)0x000014)0x000018)0x00001c)0x000020)0x000024)0x000028)0x00002c)0x000030)0x000034)0x000038)0x00003c)0x000040)0x000044)0x000048)16)Direct Mapped Cache!Direct)Mapped)Cache)• Each)block)number)mapped)to)a)single)cache)line)index)• Simplest)hardware)line)0)line)1)line)2)line)3)0x000000)0x000004)0x000008)0x00000c)0x000010)0x000014)0x000018)0x00001c)0x000020)0x000024)0x000028)0x00002c)0x000030)0x000034)0x000038)0x00003c)0x000040)0x000044)0x000048)17)Tags and Offsets!Assume)sixteen)64^byte)cache)lines)0x7FFF3D4D))=)0111)1111)1111)1111)0011)1101)0100)1101))))Need)meta^data)for)each)cache)line:)• valid)bit:)is)the)cache)line)non^empty?)• tag:)which)block)is)stored)in)this)line)(if)valid))Q:)how)to)check)if)X)is)in)the)cache?)Q:)how)to)clear)a)cache)line?)18)Memory)Direct)Mapped)Cache)Processor)A Simple Direct Mapped Cache!lb))$1)←)M[)1)])lb))$2)←)M[)13)])lb))$3)←)M[)0)])lb))$3)←)M[)6)])lb))$2)←)M[)5)])lb))$2)←)M[)6)])lb))$2)←)M[)10)])lb))$2)←)M[)12)])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:)A)=)19)Direct Mapped Cache (Reading)!V) Tag) Block))Tag)Index )Offset)20)Direct Mapped Cache Size!n)bit)index,)m)bit)offset)Q:)How)big)is)cache)(data)only)?)Q:)How)much)SRAM)needed)(data)+)overhead)?))Tag)Index )Offset)21)Cache Performance!Cache)Performance)(very)simplified):)))L1)(SRAM):)512)x)64)byte)cache)lines,)direct)mapped))Data)cost:)3)cycle)per)word)access))Lookup)cost:)2)cycle)))Mem)(DRAM):)4GB))Data)cost:)50)cycle)per)word,)plus)3)cycle)per)consecuLve)word)))))))Performance)depends)on:))Access)Lme)for)hit,)miss)penalty,)hit)rate)22)Misses!Cache)misses:)classificaLon)The)line)is)being)referenced)for)the)first)Lme)•
View Full Document
Unlocking...