Caches!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)See)P&H)5.2)(writes),)5.3,)5.5)2)Announcements!HW3)available)due)next)Tuesday))• HW3)has)been)updated.)Use)updated)version.)• Work)with)alone)• Be)responsible)with)new)knowledge)Use)your)resou rces )• FAQ,)class)notes,)book,)SecJons,)office)hours,)newsgroup,)CSUGLab)Next)six)weeks)• Two)homeworks)and)two)projects)• Op'onal)prelim1)has)been)graded)• Prelim2)will)be)Thursday,)April)28th))• PA4)will)be)final)project)(no)final)exam)))3)Goals for Today: caches!Caches)vs)memory)vs)terJary)storage)• Tradeoffs:)big)&)slow)vs)small)&)fast)– Best)of)both)worlds)• working)set:)90/10)rule)• How)to)predict)future:)temporal)&)spacial)locality))Cache)organizaJon,)parameters)and)tradeoffs)associaJvity,)line)size,)hit)cost,)miss)penalty,)hit)rate)• Fully)AssociaJve))higher)hit)cost,)higher)hit)rate)• Larger)block)size))lower)hit)cost,)higher)miss)penalty)))))4)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)consecuJve)word)))))))Performance)depends)on:))Access)Jme)for)hit,)miss)penalty,)hit)rate)5)Misses!Cache)misses:)classificaJon)The)line)is)being)referenced)for)the)first)Jme)• Cold)(aka)Compulsory))Miss)The)line)was)in)the)cache,)but)has)been)evicted)6)Avoiding Misses!Q:)How)to)avoid…)Cold)Misses)• Unavoidable?)The)data)was)never)in)the)cache…)• Prefetching!)Other)Misses)• Buy)more)SRAM)• Use)a)more)flexible)cache)design))7)Bigger)cache)doesn’t)always)help…)Mem)access)trace:)0,)16,)1,)17,)2,)18,)3,)19,)4,)…)Hit)rate)with)four)directhmapped)2hbyte)cache)lines?)))With)eight)2hbyte)cache)lines?)))With)four)4hbyte)cache)lines?))0)1)2)3)4)5)6)7)8)9)10)11)12)13)14)15)16)17)18)19)20)21)8)Misses!Cache)misses:)classificaJon)The)line)is)being)referenced)for)the)first)Jme)• Cold)(aka)Compulsory))Miss)The)line)was)in)the)cache,)but)has)been)evicted…)…)because)some)other)access)with)the)same)index)• Conflict)Miss)…)because)the)cache)is)too)small)• i.e.)the)working0set)of)program)is)larger)than)the)cache)• Capacity)Miss)9)Avoiding Misses!Q:)How)to)avoid…)Cold)Misses)• Unavoidable?)The)data)was)never)in)the)cache…)• Prefetching!)Capacity)Misses)• Buy)more)SRAM)Conflict)Misses)• Use)a)more)flexible)cache)design))10)Three common designs!A)given)data)block)can)be)placed…)• …)in)any)cache)line))Fully)AssociaJve)• …)in)exactly)one)cache)line))Direct)Mapped)• …)in)a)small)set)of)cache)lines))Set)AssociaJve)11)Memory)Fully)AssociaJve)Cache)Processor)A Simple Fully Associative 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)Hits:)))))))))))))Misses:)A)=)12)Fully Associative Cache (Reading)!V) Tag) Block)word)select)hit?)data)line)select)=) =) =) =)32bits)64bytes))Tag )) )Offset)13)Fully Associative Cache Size!m)bit)offset)Q:)How)big)is)cache)(data)only)?)Q:)How)much)SRAM)needed)(data)+)overhead)?))Tag )) )Offset),02n)cache)lines)14)FullyhassociaJve)reduces)conflict)misses...))…)assuming)good)evicJon)strategy)Mem)access)trace:)0,)16,)1,)17,)2,)18,)3,)19,)4,)20,)…)Hit)rate)with)four)fullyhassociaJve)2hbyte)cache)lines?)))0)1)2)3)4)5)6)7)8)9)10)11)12)13)14)15)16)17)18)19)20)21)15)…)but)large)block)size)can)sJll)reduce)hit)rate)vector)add)trace:)0,)100,)200,)1,)101,)201,)2,)202,)…)Hit)rate)with)four)fullyhassociaJve)2hbyte)cache)lines?)))))With)two)fullyhassociaJve)4hbyte)cache)lines?))16)Misses!Cache)misses:)classificaJon)Cold)(aka)Compulsory))• The)line)is)being)referenced)for)the)first)Jme)Capacity)• The)line)was)evicted)because)the)cache)was)too)small)• i.e.)the)working0set)of)program)is)larger)than)the)cache)Conflict)• The)line)was)evicted)because)of)another)access)whose)index)conflicted)17)Summary!Caching)assumpJons)• small)working)set:)90/10)rule)• can)predict)future:)spaJal)&)temporal)locality)Benefits)• big)&)fast)memory)built)from)(big)&)slow))+)(small)&)fast))Tradeoffs:))associaJvity,)line)size,)hit)cost,)miss)penalty,)hit)rate)• Fully)AssociaJve))higher)hit)cost,)higher)hit)rate)• Larger)block)size))lower)hit)cost,)higher)miss)penalty)))Next)up:)other)designs;)wriJng)to)caches)18)Cache Tradeoffs!Direct)Mapped)+)Smaller)+)Less)+)Less)+)Faster)+)Less)+)Very)–)Lots)–)Low)–)Common)Fully)AssociaJve)Larger)–)More)–)More)–)Slower)–)More)–)Not)Very)–)Zero)+)High)+)?)Tag)Size)SRAM)Overhead)Controller)Logic)Speed)Price)Scalability)#)of)conflict)misses)Hit)rate)Pathological)Cases?))19)Set)AssociaJve)Caches)20)Compromise!Set)AssociaJve)Cache)• Each)block)number)mapped)to)a)single)cache)line)set)index)• Within)the)set,)block)can)go)in)any)line)set)0)line)0)line)1)line)2)set)1)line)3)line)4)line)5)0x000000)0x000004)0x000008)0x00000c)0x000010)0x000014)0x000018)0x00001c)0x000020)0x000024)0x00002c)0x000030)0x000034)0x000038)0x00003c)0x000040)0x000044)0x000048)0x00004c)21)2-Way Set Associative Cache!Set)AssociaJve)Cache)Like)direct)mapped)cache)• Only)need)to)check)a)few)lines)for)each)access…)so:)fast,)scalable,)low)overhead)Like)a)fully)associaJve)cache)• Several)places)each)block)can)go…)so:)fewer)conflict)misses,)higher)hit)rate))22)3-Way Set Associative Cache (Reading)!word)select)hit?) data)line)select)=) =) =)32bits)64bytes))Tag )Index) )Offset)23)Memory)2hWay)Set)AssociaJve)Cache)Processor)A Simple 2-Way Set Associative 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)Hits:)))))))))))))Misses:)A)=)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)
View Full Document