Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2011
Problem Set 4
Due: October 19th, before class
Yale N. Patt, Instructor
TAs: Faruk Guvenilir, Milad Hashemi, Jennifer Davis, Garret Galow, Ben Lin, Taylor Morrow, Stephen Pruett, Jee Ho Ryoo

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 and the time for the discussion section you would like the problem set turned back to you. Show your work.

  1. Suppose that an instruction cycle of the LC-3 has just finished and another one is about to begin. The following table describes the values in select LC-3 registers and memory locations:

    RegisterValue
    IRx3001
    PCx3003
    R0x3000
    R1x3000
    R2x3002
    R3x3000
    R4x3000
    R5x3000
    R6x3000
    R7x3000
    Memory LocationValue
    x3000x62BF
    x3001x3000
    x3002x3001
    x3003x62BE

    For each phase of the new instruction cycle, specify the values that PC, IR, MAR, MDR, R1, and R2 will have at the end of the phase in the following table:

    PCIRMARMDRR0R1R2R3R4R5R6R7
    Fetch
    Decode
    Fetch Operands
    Execute
    Store Result

    Hint: Example 4.2 illustrates the LDR instruction of the LC-3. Notice that values of memory locations x3000, 3002, and 3003 can be interpreted as LDR instructions.

    PCIRMARMDRR0R1R2R3R4R5R6R7
    Fetchx3004x62BE x3003x62BEx3000x3000x3002x3000x3000x3000x3000x3000
    Decodex3004x62BE x3003x62BEx3000x3000x3002x3000x3000x3000x3000x3000
    Fetch Operandsx3004x62BE x3000x62BFx3000x3000x3002x3000x3000x3000x3000x3000
    Executex3004x62BE x3000x62BFx3000x3000x3002x3000x3000x3000x3000x3000
    Store Resultx3004x62BE x3000x62BFx3000x62BFx3002x3000x3000x3000x3000x3000
  2. (4.8)
    Suppose a 32-bit instruction has the following format:

    OPCODEDRSR1SR2UNUSED

    If there are 255 opcodes and 120 registers, and every register is available as a source or destination for every opcode,

    1. What is the minimum number of bits required to represent the OPCODE?
      2. 225 opcode, 8 bits are required to represent the OPCODE
    2. What is the minimum number of bits required to represent the Destination Register (DR)?
      3. 120 registers, 7 bits to represent the DR
    3. What is the maximum number of UNUSED bits in the instruction encoding?
      4. 3 registers and 1 opcode, 3x7 + 8 = 29 bits. So there are 3 ununsed bits

  3. (Adapted from 5.31)
    The following diagram shows a snapshot of the 8 registers of the LC-3 before and after the instruction at location x1000 is executed. Fill in the bits of the instruction at location x1000.
    RegisterBeforeAfter
    R0 x0000 x0000
    R1 x1111 x1111
    R2 x2222 x2222
    R3 x3333 x3333
    R4 x4444 x4444
    R5 x5555 xFFF8
    R6 x6666 x6666
    R7 x7777 x7777
    Memory LocationValue
    x1000 0001 101 000 1 11000


  4. The memory locations x3000 to x3007 contain the values as shown in the table below. Assume the memory contents below are loaded into the simulator and the PC has been set to point to location x3000. Assume that a break point has been placed to the left of the HALT instruction (ie at location x3006 which contains 1111 0000 0010 0101). Assume that before the program is run, each of the 8 registers has the value x0000 and the NZP bits are 010.
    Memory LocationValue
    X3000 0101000000100000
    X3001 0001000000100101
    X3002 0010001000000100
    X3003 0001000000000000
    X3004 0001001001111111
    X3005 0000001111111101
    X3006 1111000000100101
    X3007 0000000000000100
    1. In no more than 15 words, summarize what this program will do when the “Run” button is pushed in the simulator. Hint: What relationship is there between the value loaded from memory and the final value in R0 after the program has completed?
      2. 5 is put in R0 and shifted left the value at location x3007 times
    2. What are the contents of the PC, the 8 general purpose registers (R0-R7), and the N, Z, and P condition code registers after the program completes?
      3. PCx3006
      R0x0050
      R1x0000
      R2x0000
      R3x0000
      R4x0000
      R5x0000
      R6x0000
      R7x0000
      N0
      Z1
      P0
    3. What is the total number of CPU clock cycles that this program will take to execute until it reaches the breakpoint? Note: You should refer to the state machine (pg 568) to determine how many cycles an instruction takes. Assume each state that access memory takes 5 cycles to complete and every other state takes 1 cycle to execute.
    Memory LocationValueInstructionCycles takes to exectue oncenumber of times executedTotal Cycles for instruction
    X3000 0101000000100000AND919
    X3001 0001000000100101ADD919
    X3002 0010001000000100LD15115
    X3003 0001000000000000ADD9436
    X3004 0001001001111111ADD9436
    X3005 0000001111111101Branch9 if not taken 10 if taken3 times taken 1 time not taken39
    Total Cycles 9+9+15+36+36+39 = 144

  5. What does the following program do (in 15 words or fewer)? The PC is initially at x3000.
    Memory LocationValue
    x3000 0101 000 000 1 00000
    x3001 0010 001 011111110
    x3002 0000 010 000000100
    x3003 0000 011 000000001
    x3004 0001 000 000 1 00001
    x3005 0001 001 001 000 001
    x3006 0000 111 111111011
    x3007 1111 0000 0010 0101

    Counts the number of bits that are set to 1 in the word at x3100


  6. Prior to executing the following program, memory locations x3100 through x4000 are initialized to random values, exactly one of which is negative. The following program finds the address of the negative value, and stores that address into memory location x3050. Two instructions are missing. Fill in the missing instructions to complete the program. The PC is initially at x3000.
    Memory LocationValue
    x3000 1110 000 011111111
    x3001 0110 001 000 000000
    x3002 0000 100 000000010
    x3003 0001 000 000 1 00001
    x3004 0000 111 111111100
    x3005 0011 000 001001010
    x3006 1111 0000 0010 0101


  7. The LC-3 has just finished executing a large program. A careful examination of each clock cycle reveals that the number of executed store instructions (ST, STR, and STI) is greater than the number of executed load instructions (LD, LDR, and LDI). However, the number of memory write accesses is less than the number of memory read accesses, excluding instruction fetches. How can that be? Be sure to specify which instructions may account for the discrepancy.

    A large number of LDI instructions (two read accesses) and STI instructions (one read access and one write access) could account for this discrepancy.



  8. (7.2) An LC-3 assembly language program contains the instruction:

      ASCII       LD R1, ASCII

    The symbol table entry for ASCII is x4F08. If this instruction is executed during the running of the program, what will be contained in R1 immediately after the instruction is executed?

    R1 <-- M[ASCII]
    R1 = 0010 001 1 1111 1111
              LD   R1,     #-1



  9. (7.10) The following program fragment has an error in it. Identify the error and explain how to fix it.

      ADD R3, R3, #30    The immediate value is too large.
      ST R3, A
      HALT
    A   .BLKW 1

    Will this error be detected when this code is assembled or when this code is run on the LC-3?

    The error will be detected by the assembler since it will not be able to form the 16 bits of the instruction which performs the addition.
    One possible solution is to seperate the addition to two add instruction with immediate of #15.
      ADD R3, R3, #15
      ADD R3, R3, #15
      ST R3, A
      HALT
    A   .BLKW 1