## Department of Electrical and Computer Engineering

### The University of Texas at Austin

EE 306, Fall 2013
Problem Set 4
Due: October 28th, before class
Yale N. Patt, Instructor
TAs: Ben Lin, Mochamad Asri, Ameya Chaudhari, Nikhil Garg, Lauren Guckert
Jack Koenig, Saijel Mokashi, Sruti Nuthalapati, Sparsh Singhai, Jiajun Wang

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.

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 ________________________ `

2. 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.
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. 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. 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 LocationValue
`x3000`` 0101000000100000`
`x3001`` 0001000000100101`
`x3002`` 0010001000000100`
`x3003`` 0001000000000000`
`x3004`` 0001001001111111`
`x3005`` 0000001111111101`
`x3006`` 1111000000100101`
`x3007`` 0000000000000100`

3. 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`

4. 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`` `
`x3002`` `
`x3003`` 0001 000 000 1 00001`
`x3004`` 0000 111 111111100`
`x3005`` 0011 000 001001010`
`x3006`` 1111 0000 0010 0101`

5. 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.

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

ASCII       LD R1, ASCII

The label ASCII corresponds to the address x4F08. If this instruction is executed during the running of the program, what will be contained in R1 immediately after the instruction is executed?

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

 ADD R3, R3, #30 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?

8. (Adapted from 6.14) Consider the following machine language program:

 AND R2, R2, #0 LOOP ADD R1, R1, #-3 BRn END ADD R2, R2, #1 BRnzp LOOP END HALT

What are the possible initial values of R1 that cause the final value in R2 to be 3?

9. (Adapted from 7.16) Assume a sequence of nonnegative integers is stored in consecutive memory locations, one integer per memory location, starting at location x4000. Each integer has a value between 0 and 30,000 (decimal). The sequence terminates with the value -1 (i.e., xFFFF).
1. Create the symbol table entries generated by the assembler when translating the following routine into machine code:

 .ORIG x3000 AND R4, R4, #0 AND R3, R3, #0 LD R0, NUMBERS LOOP LDR R1, R0, #0 NOT R2, R1 BRz DONE AND R2, R1, #1 BRz L1 ADD R4, R4, #1 BRnzp NEXT L1 ADD R3, R3, #1 NEXT ADD R0, R0, #1 BRnzp LOOP DONE TRAP x25 NUMBERS .FILL x4000 .END

2. What does the above program do?

10. Below is a segment of LC-3 machine language program.

 ADD R2, R1, #0 HERE ADD R3, R2, #-1 AND R3, R3, R2 BRz END ADD R2, R2, #1 BRnzp HERE END HALT

If the data in R1 is an unsigned integer larger than 1, what does the program do? (Hint: what is the relationship between the resulting integer in R2 and the original integer in R1?)

11. (Adapted from 7.18) The following LC-3 program compares two character strings of the same length. The source strings are in the .STRINGZ form. The first string starts at memory location x4000, and the second string starts at memory location x4100. If the strings are the same, the program terminates with the value 1 in R5; otherwise the program terminates with the value 0 in R5. Insert one instruction each at (a), (b), and (c) that will complete the program. Note: The memory location immediately following each string contains x0000.

 .ORIG x3000 LD R1, FIRST LD R2, SECOND AND R0, R0, #0 LOOP ____________________ ; (a) LDR R4, R2, #0 BRz NEXT ADD R1, R1, #1 ADD R2, R2, #1 ____________________ ; (b) ____________________ ; (c) ADD R3, R3, R4 BRz LOOP AND R5, R5, #0 BRnzp DONE NEXT AND R5, R5, #0 ADD R5, R5, #1 DONE TRAP x25 FIRST .FILL x4000 SECOND .FILL x4100 .END

12. The data at memory address x3500 is a bit vector with each bit representing whether a certain power plant in the area is generating electricity (bit = 1) or not (bit = 0). The program counts the number of power plants that generate electricity and stores the result at x3501. However, the program contains a mistake which prevents it from correctly counting the number of electricity generating (operational) power plants. Identify it and explain how to fix it.

 .ORIG x3000 AND R0, R0, #0 LD R1, NUMBITS LDI R2, VECTOR ADD R3, R0, #1 CHECK AND R4, R2, R3 BRz NOTOPER ADD R0, R0, #1 NOTOPER ADD R3, R3, R3 ADD R1, R1, #-1 BRp CHECK STR R0, R2, #1 TRAP x25 NUMBITS .FILL #16 VECTOR .FILL x3500 .END

13. The following program does not do anything useful. However, being an “electronic idiot,” the LC-3 will still execute it.

``````
.ORIG x3000
LDR R3, R0, #-6
LDR R4, R1, #0
ST R2, #5
STR R1, R0, #3
HALT
.END

``````

Without using the simulator, answer the following questions:

1. What will the values of registers `R0` through `R4` be after the LC-3 finishes executing the `ADD` instruction?

2. What will the values of memory locations `Addr1` through `Addr5` be after the LC-3 finishes executing the `HALT` instruction?

14. Moved to Problem Set 5 (updated 10/23/2013)
1. Bob Computer just bought a fancy new graphics display for his LC-3. In order to test out how fast it is, he rewrote the `OUT` trap handler so it would not check the `DSR` before outputting. Sadly he discovered that his display was not fast enough to keep up with the speed at which the LC-3 was writing to the `DDR`. How was he able to tell?

2. Bob also rewrote the handler for `GETC`, but when he typed `ABCD` into the keyboard, the following values were input:

``````
AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDD
``````

What did Bob do wrong?

15. Moved to Problem Set 5 (updated 10/23/2013) (Adapted from 6.16) Shown below are the partial contents of memory locations x3000 to x3006.

 15 0 x3000 0 0 1 0 0 0 0 x3001 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 x3002 1 0 1 1 0 0 0 x3003 x3004 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 x3005 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 x3006

The PC contains the value x3000, and the RUN button is pushed.

As the program executes, we keep track of all values loaded into the MAR. Such a record is often referred to as an address trace. It is shown below.

MAR Trace
x3000
x3005
x3001
x3002
x3006
x4001
x3003
x0021

Your job: Fill in the missing bits in memory locations x3000 to x3006.