1. Instruction processing and interrupts

Instruction processing

FDE Cycle

The fetch-decode-execute cycle is the series of steps that a computer carries out when it runs a program.

• Fetch: The control unit fetches the next instruction from memory (this data comes through von Neumann bottleneck) and updates the program counter to determine where the next instruction is located. We first have to fetch an instruction from memory and place it into the IR.
• Decode: Translate the instruction into signals that the ALU can interpret and execute (it is decoded to determine what needs to be done next).
• Execute: This takes two steps.
  • Load any required data into the CPU registers. If a memory value is involved in the operation, it is retrieved and placed into the MBR.
  • Execute the instruction, placing the results in registers or memory.

Link to original

Interrupts

All computers provide a way of interrupting the FDE cycle, this is through the use of interrupts. Interrupts occur when:

• A user break (e.g. CTRL + C) is issued.
• I/O is required by the user or a program.
• A critical error occurs.

Interrupt

An interrupt allows us to alter the normal flow of execution of a program when an event of higher priority occurs. They can be triggered by different sources:

• I/O requests
• Arithmetic errors (e.g. div 0)
• Encountering invalid instructions

Each interrupt is associated with a procedure (Interrupt Service Routine) that directs the actions of the CPU to handle the events.

Link to original

Interrupt processing involves adding another step to the FDE cycle.

Processing an interrupt

To process an interrupt, a series of steps occur once one is detected: ?

1. Save data stored in registers into memory.
2. Look up Interrupt Service Routine address in interrupt table.
3. Place ISR address in PC.
4. Execute instructions of ISR.
5. Restore data to registers from memory.
6. Return to the FDE cycle.

For general-purpose computers, it is common to disable all interrupts during the time in which an interrupt is being processed. Typically, this is achieved by setting a bit in the Status (register).

• Interrupts that are ignored in this case are called Maskable Interrupt.
• Non-maskable Interrupts are those that must be processed in order to keep the system in a stable condition.

Interrupts are generally useful in processing I/O. (although interrupt-driven I/O is complicated) MARIE uses a modified form of programmed I/O:

• All output is placed in an output register, $OUT$.
• The CPU polls the input register, $IN$, until input is sensed.
• Whenever this happens, the value in the register is copied into the accumulator, $AC\leftarrow IN$.

Link to original

2. Tracing a simple MARIE program

Tracing a simple MARIE program

Consider the following program:

Address	Instruction	Contents of Memory
$100$	Load $104$	$0\text{x}1104$
$101$	Add $104$	$0\text{x}3105$
$102$	Store $104$	$0\text{x}2106$
$103$	Halt	$0\text{x}7000$
$104$	$0023$	$0\text{x}0023$
$105$	$\text{FFE}9$	$0\text{xFEE}9$
$106$	$0000$	$0\text{x}0000$

$001.\text{ Load }104$

Step	RTL	PC	IR	MAR	MBR	AC
(initial values)		$100$	-	-	-	-
Fetch	MAR $\leftarrow$ PC	$100$	-	$100$	-	-
	IR $\leftarrow \text{M}[$ MAR $]$	$100$	$1104$	$100$	-	-
	PC $\leftarrow$ PC $+1$	$101$	$1104$	$100$	-	-
Decode	MAR $\leftarrow$ IR $[11-0]$	$101$	$1104$	$104$	-	-
	(Decode IR $[15-12]$)
Get operand	MBR $\leftarrow \text{M}[$ MAR $]$	$101$	$1104$	$104$	$0023$	-
Execute	ACC $\leftarrow$ MBR	$104$	$1104$	$104$	$0023$	$0023$

$002.\text{ Add }105$

Step	RTL	PC	IR	MAR	MBR	AC
(initial values)		$101$	$1104$	$104$	$0023$	$0023$
Fetch	MAR $\leftarrow$ PC	$101$	$1104$	$101$	$0023$	$0023$
	IR $\leftarrow \text{M}[$ MAR $]$	$101$	$3105$	$104$	$0023$	$0023$
	PC $\leftarrow$ PC $+1$	$102$	$3105$	$104$	$0023$	$0023$
Decode	MAR $\leftarrow$ IR $[11-0]$	$102$	$3105$	$105$	$0023$	$0023$
	(Decode IR $[15-12]$)
Get operand	MBR $\leftarrow \text{M}[$ MAR $]$	$102$	$3105$	$105$	$\text{FFE}9$	$0023$
Execute	ACC $\leftarrow$ ACC $+$ MBR	$102$	$3105$	$105$	$\text{FFE}9$	$000\text{C}$

Link to original

3. Assemblers

Assemblers

Mnemonic instructions, such as $\text{Load }Y$, are easy for humans to write and understand but can’t be interpreted by computers.

Assembler

Assemblers translate mnemonic instructions into **machine language** that can be executed by computers.

An object program file is created from mnemonic source code in two passes: ?

• 1st pass: the assembler assembles as much of the program as possible it can while it builds a symbol table that contains memory references for all symbols in the program.
• 2nd pass: the instructions are completed using the values from the symbol table.

Link to original

Link to original

4. Extending the MARIE instruction set

Extending the MARIE instruction set

All of the MARIE instructions discussed so far use direct addressing.

But we may also need to use indirect addressing where the address of the address of the operand is given in the instruction.

MARIE’s extended instruction set contains the following indirect address mode instructions:

• $\text{AddI}$: Add value at address in address specified.
• $\text{JnS}$: Jump to subroutine at specified address.
• $\text{JumpI}$: Jump to the address in the address specified.

Additional useful instruction introduced here is:

• $\text{Clear}$: Zero the accumulator.

(see MARIE ISA for the full list)

$\text{AddI}$

The $\text{AddI}$ instruction specifies the address of the address of the operand to be added. It is implemented with RTL as follows:

$$\begin{array}{rl}MAR& \leftarrow X\\ MBR& \leftarrow M[MAR]\\ MAR& \leftarrow MBR\\ MBR& \leftarrow M[MAR]\\ AC& \leftarrow AC+MBR\end{array}$$

$\text{JnS}$

Jump-and-store, $\text{JnS}$, gives us limited functionality which allows us to use simple subroutines.

$$\begin{array}{rl}MBR& \leftarrow PC\\ MAR& \leftarrow X\\ M[MAR]& \leftarrow MBR\\ MBR& \leftarrow X\\ AC& \leftarrow 1\\ AC& \leftarrow AC+MBR\\ PC& \leftarrow AC\end{array}$$

$\text{JumpI}$

Jump to instruction specified by the address of the operand, $\text{JumpI}$, which can let us implement “return” label as $\text{JnS}$ hence jumping back to where we were earlier.

$$\begin{array}{rl}MAR& \leftarrow X\\ MBR& \leftarrow M[MAR]\\ PC& \leftarrow MBR\end{array}$$

$\text{Clear}$

We can clear the accumulator using $\text{Clear}$.

$$AC\leftarrow 0$$Link to original

5. Sample programming constructs

Programming Constructs

Below are common assembly equivalents of constructs.

Conditional Evaluation

; X=4, Y=5
; if (X-Y == 0)
;  X+Y
; stop
 
If,    Load X
       Subt Y
	   Skipcond 400
	   Jump EndIf
Then,  Load X
       Add Y
EndIf, Halt
X,     DEC 4
Y,     DEC 5

If, then, else

; X=4, Y=5
; if (X-Y == 0) {
;  X+Y
; } else {
;  X+X
; }
; stop
 
If,    Load X
       Subt Y
	   Skipcond 400
	   Jump Else
Then,  Load X
       Add Y
	   Jump EndIf
Else,  Load X
       Add X
EndIf, Halt
X,     DEC 4
Y,     DEC 5

Definite iteration

; for (i=0; i<10; i++) {
;  output i
; }
; stop
 
         Clear
		 Store Counter
Loop,    Load Counter
		 Subt Limit
		 Skipcond 000
		 Jump Next
		 Output
		 Load Counter
		 Add One
		 Store Counter
		 Jump Loop
Next,    Halt
Counter, DEC 0
Limit,   DEC 10
One,     DEC 1

Indefinite iteration

; while (x<0) {
;  output x
; }
; stop
 
Test, Load X
      Skipcond 000
	  Jump Next
	  Output
	  Jump Test
Next, Halt

Procedure invocation

; f() {
;  input
; }
;
; f();
; output
; f();
; output
; stop
 
      JnS Proc
	  Output
	  JnS Proc
	  Output
	  Halt
Proc, HEX 0
      Input
	  JumpI Proc

Link to original