CS 208: Computer Organization and Architecture

Midterm exam, due on paper at 8:30AM Friday, October 12, 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. Integers (8 points)

    1. What is the base-ten equivalent of the 32-bit two's complement integer 0xFFFCBBBB?
    2. In base ten, what is the value of the largest 32-bit two's complement integer?
    3. In base ten, what is the value of the smallest 32-bit two's complement integer? (Note that "smallest" and "largest" refer to position on the number line so, for example, -2 is smaller than 3.)
    4. If you have a 32-bit two's complement integer N > 0, and 2*N is small enough to be representable as a 32-bit two's complement integer, then you can double N by shifting its two's complement representation left by one bit. Now, suppose N < 0. Does shifting left double N? If so, explain why. If not, give an example where it fails.

  2. Pseudo-instructions (10 points)

    Chapter 2 of your textbook discusses pseudo-instructions in the MIPS assembly language.

    1. Briefly explain the difference between instructions and pseudo-instructions.
    2. What role does the MIPS register $at play in the assembly of pseudo-instructions? (Don't forget that "assembly" is a technical term in this context, referring to the translation of assembly language instructions into machine language instructions.)

    3. Suppose you were sick of the PDP-8 having only one register, and you wanted to add pseudo-instructions to PAL to create the illusion of a second accumulator. Suppose you enhanced the assembly language by adding TAD2 and DCA2 pseudo-instructions to allow you to move data in and out of an "AC2". (You could also create AND2, CMA2, RAL2, etc., but for the purposes of this exam question, let's stick with TAD2 and DCA2.)

      Explain in detail how you would go about adding these pseudo-instructions to a PAL assembler. In particular, to what instruction sequences would your assembler translate TAD2 and DCA2? Also, how would you arrange for the equivalent of $at (assuming you need such a thing) without actually modifying the hardware?

  3. What stuff goes into a machine language, and why? (10 points)

    1. The PDP-8 instruction set enables you to do bitwise AND operations with words in memory and the AC using the AND memory reference instruction. Does it also allow you to do bitwise NOT and OR instructions? (Hint: yes.) If so, how? (Hint: OSR cannot be used to perform ORs on words stored in memory, so that's not it.)
    2. The PDP-8 instruction set includes arithmetic (e.g. TAD), logic (e.g. AND), loading and storing (TAD and DCA), and basic flow of control (JMP and the various conditional skip instructions). In addition to these essential basics, the instruction set provides extra support for writing loops efficiently. Identify those parts of the instruction set designed particularly to make it easy to loop.
    3. More sophisticated instruction sets than that of the PDP-8 always include features that make it easy for compilers to generate function-calling code. That is, there are features that make it relatively easy to create and tear down stack frames, and to move data in and out of the stack frames. Briefly discuss all the features of MIPS that are designed especially with the manipulation of stack frames in mind.

  4. Free points (2 points). I just finished a book (The Yiddish Policemen's Union, by Michael Chabon--it was quite good). What should I read next?

  5. Digital Logic (8 points)

    1. Consider the following boolean function of three variables:

      
             A   B   C  | Out
            =================
             0   0   0  |  1
             0   0   1  |  1
             0   1   0  |  0
             0   1   1  |  1
             1   0   0  |  1
             1   0   1  |  0
             1   1   0  |  1
             1   1   1  |  0

      • Write a boolean algebraic expression for this function, using a conjunction (sum) of 3-term products, as we did with a similar function in class.
      • Simplify your algebraic expression as much as possible.
      • Draw a circuit implementing this function using AND, OR, and NOT gates. Use as few gates you can.
    2. Suppose I gave you two 4-choice 1-bit multiplexors plus a pile of miscellaneous AND, OR, and NOT gates. Draw a diagram showing how you could combine the 4-choice multiplexors to create one 8-choice 1-bit multiplexor.