## Department of Electrical and Computer Engineering

### The University of Texas at Austin

EE 360N, Spring 2007
Problem Set 1a
Due: before class January 29th, 2007
Yale N. Patt, Instructor
Chang Joo Lee, Rustam Miftakhutdinov, Poorna Samanta, TAs

## Instructions

You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set turned back to you.

You will need to refer to the assembly language handouts and the LC-3b ISA on the course website.

## Questions

1. Briefly explain the difference between the microarchitecture level and the ISA level in the transformation hierarchy. What information does the compiler need to know about the microarchitecture of the machine for which it's compiling code?

Classify the following attributes of LC-3b as either a property of its microarchitecture or ISA:

1. There is no subtract instruction in LC-3b.
2. The ALU of LC-3b does not have a subtract unit.
3. LC-3b has three condition code bits (n, z, and p).
4. The n, z, and p bits are stored in three 1-bit registers.
5. A 5-bit immediate can be specified in an `ADD` instruction
6. It takes n cycles to execute an `ADD` instruction.
7. There are 8 general purpose registers used by operate, data movement and control instructions.
8. The registers MDR (Memory Data Register) and MAR (Memory Address Register) are used for Loads and Stores.
9. A 2-to-1 mux feeds one of the inputs to ALU.
10. The register file has one input and two output ports.
2. Both of the following programs cause the value `x0004` to be stored in location `x3000`, but they do so at different times. Explain the difference.

1. First program:
``````      .ORIG x3000
.FILL x0004
.END``````
2. Second program:
``````      .ORIG x4000
AND R0, R0, #0
LEA R1, A
LDW R1, R1, #0
STW R0, R1, #0
HALT
A     .FILL x3000
.END``````
3. Classify the LC-3b instructions into Operate, Data Movement, or Control instructions.

4. At location `x3E00`, we would like to put an instruction that does nothing. Many ISAs actually have an opcode devoted to doing nothing. It is usually called NOP, for NO OPERATION. The instruction is fetched, decoded, and executed. The execution phase is to do nothing! Which of the following three instructions could be used for NOP and have the program still work correctly?

1. `0001 001 001 1 00000`
2. `0000 111 000000010`
3. `0000 000 000000000`

What does the `ADD` instruction do that the others do not do?

5. Consider the following possibilities for saving the return address of a subroutine:

1. In a processor register.
2. In a memory location associated with the subroutine. A different memory location is used for each different subroutine.
3. On a stack.

Which of these possibilities supports subroutine nesting, and which supports subroutine recursion (that is, a subroutine that calls itself)?

6. A small section of byte-addressable memory is given below:

`x1005` `x0A`
`x1004` `x0B`
`x1003` `x0C`
`x1002` `x11`
`x1001` `x1A`
`x1000` `x0E`
`x0FFF` `x25`
`x0FFE` `xA2`

Add the 16-bit two's complement numbers specified by addresses `x1000` and `x1002` if

1. the ISA specifies a little-endian format
2. the ISA specifies a big-endian format
7. Say we have 32 megabytes of storage, calculate the number of bits required to address a location if

3. the ISA is 128-bit addressable
8. A zero-address machine is a stack-based machine where all operations are done using values stored on the operand stack. For this problem, you may assume that its ISA allows the following operations:

• `PUSH M` - pushes the value stored at memory location M onto the operand stack.
• `POP M` - pops the operand stack and stores the value into memory location M.
• `OP` - Pops two values off the operand stack, performs the binary operation OP on the two values, and pushes the result back onto the operand stack.

Note: To compute A - B with a stack machine, the following sequence of operations are necessary: `PUSH A`, `PUSH B`, `SUB`. After execution of `SUB`, A and B would no longer be on the stack, but the value A-B would be at the top of the stack.

A one-address machine uses an accumulator in order to perform computations. For this problem, you may assume that its ISA allows the following operations:

• `LOAD M` - Loads the value stored at memory location M onto the accumulator.
• `STORE M` - Stores the accumulator value into Memory Location M.
• `OP M` - Performs the binary operation OP on the value stored at memory location M and the value present in the accumulator. The result is stored back in the accumulator (ACCUM = ACCUM OP M).

A two-address machine takes two sources, performs an operation on these sources and stores the result back into one of the sources. For this problem, you may assume that its ISA allows the following operation:

• `OP M1, M2` - Performs a binary operation OP on the values stored at memory locations M1 and M2 and stores the result back into memory location M1 (M1 = M1 OP M2).

Note 1: `OP` can be `ADD`, `SUB` or `MUL` for the purposes of this problem.

Note 2: A, B, C, D, E and X refer to memory locations and can be also used to store temporary results.

1. Write the assembly language code for calculating the expression (do not simplify the expression):

X = (A + (B × C)) × (D - (E + (D × C)))
4. In a three-address machine like the LC-3b, but which can do memory to memory operations and also has a `MUL` instruction.

9. The following table gives the format of the instructions for the LC-1b computer that has 8 opcodes.

Opcode76543210
AND 001DRASR
BR(R)010NZ PTR
LDImm011signed immediate
LEA 100signed offset
LD 101DR0TR
ST 110SR0TR
NOT 111DR000

Notes:

• Interpretation of all instructions is similar to that of the LC-3b, unless specifically stated otherwise.
• The destination register for the instructions `LDImm` and `LEA` is always register R0. (e.g. `LDImm #12` loads decimal 12 to register R0.)
• TR stands for Target Register. In the case of the conditional branch instruction `BR`, it contains the target address of the branch. In the case of `LD`, it contains the address of the source of the load. In the case of `ST`, it contains the address of the destination of the load.
• `ADD` and `AND` provide immediate addressing by means of a steering bit, bit[2], labeled A. If A is 0, the second source operand is obtained from SR. If A is 1, the second source operand is obtained by sign-extending bits[1:0] of the instruction. A bit is called a “steering” bit if its value “steers” the interpretation of other bits (instruction bits 1:0 in this case).
• Bits labeled 0 must be zero in the encoding of the instruction.
1. What kind of machine (n-address) does the above ISA specification represent?
2. How many general purpose registers does the machine have?
3. Using the above instructions, write the assembly code to implement a register to register mov operation.
4. How can we make a PC-relative branch? (HINT: You will need more than one LC-1b instruction)