Department of Electrical and Computer Engineering
The University of Texas at Austin
EE 360N, Fall 2004
Problem Set 1
Due: 8 September 2004, before class
Yale N. Patt, Instructor
Aater Suleman, Huzefa Sanjeliwala, and Dam Sunwoo, TAs
You will need to refer to the assembly language handouts and the LC-3b ISA on the course website.
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.
* The destination
register for the instructions LDImm and LEA is always register R0.
- 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:
- There is no subtract instruction in LC-3b.
- The ALU of LC-3b does not have a subtract unit.
- LC-3b has three condition code bits (n, z, and p).
- The n, z, and p bits are stored in three 1-bit regsiters.
- A 5-bit immediate can be specified in an ADD instruction
- It takes n cycles to execute an ADD instruction.
- There are 8 general purpose registers used by operate, data movement
and control instructions.
- The registers MDR and MAR are used for Loads and Stores to memory.
- A 2-to-1 mux feeds one of the inputs to ALU.
- The register file has one input and two output ports.
- 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.
AND R0, R0, #0
ADD R0, R0, #4
LEA R1, A
LDW R1, R1, #0
STW R0, R1, #0
A .FILL x3000
- Classify the LC-3b instructions into Operate,
Data Movement, or Control instructions.
- 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?
- 0001 001 001 1 00000
- 0000 111 000000010
- 0000 000 000000000
What does the ADD instruction do that the others do not do?
- Consider the following LC-3b assembly language program:
AND R5, R5, #0
AND R3, R3, #0
ADD R3, R3, #8
LEA R0, B
LDW R1, R0, #1
LDW R1, R1, #0
ADD R2, R1, #0
AGAIN ADD R2, R2, R2
ADD R3, R3, #-1
LDW R4, R0, #0
AND R1, R1, R4
NOT R1, R1
ADD R1, R1, #1
ADD R2, R2, R1
ADD R5, R5, #1
B .FILL XFF00
A .FILL X4000
- The assembler creates a symbol table after the first pass. Show
the contents of this symbol table.
- What does this program do? (in less than 25 words)
- When the programmer wrote this program, he/she did not take full
advantage of the instructions provided by the LC-3b ISA. Therefore the program
executes too many unnecessary instructions. Show what the programmer should
have done to reduce the number of instructions executed by this program.
- Consider the following LC-3b assembly language
This program shows two ways to call a subroutine. One requires two instructions:
LEA, JSRR. The second requires only one instruction: JSR. Both ways work
correctly in this example. Is it ever necessary to use JSRR? If so, in what
MAIN LEA R2,L0
L0 ADD R0,R0,#5
L1 ADD R1,R1,#5
- Consider the following possibilities for saving
the return address of a subroutine:
Which of these possibilities supports subroutine nesting, and which supports
subroutine recursion (that is, a subroutine that calls itself)?
- In a processor register.
- In a memory location associated with the subroutine. A different
memory location is used for each different subroutine.
- On a stack.
- A small section of byte-addressable memory is given below:
Add the 16-bit two's complement numbers specified by addresses 0x1000 and
- The ISA specifies a little-endian format
- The ISA specifies a big-endian format
- Say we have
(half a 64) 32 mega bytes of storage, calculate the number of
bits required to address a location if
- The ISA is bit-addressable
- The ISA is byte-addressable
- The ISA is 128-bit addressable
- A zero-address machine is a stack-based machine where all operations
are done by 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
- OP - Pops two values off the operand stack and performs the
binary operation OP on the two values. The result is pushed back onto the
- 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
- STORE M - Stores the accumulator value into Memory Location
- 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.
- 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
Note: OP can be ADD or MUL for the purposes of this problem.
- Write the assembly language code for calculating the expression:
x = (A * ( ( B * C ) + D ) )
- In a zero-address machine
- In a one-address machine
- In a two-address machine
- In a three-address machine like the LC-3b, but which can do
memory to memory operations and also has a MUL instruction.
- Give an advantage and a disadvantage of each of these machines.
- The following table gives the format of the instructions for the LC-1b
computer that has 8 opcodes.
for e.g. LDImm #12 loads decimal 12 to register R0.
:- Destination Register
S R :- Source Register
B R :- Base Register
a) ** The BR(R) i.e. the branch instruction branches to the absolute
address as contained in the Base Register. The bits N,Z and P are the condition
code bits. To use this as an unconditional jump, all 3 condition code
bits need to be set.
b) If bit A is 0, the second source operand is obtained from
SR. If bit A is 1, the second source operand is obtained by sign-extending
bits 1:0 of the instruction. Here bit A is used as a Steering Bit,
since its value steers the interpretation of other bits (instruction bits
1:0 in this example).
The behaviour of the instructions, except LEA and LDImm, is similar to that
of the LC-3b.
- What kind of machine (n-address) does the above ISA specification
- How many general purpose registers does the machine have?
- Using the above instructions, write the assembly code to implement
a register to register mov operation.
- How can a PC-relative branch be specified?
- Please print, fill out the student information sheet from the handouts
section of the course web site, attach a recognizable recent photo of yourself,
and turn it in on September 8.