CS 5513
Fall 2007
Exam 1

Answer the following questions. Clearly indicate your answer.

True or False

Write 'T' for True statements and 'F' for False statements.
  1. Conflict misses can occur with a set-associative cache.
  2. Register renaming can be done by the compiler.
  3. Register renaming can be done by the microarchitecture.
  4. Flow dependences can be eliminated by register renaming.
  5. NMOS transistors are switched on when their gate input is set to 0.
  6. PMOS transistors are not good at passing 0 from source to drain.
  7. A NAND gate requires at least 6 transistors.
  8. Each SRAM cell contains NOT gates.
  9. Special hardware is required to handle RAR (read-after-read) hazards.
  10. Branch delay slots eliminate the need for branch prediction on a deeply pipelined processor.
  11. The targets of return addresses are usually predicted by the branch target buffer.
  12. More...

Short Answer

  • Consider each of the following terms: For each term, answer the following questions in at most two sentences each:

    Problems

    1. Consider the following C code: 
      int dp (int A[], int B[], int n) {
        int i, sum = 0;

        i = 0;
        if (n == 0) 
		goto finished;
loop:
        sum = A[i];
        sum = sum * B[i]; 
        i = i + 1;
        if (i < n)
		goto loop;
finished:
        return sum;
}
      For each line of C code, the compiler produces a machine instruction. The code is not re-ordered by the compiler. Suppose that this function is called 100 times, each time with a value of 3 for n. For each of the following branch predictors, write the number of times a conditional branch in the dp function would be predicted incorrectly (write a single number for each predictor that is the total of all wrong predictions):
      1. Static "always not taken" policy.
      2. Static "backward taken/forward not taken" policy.
        For dynamic predictors, assume there is no aliasing in branch prediction tables and there is a single global history register that records the outcomes of all conditional branches, and there are no other conditional branches in the program outside the dp function. Initially all counters and all bits of history are set to 0.
      3. A bimodal predictor with two-bit saturating counters.
      4. A two-level adaptive branch predictor with a history length of 2.
    2. A 4 kilobyte write-back cache is 2-way set associative. Addresses are 32 bits. The block index is 3 bits.
      1. How many bits are in the set index?
      2. How many bits are in the tag?
      3. How many dirty bits are required for this cache?