CS 208: Computer Organization and Architecture

Final exam, due on paper by 5:00PM Monday, November 19, 2007.

This is a an exam. You may consult your notes, any book, and the Internet. You may not speak with any person other than Jeff Ondich, electronically or otherwise, about the content of this exam. If you obtain relevant information from any source other than yourself, cite your sources clearly. Justify your answers. (Note that "justify your answers" implies "show your work.") Have fun.

1. (10 points) Do problems 6.17, 6.18, and 6.19 on page 456 of Patterson and Hennessy. The best justification for your answers would involve a diagram of the relevant datapath, with appropriate labeling and explanation. In any case, don't just give me answers--give me justification as well.

2. (10 points) Consider the following caches, each of which can hold up to sixty-four 32-bit words of data. Assume that addresses are 32 bits long.

• A 16-entry direct-mapped cache with 4-word blocks.

• A 8-set 4-way set associative cache with 2-word blocks, using a "least recently used" strategy for choosing which block to evict.

For each of these caches, answer the following questions.

• Draw a diagram of the cache. How many bytes of memory does it use?

• Suppose the contents of the following addresses are requested in the indicated order:

  45, 48, 52, 56, 123, 129, 76, 250, 185, 186, 251, 306, 53, 310

  Once this sequence of requests is finished:

  • Show a diagram of the contents of the cache. This diagram should show the valid, tag, and data values for each cache entry. For the data, just show the addresses of the bytes that are stored. For example, if a cache entry contains the data from addresses 60-63, just write "60-63" in the data field (since you have no way of knowing what data is actually stored in addresses 60-63).
  • Report the hit ratio for this sequence of requests.

  Notes: (1) These addresses are byte addresses--so byte 3 is contained in the word starting at address 0. (2) These hit ratios are very low, both because the caches start out empty, and because I have made no effort to make my numbers adhere to the principles of spacial or temporal locality.

3. (20 points) Building a datapath

   Suppose you have an anemometer that reports wind speed as a 16-bit non-negative integer (the leftmost bit is always 0--wasteful, but it will make your job easier, since you'll be able to treat all 16-bit integers as signed), continuously transmitted over a 16-bit line coming from the device. Suppose further that you have a two-character display, capable of displaying any two ASCII characters, represented as 8-bit bytes sent to the display over another 16 wires.

   In addition to the anemometer and the display, you have a small machine/assembly-language architecture. It consists of:

   • 8 16-bit registers named R0 through R7,
   • a program counter PC, and
   • an instruction memory of as many 28-bit instruction words as you need.

   Each instruction has the format:

   op code [3 bits] destination register number D [3 bits] first operand register number A [3 bits] second operand register number B [3 bits] immediate data N [16 bits]

   Register R0 takes input from the anemometer (see LOAD below). Register R1's contents are wired directly to the display, so whatever characters you put into R1 appears immediately on the display.

   The op-codes are as follows.

   • Op-code 000: LOAD. R0 = current anemometer value.
   • Op-code 001: ADD D, A, B, N. Sets RD = RA + RB + N.
   • Op-code 010: SUB D, A, B, N. Sets RD = RA - RB + N.
   • Op-code 011: BLT A, B, N. if( A < B ) PC = PC + N.
   • Op-code 100: BEQ A, B, N. if( A == B ) PC = PC + N.
   • Op-code 101: BR N. PC = PC + N.

   Here's an example program, that puts "UP" on the display if the wind speed is rising, and "DN" in the display otherwise. (By "rising," I mean in the most trivial sense--that is, the most recent measurement is higher than the measurement before it--in reality, you would want to write a more sophisticated program.)

   // Initialize R2 SUB R2, R2, R2, 0 // Now loop forever. // Get the next measurement. LOAD // Modify the display, depending on the two most recent measurements. BLT R0, R2, 3 SUB R1, R1, R1, 01010101 01010000 [ASCII for "UP"] BR 2 SUB R1, R1, R1, 01000101 01001110 [ASCII for "DN"] // Wait for a while, and then loop back up to the LOAD instruction. // I'm assuming for this example a 15KHz clock, for which this delay loop // will take about 1 second. SUB R3, R3, R3, -5000 SUB R4, R4, R4, 0 BEQ R3, R4, -7 ADD R3, R3, R4, 1 BR -2

   Here's your job. Design a datapath and control to implement this machine architecture. Hand in a drawing of the datapath, a chart showing how op-codes would map to control values, and any explanations you deem appropriate.