Tue, 12 Nov 2013, 22:44

My students,

As promised, my solution to problem 6 on midterm 2, 2011.  It was not an
easy problem, and you should not be disappointed if you could not figure
it out on your own.  It was one of those problem which are good for
stretching your knowledge to the limit, better suited for a problem set
than an in-class exam.

In any case, here is the way I solved it.  (I did not make it up.  That
credit goes to one of my TAs.)

The first thing I did was look at the contents of each location at each
point in time to see what I could infer about the four instructions that
were executed.  Recall that for each instruction we could tell the contents
of these locations at the end of the fetch phase and at the end of processing.

For example, since we know that the fetch phase of each instruction requires
one memory access, it does not surprise us that the contents of the PC at the
end of instruction i is the same as the contents of MAR at the end of the fetch
phase of instruction i+1.  Also not surprising that at the end of fetch, IR
contains the instruction, which is the contents of the memory location specified
by MAR.

From this, we already know that the four instructions are B,E,I,and J, and
they are contained in locations x1800, A, D, and F respectively.

Since we know that the fetch phase increments PC, we know immediately that
A = x1801, D = x1802, and H = x1803.  Since the PC changes from H at the end 
of fetch of the third instruction to F at the end of processing the third 
instruction, we know the third instruction is a control instruction.  Since
incrementing F gives us A (x1801), F must be x1800.

At this point, we know:

A: x1801
B: instruction 1, ??
C: ??
D: x1802
E: instruction 2, ??
F: x1800
G: ??
H: x1803
I: instruction 3, a control instruction
J: instruction 4, ??

Next I noticed that the 4th instruction did not involve memory or control,
and it did write into R4.  The value x223A is sufficiently far from x1801
that the 4th instruction could not be an LEA.  Noting that R1 contained at
that time x2233, I infer that the 4th instruction was ADD R4,R1,#7, which 
is 0001 100 001 1 00111, which is x1867.  I also note that J is in memory 
location x1800.

Next I noticed that the second instruction required a memory access after the
fetch phase, and none of the registers were written to.  Also, the PC was not
updated after the fetch phase.  This means the second instruction is a store G 
into x1800.  Since the 4th instruction is in x1800, G must be that instruction,
0001 100 001 1 00111, which in hex is x1867.  Since the source of a store must
be the value in a register, C must be x1867.  The 2nd instruction must be
ST R5, location x1800, which is 0011 101 111111110, or x3BFE.

Next I note that 3rd instruction, a control instruction changes the PC to 
x1800.  I note that R7 does not change so the 3rd instruction can't be a JSR.
I note that the MAR does not change, so the only possibility is a conditional
branch.  The problem states that this instruction is x?F??.  Given the
incremented PC is x1803 and the target PC is x1800, I can infer that the
3rd instruction is 0000 111 111111101, or x0FFD.

At this point we know:

A: x1801
B: instruction 1, ??
C: x1867
D: x1802
E: instruction 2, x3BFE
F: x1800
G: x1867
H: x1803
I: instruction 3, a control instruction, x0FFD
J: instruction 4, x1867

The only thing I am still missing is the first instruction.  Since the PC
has not changed between fetch and completion and no memory activity is
required, and R7 has not changed, we are left with the operates and LEA,
with a write of x1867 to R5.  Examining the contents of the registers, we
see there is no way we can construct the result x1867 from information
in the registers.  However, since the instruction is at location x1800, we
can construct x1867 with an LEA instruction: 1110 101 001100110, i.e., xEA66.

And we are done!

As I said in class, this was a very difficult problem, perhaps the hardest
problem I have ever put on a EE306 exam.  It is not a trick question.  But
it does require you to pull together everything you know to solve it.  In the
limited time of an in-class exam, I think in retrospect, it was too hard a
problem to put on the exam.  Nonetheless, studying it and understanding it
gives you deeper insights into the workings of the LC-3.

Good luck on the midterm tomorrow.

Yale Patt