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.
(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 |
-
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
OUTtrap handler so it would not check theDSRbefore 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 theDDR. How was he able to tell? -
Bob also rewrote the handler for
GETC, but when he typedABCDinto the keyboard, the following values were input:AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDDWhat did Bob do wrong?
(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.
x3000
x3005
x3001
x3002
x3006
x4001
x3003
x0021
What are the defining characteristics of a stack? Give two implementations of a stack and describe their differences.
The output stream is a list of all the elements that are popped off the stack in the order that they are popped off.
a. If the input stream is ZYXWVUTSR, create a sequence of pushes and pops such that the output stream is YXVUWZSRT.
b. If the input stream is ZYXW, how many different output streams can be created?
PUSH M - pushes the value stored at memory location M onto the operand stack.
POP M - pops the operand stack and stores the value into memory location M.
OP - Pops two values off the operand stack and performs the binary operation OP on the two values. The result is pushed back onto the operand stack.
Note 1: OP can be ADD, SUB, MUL, or DIV for parts a and b of this problem.
(added 11/06/15) Note 2: To perform DIV and SUB operations, the top element of the stack is considered as the second operand. i.e. If we first push "A" and then push "B" followed by a "SUB" operation, "A" and "B" will be popped from stack and "A-B" will be pushed into stack.
- Draw a picture of the stack after each of the instructions below are executed.
What is the minimum number of memory locations that have to be used on the stack
for the purposes of this program? Also write an arithmetic equation expressing
u in terms of v, w, x, y, and z. The values u, v, w, x, y, and z are stored in
memory locations U, V, W, X, Y, and Z.
PUSH V PUSH W PUSH X PUSH Y MUL ADD PUSH Z SUB DIV POP U - Write the assembly language code for a zero-address machine
(using the same type of instructions from part a) for calculating
the expression below. The values a, b, c, d, and e are stored in
memory locations A, B, C, D, and E.
e = ((a * ((b - c) + d))/(a + c))
Moved to Problem Set 6 (updated 10/27/15) Jane Computer (Bob's adoring wife), not to be outdone
by her husband, decided to rewrite the TRAP x22 handler at a different place in
memory. Consider her implementation below. If a user writes a program that uses this
TRAP handler to output an array of characters, how many times is the ADD
instruction at the location with label A executed? Assume that the
user only calls this "new" TRAP x22 once. What is wrong with this TRAP handler?
Now add the necessary instructions so the TRAP handler executes properly.
Hint: RET uses R7 as linkage back to the caller
(RET is equivalent to JMP R7).
; TRAP handler
; Outputs ASCII characters stored in consecutive memory locations.
; R0 points to the first ASCII character before the new TRAP x22 is called.
; The null character (x00) provides a sentinel that terminates the output sequence.
.ORIG x020F
START LDR R1, R0, #0
BRz DONE
ST R0, SAVER0
ADD R0, R1, #0
TRAP x21
LD R0, SAVER0
A ADD R0, R0, #1
BRnzp START
DONE RET
SAVER0 .BLKW #1
.END
(Adapted from 9.2)
How many
TRAPservice routines can be implemented in the LC-3? Why?Why must a
RETinstruction be used to return from aTRAProutine? Why won't aBRnzp(unconditionalBR) instruction work instead?How many accesses to memory are made during the processing of a
TRAPinstruction?
Assume that you have the following table in your program:
MASKS .FILL x0001
.FILL x0002
.FILL x0004
.FILL x0008
.FILL x0010
.FILL x0020
.FILL x0040
.FILL x0080
.FILL x0100
.FILL x0200
.FILL x0400
.FILL x0800
.FILL x1000
.FILL x2000
.FILL x4000
.FILL x8000
-
Write a subroutine
CLEARin LC-3 assembly language that clears a bit inR0using the table above. The index of the bit to clear is specified inR1.R0andR1are inputs to the subroutine. -
Write a similar subroutine
SETthat sets the specified bit instead of clearing it.
Hint: You should remember to save and restore any registers your subroutine
uses (the "callee save" convention). Use the RET instruction as
the last instruction in your subroutine (R7 contains the address
of where in the caller to return to.)
Suppose we are writing an algorithm to multiply the elements of an array (unpacked, 16-bit 2's complement numbers), and we are told that a subroutine "mult_all" exists which multiplies four values, and returns the product. The mult_all subroutine assumes the source operands are in R1, R2, R3, R4, and returns the product in R0. For purposes of this assignment, let us assume that the individual values are small enough that the result will always fit in a 16-bit 2's complement register.
Your job: Using this subroutine, write a program to multiply the set of values contained in consecutive locations starting at location x6001. The number of such values is contained in x6000. Store your result at location x7000. Assume there is at least one value in the array(i.e., M[x6000] is greater than 0).
Hint: Feel free to include in your program
PTR .FILL x6001
CNT .FILL x6000
.ORIG x3000
JSR A
OUT ;TRAP x21
BRnzp DONE
A AND R0,R0,#0
ADD R0,R0,#5
JSR B
RET
DONE HALT
ASCII .FILL x0030
B LD R1,ASCII
ADD R0,R0,R1
RET
.END
(8.15)
- What does the following LC-3 program do?
.ORIG x3000 LD R3, A STI R3, KBSR AGAIN LD R0, B TRAP x21 BRnzp AGAIN A .FILL x4000 B .FILL x0032 KBSR .FILL xFE00 .END - If someone strikes a key, the program will be interrupted and the
keyboard interrupt service routine will be executed as shown below.
What does the keyboard interrupt service routine do?
.ORIG x1000 LDI R0, KBDR TRAP x21 TRAP x21 RTI KBDR .FILL xFE02 .END - Finally, suppose the program of part (a) started executing, and someone sitting at the keyboard struck a key. What would you see on the screen?
.ORIG x3000
LD R0, ASCII
LD R1, NEG
AGAIN LDI R2, DSR
BRzp AGAIN
STI R0, DDR
ADD R0, R0, #1
ADD R2, R0, R1
BRnp AGAIN
HALT
ASCII .FILL x0041
NEG .FILL xFFB6
DSR .FILL xFE04
DDR .FILL xFE06
.END
.ORIG x3000
ST R0, x3007
LEA R0, LABEL
TRAP x22
TRAP x25
LABEL .STRINGZ "FUNKY"
LABEL2 .STRINGZ "HELLO WORLD"
.END
1. Address of the next node
2. Starting address of the memory locations where name of the student is stored
3. Starting address of the memory locations where the his/her exam score is stored
in the given order. The first node is stored in locations x4000 ~ x4002. The ASCII code x0000 is used as a sentinel to indicate the end of the string. Both the name and exam score are stored as strings.
Write down the student's name and score in the order that it appears in the list.
Address Contents
x4000 x4016
x4001 x4003
x4002 x4008
x4003 x004D
x4004 x0061
x4005 x0072
x4006 x0063
x4007 x0000
x4008 x0039
x4009 x0030
x400A x0000
x400B x0000
x400C x4019
x400D x401E
x400E x004A
x400F x0061
x4010 x0063
x4011 x006B
x4012 x0000
x4013 x0031
x4014 x0038
x4015 x0000
x4016 x400B
x4017 x400E
X4018 x4013
x4019 x004D
x401A x0069
x401B x006B
x401C x0065
x401D x0000
x401E x0037
x401F x0036
x4020 x0000
- The program below counts the number of zeros in a 16-bit word. Fill in the missing blanks below to make it work.
.ORIG x3000 AND R0, R0, #0 LD R1, SIXTEEN LD R2, WORD A BRn B ________________ B ________________ BRz C ________________ BR A ; note: BR = BRnzp C ST R0, RESULT HALT SIXTEEN .FILL #16 WORD .BLKW #1 RESULT .BLKW #1 .END - After you have the correct answer above, what one instruction can you change (without adding any instructions) that will make the program count the number of ones instead?
- What does this new instruction do?
- There are two different formats for specifying the operands of this instruction. Fill them out below.
