Final Examination

This is the final examination for CS63: Principles of Computer Organization, Fall Semester 1997, Ray Ontko, Department of Computer Science, Earlham College. This examination covers the material discussed in class or presented in the text, Andrew S. Tanenbaum, Structured Computer Organization, Third Edition (Prentice-Hall, 1990).

This examination attempts to assess the degree to which you have mastered the important material of the course, and the degree to which you are able to apply this mastery to problems in the discipline. It is NOT open book, and calculators are NOT permitted. You should be able to do all the problems in the text using pencil, paper, your imagination and intellect.

Please answer the questions below in the answer book provided. Clearly indicate the number of the question, any intermediate results or notations you make, and clearly indicate your answer to the problem by circling it if necessary. You need not do the problems in order.

NOTE: YOUR ANSWERS MUST BE GIVEN IN THE ANSWER BOOKLET, NOT ON THE EXAMINATION ITSELF. ANY MARKS ON THE EXAMINATION ITSELF WILL BE IGNORED.

Each question is weighted equally, so attempt to answer as many questions as possible. I strongly encourage you to take two or more passes through the test, answering those which you can quickly, and going back and answering those which require more thought in a subsequent pass. All examinations and answer booklets must be turned in at the end of the allotted time.

When you are done, please turn in the examination with your answer booklet.

[The solutions for this examination are now available online; feel free to use this as a study guide.]

Assume that you are creating a virtual machine with its own language. You have a choice between implementing the machine as an interpreter or a translator. List at least five design considerations that would help you chose between the two approaches. Indicate which of the two approaches would be a probable winner for each design consideration.

A certain instruction may be implemented in hardware or microcode on a machine which can complete a single microinstruction in about 10 nsec, and the average conventional machine instruction takes 100 nsec. The instruction occurs about 5% of the time in programs. If simulated using conventional machine instructions, approximately 20 instructions are required. If implemented in microcode, approximately 25 microinstructions will be required. If implemented in hardware, only 10 microinstructions are required to decode the instruction and activate the hardware which performs the work of the instruction almost instantaneously (i.e., without any additional microinstruction cycles). Use this information to answer the following two questions.
A test program takes 100 seconds to run when using the conventional machine instruction approach. How quickly will it run if the microprogrammed approach is used.
Another test program takes 50 seconds to run when using the conventional machine instruction approach. How quickly will it run if the enhanced hardware approach is used.
Convert 105 base 7 to its decimal, binary, and hexadecimal equivalents.
Convert 1023.0625 base 10 to its binary, octal, and hexadecimal equivalents.
Convert -1234 base 10 to its sixteen-bit one's complement binary equivalent.
Convert -2345 base 10 to its sixteen-bit two's complement binary equivalent.
Convert 10000001 from eight-bit one's complement to decimal.
Convert 10010011 from eight-bit two's complement to decimal.
Perform an eight-bit two's complement addition of 01101001 and 10001000.

In IEEE single-precision notation, there is a sign bit, an 8-bit radix 2 excess 127 exponent, and a 23-bit significand in which the leading 1 and binary point is implied for normalized numbers. Use this information to solve the next four problems.
Convert -129.0625, a decimal number, to a 32-bit hexadecimal representation of its IEEE single-precision floating point equivalent.
Convert CDB00000, a 32-bit hexadecimal representation of an IEEE single-precision floating point number, into its decimal equivalent.
Compute the SUM of the following IEEE single-precision floating point numbers and express the result as a decimal number: 3FC00000, 3FA00000.
Compute the PRODUCT of the following IEEE single-precision floating point numbers and express the result as a decimal number: BFD00000, BFB00000.

Consider a computer having 4-bit memory cells. Use this assumption to answer the following two questions.
How many bytes of memory can be accessed using a 16-bit address?
If a single memory cell were used to store a single symbol, how many different symbols could be represented by a cell?

A certain hard disk has 960 cylinders, 8 tracks, and 32 sectors of 512 bytes each. It spins at 6000 revolutions per minute, and has an adjacent cylinder seek time of 1 msec, and a max seek time of 100 msec. Switching between tracks in the same cylinder is instantaneous. Use this information to answer the following 4 questions.
What is the total available storage capacity of the disk?
What is the minimum worst-case time required to read all the data on the disk, starting with the first track of the first cylinder, reading all the tracks in that cylinder, advancing to the next cylinder, etc.?
How much bandwidth (Mbytes/second) would a bus need to keep up with this drive at its maximum sustained data rate? Round your answer to two significant digits.
How large a buffer would be needed to allow a complete cylinder to be stored to permit reading or writing to occur at top speed?
Compute the Hamming distance of the following code:
```
1000000011111110
0100000011111101
0010000011111011
0001000011110111
0000100011101111
0000010011011111
0000001010111111
0000000101111111
```
In a certain 7-bit even parity Hamming code, bit 0 (the low order bit) is a check bit for bits 0, 2, 4, and 6; bit 1 is a check bit for bits 1, 2, 5, 6; bit 3 is a check bit for bits 3, 4, 5, and 6; and all other bits are data bits (i.e., the low-order data bit appears in bit 2 of the Hamming code). Use this information to answer the following four questions.
Show the 7-bit, even parity Hamming code for 0.
Show the 7-bit, even parity Hamming code for 9.
Assuming a single-bit error has occured in the 7-bit, even parity Hamming code 1101101, what is the corrected 4-bit value?
Assuming a single-bit error has occured in the 7-bit, even parity Hamming code 0101100, what is the corrected 4-bit value?
How many seconds are required to transmit 700 Kbytes at 56,000 bits per second (synchronous)?
How many seconds are required to transmit 384 Kbytes at 19,200 bits per second (asynchronous)?
How many seconds are required to transmit 2 Kbytes at 110 bits per second (asynchronous)?

Use the diagram below to answer the following three questions.

Assume that each of the NAND gates depicted above is implemented directly (using the appropriate transistors and resistors) as a 3-input NAND or 4-input NAND, and not as a module containing several 2-input gates.
What common, useful function does the circuit compute?
Assuming a propagation delay of 5 nsec per gate, what is the maximum propagation delay for the circuit?
How many transistors are required (minimum) to implement the gates of the circuit?

An 8-input multiplexor chip has 8 data in pins (D0-D7), 3 selector pins (A0-A2), an output pin (F), and pins for ground and Vcc. This information applies to the following three questions.
Draw a logic circuit diagram which implements the function of the 8-input multiplexor chip. Use AND, OR, and NOT gates only.
A 8-input multiplexor chip can implement any 3-bit function by selectively connecting each of the 8-inputs to ground or Vcc. Draw a diagram showing the connections for an 8-input multiplexor chip implements a 3-bit parity function.
Explain how three 8-bit multiplexor chips can be used to compute the 3 check-bits in a 7-bit, even-parity Hamming code. Draw a rough sketch to help explain your design.
Explain the difference between a horizontal and vertical microarchitecture.
Explain the difference between nanoinstructions and microinstructions.
Explain why the data path of a machine typically includes a clock with multiple sub-cycles.

For the following three questions, assume that memory locations contain the values shown in the following table:
```
Location  Value
--------  -----
     100    150
     110    130
     120    110
     130    100
     140    120
     150    140
```
Suppose the instruction "load immediate 100" were encountered. What value would be loaded?
Suppose the instruction "load direct 100" were encountered. What value would be loaded?
Suppose the instruction "load indirect 100" were encountered. What value would be loaded?
What instructions and data structures are typically used to implement procedure calls and parameter passing at the conventional machine level?
You are designing a computer with 16 registers, and a 16-bit word size. Design an instruction set (using an expanding opcode) which provides the following: 6 3-operand instructions, 12 2-operand instructions, 15 1-operand instructions, and 16 0-operand instructions. Assume that all operands are register references, and that any register may be specified as any operand.

Consider the following infix assignment statement:
```
X := ((A-B)+((C-D)/E))*F
```
Use this statement to answer the following five questions.
Convert the infix expression to postfix notation.
Using two-operand instructions and no more than 4 registers (R0-R3), show the instructions required to implement the statement. Assume that MOVE A,B moves A to B, ADD A,B adds A to B, SUB A,B subtracts A from B, MUL A,B multiplies A times B, and DIV A,B divides A into B. In all cases, A or B can be a register or memory address, and the result is always stored in B.
Assuming each instruction takes 16 bits if only registers are referenced, and 16 additional bits for each memory reference, how many bytes long is your program?
Using 0-operand instructions on a stack-oriented machine, show the instructions required to implement the statement. Assume that PUSH A pushes the contents of location A onto the stack, ADD replaces A B with A + B, SUB replaces A B with A - B, MUL replaces A B with A * B, DIV replaces A B with A / B, SWAP replaces A B with B A, and POP A takes the top item off the stack and stores it to location A. (In the above, if A B are on the stack, consider B to be the top of the stack and A to be the one below.)
Assuming each instruction takes 8 bits for the opcode and 16 bits for a memory address, if any, how many bytes long is your program?
Expain the difference between an interrupt and a trap.
Explain the difference between a protection fault, segment fault, and page fault in virtual memory operations.
Why are assemblers typically implemented as two- or three-pass translators?
From the standpoint of a linker, what sections might you expect to find in a separately compiled module?

A certain RISC architecture uses overlapping register windows for passing parameters between procedures. The machine has 256 registers, and each window has 32 registers, of which 10 are global variables and 10 are local variables. Use this information to answer the following four questions.
How many registers would be available for use by input parameters?
How many registers would be available for use by output parameters?
By how much would the Current Window Poiner (CWP) be incremented at each procedure call?
How many call frames may be present in the register file?
SIMD occurs as an acronym in Flynn's taxonomy. What does it stand for? Give a brief description and an example.
MIMD occurs as an acronym in Flynn's taxonomy. What does it stand for? Give a brief description and an example.
You are designing a multiprocessor network with 1024 nodes using a hypercube interconnection scheme. Of what degree is the hypercube?