This is an exam. If you have questions, you may consult books, the Internet, or Jeff Ondich, but not anybody else.

Have fun.

1. (8 points) If you watch a 7-line digital display (the kind that displays a single digit on a digital clock), you will see that the bottom line lights up when the display is showing a 0, 2, 3, 5, 6, 8, or 9, and does not light up for 1, 4, or 7.

   Design a circuit that takes a 4-bit number as input and produces 1 bit of output. For input values between 0 and 9 (i.e. 0000 through 1001), the output should be a 1 if the bottom line of the corresponding 7-line display should be lit, and 0 otherwise. So, for example, if the input is 0010, the output should be 1 because the bottom line of a 7-line display is lit when the display is showing a 2. For input values between 10 and 15 (i.e. 1010 through 1111), it does not matter what your output value is.

   Design your circuit to be as simple as possible.

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

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

   • A 4-entry 4-way set associative cache with 1-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 much memory does it use?

   • If the contents of the following addresses are requested in the indicated order, what words are in which entries at the end, and what is the hit ratio? Assume the cache starts out empty.

     16, 17, 20, 32, 36, 98, 50, 56, 81, 33, 34, 96

     Note that these addresses are byte addresses--so byte 3 is contained in the word starting at address 0. Also, indicate a word by writing out its byte range (so the word starting at address 52, for example, would be written as "52-55").

3. (5 points) Consider the datapath shown in Figure 5.22. Show how you would modify this datapath to enable it to support the BNE instruction. Would you need to modify the control as well? If not, why not? If so, how?

4. (3 points) Those jokes were awful. Let's try this instead: please recommend a book for me to read.

5. (16 points) John von Neumann's "First Draft of a Report on the EDVAC." I will give you a copy of the first ten pages of von Neumann's report on Wednesday in class. Read it and answer the following questions.

   • Patterson and Hennessy discuss von Neumann's report in Chapter 1 of your textbook. They note that the report was one of several things that attorneys used to break the Mauchly/Eckert patent on the computer. What besides this report was relevant in the patent case?

   • Throughout the report, von Neumann refers to the main subdivisions of a computing system as CA, CC, I, O, R, and M. To what modern concepts do these six subdivisions refer?

   • Section 1.2 refers to several mechanisms by which program instructions may be stored. Name a mechanism used in modern computing systems that is not contained in von Neumann's list.

   • [Don't use this question again.] Explain briefly in modern terms what 1.3 is about.

   • There is a sentence in section 2.9 that begins with "As to (h) (sorting and statistics), the situation is somewhat ambiguous...." This sentence hints at the subject of one of the chapters in Patterson and Hennessy. Which chapter?

   • Summarize von Neumann's arguments in favor of binary rather than decimal computation. Are these arguments still valid?

   • Why does von Neumann like vacuum tubes?

   • [Reformulate] Consider the last paragraph of section 5.6. How does it compare to the principles articulated by the designers of RISC architectures?