Summer Diet -1- CS1S 2021 Solutions
CS1S Computer Systems: Questions and Solutions
May 2021
Duration: 1 hour
Rubric: Answer all questions
This examination is worth a total of 50 marks
1. (a) Convert 1011 1100 to a decimal number, assuming binary representation.
[2]
Calculate 128 + 32 +16 + 8 + 4= 188 by adding the powers of 2 corresponding to the
positions where there is a 1 bit in the word.
[Problem solving. 1 mark for correct powers of 2, 1 mark for adding them]
(b) Convert 1011 1100 to a decimal number, assuming two’s complement
representation.
[3]
Since the leftmost bit is 1, this is a negative number. Negate it to get a nonnegative
number. To negate, first invert it, giving 0100 0011. Then increment it, giving 0100
0100. Now this result is nonnegative, so its binary representation is the same as its two’s
complement value; this is 64 + 4 = 68. Since the negation of the original word is 68, the
answer is -68.
[Problem solving. 1 mark for identifying it as negative; 1 mark for inverting and 1 mark
for adding 1 and getting the correct result.]
(c) Translate the following Sigma16 assembly language to a single line statement in
high level language, assuming that y, i are integer variables and x is an array. The
data statements for the variables are omitted for simplicity. Just identify the
calculation performed and present it in a single statement.
load R1,i[R0]
load R2,x[R1]
lea R3,35[R0]
div R4,R2,R3
store R4,y[R0]
[4]
y := x[i]/35
[Problem solving, requires understanding usage of registers, variables, and basic
instructions. 1 mark for loads, 1 mark for store, 1 mark for arithmetic, 1 mark for lea.]
Summer Diet -2- CS1S 2021 Solutions
(d) Give a detailed account of the sequence of steps performed by the processor as it
executes the instruction: store R3,z[R4]
[4]
(1) The instruction is fetched: ir = mem[pc], pc++. (2) Then the opcode is examined and
the control jumps to the control for a store. The second word of the instruction is fetched:
adr = mem[pc]; this places the value of z in adr. (3) The effective address is calculated:
adr = adr + R4 = z + R4. (4) The data is fetched from the Destination Register and placed
in the destination adr: mem[adr + R4] = mem[z + R4] = R3
[Bookwork and synthesis. 1 mark for each step.]
(e) Computer architectures today are mostly 64-bit: give two potential benefits.
[2]
Expanding from 32 bits to 64 bits allows for larger address spaces to be accessed giving
access to more than 4Gb of memory (more memory). 64 bit data paths increase the
memory bus bandwidths (faster). Will allow variations on this.
[Bookwork and critical thinking. 1 mark for each benefit.]
(f) There is an array named x that contains n integers, where n is an integer variable
in memory. Write a Sigma16 assembly language program that creates another
array y of length n which contains all the elements of array x but changes them to
positive (take care to handle negative numbers and store as positive). The
program must work correctly for any n and initial array of elements. You may
assume that the variables have been declared but not initialised. Your program
should exit cleanly.
[10]
; R1 = i = loop index
; R2 = n = array size
; R3 = constant 1
; R4 = temp for negatives
; R5 = temp
; Initialise the variables in registers
add R1,R0,R0 ; i = 0
load R2,n[R0] ; R2 = n
lea R3,1[R0] ; R4 = 1
; Traverse the array and calculate sum of positives
loop
cmp R1,R2 ; compare i with n
jumpge done[R0] ; if i >= n then goto done
Summer Diet -3- CS1S 2021 Solutions
load R5,x[R1] ; temp = x[i]
cmp R5,R0 ; compare temp with 0
jumpge poss[R0] ; if x[i] >= 0 then goto poss
sub R4,R0,R5 ; temp for neg = 0 - x[i] = -
x[i]
store R4,y[R1] ; y[i] = temp for negatives
jump skip[R0] ; goto skip, skip the else block
poss
store R5,y[R1] ; y[i] = x[i]
skip
add R1,R1,R3 ; i = i + 1
jump loop[R0] ; goto loop
; terminate
done
trap R0,R0,R0 ; terminate
[Problem solving, requires understanding of the instruction set, conditionals, indexed
addressing and loops. 3 marks for initialization, 2 marks for loop, 1 marks for
conditional, 1mark for storing to array y, 1 mark for 0-x[i] (absolute), and 1 mark for
termination.]
Summer Diet -4- CS1S 2021 Solutions
2. (a) Define the behaviour of a demultiplexer (the demux1 circuit), given the control
input c and the data input d. Give a circuit that implements a demultiplexer using
logic gates.
[3]
The behavior depends mainly on the control signal c. If c=0, c1 and c2 are always 0. If
c=1 the value of c1 and c2 depend on the value of d. If d=0, c1=1 and c2=0. If d=1, c1=0
and c2=1.
[Bookwork. 2 marks for behaviour, 1 mark for circuit]
(b) Explain what the levels of abstraction of a computer system are. Include a
diagram representing them.
[4]
The level of abstractions of a computer system describe it from different point of views.
Typically, lower levels serve, implement or provide services to higher ones. We can
mainly differentiate between SW and HW levels. In the middle of the two is the ISA
(Instruction Set Architecture), which is a very important level, as it represents the
HW/SW interface. An example diagram representing the levels is the following:
[Bookwork. 3 marks for differentiate HW, SW and ISA, 1 mark for the diagram]
(c) Given the following assembly program:
load R2,x[R0]
load R3,y[R0]
add R1,R2,R3
store R1,y[R0]
trap R0,R0,R0
x data 30
y data 40
Summer Diet -5- CS1S 2021 Solutions
Show the content of the memory using three columns for each memory location
to indicate: 1) address (four hex values); 2) contents; 3) what the contents mean.
[6]
address contents what the contents means
0000 f201 first word of load R2,x[R0]
0001 0008 second word: address of x
0002 f301 first word of load R3,y[R0]
0003 0009 second word: address of y
0004 0123 add R1,R2,R3
0005 f102 first word of store R1,y[R0]
0006 0009 second word: address of y
0007 d000 trap R0,R0,R0
0008 001E x=30
0009 0028 x=40
[Bookwork. 1 mark for each instruction, 1 mark for the data]
(d) Consider a doubly linked ordered list where p is a pointer to a node in the list (not
the header) and each node is a record consisting of three words: an integer
value, a pointer to the previous node in the list prev, and a pointer to the next
node in the list next. Note that the value of the header node is 0, the last node
in the list has nil in the next field (nil is represented by 0), and the value of each
node is greater than the prev node but less than the next node. The following
program deletes the node whose value is equal to the input variable x (assume
that x ≠ 0 and there is a node that meets this condition). Translate the program to
Sigma16 assembly language. You don’t need to write out the low level language
version, and you don’t need to define the variables or the linked list.
; given p = pointer to list, x = value to delete
while (*p).value /= x do
if (*p).value < x
p := (*p).next
else
p := (*p).prev
; delete the node
q := (*p).prev;
(q*).next := (*p).next;
[9]
; R1 = p (given)
; R2 = q
; R3 = x (given)
; R4 = temp
loop
Summer Diet -6- CS1S 2021 Solutions
load R4,0[R1] ; R4 := (*p).value
cmp R4,R3 ; compare (*p).value and x
jumpeq del[R0] ; if (*p).value == x then goto del
cmp R4,R3 ; compare (*p).value and x
jumplt next[R0] ; if (*p).value < x then goto next
load R1,1[R1] ; p := (*p).prev
jump loop[R0] ; goto loop
next
load R1,2[R1] ; p := (*p).next
jump loop[R0] ; goto loop
del
load R2,1[R1] ; q := (*p).prev
load R1,2[R1] ; p := (*p).next
store R1,2[R2] ; (q*).next := (*p).next
trap R0,R0,R0 ; terminate
[Problem solving. 1 mark for initialisation, 1 mark for dereferencing p, 1 mark for each
cmp+jump (2 in total), 1 mark for each load+jump (2 in total), 3 marks for delete and 1
for trap]
(e) Identify three different causes of interrupts in a computer system and give an
example for each case.
[3]
There are mainly three reasons that can cause interrupts:
1) An error in a user program: e.g. overflow (result of arithmetic is too large to fit t in a
registers);
2) A trap: this is an explicit jump to the operating system, but the program doesn't
specify the address;
3) An external event: e.g. a disk drive needs attention right now, or the timer goes off.
[Bookwork. 1 mark for each of the three reasons.]