Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 360N, Fall 2003
Problem Set 2
Due: 24 September 2003, before class
Yale N. Patt, Instructor
Santhosh Srinath, Danny Lynch, 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 returned to you.

  1. For both Part A and B, assume that the system call initiated by the HALT instruction takes 20 cycles to execute. Note that this does not include the number of cycles it takes to execute the HALT instruction itself.

    A. What does the following LC-3b program do? How many cycles does each instruction take to execute on the LC-3b microarchitecture described in Appendix C? How many cycles does 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

    B. What does the following LC-3b program do? How many cycles does 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
  2. In the LC-3b datapath, PCMUX has three inputs. For each of those inputs, list all the instructions which make use of that input and show the corresponding state in the LC-3b state diagram.

  4. States 18, 33, and 35 of the LC-3b state machine are:
    	State 18: MAR <- PC, PC <- PC + 2
            State 33: MDR <- M
            State 35: IR <- MDR
    Which of the following different organizations would still work correctly, why or why not? (Assume that a memory access takes five cycles).

    1. 	State 18: PC <- PC + 2
      	State 33: MAR <- PC, MDR <-M
      	State 35: IR <- MDR

    2. 	State 18: MAR <- PC
      	State 33: PC <- PC + 2, MDR <-M
      	State 35: IR <- MDR

    3. 	State 18: MAR <- PC
      	State 33: MDR <- M
      	State 35: IR <- MDR, PC <- PC + 2

  5.     1.In which state(s) in the LC-3b state diagram should the LD.BEN signal be asserted? Is there a way for the LC-3b to work correctly without the LD.BEN signal? Explain.
        2.Suppose we want to get rid of the BEN register altogether. Can this be done? If so, explain how. If not, why not? Is it a good idea? Explain.
        3.Suppose we took this further and got rid of state 0. The figure below shows a modified microsequencer. What is the 4-bit signal denoted as A in the figure? What is the 1-bit signal denoted as B?

  6.   Little Computer Inc. has decided to modify the LC-3b ISA to include the PUSH and POP instructions. The description of these operations are as follows:
  7. Assembler format for PUSH:


    R6 = R6 - 2;
    MEM[R6] = SR;

    SR is pushed onto the stack.

    PUSH R1

    Assembler format for POP:
    POP DR


    DR = MEM[R6];
    R6 = R6 + 2;

    Top word is popped off the stack and loaded into DR. Condition codes are set based on the value loaded into DR.

    POP R1

    Your job:
    A. Append the current state machine for supporting PUSH and POP instructions.
    B. Will the current datapath support the above state machine? If not, then draw the new datapath to implement the above state machine. Show the new structures you added to support PUSH and POP operations.
    C. Are there any additional control signals needed for the new states? If so, what are they? Give the values of these new control signals in each new state you added and show them clearly in your datapath figure for Part B.
    D. How many cycles will each of the following set of instructions take to execute? 

          1. PUSH R4

          2. ADD R6, R6, # -2
               STW R4, R6, #0

          3. POP R0

          4. LDW R0, R6, #0
              ADD R6, R6, #2

  8.    Design the "WE Logic" block of the LC-3b datapath as shown on Figure C.3 in Appendix C.  The inputs to the block are MAR[0], R.W, and DATA.SIZE. The outputs of the block are WE0 and WE1. Show the truth table for this logic block and give a gate-level implementation.

  10.   The Address Control Logic in the LC-3b datapath of Figure C.3 in Appendix C allows the LC-3b to support memory-mapped I/O. There are three inputs to this logic:
      The logic has five outputs:
      Your task is to draw the truth table for this Address Control Logic. Mark don't care values with X in your truth table. Use the conventions described above to denote the values of inputs and outputs. Please read Section C.6 in Appendix C on Memory-mapped I/O before answering this question. Also, refer to Appendix A to find out the addresses of device registers.

  12. A processor supports byte-addressable memory with a 26-bit address space. The processor is connected to memory via a 64-bit data bus. Design an eight-way interleaved memory that supports the full address space of the processor. Use only 512Kbit (2^19 * 1 bit) memory chips. Draw a diagram of your memory system, with chip enables, write enables, data bus, and address bus. On your diagram, label memory locations 0 through 31. How big is this memory? Give a breakdown of each field in a memory address. (Do not worry about the logic for unaligned accesses.)

  14.   The figure below illustrates the logic and memory to support 512 MB (byte addressable) of physical memory, supporting unaligned accesses.  The ISA contains LDByte, LDHalfWord, LDWord, STByte , STHalfWord and STWord instructions, where a Word is 32 bits. 

        Construct the truth table to implement the LOGIC block, having inputs SIZE, R/W, 1st or 2nd access, PHYS_ADDR[1:0] and the outputs shown in the above figure. Assume that the value of SIZE can be Byte (00), HalfWord (01), and Word (10). Clearly explain what function each output serves.


  16.   Added 16th September
    Why do we have states 18 and 19 in the state diagram of the LC-3b instead of having just one of the two?