Department of Electrical and Computer Engineering
The University of Texas at Austin
EE 360N, Spring 2001
Yale N. Patt, Instructor
Kameswar Subramaniam, Onur Mutlu, TAs
Problem Set 1, Due February 12, 5:30 pm

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


1. Both of the following programs cause the value x0004 to be stored in location x3000, but at different times. Explain the difference.


2. What do each one of these LC-2 instructions do? (Assume all three instructions are at x3000 when they are executed)

       0001 001 001 1 00000
       0101 001 001 1 11111
       0000 101 000000001

     How do they differ from each other?


3. Consider the following LC-2 assembly language program 

	.ORIG x3000
	AND  R5, R5, #0
	AND  R3, R3, #0
	ADD  R3, R3, #8
	LDI  R1, A
	ADD  R2, R1, #0
Again	ADD  R2, R2, R2
	ADD  R3, R3, #-1
	BRp  Again
	LD   R4, B
	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

  a) The assembler creates a symbol table after the first pass. Show the contents of this symbol table.
  b) What does this program do?


4. Write a program in LC-2 assembly language that multiplies the unsigned integer at location x4000 with the unsigned integer at location x4001 and stores the result at location x4002. Assume that the numbers are such that their result fits in a 16-bit memory location.


5. a) The LC-2 JMP/JSR instruction does not execute exactly the same if L=0 and L=1. Why is the case L=0 irrelevant to the LC-2 ISA?

      b) Why is this not also true for the JMPR/JSRR instruction pair?


6. How many cycles do each of the instructions in this short program take to execute on the LC-2? How many cycles will the entire program take to execute? (Assume that a memory access takes five cycles) 

	.ORIG x3000
	LD  R0, LABEL1
	LDR R1, R0, #0
	ADD R1, R1, #1
	STR R1, R0, #1
	TRAP x25
	.END


7. The LC-2 has several registers, for example MAR, PC, R0. Which of the three are part of the LC-2 ISA? Explain.


8. In the LC-2 datapath, PCMX has four inputs. For each of those inputs, give an instruction which makes use of that input and show the corresponding state in the LC-2 state diagram.


9. The first three states of the LC-2 state machine are: 

	
	State 1: MAR <- PC, PC <- PC + 1
        State 2: MDR <-M
        State 3: IR <- MDR

    Which of the following different organizations would still work correctly, why or why not? (Assume that a memory access takes five cycles) 
a.	State 1: PC <- PC + 1
	State 2: MAR <- PC, MDR <-M
	State 3: IR <- MDR

b.	State 1: MAR <- PC
	State 2: PC <- PC + 1, MDR <-M
	State 3: IR <- MDR

c.	State 1: MAR <- PC
	State 2: MDR <- M
	State 3: IR <- MDR, PC <- PC + 1


10. The definition of the control signals lists four separate signals: GATE_PC, GATE_ALU, GATE_MDR, and GATE_MARMX. An ingenious designer said: This takes four bits of storage for every entry in the control store. What if we encode these four signals into two bits, and put a 2 to 4 decoder at the output of those two bits of microinstruction. For a few gates of decoder, we can save 2 bits of each control store entry. Will it work? Good idea or bad idea? Why?


11. Same problem, except now our ingenious designer moves over to the following four signals: LD_PC, LD_MAR, LD_MDR, and LD_IR. Same solution. Will it work? Good idea or bad idea? Why?


12. Consider the following possiblities 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)?


13. The LC-2 company has decided it can not afford an opcode to do nothing, so it commissions a designer to use the NOP opcode to do SUBtract. Augment the state machine to carry out the instruction SUB  R1, R2, R3. The semantics of this instruction is to set R1 to R3-R2. Assume the addition to the data path and  its  control, as shown below. That is, an additional MUX and a constant 1 register is added to the data path, and an additional microcontrol signal SUBCORRECT is added to the microinstruction. Note: The LC-2 Company does not expect you to implement SUBtract Immediate.







                                   ------------
                                  | Constant 1 |
                                   ------------    From SR2 out
                                         |              |
                                         |              |
                                         |              |
                                      ----------------------
                                      \                    /
                    SUBCORRECT ------> \                  /
                                        ------------------
           ------                               |
    ----->| SEXT |--------------                |
           ------              |                |
                               |                |
                            -----------------------
                            \                     /
                 SR2MX ----> \                   /
                              -------------------
                                       |
                                       |
                                       |
                              To left input of ALU


14. In the ISA of problem 10, opcode 1000 means SUBtract. We must also fix instruction <5:5> to MBZ (i.e.,  must  be  zero). Why?
At first blush, it appears that there is an imbalance. That is, we can do ADD immediate and AND immediate, but not SUB immediate. Why does not implementing SUB immediate not create an imbalance. In other words, why is it okay to not implement SUB immediate.