ITC544 Assignment 1: Computer Architecture and Fibonacci Program

This document presents a comprehensive solution to a computer science assignment (ITC544) covering several key areas. The first part addresses data representation, including base conversions (binary, octal, decimal, and base-3), and determining the range of values representable by a tiny co...Read More

Question 1.
a) Determine the value of base b if (152)b = 0x6A. Please show all steps. [3 marks]
0x6a = 161 x 6 + 160 x 10
= 96 + 10
= 106
152b = = b2 x 1 + b1 x 5 + b0 x 2 = b2 + 5b + 2
Since both values are equal then
b2 + 5b + 2 = 106
 (b + 13) ( b – 8 ) = 0
 The solution for b is -13 and +8. –ve base would result in values less than 1. So base
must be +ve number i.e. 8
b) Convert the followings: (Please show all steps; no marks will be awarded if no steps are
shown) [1.5x4 = 6 marks]
i) 0xBAD into 3-base representation
0xBAD = 162 x 11 + 161 x 10 + 160 x 13
= 2816 + 160 + 13
= 2989 in decimal
Converting this to Base 3 using repeated division
2989 / 3 = 996 R 1
996 / 3 = 332 R 0
332 / 3 = 110 R 2
110 / 3 = 36 R 2
36 / 3 = 12 R 0
12 / 3 = 4 R 0
4 / 3 = 1 R 1
1/ 3 = 0 R 1
 0x BAD = 110022013
ii) 3217 into 2-base (binary) representation
Converting 3217 to base 2 using repeated division
3217 / 2 = 1608 R 1
1608 / 2 = 804 R 0
804 / 2 = 402 R 0
402 / 2 = 201 R 0

201 / 2 = 100 R 1
100 / 2 = 50 R 0
50 / 2 = 25 R 0
25 / 2 = 12 R 1
12 / 2 = 6 R 0
6 / 2 = 3 R 0
3 / 2 = 1 R 1
1 / 2 = 0 R 1
 3217 = 110010010001b
iii) 1235 into octal representation
Converting 1235 to base 8 by repeated division
1235 / 8 = 154 R 3
154 / 8 = 19 R 2
19 / 8 = 2 R 3
2 / 8 = 0 R 2
 1235 = 23238
iv) 21.218 into decimal representation
c) Given a (very) tiny computer that has a word size of 3 bits, what are the lowest value
(negative number) and the highest value (positive number) that this computer can represent in
each of the following representations? [3 marks]
i) One's complement
Highest Positive Value = 2(3-1) -1 = + 3
Highest Negative Value = - (2(3-1) -1) = -3
ii) Two's complement
Highest Positive Value = 2(3-1) -1 = + 3
Highest Negative Value = - (2(3-1)) = -4
iii) Signed Magnitude
Highest Positive Value = 2(3-1) -1 = + 3
Highest Negative Value = - (2(3-1) -1) = -3

Question 2.
a) The Fibonacci numbers are the numbers in the following integer sequence, called the
Fibonacci sequence, and are characterised by the fact that every number after the first two is
the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 114, … etc.
By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each
subsequent number is the sum of the previous two. We define Fib(0)=0, Fib(1)=1, Fib(2)=1,
Fib(3)=2, Fib(4)=3, etc. The first 22 Fibonacci numbers given below:
Fib(0)
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(5)
Fib(6)
Fib(7)
Fib(8)
Fib(9)
Fib(10)
0
1
1
2
3
5
8
13
21
34
55
Fib(11)
Fib(12)
Fib(13)
Fib(14)
Fib(15)
Fib(16)
Fib(17)
Fib(18)
Fib(19)
Fib(20)
Fib(21)
89
144
233
377
610

987
1597
2584
4181
6765
10946
Write a MARIE program to calculate Fib(n), where the user inputs n. For example, if the user
inputs 7, the program outputs the value 13; if the user inputs 15, the program outputs the
value 610; if the user inputs 20, the program outputs the value 6765 and so on. You need to
write and run the program using MARIE simulator. Please include appropriate comments to
make your code readable.[8 marks]
///The Fibonacci numbers are the numbers in the following integer sequence,
///called the Fibonacci sequence, and are characterised by the fact that
///every number after the first two is the sum of the two preceding ones:
///0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 114, … etc.
///a MARIE program to calculate Fib(n), where the user inputs n
ORG 0
/// Get user input for Fib (n)
INPUT
/// Store input in Variable
STORE Fibn
///Generate Fib numbers till loop count greater than 0
loop, LOAD Fibn
SUBT ONE / Subtract one for current loop
STORE Fibn / Fibn = Fibn - 1

SKIPCOND 800 / Execute Next Inst if AC = 0
JUMP exitloop
///Calculate Fib(n) = Fib(n- 1) + Fib(n-2)
CLEAR / Set AC to 0
ADD Fibn_1 / AC + Fibn0
ADD Fibn_2 / AC + Fibn1 => AC = Fibn0 + Fibn1
STORE Fibtemp / Fibn2 = AC => Fibn2 = Fibn0 + Fibn1
OUTPUT / for Debug output result every iteration
/// Fibn_1 and Fibn_2 update
LOAD Fibn_2
STORE Fibn_1 / Fibn_1 = Fibn_2
LOAD Fibtemp
STORE Fibn_2 / Fibn_2 = Fibtemp
JUMP loop
exitloop, LOAD Fibtemp
OUTPUT
End, HALT / HALT process
/// We define Fib(0)=0, Fib(1)=1
Fibn, DEC 0 / User Input
Fibn_1, DEC 0 / Fib(0) = 0

Fibn_2, DEC 1 / Fib(1) = 1
Fibtemp, DEC 0 / Temp to hold intermediate results
/// Constants used in Prog
ONE, DEC 1
b) For some values of n, your program will not produce correct results. You can check this by
gradually increasing the values of n and checking for the correct outputs. What is the
maximum value of n for which your program produces a correct result? Why? Please
comment on this [3 marks].
Registers in MARIE are all 16 bits and use two’s complement representation for
numbers. Highest possible positive number is Highest Positive Value = 2(16-1) -1
= + 32766. Fib number(23) = 28657. Any number larger than this is not
representable by the simulator and hence can’t produce numbers beyond 23
faithfully.

Question3.
a) What are the 'interrupts' in a computer system? Describe the approache****** deal ******
multiple interrupts in a system. [4 marks]
CPU has to interact with external devices to exchange data for the program and get user
inputs. But I/O devices respond much slowly compared to CPU execution speed. To avoid
CPU from wasting time waiting for I/O to complete operation, it is allowed to execute
instructions and interrupted by I/O devices when they have completed operation and want to
transfer data to / from CPU. This mechanism is implemented by use of signal called Interrupt.
The device can have several I/O devices at the same time and it might happen more than one
device needs access to CPU at the same time or at time when CPU is already servicing
another interrupt. This is case of multiple interrupts. Different CPU deal with it in different
manner. Some CPU use interrupt masking. In this case, the CPU does not acknowledge
existence of any other interrupt when it is already in interrupted state due to earlier interrupt.
The CPU shall finish execution of this interrupt first and on return it will acknowledge
presence of any other interrupt and service it. Another approach is nested interrupt. It used
stack and context switching operations. The CPU saves current register state and enters the
Interrupt handler code. While servicing and Interrupt, if it encounters another interrupt, it
would again save the correct register state and enter handler routine of this new interrupt.
This is called nested interrupt. Most processors use this scheme as it is important to
acknowledge interrupts as they arrive and resolve them by serving the interrupt routine.
b) Analyse the benefits of using a multiple-bus architecture compared to a single-bus
architecture for a computer system. [3 marks]
Initially CPU’s had only one bus on which all devices were connected. Any time a devices
needed to access a resource, it would ask CPU to get the data. This caused lot of CPU time
wastage. This led to evolution of multiple bus architectures. Now CPU is connected to
several devices at the same time. While devices can also connect to each other at the same
time without CPU getting involved. Such multiple bus systems improve CPU efficiency and
also improve system speed as I/O devices can now talk to each other in parallel to CPU
execution. Further multiple bus architectures also help perform multiple operations by CPU
at same time. On one bus, CPU could be doing an instruction fetch operation while on
another bus it could be programming another interfaced device. This helps improve system
performance and allow higher CPU utilization for execution of user programs.
Rationale
back to top
This assessment task will assess the following learning outcome/s:
be able to investigate and describe the essential elements of a computer and their
functionalities.
be able to apply an understanding of data representations and calculations to practical
situations.
be able to develop an elementary computer program.

Presentation:
File naming convention: When you upload files to the TURNITIN for this subject, please use
your student ID and Assignment number to name your files. For example,
123456_Assignment1.doc or 123456_Assignment1.docx etc (where 123456 is your Student
ID)
Please also adhere to the following formatting rules:
Please also adhere to the following formatting rules:
1. For Q2(a) you need to submit a *.mas file.
2. Please compose the answers of rest of the questions 3 in a document file (doc or docx
format). Please do not submit in pdf formats. Please upload the document in the TURNITIN
within deadline.
3. You may put the mas file and document file in a folder, compress the folder and upload the
compressed file to the TURNITIN. You may also upload the two files separately.
4. The first page (cover page) of the document file should have the following information
clearly mentioned:
a. Your full name
b. Your Student ID
c. Subject Code (ITC544)
d. Assessment item number and name (Assignment 1: Computers, data and programming)
5. Each page should have page numbers in “page x of y” format (including the cover page).
6. Please use APA version 6 referencing style where appropriate.