CPSC 330 - Spring 2009 Study Guide for Exam 2 Coverage: CPU implementation and memory 1. Be able to define or match these terms register internal CPU bus tri-state buffer CPU data path control control signal hardwired control microprogrammed control control store pipelining pipeline stages pipeline latches structural hazard data dependencies RAW (read after write ordering must be preserved) - true dependency WAR (write after read ordering must be preserved) - anti-dependency WAW (write after write ordering must be preserved) - output dependency load-use data hazard pipeline stall register scoreboard forwarding multi-ported register file control hazard (branch hazard) branch target address (BTA) branch taken branch not taken (untaken) delayed branch branch delay slot branch prediction misprediction misprediction recovery flushing pipeline stages dynamic branch prediction branch target address cache (BTAC) branch history table (BHT) branch target buffer (BTB) branch history shift register (BHSR) gshare branch prediction algorithm random access memory (RAM) static RAM (SRAM) dynamic RAM (DRAM) refresh memory cell array row decoder row address strobe (RAS) row buffer column decoder column address strobe (CAS) page-mode DRAM read-only memory (ROM) programmable ROM (PROM) erasable PROM (EPROM) memory hierarchy locality spatial locality temporal locality working set instruction cache data cache multilevel cache primary cache (level one, L1) secondary cache (level two, L2) cache hit hit rate hit time cache miss miss rate miss penalty refill burst transfer over memory bus for refill fetch policy (demand fetch or prefetch) placement policy (fully associative, set-associative, direct-mapped) replacement policy (LRU, pseudo-LRU, random, etc.) write-hit policy (write-through or write-back) write-miss policy (write-allocate or write-no-allocate) cache lines (often called cache blocks) tag valid bit dirty bit (also known as modified bit and changed bit) direct-mapped cache set-associative cache fully associative cache compulsory miss capacity miss conflict miss 2. Be able to: A. Given a high-level RTL or assembly language statement, give the necessary step-by-step RTL and/or control signals to implement that statement on a given datapath. B. Identify critical path(s) in a datapath when implementing a high- level RTL statement or assembly-language instruction. C. Given a code sequence, draw a data dependency graph. D. Describe in general what each stage in the 5-stage pipeline does. E. Given a code sequence, identify where any stalls occur and determine their duration on the 5-stage pipeline. F. Given a code sequence, identify where any forwarding actions occur on the 5-stage pipeline. G. Given a code sequence, draw the pipeline cycle diagram (stairstep diagram) for that code executing on the 5-stage pipeline. H. Explain how data hazards are detected and how forwarding paths work. U. Draw forwarding paths on a pipeline diagram. J. Describe how delayed branches work in the 5-stage pipeline. K. Describe how a BTB (or BTAC and BHT) provides a predicted next instruction address for branch instructions. L. Calculate the specific or average CPI for a given branching scheme. Alternatively, calculate misprediction penalties. M. Draw a block diagram (high-level circuit) showing the two-dimensional organization of a RAM and/or identify the components and signals required to access RAM. N. Draw a timing diagram of bus and RAM chip activity for a memory read. Be able to identify differences for burst transfer mode. O. Give typical capacity, latency, and block size values for the memory hierarchy components. P. Identify at least one example each of temporal and spatial locality of memory references. Q. Given memory and cache parameters, give the tag, index, and offset field sizes within the main memory address. R. Given an address stream and cache parameters, determine the number of misses. S. Explain how row versus column access to a matrix affects cache misses. (E.g., discuss how misses were reduced in the matrix multiply example.) Be prepared to work problems as given in homeworks 3 and 4.