How will execution time grow with SIZE?Actual Data from remsun2.ews.uiuc.eduWelcome to Part 3: Memory Systems and I/OLarge and fastSmall or slowIntroducing cachesToday: Cache introductionThe principle of localityTemporal locality in programsTemporal locality in dataSpatial locality in programsSpatial locality in dataHow caches take advantage of temporal localityHow caches take advantage of spatial localityOther kinds of cachesDefinitions: Hits and missesA simple cache designFour important questionsWhere should we put data in the cache?Least-significant bitsHow can we find data in the cache?Figuring out what’s in the cacheWhat happens on a cache hitWhat happens on a cache missLoading a block into the cacheWhat if the cache fills up?Summary1How 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]; } }SIZETIMEPlot?2Actual Data from remsun2.ews.uiuc.edu0510152025303540450 2000 4000 6000 8000 10000Series1array fits in cache3Welcome to Part 3: Memory Systems and I/OWe’ve already seen how to make a fast processor. How can we supply the CPU with enough data to keep it busy?The rest of CS232 focuses on memory and input/output issues, which are frequently bottlenecks that limit the performance of a system.We’ll start off by looking at memory systems for the next few weeks, and turn to I/O.—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/Output4Large and fastToday’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 so forth.—Speed is important to keep up with our pipelined CPUs, which may access both an instruction and data in the same clock cycle. Things get 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 access memory twice in one cycle, but as we’ll see that’s a simplification.5Small or slowHere are rough estimates of some current storage parameters.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 units in a datapath. If every lw or sw accessed dynamic memory, we’d have to either increase the cycle time or stall frequently.Storage Delay Cost/MB CapacityStatic RAM 1-10 cycles ~$5 128KB-2MBDynamic RAM100-200 cycles ~$0.10 128MB-4GBHard disks 10,000,000 cycles~$0.0005 20GB-400GB6Introducing cachesWouldn’t it be nice if we could find a balance between fast and cheap memory?We do this by introducing a cache, which is a small amount of fast, expensive memory.—The cache goes between the processor and the slower, dynamic main memory.—It keeps a copy of the most frequently used data from the main memory.Memory access speed increases overall, because we’ve made the common case faster.—Reads and writes to the most frequently used addresses will be serviced by the cache.—We only need to access the slower main memory for less frequently used data. Lots ofdynamic RAMA little staticRAM (cache)CPU7Today: Cache introductionToday 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?8The principle of localityIt’s usually difficult or impossible to figure out what data will be “most frequently accessed” before a program actually runs, which makes it hard to know what to store into the small, precious cache memory.But in practice, most programs exhibit locality, which the cache can take advantage of.—The principle of temporal locality says that if a program accesses one memory address, there is a good chance that it will access the same address again.—The principle of spatial locality says that if a program accesses one memory address, there is a good chance that it will also access other nearby addresses.9Loops 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 the instruction memory repeatedly.For example: —Each instruction will be fetched over and over again, once on every loop iteration.Temporal locality in programsLoop: lw $t0, 0($s1)add $t0, $t0, $s2sw $t0, 0($s1)addi $s1, $s1, -4bne $s1, $0, Loop10Programs often access the same variables over and over, especially within loops. Below, sum and i are repeatedly read and written.Commonly-accessed variables can sometimes be kept in registers, but this is not always possible.—There are a limited number of registers.—There are situations where the data must be kept in memory, as is the case with shared or dynamically-allocated memory.Temporal locality in datasum = 0;for (i = 0; i < MAX; i++)sum = sum + f(i);11The principle of spatial locality says that if a program accesses one memory address, there is a good chance that it will also access other nearby addresses.Nearly every program exhibits spatial locality, because instructions are usually executed in sequence—if we execute an instruction at memory location i, then we will probably also execute the next instruction, at memory 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)12Programs often access data that is stored contiguously.—Arrays, like a in the code on the top, are stored in memory contiguously.—The individual fields of a record or object like employee are also kept contiguously in memory.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];13How caches take advantage of temporal localityThe first time the processor reads from an address in main memory, a copy of that data is also stored in the cache.—The next time that same address is read, we can use the copy of the data in the cache instead
View Full Document
Unlocking...