Lecture notes for CSC 252, Tues. Mar. 20 ff, 2007 Announcements A5 is on the web trivia due noon, Thurs. 22 Mar. main assignment due Monday, 2 Apr., 11:59pm Read chapter 6. I'm planning to skip chapter 7. I want the extra lecture for the current unit. -------------------------------- Greek prefixes exa 10^18 ~= 2^60 XB peta 10^15 ~= 2^50 PB tera 10^12 ~= 2^40 TB giga 10^9 ~= 2^30 GHz, GB mega 10^6 ~= 2^20 MHz, MB kilo 10^3 ~= 2^10 KHz, KB milli 10^(-3) ~= 2^(-10) ms micro 10^(-6) ~= 2^(-20) us nano 10^(-9) ~= 2^(-30) ns pico 10^(-12) ~= 2^(-40) ps femto 10^(-15) ~= 2^(-50) fF (charge on DRAM cell) You need to get used to common units and develop a feel for their size. With current technology (these are moving targets): The clock on a 3GHz processor ticks 3B times/sec; its cycle time is 0.33ns. A register can be accessed in one cycle. L1 cache can be accessed in about 1ns (2-3 cycles) L2 or L3 cache in 5-20ns. Main memory in 60-100ns. Disk in 5-12ms. L1 cache holds 32-256KB L2 and L3 cache holds 1-32MB Main memory on a PC holds 64MB to 4GB (much more on a mainframe or supercomputer) A single disk holds 50-500GB. Large databases are measured in PB. -------------------------------- The Memory (Storage) Hierarchy registers L1 cache L2 cache L3 cache main memory local disk remote or tertiary storage (tape, optical jukebox, etc.) *** The goal of the memory hierarchy is to give the appearance of a uniform store with the latency of the top levels and the capacity of the bottom levels. How can we do it? Use CACHING to exploit LOCALITY temporal locality if we use something we're likely to use it again soon spatial locality if we use something we're likely to use something nearby soon Caching keep WORKING SET (things we're using a lot at present) in the smaller, faster levels of the storage hierarchy, and other stuff in the larger, slower levels. REUSE DISTANCE: rd(a), where a is a memory reference, is the amount of data accessed one or more times since the most recent previous reference to the datum accessed in a. Best known quantification of locality. Can be defined for arbitrary units of data granularity, e.g. bytes, words, cache lines, pages. << draw working set diagram: reuse distance v. cumulative data cover >> << conversely, cache size v. cache miss rate >> Caching happens at every level of the hierarchy. In most cases it's handled automatically, so your program doesn't know what's going on. This only sort of works at the top level, where your *source* program doesn't know what's going on, but the compiler does, and embeds its knowledge in the assembly level program. We'll concentrate in particular on (1) caching of main memory in L1/2/3 cache, and (2, later) caching of disk in main memory. cache virtual memory technology SRAM DRAM management HW HW/OS block size ~64B ~8KB -------------------------------- What a program can do right/wrong: Bad temporal locality: for (i = 0; i < N; i++) { row_sum[i] = 0; } for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { row_sum[i] += A[i][j]; } } If A is big it's likely that row_sum[i] won't be in the cache anymore (at least not in the L1 cache) the 2nd time we use it. Better version: for (i = 0; i < N; i++) { row_sum[i] = 0; for (j = 0; j < N; j++) { row_sum[i] += A[i][j]; } } Bad spatial locality: int grand_total = 0; for (j = 0; j < N; j++) { for (i = 0; i < N; i++) { grand_total += A[i][j]; } } This walks through A in the "wrong order" -- column-wise. (Unless we're writing in Fortran.) Better version reverses the loops: int grand_total = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { grand_total += A[i][j]; } } *** A really good compiler will do a lot of this for you. With just a so-so compiler you need to do it yourself. It's almost always worth doing if it doesn't mess up the readability of the code. If it does make the code uglier, do it only if profiling indicates you have performance problems in this particular place. Much more on cache-friendly code coming up below. -------------------------------- memory technology SRAM DRAM variants: FPM DRAM, EDO DRAM, SDRAM, DDR SDRAM, VRAM (don't ask :-) ROM, PROM, EPROM, EEPROM (Flash) SRAM 6 transistors per bit 8-16X faster 8-16X more expensive 4-8X less dense doesn't require refresh used for cache, supercomputer memories DRAM 1 transistor and a capacitor per bit must be refreshed after read, and every few ms even when not read used for main memory on most machines Conventional DRAM chip has d X c cells, each of which contains w bits. A 64Mb chip might have 8M = 2^23 cells, each with 8 = 2^3 bits. To minimize pin count and simplify internal circuitry, the chip must be "strobed" (fed address bits) twice: once for row and once for column. If we have 11 rows and 12 columns, we'd feed in 11 bits, then 12, then read out 8 bits. Memory is commonly packaged on DIMMs (dual-in-line memory modules). These produce 64 bits at a time. We could build a 64MB DIMM from 8 of the chips above. The DIMM controller feeds the row and column bits to all 8 chips simultaneously, then assembles the 8B output. ------------------------------ bus architecture Processor, memory, and devices connected by a collection of BUSes: shared communication lines. The more I/O connections you have, and the more general (i.e. simple) they are, the slower the bus tends to be. Really cheap systems may have a single bus. Fancier systems (including most current PCs) have multiple buses, with more general I/O interfaces available on slower, subsidiary buses. Common arrangement system bus memory bus CPU <-----------> I/O bridge <-----------> memory ^ | <----+-------------+-----------------> | PCI bus | | USB bus v *** I/O bridge allows CPU and memory to talk to each other without bothering devices, and disk (on PCI bus) and memory to talk to each other without bothering the CPU(s). bus design alternatives expensive cheap fast slow physically short physically long wide narrow synchronous asynchronous complicated interface simple interface multiple masters single or no master block transfers word at a time split transaction single transaction Clock skew limits the physical length of synchronous buses. All devices on synchronous bus must run at same speed. Asynchronous buses can be very long if you're willing to tolerate long handshaking delays: witness (non-switched) Ethernet : ~1km length. bus arbitration: who is allowed to send when? central arbiter (e.g. PCI) generally requires extra control lines daisy chain (e.g. SCSI, USB, FireWire) simple, but slower, and not as fair collision detection (e.g. Ethernet) not used in backplanes (too slow); works well for LAN Memory-mapped I/O (usual case) v. special I/O instructions (antiquated option on the x86) -------------------------------- disk technology platter (1 to maybe 15) sector (typically 512 bytes, 64-200 per track) track (typically > 10^4 per platter) grouped into zones: each track in a given zone has the same number of sectors; tracks in outer zones have more than those in inner zones cylinder: corresponding tracks on different surfaces -- can be accessed without seeking. capacity growing at an amazing rate typical PC hard disk today: 100GB capacity 10,000 rpm ==> 3ms average rotational latency (0.5 revolutions / 10000 rpm * 60s/min) 10ms typical seek latency (varies from 0 to maybe 15) maybe 30MB/s transfer rate All these numbers are moving targets, though capacity moves the fastest. Rotational speed has grown no more than 3X since the 1960s, mostly enabled by reductions in physical size. contributors to access time: seek time rotational latency transfer time controller overhead OS overhead Trends In the 20 years between 1980 and 2000: CPU speed 600X SRAM capacity 200X latency 100X DRAM capacity (MB/$) 8,000X latency 6X disk capacity (MB/$) 50,000X latency 10X Implication: caching is a LOT more important than it used to be. Note, however, that the CPU trend has changed in the last 3 years. The memory/CPU latency gap has more or less stopped growing. BUT: memory/CPU _bandwidth_ gap is still growing, and we're at the limit of physical pins. -------------------------------- Emerging technology MRAM, MEMS, ... ================================ Caches terminology cache miss page fault hit rate miss rate hit time miss penalty thrashing multi-level inclusion split v. unified Typical modern machines have separate I and D caches at L1 (Harvard architecture) Split L1 cache makes it easier to read both instructions and data in every cycle. Code is read-only in most systems. If you know you can't modify code you never have to worry about pipeline hazards due to writes into the instruction space. And if you have separate I & D L1 caches you never have to kick anything out of L1 because of a write. blocks, blocksize lines, linesize Text uses "line" to mean "block plus tag and valid/dirty bits"; other authors use the terms interchangably. associativity fully associative N-way associative direct-mapped sets ways indexing via middle bits of physical address (ignore virtual memory for now) word selection via low-order bits M = 2^m byte address space m-bit address Divide address into t-bit tag, s-bit set selector, b-bit byte selector; m = t + s + b B = 2^b bytes per block (line) S = 2^s sets E ways = # of lines per set T = 2^t addresses in memory map to the same set C = B x E x S cache capacity In a direct-mapped cache, E = 1, so C = B x S. In a fully-associative cache, S = 1, s = 0, and C = B x E. The Pentium (at least up through PIII) has L1-I (on-chip) B = 32B, E = 4, S = 128, C = 16KB L1-D (on-chip) B = 32B, E = 4, S = 128, C = 16KB L2 (off-chip, unified) B = 32B, E = 4, S = 1024-16384, C = 128KB - 2MB Our 3-year-old IBM Regatta machine has two processors per chip. Each processor has L1-I (per processor) B = 128B, E = 1 (direct map), C = 64KB L1-D (per processor) B = 128B, E = 2, C = 32KB L2 (shared) B = 128B, E = 8, C = 1.5MB L3 (off-chip, shared) B = 512B, E = 8, C = 32MB write-back v. write-through v. uncached (I/O) write-allocate v. write-no-allocate Typically write-back caches are write-allocate, while write-through caches are no-write allocate. In the Regatta, the L1 d-cache is write-through; the L2 and L3 caches are write-back. Write buffer Holds to-be-completed writes. The pipeline doesn't have to wait for these to reach memory, but reads have to check the write buffer to see if there is any as-yet-uncompleted write to the location we're reading. Does this in parallel with access to L1. Write merging Also note that *lots* of stuff becomes more complicated when there is more than one processor. More on this later in the semester. misses cold-start (obligatory) capacity need a bigger cache conflict need more associativity, or reorganized program coherence need less sharing (true or false) Design tradeoffs cache size bigger --> higher hit rate, higher hit time block size bigger --> higher hit rate due to spatial locality bigger --> lower hit rate due to temporal locality bigger --> higher miss penalty associativity higher --> higher hit rate and lower likelihood of thrashing, due to fewer conflict misses higher --> higher hit time higher --> smaller cache size, due to associative circuitry and longer tags write strategy write-through --> simpler, with lower miss penalty due to lack of dirty lines write-back --> better use of bus and memory bandwidth In general, caches higher up in the hierarchy are more likely to be small, with small blocks, direct-mapped, and write-through; caches lower in the hierarchy are more likely to be large and more associative, with large blocks and write-back. But these are not hard-and-fast rules. Also, the trend over time is toward larger caches and larger blocks -- an attempt to use density (which is increasing rapidly) and bandwidth (which is increasing moderately) to tolerate latency (which isn't decreasing much at all). -------------------------------- The "Memory Mountain" Consider the following program: int A[2M] for size = 512 to 2M do for stride = 1 to 16 do num_trials times do start timer for i = 0 to size by stride do read A[i] end timer plot (bytes moved / min time) for each set of trials The result is a "memory bandwidth mountain", as in fig. 6.42 in the text. From PIII Xeon system. 2/7/25 cycles latency to L1, L2, main memory. - Three levels corresponding to working sets that fit in L1, L2, and main memory. - Slopes on L2 and memory levels, due to effect of spatial locality in L1 and (on memory level) L2. Slope is more noticable on L2 level because of scale, but is proportionally the same on this machine, because 2/7 ~= 7/25. - Artifacts due to loop overhead when working set is small. In particular, that accounts for the "back slope" and for the fact that the ridge isn't level. Other minor artifacts, too (e.g. bump at right of L2 level); not sure why. (Comments in the book on p. 514 are somewhat misleading. In particular: the steepness of the slope of the L2 ridge is NOT because of the "large absolute miss penalty that the L2 cache suffers when it has to transfer blocks from main memory". The whole working set fits in the L2 in this region! The real explanation is the miss penalty of the L1 when it retrieves blocks from the L2, as described in the paragraph beginning at the bottom of p. 515.) Cuts through the surface (figs 6.43 and 6.44) also interesting. Can really see temporal and spatial locality. Note the "in-between" bar at 512K in fig. 6.43. While the L2 is big enough to hold all the data at this point, it isn't big enough to hold all the data *and* all the instructions. ================================ Cache-friendly code Consider matrix multiplication: double A[], B[], C[] for i = 0 to N-1 C[i] = 0 for i = 0 to N-1 for j = 0 to N-1 for k = 0 to N-1 C[i,j] += A[i,k] * B[k,j] Ignore initialization of C from now on; focus on the nested loops. Notice that the i, j, and k loops are completely symmetric. So we can permute them into any of six orders: for i for j for j for i for k for k for j for k for k for j for i for i for k for i for i for k for j for j In the original (i, j, k) version of the loop nest, a decent compiler should keep C[i,j] in a register during the inner loop. It might not be able to if A, B, and C were by-reference parameters, so that aliases are a potential problem. We can force it to (since we know we won't create an alias) by introducing a local variable: for i for j sum = 0 for k sum += A[i,k] * B[k,j] C[i,j] = sum There are similar optimizations possible in the other 5 cases. The (j, i, k) version looks like the above. In both cases k is the inner index, and the inner loop accesses A and B but not C. The (j, k, i) and (k, j, i) versions look like this: for j for k r = B[k,j] for i C[i,j] += A[i,k] * r Here i is the inner index, and the inner loop accesses A and C but not B. The (k, i, j) and (i, k, j) versions look like this: for k for i r = A[i,k] for j C[i,j] += r * B[k,j] Here j is the inner index, and the inner loop accesses B and C but not A. These three main variants have different memory reference patterns and different locality: inner loop behavior loads stores tot-mem A-miss B-miss C-miss tot-miss AB (k inner) 2 0 2 0.25 1 0 1.25 AC (i inner) 2 1 3 1 0 1 2 BC (j inner) 2 1 3 0 0.25 0.25 0.5 The AC variant (i inner) is clearly bad. It doesn't access B in the inner loop, but it walks both A and C in column-major order, for really bad locality. The AB variant wins on total memory accesses. The BC variant wins on cache misses. Which one will be better depends on the machine. For the PIII Xeon used for the experiments in the book, the AB variant was slightly better. But all three variants got worse with increasing array size (figure 6.47 in the book). Can we fix that? -------------------------------- Blocking Works for many codes based on multi-dimensional arrays. Really messes up the appearance of the code. Can be done by some really good high-end compilers. Not done by most C compilers. Worth doing by hand in truly performance-critical code (but realize it's going to make maintenance a *lot* harder.) The idea: treat the arrays not as arrays of ints, but as arrays of little arrays. Iterate over the little arrays, which fit in the L1, doing (as much as possible) all the work on a given set of little arrays before moving on to the next set. In an unfortunate overloading of terminology, the little arrays are called "blocks" -- not to be confused with cache blocks (the things that reside in lines). We can apply blocking to any of the 6 variants of matrix multiply above. It introduces additional levels of loop nest, which go around the existing loops. We could choose to block A, B, and/or C, and then nest the new, outer loops in any order. There are a *lot* of resulting possibilities -- too many to enumerate here. One option that works well is to use the (i, j, k) version above, and apply blocking to B. we get something like this: const bsize = 25 // or whatever -- right value depends on size of L1 cache init: for i, j { C[i,j] = 0 } for kk = 0 to N-1 by bsize for jj = 0 to N-1 by bsize for i = 0 to N-1 for j = jj to jj+bsize-1 sum = C[i,j] for k = kk to kk+bsize-1 sum += A[i,k] * B[k,j] C[i,j] += sum The inner (k) loop moves across a 1 X bsize sliver of A and down one column of a bsize X bsize block of B. The next loop out (j) iterates over the columns of that block of B, using the same sliver of A over and over, and updating the elements of a 1 X bsize sliver of C. The next loop out (i) moves down one sliver in A and C, and repeats the above, using the same bsize X bsize block of B. The outer two loops iterate over the blocks of B, repeating the above. Figure 6.49 helps make this clearer. When studying it, keep the order of the loop nests in mind: (1) k varies fastest, followed (moving outward) by j, i, jj, and kk (2) We never return to a block of B, but we do return to A and C. Specifically, for every new block of B we scan an entire N X bsize vertical stripe of A, and update the corresponding N X bsize vertical stripe of C. (3) A given element C[x,y] gets updated in n/bsize iterations of the outer kk/jj loops -- specifically the ones corresponding to the blocks of B containing column y. The bottom line: as shown in figure 6.50 (p. 523), blocking virtually eliminates the performance degredation associated with increases in array size: we get a nice flat performance curve. (For small arrays, however, the flat curve is *above* the sloping curves for simpler algorithms, due to the extra loop overhead.)