MARIE Program Trace for Fetch-Execute Cycle with Register Transfer Notation

[twoski]

Homework Statement

This question is being done using MARIE.

Suppose initially AC = 1000, M[200] = FFFF, PC = 100. Trace the fetch execute (instruction) cycle of the following sequence of MARIE instructions using Register transfer notation (similar to Figure 4.14 of your text).

Load 200 //PC = 100 here
Add 200
Jns 300

The Attempt at a Solution

I am using the same notation as my book.

The problem is, in the textbook program the hex contents of memory is listed for 100,101,102... etc. In my program, i am only told that M[200] = FFFF. What happens when i try to access M[101]? Is it just zeroes? Am i right in assuming that?

 

[aralbrec]

The problem is, in the textbook program the hex contents of memory is listed for 100,101,102... etc. In my program, i am only told that M[200] = FFFF. What happens when i try to access M[101]? Is it just zeroes? Am i right in assuming that?

If you don't know what is there you cannot assume anything.

But I think you do know what is there. Where is your program stored?

 

[twoski]

Ohhh... I totally forgot that PC is 100 at the first instruction.

So therefore, IR should be 3200 since Add is 3 and we're adding 200. Right?

 

[aralbrec]

Ohhh... I totally forgot that PC is 100 at the first instruction.

So therefore, IR should be 3200 since Add is 3 and we're adding 200. Right?

Adding the contents of address 200 to the accumulator, yes.

You have the right idea; the opcode for Add is read from address 101. You'll have to trust yourself on the specifics since I don't know anything about Marie :)

 

[twoski]

She is a cruel mistress.

Okay so technically this program is loading FFFF then adding FFFF to it. Since MARIE uses 2's complement, this is the same (i think) as adding -1 to -1 which results in FFFD.

 

[aralbrec]

She is a cruel mistress.

lol

Okay so technically this program is loading FFFF then adding FFFF to it. Since MARIE uses 2's complement, this is the same (i think) as adding -1 to -1 which results in FFFD.

-2 is FFFE

+2 = ..0010
complement = ..1101
increment = ..1110 = E

FFFF=-1
FFFE=-2
FFFD=-3
...Whether the numbers are interpretted as unsigned or signed (2's complement), the result is the same. An unsigned addition FFFF+FFFF will also result in FFFE. Only the interpretation of the bits (by a human) will change.

 

[twoski]

Oh my bad, that was supposed to read FFFE.

Here's what i have.

 

[rcgldr]

Not included in your document is the description for JNS, but I found a document for MARIE computer doing a web search. JNS is a old style call instruction that stores the return at address X and then jumps to address X+1. On the JNS instruction, you left out the fetch (don't forget the PC = PC + 1 part), decode, and get operand descriptions. The opcode for JNS is 0000, but you left the IR as 3200, when it should be 0000 + address. The JNS "fetch" descritpion is really the "execute" description.

Here's an extra question: After you've done the JNS 300, how could you use the JUMPI (jump indirect) instruction to "return" back to 103?

 

[twoski]

Whoops.

On a related note, i have to decipher this program. Specifically, determine how many times the instruction at S is executed, and what is contained in Data when the program halts. I don't get how this can be determined since the input could alter how long it takes for the program to halt.

000 5000 | S INPUT
001 400A | SUBT Thirty
002 300B | ADD Data
003      | STORE Data
004 100C | LOAD Round
005 400D | SUBT One
006 200C | STORE Round
007      | SKIPCOND 400
008 9000 | JUMP S
009 7000 | HALT
00A 0030 | Thirty DEC 48
00B 0000 | Data DEC 0
00C      | Round DEC 10
00D 0001 | One DEC 1

 

[rcgldr]

You have part of the JNS execute mixed with the decode. The decode for JNS is the same as the other instructions. The execute should include a M[MAR] = PC (103), or perhaps MBR = PC, then M[MAR] = PC (I don't know how this processor is supposed to work), followed by PC = AC.

 

[twoski]

Our textbook shows the transfer notation for Jns as such:

JNS X

MBR <- PC
MAR <- X
M[MAR] <- MBR
MBR <- X
AC <- 1
AC <- AC + MBR
PC <- AC

The only place where PC is used is at the very start and very end :S

 

[rcgldr]

I have to decipher this program.

The skipcond instruction is only affected by the last math operation, so the input does not effect the number of times the loop is run.

Our textbook shows the transfer notation for Jns as such:

JNS X

MBR <- PC
MAR <- X
M[MAR] <- MBR
MBR <- X
AC <- 1
AC <- AC + MBR
PC <- AC

The only place where PC is used is at the very start and very end

This seems to be correct, but the fetch part of JNS is the same as it for all the other instructions. The fetch for JNS does not include MBR <- PC, that is part of the execute.

 

[twoski]

I want to be doing MBR <- PC before PC <- AC in order to store 103, right? because otherwise 103 is erased.

 

[rcgldr]

I want to be doing MBR <- PC before PC <- AC in order to store 103, right? because otherwise 103 is erased.

MBR, PC, and AC are registers, memory is not erased when you do operations with the registers. The fetch for JNS and all instructions will be the same for this processor. Only the execute part will be different. Try writing the trace again for the JNS using the same fetch and decode as the other instructions, and then the execute as shown from your book.

On side note, after doing the JNS 300, if the instruction at 301 was JUMPI 300, what would that do?

 

[twoski]

Okay so if I'm understanding SKIPCOND right, it uses the second 2 digits of the operand to do its thing.

So SKIPCOND 400 uses 00 which means that if AC < 0 it skips the next instruction. Which means that the instruction S will be executed twice since it's comparing the Round label to 0.

I don't understand what it's asking me to say about the Data label when the program halts. Isn't Data dependent on the input?

 

[rcgldr]

Okay so if I'm understanding SKIPCOND right, it uses the second 2 digits of the operand to do its thing.

It seems your book isn't explaining the instructions well. SKIPCOND uses the first 2 bits of the 12 bit operand, so 000 checks for AC < 0, 400 checks for AC == 0, and 800 checks for AC > 0.

Again, could you try redoing the trace again for the JNS using the same fetch and decode as the other instructions, and then the execute as shown from your book. On side note, after doing the JNS 300, if the instruction at 301 was JUMPI 300, what would that do?

 

[twoski]

I guess I'm confused why it uses 000, 400 and 800 to determine the action that SKIPCOND uses. It explains in the book that if IR[11-10] == 01 then it does an equality check, 00 is < and 10 is >. IR[11-10] in this case is 40 though, right? I thought we were working with individual bits and not hex...

I find the mixture of binary and hex more messy than beneficial in this assignment. :/

I'm not sure i follow what you want me to do with the JNS, It's basically the same as all the other instructions except at the execute stage it does things differently with the PC. I marked in green the 2 lines that might need to be moved around but the rest matches up with everything else.

 

[rcgldr]

I guess I'm confused why it uses 000, 400 and 800 to determine the action that SKIPCOND uses. It explains in the book that if IR[11-10] == 01 then it does an equality check, 00 is < and 10 is >. IR[11-10] in this case is 40 though, right? I thought we were working with individual bits and not hex... I find the mixture of binary and hex more messy than beneficial in this assignment.

It might be more messy, but you'll need to know how to code the SKIPCOND instruction using the conventional format, which uses hex, so if IR[11 10] = 00, then IR = 000, IR[11 10] = 01, then IR = 400, and IR[11 10] = 10, then IR = 800.

I'm not sure i follow what you want me to do with the JNS, It's basically the same as all the other instructions except at the execute stage it does things differently with the PC. I marked in green the 2 lines that might need to be moved around but the rest matches up with everything else.

You should not move those 2 lines around. The lines for fetch and decode should be identical to the lines you have for the other instructions. There is no get operand step, since memory is not being read. Your textbook doesn't explain that MAR will hold the value for X. See if you can complete the trace for JNS 300 starting with this partial trace:

fetch           MAR <- PC
                IR  <- M[MAR]
                PC  <- PC + 1
decode          MAR <- IR[11 0]
execute         MBR <- PC
                ...

In order to understand the purpose of the JNS 300, assume memory location 301 has a JUMPI 300 and do the trace for JUMPI 300.

 

[twoski]

I think it's proper now.

You'd just use the indirect jump on 300 since 103 is stored at that location.

I have yet another question i can't solve.

Suppose we add a stack-duplicate (SDUP) instruction in MARIE where memory location FFF is reserved to store the stack pointer (address of the top of the stack).
When executed, SDUP duplicates the top of the stack by pushing another copy of its value onto the stack. For example, if M[FFF] = F01 and M[F01] = 1234, upon execution, M[F00] = M[F01] = 1234, and M[FFF] = F00.

(a) Represent the fetch-decode-execute cycle of this instruction in RTN.
(b) Can this SDUP instruction be simulated using the original set of MARIE instructions? If so, write the program fragment that does the simulation. If not, explain what difficulty arises?

I'm supposed to be doing it using register transfer notation, but i don't know what value to use for the instruction. If I'm calling SDUP F01 then what would i put into the IR?

This is messy and probably wrong but i don't know else what to do. Should i even be mentioning the AC in my solution?

 

[rcgldr]

I think it's proper now.

If AC <- AC + MAR is allowed in addition to AC <- AC + MBR, then you wouldn't need to use MBR <- IR[11-0] again, but I don't know what is allowed on the processor. What you have now is correct.

If I'm calling SDUP F01 then what would i put into the IR?

You'd be using SDUP FFF (instead of SDUP F01, M[FFF] contains the F01). You can make up any value you want, opcodes 0 through C are already used, so you could use opcode D, so the entire instruction for SDUP FFF could be hex DFFF. In this case, the fetch, decode, and get operand will be the same as your other instructions, since you need to get the stack address from memory at FFF. Try to create the trace using DFFF for the instruction word.

 

[twoski]

If i made the fetch in SDUP the same as the others then i'd be incrementing FFF which would mess it up though, right?

 

[rcgldr]

If i made the fetch in SDUP the same as the others then i'd be incrementing FFF which would mess it up though, right?

None of the other instructions increment a location in memory or any register except for PC <- PC + 1. SDUP will start off the same as LOAD, then continue with more execution steps after AC <- MBR as seen at the end of LOAD.

 

[twoski]

How close was i?

Also, I've made progress with the question from the first page regarding the program i have to examine.

It basically loads user input into the AC, subtracts 0x30, adds "Data" to the AC, and stores the AC at "Data" 10 times. The question asks what "Data" contains at the end, which confuses me because Data could contain anything depending on what you input for each iteration.

 

[rcgldr]

How close was i?[/QUOTE}This is what you want to do logically, but I don't know if M[AC] <- M[MBR] is allowed. If not, you'll need to separate this into multiple steps. Hint, use MBR to hold the data to be duplicated, start execute with:

MAR <- MBR
MBR <- M[MAR]

Assuming that MAR <- MAR - 1 isn't allowed, you'll have to use AC to do the decrement instead.

Also, I've made progress with the question from the first page regarding the program i have to examine. It basically loads user input into the AC, subtracts 0x30, adds "Data" to the AC, and stores the AC at "Data" 10 times. The question asks what "Data" contains at the end, which confuses me because Data could contain anything depending on what you input for each iteration.

What probably hasn't been explained to you is that 0x30 is the value for ASCII '0'. If the user enters a character from '0' to '9', then subtracting 0x30 converts the ASCII character into a value 0 to 9.

You're only supposed to describe what DATA contains based on the assumption that the user input '0' to '9', and did this 10 times.

 

[twoski]

Well if the user enters zero 10 times, then data will contain 0. If they enter 9 each time then data will contain 90, and so on... So i guess i could just give an explanation as to what the program does with user input and that would be sufficient?

 

[rcgldr]

Well if the user enters zero 10 times, then data will contain 0. If they enter 9 each time then data will contain 90, and so on... So i guess i could just give an explanation as to what the program does with user input and that would be sufficient?

Yes that would be sufficient. What if the user enters 0, 1, 2, 3, 4, 5, 6, 7, 8 , 9?