CS61C L34 Caches III (1)Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine StructuresLecture 34 Caches III2004-11-17The Incredibles!⇒TheBiggest digital photoof all time is a huge78,797 x 31,565, I.e.,2.5 Gibipixels, 7.5 GiBZoom away!www.tpd.tno.nl/smartsite966.htmlCS61C L34 Caches III (2)Garcia, Fall 2004 © UCBReview…• Mechanism for transparent movement ofdata among levels of a storage hierarchy• set of address/value bindings• address => index to set of candidates• compare desired address with tag• service hit or miss- load new block and binding on missValidTag0x0-30x4-7 0x8-b 0xc-f0123...10 a b c d000000000000000000 0000000001 1100address: tag index offsetCS61C L34 Caches III (3)Garcia, Fall 2004 © UCB• Blah blah Cache size 16KB blah blah223 blocks blah blah how many bits?• Answer! 2XY means…X=0 ⇒ no suffixX=1 ⇒ kibi ~ Kilo 103X=2 ⇒ mebi ~ Mega 106X=3 ⇒ gibi ~ Giga 109X=4 ⇒ tebi ~ Tera 1012X=5 ⇒ pebi ~ Peta 1015X=6 ⇒ exbi ~ Exa 1018X=7 ⇒ zebi ~ Zetta 1021X=8 ⇒ yobi ~ Yotta 1024Memorized this table yet? Y=0 ⇒ 1Y=1 ⇒ 2Y=2 ⇒ 4Y=3 ⇒ 8Y=4 ⇒ 16Y=5 ⇒ 32Y=6 ⇒ 64Y=7 ⇒ 128Y=8 ⇒ 256Y=9 ⇒ 512*CS61C L34 Caches III (4)Garcia, Fall 2004 © UCBHow Much Information IS that?• Print, film, magnetic, and optical storage mediaproduced about 5 exabytes of new information in2002. 92% of the new information stored onmagnetic media, mostly in hard disks.• Amt of new information stored on paper, film,magnetic, & optical media ~doubled in last 3 yrs• Information flows through electronic channels --telephone, radio, TV, and the Internet -- contained~18 exabytes of new information in 2002, 3.5x morethan is recorded in storage media. 98% of this totalis the information sent & received in telephonecalls - incl. voice & data on fixed lines & wireless.• WWW ⇒ 170 Tb of information on its surface; in volume17x the size of the Lib. of Congress print collections.• Instant messaging ⇒ 5x109 msgs/day (750GB), 274 TB/yr.• Email ⇒ ~400 PB of new information/year worldwide.www.sims.berkeley.edu/research/projects/how-much-info-2003/CS61C L34 Caches III (5)Garcia, Fall 2004 © UCBBlock Size Tradeoff (1/3)• Benefits of Larger Block Size• Spatial Locality: if we access a givenword, we’re likely to access othernearby words soon• Very applicable with Stored-ProgramConcept: if we execute a giveninstruction, it’s likely that we’ll executethe next few as well• Works nicely in sequential arrayaccesses tooCS61C L34 Caches III (6)Garcia, Fall 2004 © UCBBlock Size Tradeoff (2/3)• Drawbacks of Larger Block Size• Larger block size means larger misspenalty- on a miss, takes longer time to load a newblock from next level• If block size is too big relative to cachesize, then there are too few blocks- Result: miss rate goes up• In general, minimizeAverage Access Time= Hit Time x Hit Rate+ Miss Penalty x Miss RateCS61C L34 Caches III (7)Garcia, Fall 2004 © UCBBlock Size Tradeoff (3/3)• Hit Time = time to find and retrievedata from current level cache• Miss Penalty = average time toretrieve data on a current level miss(includes the possibility of misses onsuccessive levels of memoryhierarchy)• Hit Rate = % of requests that arefound in current level cache• Miss Rate = 1 - Hit RateCS61C L34 Caches III (8)Garcia, Fall 2004 © UCBExtreme Example: One Big Block• Cache Size = 4 bytes Block Size = 4 bytes• Only ONE entry in the cache!• If item accessed, likely accessed again soon• But unlikely will be accessed again immediately!• The next access will likely to be a miss again• Continually loading data into the cache butdiscard data (force out) before use it again• Nightmare for cache designer: Ping Pong Effect Cache DataValid BitB 0B 1B 3TagB 2CS61C L34 Caches III (9)Garcia, Fall 2004 © UCBBlock Size Tradeoff ConclusionsMissPenaltyBlock SizeIncreased Miss Penalty& Miss RateAverageAccessTimeBlock SizeExploits Spatial LocalityFewer blocks: compromisestemporal localityMissRateBlock SizeCS61C L34 Caches III (10)Garcia, Fall 2004 © UCBAdministrivia• Project 2 grades are frozen• Details on Midterm clobbering• Final exam will contain midterm-labeledquestions (covering weeks 1-7), calledFinalMid• On these questions, if your st. dev (σ) isgreater than your σ on the Midterm, youhave clobbered your grade and we’llreplace your Midterm w/σ-equivalentgrade from FinalMid• E.g., Mid x ≈ 50, σ =12, you got 38. YourMid grade is -1.0 σ. FinalMid x ≈ 60, σ=10, you get 65. Your FinalMid grade is0.5 σ. Your new Mid grade is now 0.5 σ,or 50 + 0.5 σ = 56! WooHoo!CS61C L34 Caches III (11)Garcia, Fall 2004 © UCBTypes of Cache Misses (1/2)• “Three Cs” Model of Misses• 1st C: Compulsory Misses• occur when a program is first started• cache does not contain any of thatprogram’s data yet, so misses are boundto occur• can’t be avoided easily, so won’t focuson these in this courseCS61C L34 Caches III (12)Garcia, Fall 2004 © UCBTypes of Cache Misses (2/2)• 2nd C: Conflict Misses• miss that occurs because two distinct memoryaddresses map to the same cache location• two blocks (which happen to map to the samelocation) can keep overwriting each other• big problem in direct-mapped caches• how do we lessen the effect of these?• Dealing with Conflict Misses• Solution 1: Make the cache size bigger- Fails at some point• Solution 2: Multiple distinct blocks can fit in thesame cache Index?CS61C L34 Caches III (13)Garcia, Fall 2004 © UCBFully Associative Cache (1/3)• Memory address fields:• Tag: same as before• Offset: same as before• Index: non-existant• What does this mean?• no “rows”: any block can go anywhere inthe cache• must compare with all tags in entire cacheto see if data is thereCS61C L34 Caches III (14)Garcia, Fall 2004 © UCBFully Associative Cache (2/3)• Fully Associative Cache (e.g., 32 B block)• compare tags in parallelByte Offset: Cache DataB 00431:Cache Tag (27 bits long)Valid:B 1B 31: Cache Tag=====:CS61C L34 Caches III (15)Garcia, Fall 2004 © UCBFully Associative Cache (3/3)• Benefit of Fully Assoc Cache• No Conflict Misses (since data can goanywhere)• Drawbacks of Fully Assoc Cache• Need hardware comparator for everysingle entry: if we have a 64KB of data incache with 4B entries, we need 16Kcomparators: infeasibleCS61C L34 Caches III (16)Garcia,
View Full Document
Unlocking...