6.2 MARIE Architecture, Registers & Instruction Set

Theory: MARIE Architecture, Registers & Instruction Set

MARIE (Machine Architecture that is Really Intuitive and Easy) is a model computer from Null & Lobur (Ch. 4). It is far too simple to do useful real-world work, but every idea in it (registers, a bus, an instruction set, fetch–decode–execute, a control unit) appears in exactly the same form in real processors. If you understand MARIE completely, real architectures are “just more of the same”.

MARIE’s Characteristics

Feature	MARIE
Data representation	binary, two’s complement
Program model	stored program: instructions and data live in the same memory
Word length	fixed: every data word and every instruction is 16 bits
Main memory	4K words ($2^{12} = 4096$), word-addressable, addresses $\text{000}_{16}$–$\text{FFF}_{16}$
Data word	16 bits
Instruction	16 bits = 4-bit opcode + 12-bit address
ALU	16-bit
Registers	seven, for control and data movement

MARIE’s Seven Registers

Register	Width	Holds	Why this width
AC (accumulator)	16	one operand of a two-operand instruction and the result (also used for conditions such as “less than zero”)	it holds a full 16-bit data word
MAR (memory address register)	12	the memory address of an instruction or operand	memory has $2^{12}$ words, so an address is 12 bits
MBR (memory buffer register)	16	data just read from memory, or about to be written to memory	a memory word is 16 bits
PC (program counter)	12	the address of the next instruction	it is an address, so 12 bits
IR (instruction register)	16	the instruction about to be executed	an instruction is 16 bits (opcode + address)
InREG	8	data read from an input device	MARIE’s I/O works one 8-bit character at a time
OutREG	8	data ready for an output device	same

Rule of thumb: registers that hold addresses (MAR, PC) are 12 bits because $4\text{K} = 2^{12}$; registers that hold data or instructions (AC, MBR, IR) are 16 bits because the word is 16 bits.

Mini-example

The largest address MAR can hold is $1111\,1111\,1111_2 = \text{FFF}_{16} = 4095$. The AC, as a 16-bit two’s complement register, holds values from $-2^{15} = -32768$ to $2^{15}-1 = 32767$.

The Datapath and the Common Bus

The registers are interconnected, and connected to main memory, through one common 16-bit data bus. Each device on the bus has a unique number; the control unit puts that number on the control lines to say which device sends data onto the bus and which device receives it.

Device	Memory	MAR	PC	MBR	AC	InREG	OutREG	IR
Bus number	0	1	2	3	4	5	6	7
Binary	000	001	010	011	100	101	110	111

In addition, there are separate connections between the AC, the MBR and the ALU. This lets an arithmetic result such as AC + MBR go straight back into the AC without using the main bus (the control signal for this path is called $L_{ALT}$; see 7.1).

Diagram loads as you scroll.

Instruction Set Architecture (ISA)

A computer’s ISA specifies the format of its instructions and the primitive operations the machine can perform. It is the interface between hardware and software: the hardware promises to execute these instructions; the software (compiler, assembler, programmer) promises to use only these. Real ISAs can have hundreds of instructions; MARIE has fifteen (opcodes $0$–$\text{E}$).

Instruction format

15–12opcode (4 bits)

11–0address (12 bits)

Because the opcode is the first hex digit and the address is the last three hex digits, hex is the natural way to read MARIE code: instruction 1104 is opcode 1 (Load) with address 104.

The full instruction set

Opcode (bin)	Hex	Instruction	Meaning	RTN
0000	0	JnS X	store return address at X, jump to X+1	MBR ← PC; MAR ← X; M[MAR] ← MBR; MBR ← X; AC ← 1; AC ← AC + MBR; PC ← AC
0001	1	Load X	AC gets contents of X	MAR ← X; MBR ← M[MAR]; AC ← MBR
0010	2	Store X	contents of AC go to X	MAR ← X, MBR ← AC; M[MAR] ← MBR
0011	3	Add X	AC ← AC + M[X]	MAR ← X; MBR ← M[MAR]; AC ← AC + MBR
0100	4	Subt X	AC ← AC − M[X]	MAR ← X; MBR ← M[MAR]; AC ← AC − MBR
0101	5	Input	read a value from the keyboard into AC	AC ← InREG
0110	6	Output	send AC to the display	OutREG ← AC
0111	7	Halt	stop the program	(none)
1000	8	Skipcond	skip next instruction on a condition	see below
1001	9	Jump X	continue at address X	PC ← IR[11–0]
1010	A	Clear	AC ← 0	AC ← 0
1011	B	AddI X	add indirect	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← M[MAR]; AC ← AC + MBR
1100	C	JumpI X	jump indirect	MAR ← X; MBR ← M[MAR]; PC ← MBR
1101	D	LoadI X	load indirect	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← M[MAR]; AC ← MBR
1110	E	StoreI X	store indirect	MAR ← X; MBR ← M[MAR]; MAR ← MBR; MBR ← AC; M[MAR] ← MBR

In RTN / RTL (register transfer notation/language), M[X] means the data stored in memory location X and ← means copy into. Each machine instruction is really a short sequence of these microoperations.

Notice that everything goes through MAR and MBR: memory can only be addressed via the MAR and data only enters or leaves memory via the MBR. Instructions that do not touch memory (Input, Output, Halt, Skipcond, Jump, Clear) ignore the address field; the assembler fills it with zeros, e.g. Halt = 7000.

Mini-example (as in the lecture)

The bit pattern 0001 0000 0000 0011 in the IR: opcode $0001 = 1$ → Load; address $0000\,0000\,0011 = 3$. So it is Load 3, hex 1003. Its RTN: MAR ← 003, MBR ← M[003], AC ← MBR.

Encoding and Decoding Instructions

Assembly → hex (encoding):

1. Look up the opcode’s hex digit (Load = 1, Store = 2, …).
2. Write the address as 3 hex digits (pad with leading zeros).
3. Concatenate: opcode digit + 3 address digits.
4. For binary, expand each hex digit into 4 bits.

Hex/binary → assembly (decoding):

1. If given binary, split into 4 + 12 bits (or into four groups of 4 and convert each to hex).
2. The first hex digit is the opcode → mnemonic.
3. The last three hex digits are the address (meaningless for Input/Output/Halt/Clear; for Skipcond they hold the condition).

Mini-example

Store 1A3 → opcode 2, address 1A3 → 21A3 = 0010 0001 1010 0011. Going back: 0100 0000 1111 1111 → 4, 0FF → Subt 0FF (hex 40FF).

Skipcond: MARIE’s Only Conditional Instruction

Skipcond (opcode 8) skips the next instruction (by doing PC ← PC + 1 one extra time) if the AC satisfies a condition. The condition is chosen by bits 11–10 of the instruction:

If IR[11-10] = 00 then
    If AC < 0 then PC <- PC + 1
else If IR[11-10] = 01 then
    If AC = 0 then PC <- PC + 1
else If IR[11-10] = 10 then
    If AC > 0 then PC <- PC + 1

Bits 11–10	Assembly	Hex	Skips the next instruction when
00	Skipcond 000	8000	AC $\lt$ 0
01	Skipcond 400	8400	AC = 0
10	Skipcond 800	8800	AC $\gt$ 0

Why “400” and “800”? The operand is written as the 3 hex digits of the address field: bits 11–10 = 01 gives 0100 0000 0000 = 400, and 10 gives 1000 0000 0000 = 800.

Mini-example (as in the lecture)

The IR holds 1000 1000 0000 0000. Opcode $1000 = 8$ → Skipcond; bits 11–10 = 10 → skip if AC $\gt 0$. In hex: $1000 = 8$, $1000 = 8$, $0000 = 0$, $0000 = 0$ → 8800, i.e. Skipcond 800.

Skipcond is almost always followed by a Jump. “Skip the jump if the condition holds” is how MARIE builds if statements and loops (see 6.4).

Indirect Addressing

In a direct instruction (Load X) the address field X is the address of the data. In an indirect instruction (LoadI X, AddI X, StoreI X, JumpI X) the address field X is the address of a pointer: memory location X holds the address of the data.

Instruction	Effective result
Load X	AC ← M[X]
LoadI X	AC ← M[ M[X] ]
AddI X	AC ← AC + M[ M[X] ]
StoreI X	M[ M[X] ] ← AC
JumpI X	PC ← M[X]

Indirection costs one extra memory read (MAR ← MBR; MBR ← M[MAR]) but allows pointers: by changing the value stored at X, the same instruction can walk through an array.

JnS: Jump-and-Store (Subroutine Call)

JnS X stores the return address (the current PC, which already points to the instruction after the JnS) in memory location X and then continues at X + 1. The subroutine ends with JumpI X, which jumps to the address stored at X, i.e. back to the caller.

---

Worked Examples

Exercise 1

Hand-encode each MARIE instruction in hexadecimal and in binary.

(a) Load 104 (b) Store 1A3 (c) Skipcond 800 (d) Jump 03F (e) Halt (f) Clear (g) AddI 20F

Show solution ↓Hide solution ↑

Solution

Opcode digit + 3-digit address; non-memory instructions get address 000.

Instruction	Opcode	Address	Hex	Binary
Load 104	1	104	1104	0001 0001 0000 0100
Store 1A3	2	1A3	21A3	0010 0001 1010 0011
Skipcond 800	8	800	8800	1000 1000 0000 0000
Jump 03F	9	03F	903F	1001 0000 0011 1111
Halt	7	000	7000	0111 0000 0000 0000
Clear	A	000	A000	1010 0000 0000 0000
AddI 20F	B	20F	B20F	1011 0010 0000 1111

Check (d): $\text{03F}_{16} = 63$ and $0000\,0011\,1111_2 = 32+16+8+4+2+1 = 63$ ✓.

Exercise 2

Decode each MARIE machine instruction into assembly language and give its RTN.

(a) $\text{2106}_{16}$ (b) $\text{9100}_{16}$ (c) $\text{8400}_{16}$ (d) $\text{C108}_{16}$ (e) $\text{6000}_{16}$ (f) $0000\,0011\,0000\,0000_2$

Show solution ↓Hide solution ↑

Solution

First hex digit = opcode, last three = address.

Code	Opcode	Address	Assembly	RTN
2106	2	106	Store 106	MAR ← 106, MBR ← AC; M[MAR] ← MBR
9100	9	100	Jump 100	PC ← IR[11–0] = 100
8400	8	400 → bits 11–10 = 01	Skipcond 400	if AC = 0 then PC ← PC + 1
C108	C	108	JumpI 108	MAR ← 108; MBR ← M[MAR]; PC ← MBR
6000	6	(unused)	Output	OutREG ← AC

(f) Group the bits: $0000\ 0011\ 0000\ 0000$ → hex 0300. Opcode 0 → JnS 300: MBR ← PC; MAR ← 300; M[MAR] ← MBR; MBR ← 300; AC ← 1; AC ← AC + MBR; PC ← AC (so PC = 301).

Exercise 3

The AC holds each value below and the next instruction is a Skipcond. State whether the following instruction is skipped.

	AC (hex)	Instruction
(a)	FFFB	Skipcond 000
(b)	FFFB	Skipcond 800
(c)	0000	Skipcond 400
(d)	0000	Skipcond 800
(e)	0005	Skipcond 800
(f)	8000	Skipcond 000

Show solution ↓Hide solution ↑

Solution

First interpret the AC as a 16-bit two’s complement number (MSB 1 → negative).

	AC	Signed value	Condition	Skip?
(a)	FFFB	MSB 1 → $-(0004+1) = -5$	AC $\lt 0$	Yes
(b)	FFFB	$-5$	AC $\gt 0$	No
(c)	0000	$0$	AC $= 0$	Yes
(d)	0000	$0$	AC $\gt 0$	No (0 is not positive)
(e)	0005	$+5$	AC $\gt 0$	Yes
(f)	8000	$-32768$	AC $\lt 0$	Yes

To negate FFFB: invert → 0004, add 1 → 0005, so FFFB = $-5$ ✓.

Exercise 4

Memory contains: $M[\text{200}] = \text{0205}$, $M[\text{205}] = \text{0042}$. The AC holds 0010. Starting from this state each time, give the result of:

(a) Load 200 (b) LoadI 200 (c) AddI 200 (d) StoreI 200 (e) JumpI 200

Show the RTN steps with values for (c).

Show solution ↓Hide solution ↑

Solution

(a) Direct: AC ← M[200] = 0205.

(b) Indirect: M[200] = 0205 is a pointer, so AC ← M[205] = 0042.

(c) Step by step:

RTN	MAR	MBR	AC
MAR ← X	200		0010
MBR ← M[MAR]	200	0205	0010
MAR ← MBR	205	0205	0010
MBR ← M[MAR]	205	0042	0010
AC ← AC + MBR	205	0042	0052

$\text{0010} + \text{0042} = \text{0052}$ (16 + 66 = 82 = $\text{52}_{16}$ ✓).

(d) M[M[200]] = M[205] ← AC, so M[205] becomes 0010 (M[200] stays 0205).

(e) PC ← M[200] = 205: execution continues at address 205.

Exercise 5

The instruction JnS 200 is stored at address 105. Trace its RTN, giving the values of PC, MAR, MBR and AC after each step, and state what is in memory location 200 afterwards and where execution continues. (Assume AC = 0007 beforehand.)

Show solution ↓Hide solution ↑

Solution

After fetching the instruction at 105, the PC has already been incremented to 106 (the return address).

RTN	PC	MAR	MBR	AC	Memory
(after fetch)	106			0007
MBR ← PC	106		0106	0007
MAR ← X	106	200	0106	0007
M[MAR] ← MBR	106	200	0106	0007	M[200] = 0106
MBR ← X	106	200	0200	0007
AC ← 1	106	200	0200	0001
AC ← AC + MBR	106	200	0200	0201
PC ← AC	201	200	0200	0201

So M[200] = 0106 (the return address) and execution continues at 201, the first instruction of the subroutine. When the subroutine finishes with JumpI 200, PC ← M[200] = 106 and the caller resumes right after the JnS ✓.

JnS overwrites the AC (with X + 1). If the caller needs the AC value, store it before calling.

Exercise 6

(a) Why is MARIE’s MAR 12 bits while its AC is 16 bits? (b) What would have to change if MARIE’s memory were enlarged to 16K words, keeping 16-bit instructions? (c) How many different opcodes can MARIE’s format support, and how many are used?

Show solution ↓Hide solution ↑

Solution

(a) The MAR holds an address. Memory has $4\text{K} = 2^{12}$ words, so 12 bits are enough to name every word (000–FFF). The AC holds a data word, and MARIE’s data words are 16 bits.

(b) $16\text{K} = 2^{14}$ words → addresses need 14 bits, so MAR and PC would grow to 14 bits. But a 16-bit instruction with a 4-bit opcode has only 12 address bits, so a direct instruction could reach only the first 4K words; the rest would be reachable only indirectly (through 16-bit pointers via LoadI/StoreI/JumpI) or the instruction format would have to change (e.g. 2-bit opcode, which would allow only 4 instructions).

(c) 4 opcode bits → $2^4 = 16$ possible opcodes ($0$–$\text{F}$). MARIE uses 15 ($0$–$\text{E}$), leaving one ($\text{F}$) free.