Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 360N, Spring 2003
Problem Set 1
Due: 27 January 2003, before class
Yale N. Patt, Instructor
Hyesoon Kim, Moinuddin Qureshi, Onur Mutlu, Santhosh Srinath, TAs

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.

  1. Briefly explain the difference between the microarchitecture level and the ISA level in the transformation hierarchy.
  2. What information does the compiler need to know about the microarchitecture of the machine for which it's compiling code? Explain.
  3. 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.

  4. Classify the LC-3b instructions into Operate, Data Movement, or Control instructions.
  5. 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 000000001
    3. 0000 000 000000000

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

  6. Consider the following LC-3b assembly language program:
    	.ORIG x3000
    	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
    	BRp AGAIN
    	LDW R4, R0, #0
    	AND R1, R1, R4
    	NOT R1, R1
    	ADD R1, R1, #1
    	ADD R2, R2, R1
    	BRnp NO
    	ADD R5, R5, #1
    B	.FILL XFF00
    A	.FILL X4000
    1. The assembler creates a symbol table after the first pass. Show the contents of this symbol table.
    2. Assemble this program. Show the LC-3b machine code for each instruction in the program as a hexadecimal number.
    3. What does this program do?
    4. 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.
  7. Consider the following LC-3b assembly language program.
    	.ORIG	x4000
    MAIN	LEA	R2,L0
    	JSRR	R2
    	JSR	L1
    L0	ADD	R0,R0,#5
    L1	ADD	R1,R1,#5
    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 situation?
  8. Name the different addressing modes supported by the LC-3b. Briefly describe each and give an example.
  9. 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)?
  10. A small section of byte-addressable memory is given below:
    Address Data
    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 0x1000 and 0x1002 if:
  11. Let's say we have 64MB of memory. Calculate the number of bits required to address a location if
    1. The ISA is bit-addressable
    2. The ISA is byte-addressable
    3. The ISA is 128-bit addressable
  12. Write an LC-3b program that swaps the values in R1 and R2 without using any other registers. Make sure that your program works for any possible values in R1 and R2.
  13. Note: OP can be ADD or MUL for the purposes of this problem.

    1. 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.
    2. Give an advantage and a disadvantage of each of these machines.
  14. Note: This problem is postponed to Problem Set #2.
    1. What does the following LC-3b program do? How many cycles do each of the instructions take to execute on the LC-3b microarchitecture described in Appendix C? How many cycles will the entire program take to execute? ( Assume that a memory access takes 5 cycles )
      	.ORIG x4000
      	AND   R1, R1, #0
      	ADD   R1, R1, #5
      	LSHF  R1, R1, #12
      	LDW   R2, R1, #0
      	RSHFL R3, R2, #8
      	LSHF  R4, R2, #8
      	ADD   R2, R3, R4
      	STW   R2, R1, #1
    2. What does the following LC-3b program do? How many cycles will it take to execute? ( Assume that a memory access takes 5 cycles )
      	.ORIG x4000
      	AND   R1, R1, #0
      	ADD   R1, R1, #5
      	LSHF  R1, R1, #12
      	LDB   R2, R1, #0
      	STB   R2, R1, #3
      	LDB   R2, R1, #1
      	STB   R2, R1, #2
  15. Assume for the following questions that an LC-3b instruction is loaded into a random memory location such that it can be executed.
    1. What is the probability that the instruction is stored in location 0x0057?
    2. What is the probability that the instruction is stored in location 0x300E?

  16. The LC-3b company wants to increase the number of instructions in the ISA. They have hired you to add 64 new instructions to the ISA. Give us a way to increase the number of opcodes without having to change the current program binaries.