EE 306, Fall 2008
Problem Set 4
Due: Monday October 27th, before class
Instructor: Yale N. Patt
TAs: Jeffrey Allan, Arvind Chandrababu, Eiman Ebrahimi, Aravind Jakkani,
Khubaib,
Allison Korczynski, Pratyusha Nidamaluri, Zrinka Puljiz, Che-Chun Su, Christopher Wiley
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 turned back to you.
1. (Adapted
from 5.4) If a memory consists of
4096 locations, and each location contains 32 bits.
a. How many bytes of data can we store in
this memory?
b. How many bits are required for the
address?
c. If we use the PC-relative addressing
mode, and want to allow control transfer between instructions up to 50
locations away, how many bits of a branch instruction are needed to specify the
PC-relative offset?
d. If a control instruction is in location
3, what is the PC-relative offset of address 10? Assume that the control
transfer instructions work the same way as in the LC-3.
2. (Adapted from
5.24) An LDR instruction, located at x3200, uses R4 as its base register. The
value currently in R4 is x4011.
a.
What
is the largest address that this instruction can load from?
b.
Suppose
we redefine the LDR offset to be zero-extended, rather than sign-extended. Then
what would be the largest address that this instruction could load from?
c.
With
the same assumptions as b., what would be the smallest address that this
instruction could load from?
3. (5.14) There is no instruction in the LC-3 ISA that
performs the OR operation. However, we can write a sequence of instructions to
implement the OR operation. The four-instruction sequence below performs the OR
of the contents of register 1 and register 2 and puts the result in register 3.
Fill in the two missing instructions so that the four-instruction sequence will
do the job.
(1): 1001 1000 0111 1111
(2):
(3): 0101 1101 0000 0101
(4):
4. (Adapted from
5.22) The PC contains x3010. The following memory locations contain values as
shown:
location: value:
x3049 x70A3
x3050 x70A4
x70A3 xF231
x70A4 x123F
The
following three LC-3 instructions are then executed, causing a value to be
loaded into R6. What is that value?
x3010
1110 0110 0011 1111
x3011
0110 1000 1100 0000
x3012
0110 1101 0000 0000
We
could replace the three-instruction sequence with a single instruction. What is
it?
5. The following LC-3
machine language program is supposed to multiply the contents of R1 with R2 and
store the result in R3. The program assumes that both R1 and R2 contain
positive integers. However, there is an error in the program.
x3000
0101 0110 1110 0000
x3001
0001 0110 1100 0010
x3002
0001 0010 0111 1111
x3003
0000 0101 1111 1101
x3004
1111 0000 0010 0101
Please
indicate where the error is and explain why there is an error. Modify it to
make the program work correctly.
6. (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?
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 |
.FILL #0 |
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).
a. 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 |
b. 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?) (Updated on 10/24/08)
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.
.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.
(Adapted from 7.24) The following program fragment was written by an Aggie in response
to the programming assignment: Write a program that shifts the contents of R3
four bits to the left. As you
might expect, there is a bug. Identify the bug and explain how to fix it.
.ORIG
x3000
AND
R2, R2, #0
ADD
R2, R2, #4
LOOP BRz DONE
ADD
R2, R2, #-1
ADD
R3, R3, R3
BR
LOOP
DONE HALT
.END
13. (Adapted from
6.16) Shown below are 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.