CS 208: Computer Organization and Architecture

Midterm exam, due on paper at 8:30AM Wednesday, November 7, 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) Consider the multi-cycle datapath shown in Figure 5.28 in Patterson and Hennessy. Suppose the PC starts with the value 50000, the instruction at location 50000 of memory is "beq $4, $5, -24", and the contents of registers $4 and $5 are 750 and 750, respectively. Suppose further that we have executed this instruction up through the very end of its third clock cycle, but that the clock has not yet fallen to end the third cycle and begin the fourth. Print Figure 5.28 and show the values of as many lines on the datapath as possible. This includes control lines, lines whose values are used during this cycle, lines whose values are not used during this cycle, lines whose values are left over from old cycles, etc.

2. (8 points) Still using Figure 5.28, suppose the propagation delays of the various elements are: 12 ns for memory, 14 ns for the ALU, 3 ns for the registers, 4 ns for the Control, 4 ns for the ALU Control, 2 ns for each of the multiplexors, 1 ns for the shift left, 1 ns for the sign extend, and 1 ns for individual gates. Also, assume that the memory elements IR, PC, A, B, Memory data register, and ALUOut show the proper output 1 ns after the trailing clock edge (assuming the appropriate write-enable lines are set).

   Consider the beq instruction of the previous problem. For each of the three clock cycles it takes to complete this instruction, what amount of time is required to complete that cycle's work? Based only on beq, then, what is the fastest allowable clock rate?

3. (12 points) UTF-8 and UTF-16.

   1. What are UTF-8 and UTF-16?
   2. Who invented UTF-8, and when?
   3. What is the Unicode value for the lowercase alpha in the Greek alphabet?
   4. What is the UTF-8 representation of the lowercase alpha?
   5. What is the UTF-16 representation of the lowercase alpha?
   6. Suppose you were receiving a stream of UTF-8 characters and the stream got corrupted briefly, and then started appearing correctly again, possibly in the middle of a character. Describe a procedure you could use to discard bytes until you were sure you were at the beginning of a new character.
   7. Suppose you were receiving UTF-16 characters instead of UTF-8 characters in the previous question? Could you reliably find the beginning of a character once the stream started arriving correctly after the outage? Why or why not?
   8. If you store UTF-8 characters in a file on a big-endian system, and the same characters on a little-endian system, will the order of bytes in the file differ? How about if you store UTF-16 characters?

4. (2 points) What's cool on the Internet these days?

5. (20 points) This part of the exam concerns the first few pages of John von Neumann's First Draft of a Report on the EDVAC. Read it and answer the following questions. For the first three questions, which concern the historical context of this report, you may need to look elsewhere for information.

   1. Patterson and Hennessy discuss von Neumann's report in section 1.7 of your textbook (on the CD). 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?

   2. Who besides von Neumann deserves credit for this report?

   3. During the 1940's, several women were heavily involved in the development and operation of the ENIAC. Name at least two of them, and briefly describe their roles in the project.

   4. Throughout the Draft 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?

   5. What does von Neumann means by the term elastic in section 2.3? He also advocates separating some things in the interests of elasticity. What does he want to separate, and how does this separation serve the goals of elasticity?

   6. 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?

   7. Clarify the first paragraph of section 4.1. You might find it handy to include an example or two using modern gate language.

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

   9. Why does von Neumann like vacuum tubes? (Vacuum tubes, by the way, are devices that can be used to perform switching operations like those done by transistors. Thus, you could build gates out of vacuum tubes. Vacuum tubes tended to burn out like light bulbs do, so it was common for drug stores and hardware stores to sell them. When I was a kid, our neighborhood drug store had a kiosk where you could bring in a burnt-out tube and stick it into the plugs on the kiosk to figure out which replacement tube would work. This was necessary if you wanted your TV to keep working.)

   10. Consider the last paragraph of section 5.6. In what ways is von Neumann's advice still valid, and in what ways is it not?