COMPUTER ORGANIZATION November 14, 2002

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

DUE	TUESDAY, NOVEMBER 26^th, 2002 IN CLASS -- or -- UNDER MY DOOR IN MY OFFICE CEPSR 605, BY WEDNESDAY, NOVEMBER 27^th, 2002 BEFORE 12 NOON.

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, djh44@columbia.edu or ah679@columbia.edu.

1. (5 points): Patterson and Hennessy Exercise 6.3.

2. (5 points): Patterson and Hennessy Exercise 6.5. Make sure to: (i) label all fields in the pipeline registers, (ii) indicate the length of each field in each pipeline register (number of bits) and (iii) indicate the total length of each pipeline register (number of bits).

3. (20 points): Patterson and Hennessy Exercise 6.9.

4. (20 points): Patterson and Hennessy Exercise 6.20.

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

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

7. (35 points): Adding the CIB instruction to the pipelined datapath. The cib instruction does the following 3 operations in a single instruction: comparison, increment and branch. The cib instruction compares two registers and branches if one is less than the other, it then increments the index after (or during) the comparison. As an example consider:

cib $19, $20, Loop

The above does the following. It compares $19 and $20 (or whatever other rs/rt registers are specified). If $19 < $20, then it branches to Loop; if not, it does not branch. Finally, in either case, it increments $19 by 1, i.e. $19=$19+1. Note that the comparison is made using the old value of $19, not the incremented value of $19. Also, note that only one register in the Register File is written (in this example, $19).

Instruction Format. Assume that cib has an I-type instruction format:

opcode	rs	rt	immediate
Bits 31-26	Bits 25-21	Bits 20-16	Bits 15-0

Note that the register to be written is rt. Therefore, in the above particular example, $19 is rt (not rs!), and $20 is rs. (Be careful with this reversal!). Also, note that the instruction uses PC-relative addressing, so the 16-bit immediate field is used to calculate the address of the Loop to branch to, in the same way as it would be done in beq. Finally, assume that cib has its own unique opcode.

Rules. You are allowed to add 1 new Adder, if you want. But avoid adding any ALUs, memories or register files (which will cost you credit). As usual, you can add other small components like MUXes, special registers, etc. free of charge.

Hints. You may need to modify the ALU Control. If you do, clearly show your modifications to Figure 5.15 and explain why you made your modifications.

What to Do:

(a) (30 points) Starting with Figures 6.28 and 6.30, show modifications to both the datapath and control to implement the cib instruction in the pipelined MIPS processor. In particular, (i) indicate all changes on the datapath of Figure 6.30, (ii) indicate changes to the control of Figure 6.28 (and Figure 5.15 if necessary as in the Hints section above), and (iii) indicate which operations are performed in each pipeline stage, for cib, in your new implementation.

Note: In this problem, you can ignore issues of data hazards and branch hazards. In particular, assume that the pipeline always stalls until cib determines whether to branch.

(b) (5 points) Assuming your above implementation, will a correctly incremented result always be written into rt in the WB stage, even when cib has a branch taken? Give a clear 1-3 sentence answer and justification.