Computer Architecture and Assembly: Fibonacci, Instructions, and Codes

This document presents a comprehensive solution to a computer architecture assignment. The assignment focuses on implementing a Fibonacci sequence calculation using a MARIE assembly program, including the determination of the maximum input value for correct results. The solution also delves into the design of computer instructions, specifying the number of 0-address instructions based on the total instruction bits and the number of 1-address and 2-address instructions. Furthermore, the document provides code implementations for the expression A = (B + C) * (D – E) across 3-address, 2-address, 1-address, and 0-address machine architectures, demonstrating the different approaches to assembly code generation for the same computational task. The content is designed to assist students in understanding computer architecture concepts and assembly language programming.

Computer organisation &
architecture

TABLE OF CONTENTS
Task .................................................................................................................................................3
1)......................................................................................................................................................3
a) MARIE Program for calculating Fib(n) ..................................................................................3
b) Maximum value of n for getting correct results .....................................................................4
2)......................................................................................................................................................4
Computer instructions:.................................................................................................................4
3)......................................................................................................................................................5
Codes for implementation: A= (B + C) * (D – E).......................................................................5
2

TASK
1)
a) MARIE Program for calculating Fib(n)
Following is the program designed for calculating the value of Fib(n), where n is the user input
provided during execution.
For instance, when n = 7, the value is 13.
Hence, the below mentioned program is designed for getting the respective values in MARIE
simulation:
N= input('Pick a number\n');
Fib=zeros(1,N);
Fib(1)=1;
Fib(2)=1;
k=3
while k<=N
Fib(k)= Fib(k-2)+ Fib(k-1);
k= k+1;
end
fprintf('The Fibonacci sequence to %d terms is \n', N);
fprintf('%g',Fib);
fprintf('\n');
Following is the output of the program when simulated:
Pick a number
14
The Fibonacci sequence to 14 terms is
1 1 2 3 5 8 13 21 34 55 89 144 233 377
3

The above program when simulated in MARIE has certain steps which have been disclosed as
follows:
LOAD K
ADD ONE
STORE K
LOAD FIBK
ADD FIBK1
STORE FIBK
LOAD FIBK
SUBT FIBK1
STORE FIBK1
b) Maximum value of n for getting correct results
For finding the maximum value of n for a given function following program can be used
int Fib(int n)
{
if (n< 2)
return 1;
int n_1 = 1, n_2= 1;
for (int i=2; i<=n; i=1)
{
int n_new = n_1 +n_2;
n_1 = n_2;
n_2 = n_new;
}
return n_2;
}
2)
Computer instructions:
It has been provided that an instruction set has to be designed.
The instructions are 11 bits long.
4

It is also provided that 5 2-address instructions and 45 1-address instructions have been designed.
We need to calculate the number of 0-address instructions for fitting the instructions.
The instruction is 11 bits long, this implies that about 2048 instruction codes are
generated. Every address has about 2^4 values which means 16 values. This implies that 2-
address has 16*16 combinations
5 2-address instructions = 5*256 values = 1280 values
Similarly,
45 1-address instruction = 45*16 = 720 values.
These 720 values represent the 1-address instruction.
It can be stated that about 32 0-address instructions will be used for the particular program.
These have been depicted as follows:
11111100000
11111101111
32 0-address instructions
11111110000
11111111111
3)
Codes for implementation: A= (B + C) * (D – E)
Following computational program has been designed for implementing the expression: A= (B +
C) * (D – E)
For the 3- address machine:
Add R1, B, C
Sub R2, D, E
Mult A, R1, R2
For 2-address machine:
Load R1, B
Add R1, C
5

Load R2, D
Sub R2, E
Mult R2, R1
Store A, R2
For 1-address machine:
Load B
Add C
Store Temp
Load D
Sub E
Mult Temp
Store A
For 0-address machine:
Push B
Push C
Add
Push D
Push E
Sub
Mult
Store A
6