April 16, 2003 Cache introduction 1How will execution time grow with SIZE?int array[SIZE];int A = 0;for (int i = 0 ; i < 200000 ; ++ i) {for (int j = 0 ; j < SIZE ; ++ j) {A += array[j];}}SIZETIMEPlotApril 16, 2003 Cache introduction 2Actual Data from remsun2.ews.uiuc.edu0510152025303540450 2000 4000 6000 8000 10000Series1October 19, 2007 ©2003 Craig Zilles (derived fromslides by Howard Huang)3Welcome to Part 3: Memory Systems and I/O We’ve already seen how to make a fast processor. How can we supply theCPU with enough data to keep it busy? The rest of CS232 focuses on memory and input/output issues, which arefrequently bottlenecks that limit the performance of a system. We’ll start off by looking at memory systems for the next two weeks, andthen turn to I/O for a week.— How caches can dramatically improve the speed of memory accesses.— How virtual memory provides security and ease of programming— How processors, memory and peripheral devices can be connectedMemoryProcessorInput/OutputOctober 19, 2007 ©2003 Craig Zilles (derived fromslides by Howard Huang)4Today: Cache introduction Today we’ll answer the following questions.— What are the challenges of building big, fast memory systems?— What is a cache?— Why caches work? (answer: locality)— How are caches organized?• Where do we put things -and- how do we find them?October 19, 2007 Cache introduction 5Large and fast Today’s computers depend upon large and fast storage systems.— Large storage capacities are needed for many database applications,scientific computations with large data sets, video and music, and soforth.— Speed is important to keep up with our pipelined CPUs, which mayaccess both an instruction and data in the same clock cycle. Thingsget become even worse if we move to a superscalar CPU design. So far we’ve assumed our memories can keep up and our CPU can accessmemory twice in one cycle, but as we’ll see that’s a simplification.October 19, 2007 Cache introduction 6Small or slow Unfortunately there is a tradeoff between speed, cost and capacity. Fast memory is too expensive for most people to buy a lot of. But dynamic memory has a much longer delay than other functional unitsin a datapath. If every lw or sw accessed dynamic memory, we’d have toeither increase the cycle time or stall frequently. Here are rough estimates of some current storage parameters.LargestCheapestSlowestHard disksLargeCheapSlowDynamic RAMSmallestExpensiveFastestStatic RAMCapacityCostSpeedStorage20GB-400GB~$0.000510,000,000 cyclesHard disks128MB-4GB~$0.10100-200 cyclesDynamic RAM128KB-2MB~$51-10 cyclesStatic RAMCapacityCost/MBDelayStorageOctober 19, 2007 Cache introduction 7Introducing caches Wouldn’t it be nice if we could find a balance betweenfast and cheap memory? We do this by introducing a cache, which is a smallamount of fast, expensive memory.— The cache goes between the processor and theslower, dynamic main memory.— It keeps a copy of the most frequently used datafrom the main memory. Memory access speed increases overall, because we’vemade the common case faster.— Reads and writes to the most frequently usedaddresses will be serviced by the cache.— We only need to access the slower main memoryfor less frequently used data.Lots ofdynamic RAMA little staticRAM (cache)CPUOctober 19, 2007 Cache introduction 8The principle of locality It’s usually difficult or impossible to figure out what data will be “mostfrequently accessed” before a program actually runs, which makes it hardto know what to store into the small, precious cache memory. But in practice, most programs exhibit locality, which the cache can takeadvantage of.— The principle of temporal locality says that if a program accesses onememory address, there is a good chance that it will access the sameaddress again.— The principle of spatial locality says that if a program accesses onememory address, there is a good chance that it will also access othernearby addresses.October 19, 2007 Cache introduction 9 The principle of temporal locality says that if a program accesses onememory address, there is a good chance that it will access the sameaddress again. Loops are excellent examples of temporal locality in programs.— The loop body will be executed many times.— The computer will need to access those same few locations of theinstruction memory repeatedly. For example:— Each instruction will be fetched over and over again, once on everyloop iteration.Temporal locality in programsLoop: lw $t0, 0($s1)add $t0, $t0, $s2sw $t0, 0($s1)addi $s1, $s1, -4bne $s1, $0, LoopOctober 19, 2007 Cache introduction 10 Programs often access the same variables over and over, especially withinloops. Below, sum and i are repeatedly read and written. Commonly-accessed variables can sometimes be kept in registers, but thisis not always possible.— There are a limited number of registers.— There are situations where the data must be kept in memory, as is thecase with shared or dynamically-allocated memory.Temporal locality in datasum = 0;for (i = 0; i < MAX; i++)sum = sum + f(i);October 19, 2007 Cache introduction 11 The principle of spatial locality says that if a program accesses onememory address, there is a good chance that it will also access othernearby addresses. Nearly every program exhibits spatial locality, because instructions areusually executed in sequence—if we execute an instruction at memorylocation i, then we will probably also execute the next instruction, atmemory location i+1. Code fragments such as loops exhibit both temporal and spatial locality.Spatial locality in programssub $sp, $sp, 16sw $ra, 0($sp)sw $s0, 4($sp)sw $a0, 8($sp)sw $a1, 12($sp)October 19, 2007 Cache introduction 12 Programs often access datathat is stored contiguously.— Arrays, like a in the codeon the top, are stored inmemory contiguously.— The individual fields of arecord or object likeemployee are also keptcontiguously in memory. Can data have both spatial andtemporal locality?Spatial locality in dataemployee.name = “Homer Simpson”;employee.boss = “Mr. Burns”;employee.age = 45;sum = 0;for (i = 0; i < MAX; i++)sum = sum + a[i];October 19, 2007 Cache introduction 13How caches take advantage of temporal locality The first time the processor reads from an address inmain memory, a copy of that data is also stored in thecache.— The next time that same address
View Full Document
Unlocking...