COMPUTER ORGANIZATION                     October 10, 2002

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

 

 

DUE

THURSDAY, OCTOBER 31st, 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: kdunn@cs.columbia.edu or am2104@columbia.edu.

 

 

1. (20 points): Patterson and Hennessy Exercise 4.57.

 

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

 

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

 

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

 

5. (15 points): Patterson and Hennessy Exercise 5.12.

 

6. (40 points): MIPS Single-Clock Cycle Implementation. In class, we covered a MIPS single-clock cycle implementation which handled “core” MIPS instructions: R-type (add, sub, and, or, slt), memory-reference (lw,sw), conditional branch (beq) and jump (j). In this problem, we will add a PowerPC-style function to the MIPS single-cycle datapath.

 

This function is storeword-and-autoincrement, which we shall write in assembly language as “sw+”. This function is useful if we have to store many elements in an array and have to run through it quickly. It stores a word just like “sw” does, but also increments the address register to the next word in the same single instruction. For example, the following command

          sw+ $8,0($9)

will store the current value of register $8 into the memory location pointed to by register $9 (plus the offset 0). It will then increment the address in register $9 by 4 to point to the next word in memory. Thus, the “sw+” instruction is equivalent to the two MIPS instructions:

          sw $8,0($9)

          addi $9,$9,4

The “sw+” instruction always increments the address register by 4 (not a variable amount). Also, it need not have 0 as the offset, we could have just as easily said:

          sw+ $8,40($9)

which is equivalent to:

          sw $8,40($9)

          addi $9,$9,4

 

We would like to include this as another single instruction in the single-cycle implementation so both the “sw” and the “addi” should occur in parallel in the same clock cycle (as is the case for all single-cycle datapaths we have seen). Assume that “sw+” has the same instruction format as “sw” but a different opcode (so that the machine can distinguish the two). Modify the single-cycle datapath and the control circuits from what we had in class (i.e. near the end of section 5.3 in the text) right before we added the “jump” instruction. In other words, assume we have the datapath in Figure 5.26 which implements R-types, lw, sw and beq (not jump). Modify this datapath to implement the “sw+” instruction. In particular, do the following:

 

(a)   Add any necessary datapath and control signals to the single-clock cycle datapath to implement sw+. Either mark changes clearly and readably to a photocopy of Figure 5.26 or draw your own figure with changes on a blank sheet. Please write clearly and label all changes. For full credit, don’t use extra hardware (such as ALUs, adders, register files or memory). Simple gates, wires and multiplexors can be used freely. The less hardware your design has, the less ‘expensive’ it is to build and the more credit you will get.

 

(b)   Show the additions to the Main Control Table in Figure 5.20 in the text. You don’t need to worry about the gate design or the actual opcodes for “sw+”. You only need to list an extra row entry in the Main Control Table for “sw+”. You don’t need to update the control lines for the other instructions. Set all control lines, including the 9 already in the table (RegDst,ALUSrc, etc.) and any extra control lines that you need for your design. Be sure to mark “don’t-cares” whenever possible.

 

7. (5 points): Patterson and Hennessy Exercise 2.10.

 

8. (10 points): Patterson and Hennessy Exercise 2.11.

 

9. (10 points): Patterson and Hennessy Exercise 2.18.

 

10. (10 points): Patterson and Hennessy Exercise 2.43. Read section on p.101 first and read exercise 2.41 to see the context.

 

11. (5 points): Patterson and Hennessy Exercise 2.44. Read section on p. 101 first.