Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 360N, Fall 2005
Problem Set 1
Due: 14 September 2005, before class
Yale N. Patt, Instructor
Aater Suleman, Linda Bigelow, Jose Joao, and Veynu Narasiman, 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.

  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 and MAR 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.

  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 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
    NO HALT
    B .FILL XFF00
    A .FILL X4000
    .END
    1. The assembler creates a symbol table after the first pass. Show the contents of this symbol table.
    2. What does this program do? (in less than 25 words)
    3. 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.
  6. Consider the following LC-3b assembly language program.
    	.ORIG	x4000
    MAIN LEA R2,L0
    JSRR R2
    JSR L1
    HALT
    ;
    L0 ADD R0,R0,#5
    RET
    ;
    L1 ADD R1,R1,#5
    RET
    1. Assemble the above program. Show the LC-3b machine code for each instruction in the program as a hexadecimal number.
    2. 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?
  7. 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)?
  8. 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:
  9. Say we have 32 mega bytes of storage, 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
  10. 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 )))
      • 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 a one-address machine versus a zero-address machine.
  11. The following table gives the format of the instructions for the LC-1b computer that has 8 opcodes.        


    Opcode 7    6     5 4     3 2
    1      0
    ADD
    0     0    0
    DR
    A
    SR
    AND
    0     0    1
    DR A SR
    BR(R)
    0     1    0 N    Z      P
    TR
    LDImm
    0     1    1
    signed immediate
    LEA
    1     0    0 signed offset
    LD
    1     0    1
    DR 0
    TR
    ST
    1     1    0 SR 0
    TR
    NOT
    1     1    1
    DR 0
    0     0
     
    
    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 source of the load.  In the
            case of ST, it contains the destination of the store.
                                                                                    
            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)
  12. Answer the following short questions.
    1. A memory's addressability is 64 bits. What does that tell you about the sizes of the MAR and the MDR?
    2. We want to increase the number of registers that we can specify in the LC-3b ADD instruction to 32. Do you see any problem with that? Explain.
  13. Please go to the handouts section of the course web site, print and fill out the student information sheet, and turn it in with a recognizable recent photo of yourself on September 14th.