COMPUTER ORGANIZATION October 31, 2002

WC3824-001 (CSEE) HOMEWORK #5
PROF. TONY JEBARA

DUE	THURSDAY, NOVEMBER 14^th, 2002 AT BEGINNING OF CLASS

Please use the class newsgroup (bulletin board) for questions, updates, clarifications, and corrections related to the homework. It is linked off of the class home page: http://www.cs.columbia.edu/~jebara/3824. As a second resort, you can also email a TA directly: am2104@columbia.edu or djh44@columbia.edu.

For the following questions, please look at the ‘guidelines’ right after for suggestions on solving them (whenever relevant).

1. (15 points): Patterson and Hennessy Exercise 5.15.

2. (5 points): Patterson and Hennessy Exercise 5.16.

3. (15 points): Patterson and Hennessy Exercise 5.20.

4. (15 points): Patterson and Hennessy Exercise 5.24.

5. (20 points): Patterson and Hennessy Exercise 5.26.

6. (30 points): Patterson and Hennessy Exercise 5.27.

7. (15 points): Patterson and Hennessy Exercise 5.29.

Guidelines:

· When adding new instructions, do not break the operation of standard ones.

· Avoid adding ALUs, adders, Register Files, or Memories to the datapath.

· You can add components like MUXes, shifters, etc. but try to do so sparingly.

· Avoid lengthening the basic cycle time significantly over the text’s design.

· In the IF step, assume each instruction fetch from Memory takes most of the cycle time. Do not add any operations after the instruction is read from Memory and before it is written to IR.

· In the ALU step, assume that the ALU takes most of the cycle time. Do not do an ALU operation followed by a Register Write (of the ALU result), or followed by a Memory Read/Write in the same cycle.

· In the IF/ID Main Control step: Note that in the ID step, the Main Control outputs are always the same, regardless of instruction! Similarly, in IF step, the outputs are always the same. Do not try to write several different IF or ID states that depend on the instruction, it is illegal because the instruction needs to be decoded before you can take action on what it is.

· In the ID step, Main Control simply computes the correct next-state; that is, it determines the new state which the machine will go to for the next cycle, EX. Since this new state depends on the opcode, therefore, finally in EX, the machine may be in a different state, depending on the actual instruction. That is, for each type of instruction, there can be a distinct EX state in the diagram; each state can have its own unique control signals (Main Control outputs), which control the unique set of operations for the given instruction.

· As an example, for a jump instruction, you might want jump to occur after 2 cycles but it cannot: the correct control signals for jump, PCWrite=1 and PCSource=10 (jump control signals), can only be set in the EX cycle after the jump is decoded (in the ID step). If you set these signals in ID, then they would also be set for every other instruction in ID because you don’t know it is a jump instruction that early on.