Homework 1

22C:122, Fall 1998

Due Monday Aug 30, 1999, in class

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

This assignment is dominated by review questions that are not as much specific to the material in the book as they are to material you should have learned in prior courses or work experience.

1. What is your E-mail address? (If you have more than one, give the address you'd prefer used for class purposes.)

2. Background: Look at the Preliminary discussion of the logical design of an electronic computing instrument, by Burks, Goldstine and von Neumann. This paper, first distributed in 1946, inspired the first generation of stored-program digital computers. Machines such as ORDVAC, ILLIAC I, MANIAC, JOHNNYIAC, and many others were designed to directly implement the ideas presented in this paper.

   The Problem: Focus exclusively on architecture, not on technology, and ignore questions of word-size and memory size. What ideas common to many modern computers are entirely missing from the machine described in this paper? All such architectural features can be correctly described as non-von-Newmann features!

3. Background: Consider an ALU able to perform add, subtract and a few other operations. Each bit in this ALU has a function described as follows:

        X  Y   A    B   Cin |   F  Cout
       ---------------------+------------
        0  0   0    0    0  |   0   0
        0  0   0    0    1  |   0   0
        0  0   0    1    0  |   1   0
        0  0   0    1    1  |   1   0
        0  0   1    0    0  |   1   0
        0  0   1    0    1  |   1   0
        0  0   1    1    0  |   0   0
        0  0   1    1    1  |   0   0
                            |
        0  1   0    0    0  |   0   0
        0  1   0    0    1  |   1   0
        0  1   0    1    0  |   1   0
        0  1   0    1    1  |   0   1
        0  1   1    0    0  |   1   0
        0  1   1    0    1  |   0   1
        0  1   1    1    0  |   0   1
        0  1   1    1    1  |   1   1
                            |
        1  0   0    0    0  |   1   0
        1  0   0    0    1  |   1   0
        1  0   0    1    0  |   0   0
        1  0   0    1    1  |   0   0
        1  0   1    0    0  |   0   0
        1  0   1    0    1  |   0   0
        1  0   1    1    0  |   1   0
        1  0   1    1    1  |   1   0
                            |
        1  1   0    0    0  |   1   0
        1  1   0    0    1  |   0   1
        1  1   0    1    0  |   0   1
        1  1   0    1    1  |   1   1
        1  1   1    0    0  |   0   0
        1  1   1    0    1  |   1   0
        1  1   1    1    0  |   1   0
        1  1   1    1    1  |   0   1
   

   Assume that 16 of these 1-bit units are combined to make a 16 bit ALU, where A and B are 16 bit words inputs, F is a 16 bit output, and the X and Y operation select inputs are sent to all 16 1-bit units. Cin to the least significant 1-bit unit is also a control input, and Cout from the most significant 1-bit unit is a 1-bit output. For all other cases, Cout of each 1-bit unit is connected to Cin of the next most significant 1-bit unit.

   The Problem: Give C expressions, of the form F = A (op) B (possibly with other terms) for each of the 8 possible operations this ALU performs.