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.
(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.
Register | Before | After |
---|---|---|
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 Location | Value |
---|---|
x1000 | 0001 101 000 1 11000 |
Memory Location | Value |
---|---|
X3000 | 0101000000100000 |
X3001 | 0001000000100101 |
X3002 | 0010001000000100 |
X3003 | 0001000000000000 |
X3004 | 0001001001111111 |
X3005 | 0000001111111101 |
X3006 | 1111000000100101 |
X3007 | 0000000000000100 |
PC | x3006 |
R0 | x0050 |
R1 | x0000 |
R2 | x0000 |
R3 | x0000 |
R4 | x0000 |
R5 | x0000 |
R6 | x0000 |
R7 | x0000 |
N | 0 |
Z | 1 |
P | 0 |
Memory Location | Value | Instruction | Cycles takes to exectue once | number of times executed | Total Cycles for instruction |
---|---|---|---|---|---|
X3000 | 0101000000100000 | AND | 9 | 1 | 9 |
X3001 | 0001000000100101 | ADD | 9 | 1 | 9 |
X3002 | 0010001000000100 | LD | 15 | 1 | 15 |
X3003 | 0001000000000000 | ADD | 9 | 4 | 36 |
X3004 | 0001001001111111 | ADD | 9 | 4 | 36 |
X3005 | 0000001111111101 | Branch | 9 if not taken 10 if taken | 3 times taken 1 time not taken | 39 |
What does the following program do (in 15 words or fewer)? The PC is initially at x3000.
Memory Location | Value |
---|---|
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 |
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 Location | Value |
---|---|
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 |
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.
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
ADD R3, R3, #30 | The immediate value is too large. | |
ST R3, A | ||
HALT | ||
A | .BLKW 1 |
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 |
AND R2, R2, #0 | R2 <- 0 | |
LOOP | ADD R1, R1, #-3 | R1 <- R1-3 |
BRn END | End when R1 is negative | |
ADD R2, R2, #1 | R2 <- R2+1 | |
BRnzp LOOP | ||
END | HALT |
For R2 to contain the value 3, the BRn must not have intiated a branch for 3 consecutive times. Therefore, R1 wasn't negative after the instruction ADD R1, R1, #-3 was exectued 3 times and was negative after the instruction was executed 4 times. That is, R1-3x3 = R1-9 >= 0 and R1-3x4 = R1-12 < 0. Solving the inequalities yields, 9 <= R1 < 12. Since a register contains integers, R1 could have been 9, 10, or 11.
.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 |
Label | Memory Address |
LOOP | x3003 |
L1 | x300A |
NEXT | x300B |
DONE | x300D |
NUMBERS | x300E |
The instruction AND R2, R1, #1 performs a bit mask (x0001) to decide whether the least significant bit of the value is 0 or 1. The LSB of a number is used to determine whether the integer was even or odd. For example, numbers with a zero LSB are: 0000 (#0), 0010 (#2), 0100 (#4), 0110 (#6), which are all even. Hence, R3 counts the amount of even numbers in the list and R4 counts the amount of odd numbers.
ADD R2, R1, #0 | |
HERE | ADD R3, R2, #-1 |
AND R3, R3, R2 | |
BRz END | |
ADD R2, R2, #1 | |
BRnzp HERE | |
END | HALT |
The program finds out the smallest power of 2 which is larger than or equal to the unsigned integer in R1.
.ORIG x3000 | ||
LD R1, FIRST | ||
LD R2, SECOND | ||
AND R0, R0, #0 | ||
LOOP | LDR R3, R1, #0 | ; (a) |
LDR R4, R2, #0 | ||
BRz NEXT | ||
ADD R1, R1, #1 | ||
ADD R2, R2, #1 | ||
NOT R4, R4 | ; (b) | |
ADD R4, R4, #1 | ; (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 |
.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 | ||
LD R2, VECTOR | <- missing instruction | |
STR R0, R2, #1 | ||
TRAP x25 | ||
NUMBITS | .FILL #16 | |
VECTOR | .FILL x3500 | |
.END |
R2 contains the bit vector, and not the address at which the bit vector is contained. The instruction LDI R2, VECTOR loaded the value at x3500 into R2 since the value at the memory address labeled as VECTOR was used as the address from which to load. The store instruction STR R0, R2, #1 uses the value of R2 to evaluate an address. However, R2 must be modified to contain an address for an STR instruction to work. Thus, LD R2, VECTOR is an additional required instruction.
.ORIG x3000
LD R0, Addr1
LEA R1, Addr1
LDI R2, Addr1
LDR R3, R0, #-6
LDR R4, R1, #0
ADD R1, R1, #3
ST R2, #5
STR R1, R0, #3
STI R4, Addr4
HALT
Addr1 .FILL x300B
Addr2 .FILL x000A
Addr3 .BLKW 1
Addr4 .FILL x300D
Addr5 .FILL x300C
.END
Without using the simulator, answer the following questions:
What will the values of registers R0
through R4
be after the LC-3 finishes executing the ADD
instruction?
R0 - x300B
R1 - x300D
R2 - x000A
R3 - x1263
R4 - x300B
What will the values of memory locations Addr1
through Addr5
be after the LC-3 finishes executing the HALT
instruction?
Addr1 - x300B
Addr2 - x000A
Addr3 - x000A
Addr4 - x300B
Addr5 - x300D