CS 208: Computer Organization and Architecture

Final exam, due on paper or via e-mail as a PDF by 5:00PM Monday, November 21, 2011.

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, state your assumptions, show your work, etc. Have fun.

1. (10 points) Do Exercise 4.13, parts 1 through 4, from pages 420-421 of your textbook. Use the instructions and times labeled "a" only.

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

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

• A 16-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.

1. Draw a diagram of the cache. How many bits of memory does it use? (Please do not include or concern yourself with showing the memory required to implement the least-recently-used eviction strategy.)

2. Suppose the byte located at each of the following addresses is requested in the indicated order:

   55, 48, 60, 56, 121, 129, 120, 572, 580, 60, 306, 310, 55, 573, 55

   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 byte addresses 56-63, just write "[56-63]" in the data field (since you have no way of knowing what data is actually stored in addresses 56-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. (2 points) To complete my education via 2-point exam questions...how about a recommendation for some music to listen to?

4. (14 points) Some questions about instruction set design.

   1. Modern instruction sets are designed in part to support features needed by high-level programming languages and operating systems, such as function-calling and virtual memory. Give at least three examples of features built into the MIPS instruction set that are meant to support these higher-level features.

   2. The Intel 80x86 instruction set has a collection of "string" instructions that are used to perform operations on arrays of bytes. The "REP MOVS" instruction, for example, can be used to copy a block of memory from one location to another.

      If you want to tell the CPU to copy a block of data from one place to another, what information do you need to provide up front? With this in mind, use on-line Intel assembly language references to describe what programmers have to do before executing the REP MOVS instruction.

   3. Suppose you wanted to add a string copy operation "movs" analagous to REP MOVS to the MIPS instruction set. Which instruction format (R, I, or J) would you use for for your movs instruction, and why? What would each of the fields mean?

   4. If you wanted to add your movs instruction to the datapath from Figure 4.17 of your textbook, what would you need to modify? Describe your modifications in enough detail that I would be able to carry out the changes myself. (Drawings of the modified datapath and modified control might be helpful.)