ENEE350H - Fall, 2004

Homework 4

(Due in class on Tuesday, October 26)

1. A machine supports 16 bit instructions and has 32 general purpose registers. The machine supports the following types of instructions:

·         60 instructions with two register fields

·         30 instructions with one register field

·         3 instructions with a 10 bit immediate field

·         26 instructions with no operands

(a)  Is it possible to design an instruction word format for this machine without expanding opcodes?  If so, give a design.  If not, give a reason why such a design is not possible.  (A design without expanding opcodes is where the entire opcode for all instructions is in a single length-invariant opcode field.)

(b)  Design an instruction word format for this machine using expanding opcodes.  For each of the four types of instructions, draw the 16-bit instruction; divide it among its components; label each with name and number of bits; and specify the particular opcode combination numbers for each. (The choice of combinations to use is yours).

(c)  How many more instructions with no operands could this machine support?

(d)  Suppose you need the machine to support one instruction with three register fields. Since there is not enough room in the instruction word for this new instruction, you must reduce the number of instructions currently supported. Suppose you can only afford to reduce the number of instructions of one particular type. Which type must you choose and what are the new (reduced) number of instructions of that type?

2. A possible reduced instruction set machine might support the following instructions:

·         NAND rd, rs, rt

·         LUI rd, imm

·         LW rd, (rt)

·         SW rs, (rt)

·         LLI rd, imm

·         JALR rd, rs

Suppose that this machine has 8 general purpose registers. Also suppose that the immediate operand fields on LUI and LLI can hold any integer from -128 to 127. The width of the opcode field is the same for every instruction.

LUI (load upper immediate) and LLI (load lower immediate) allow an immediate number to be loaded into a register. LUI loads the immediate number into the exact upper half of the register specified by rd while LLI loads the immediate number into the exact lower half of rd. Assume that no instructions beside LUI and LLI are needed to get an immediate number into a register, and assume that the immediate field is the same size in LLI and LUI.

(a)  Ignoring BEQ, how many bits are needed in the instruction word to support all of these instructions?

(b)  If the instruction word is to contain as few bits as possible, how many bits is the BEQ instruction's address field? Assuming that BEQ uses relative addressing, how many instructions ahead can it branch to? (Consider that BEQ can branch backwards as well as forwards and assume that the BEQ PC-relative displacement value is the number of instructions of displacement.).

(c)  How many bits are stored in each general purpose register?

(d)  If LW and SW use register indirect addressing, how many addresses can this machine index?

3. Consider the following recursive C function:

main(){

printf("2 to the power of 5 is %d", two-power(5));

}

int two-power(int n)

{

if (n ==0)

return(1);

else

return(2 * two-power(n-1));

}

(a)  Draw a representation of the stack frame for two-power(). Show what each field is intended to hold (by name).

(b)  Write a DLX assembly program to implement the C program.

• Printout of the .s file (assembly program) you wrote.

• Printout of a dlxsim session of your program running for a call to two-power(5) from main().  To do so, you could cut and paste a transcript of the session into your favourite editor, eg. Emacs or vi, and then print it out.

• Print out another dlxsim session of your program for a call to two-power(12) from main(), but this time, also use DLXSIM to tell you statistics on the program.  Use the "stats" command with the "all" option in DLXSIM to do so.  On your printout, highlight or circle the total number of cycles your program took to execute.

(Useful references:

• Look at how the stack is addressed and grown in DLX assembly programs by looking at the examples in the ~/dlx/test/ directory.

• Use the instructions on the class website for how to use the DLX software and its documentation, just like in homework 1.

• A discussion on the fundamentals of the stack is in section 5.6.2 of the textbook).