CS 220 - Final Exam Study Guide

Final Exam Topics

The topics covered since the first exam are:

  1. Integer Multiplication (3.3)
    1. Review study questions for quiz 6 from day 16
    2. Review quiz 6
  2. Floatintg-Point representation, programming the floating-point registers and instructions.
    1. Write a floating-point program that reads a temperature in fahrenheit from the console and prints its celsius equivalent.
    2. Don't review homework for computing $e^x$. That is too complicated for an exam.
  3. The Single Cycle Datapath (4.1 - 4.4)
    1. Review single cycle problems and solutions from day 20
    2. Review quiz 7
  4. The MIPS Pipeline (4.5)
    1. Review pipeline problems and solutions from day 22
    2. Review quiz 8
  5. Caches (5.1 - 5.2)
    1. Review cache problems and solutions from day 24
    2. Review quiz 9
  6. Virtual Memory (5.4)
  7. Disk Storage and RAID (6.1 - 6.3, 6.9)
  8. I/O (6.6)

Here are some questions

  1. True/False. The single cycle datapath has a CPI of one, so it has better performance than the MIPS pipelined datapath which has a CPI of five. Explain your answer.
  2. Assuming current technology, give an approximate and reasonable estimate of the access time for cache? main memory? disk?
  3. What is a write-through cache? What is a write-back cache? We didn't go over in class, see discussion on pages 466-468 in book.
  4. Explain the concept of temporal locality? How does a cache exploit it? Give an example of program that would have good data temporal locality.
  5. Explain the concept of spatial locality? How does a cache exploit it? Give an exanmple of a program that would have good data spatial locality.
  6. What is a comparator and where are they used in cache implementations?
  7. Why is a fully associative cache more expensive to implement than a direct mapped cache?
  8. Explain the difference between direct-mapped, set-associative, and fully associative cache designs.
  9. If a cache has one set it is the same as a ___________________ cache.
  10. If a cache with $n$ blocks has $n$ sets it is the same as a __________________ cache.
  11. Express the floating-point number -7.3125 in single precision IEEE floating-point format. Write your answer in hexadecimal.
  12. If a multiplexor has n inputs how many selector wires does it require?
  13. If n bits of an address are used to specify a block in a direct mapped cache how many blocks does the cache have?
  14. If a set associative cache has n sets how many bits are needed in the address to specify the set the address maps to?
  15. Why does the MIPS need exactly five bits to specify the destination register in an R-type instruction?
  16. If a decoder has n inputs, how many outputs does it have?
  17. What is a page table?
  18. Assume we have 32 bit addresses and a page size of 8K bytes. Mow many entries can the page table contain?
  19. What floating-point number does 0xC2078000 represent when interpreted as a sinlge precision IEEE floating-point number? Express your answer in decimal. You must show work to receive credit.
  20. What is a page fault?
  21. Is the cycle time of the pipelined MIPS more or less than the cycle time of the single cycle MIPS? Explain your answer in one sentence.
  22. Name four problems virtual memory solves.
  23. Are memory accesses in a system with virtual memory faster or slower than in a system without virtual memory? Briefly explain your answer. Describe one technique used to address performance problems in virtual memory.
  24. Consider the single cycle MIPS datapath on page 322 of the book. What instruction(s) would not work if the MemToReg control line between the main control unit and the Mux was stuck-at-0?
  25. Suppose a program has a miss rate of 6% for data accesses and 4% for instruction accesses; a miss penalty of 40 cycles; the frequency of lw/sw instructions is 35%; a CPI of 2 if the cache's hit ratio was 100%. What is the speedup for this program with a system that has a cache over a system that has no caches at all?
  26. Consider the following MIPS code fragment 
    lw $t3, 0($t0)    ; instruction 1
add $t3, $t3, $t3 ; instruction 2
sw $t3, 0($t0)    ; instruction 3
    1. List all of the dependencies above by describing where the depenencies occur, on which registers, and the kind of dependency.
    2. Which dependencies result in a stall in the five stage MIPS pipeline that has EXE forwarding.
  27. Consider a direct mapped cache with 2K blocks, four words per block, and 32-bit addresses. Also assume that addresses must be on a word boundary and that a word is four-bytes.
    1. Show how the bits in an address determine which word in the cache the address maps to.
    2. Which block and word in the block does the address 0x0F0FB004 map to?
    3. What is the size of the cache in the total number of bits?
  28. Explain the purpose of a TLB and why all modern processors have them.
  29. Do problems 6.3.1 and 6.3.3.
  30. Do problems 6.14.1, 6.15.1, 6.15.2, 6.15.4

I/O - Polling and Interrupts (we might not get here)

Explain the concept of memory mapped I/O.

Do problems 6.9.1 and 6.9.2.

Explain the difference between an exception and an interrupt?

Write a short MIPS instruction sequence that causes an exception for exception codes 4,5, and 12.

Why does the exception handler not use the stack to save and restore registers that it uses?

On the MIPS we use the stack to implement recursive functions and to save and restore registers. Why don't we require a stack for the exception handler?