FROM FALL 2011

CPSC 330 - Fall 2011
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.