Summer Diet -1- CS1S 2019 Solutions
CS1S Computer Systems: Questions and Solutions
May 2019

Duration: 1 hour
Rubric: Answer all questions
This examination is worth a total of 50 marks

1. (a) Convert 1100 0011 to a decimal number, assuming binary representation.
[2]

Calculate 128 + 64 + 2 + 1 = 195 by adding the powers of 2 corresponding to the
positions where there is a 1 bit in the word.
[Problem solving.]
(b) Convert 1100 0011 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 0011 1100. Then increment it, giving 0011
1101. Now this result is nonnegative, so its binary representation is the same as its two’s
complement value; this is 32 + 16 + 8 + 4 + 1 = 61. Since the negation of the original
word is 61, the answer is -61.
[Problem solving. 1 mark for identifying it as negative; 2 marks for negation.]
(c) Translate the statement a := b*c – d/b into Sigma16 assembly language,
assuming that a, b, c, and d are integer variables. You do not need to write a
complete program, and you don’t need to write data statements for the variables.
Just translate this one statement.
[3]

load R1,b[R0] ; R1 := b
load R2,c[R0] ; R2 := c
load R3,d[R0] ; R3 := d
mul R4,R1,R2 ; R4 := b*c
div R5,R3,R1 ; R5 := d/b
sub R4,R4,R5 ; R4 := b*c – d/b
store R4,a[R0] ; a := b*c – d/b
[Problem solving, requires understanding usage of registers, variables, and basic
instructions. 2 marks for loads and store, 1 mark for arithmetic.]
(d) In the following program, variables k, i and n are integers, and x is an array of
signed integers containing n elements. Suppose the program is executed with
these initial values:
n = 7
x = [9, -2, 13, 0, 45, -8, 7]
After the program executes, what are the values of k and x?

Summer Diet -2- CS1S 2019 Solutions
k := 0;
for i := 0 to n-1 do
{ if x[i] < 0
then { x[i] := -x[i]; }
else { k := k+1; } }
[2]

k = 5
x = [9, 2, 13, 0, 45, 8, 7]
(k is the number of nonnegative numbers in the array, and each element of x that was
negative is negated, although it isn’t required to say that.)
[Problem solving. 1 mark for value of k, 1 mark for the array.]
(e) Translate the program in part (d) into low level language. You do not need to
define the variables or array, just translate the program code. (The low level
language contains assignment statements, goto statements, and statements of the
form if b then goto label, where b is a Boolean expression.)
[5]
k := 0;
i := 0;
forloop: if not (i if not (x[i]<0) then goto nonneg;
x[i] := -x[i];
goto afterif;
nonneg: k := k+1;
afterif: i := i+1;
goto forloop;
done:
[Problem solving. 1 mark for variables, 2 marks for loop, 2 marks for conditional.]

(f) Translate the low level program in part (e) into a complete program in Sigma16
assembly language. Use data statements to define the initial values specified in
part (d).
[10]

; R1 = k = count of nonnegative elements of x
; R2 = i = loop index
; R3 = n = array size
; R4 = constant 1
; R5 = x[i]

add R1,R0,R0 ; R1 = k := 0
add R2,R0,R0 ; R2 = i := 0
load R3,n[R0] ; R3 := n
lea R4,1[R0] ; R4 := 1
Summer Diet -3- CS1S 2019 Solutions
forloop
cmplt R5,R2,R3 ; R5 := i jumpf R5,done[R0] ; if not (i load R5,x[R2] ; R5 := x[i]
cmplt R6,R5,R0 ; R6 := (x[i]<0)
jumpf R6,nonneg[R0] ; if not (x[i]<0) then goto nonneg
sub R5,R0,R5 ; R5 := -x[i]
store R5,x[R2] ; x[i] := -x[i]
jump afterif[R0] ; goto afterif
nonneg
add R1,R1,R4 ; k := k+1
afterif
add R2,R2,R4 ; i := i+1
jump forloop[R0] ; goto forloop
done
store R1,k[R0] ; k := R1
trap R0,R0,R0 ; terminate
k data 0
n data 7
x data 9
data -2
data 13
data 0
data 45
data -8
data 7
[Problem solving, requires understanding of the instruction set, conditionals, indexed
addressing and loops. 2 marks for initialization and storing k, 2 marks for loop, 2 marks
for conditional, 1 mark for array access, 3 marks for correspondence to low level
algorithm.]
Summer Diet -4- CS1S 2019 Solutions
2. (a) Describe the behavior of the 1-bit register circuit (reg1) with data input x, control
input load, and output r.
[3]

The register has an internal state. It continually outputs its state on r. At a clock tick, the
register sets its state to (if load then x else r) using a multiplexer. Consequently, if
load=1 then at a tick the register loads the value of x, but if load=0 then the register
retains its previous state.
[Bookwork. 1 mark for state, 1 mark for conditional load, 1 mark for clock tick. It is not
necessary to describe how it works (though many students might do so); it only required
to describe the circuit’s behavior. 2 marks if they give the circuit but don’t describe the
behavior.]
(b) Design a circuit that takes two inputs a, b. It produces one output, x, which is
defined by the truth table below. Implement the circuit using any of the standard
logic gates (inv, and2, or2, xor2). You may specify the circuit using any of the
following notations (just use one): a schematic diagram, Boolean algebra, or
Hydra notation.

a b x
0 0 1
0 1 1
1 0 0
1 1 1
[3]

There are many solutions, including
x = inv (and2 a (inv b))
x = or2 (inv a)(and2 a b)
Any correct solution is acceptable.
[Problem solving.]

(c) Explain what could happen in a synchronous circuit if the clock speed is too fast.
[3]

The critical path is the longest path through logic gates. At a clock tick, every flip flop
latches the value of its input signal and it is essential that all these signals are correct.
The signal produced by the critical path goes through the largest number of logic gates,
so it takes the largest amount of time to settle down to the valid value. If the clock runs
too fast, a clock tick could occur before the critical path signal becomes valid.
Consequently, the flip flop could latch an incorrect value (or even a signal in transition,
which would not represent either 0 or 1). Therefore the clock must run slowly enough to
Summer Diet -5- CS1S 2019 Solutions
allow the critical path to become valid; that guarantees that all signals are valid at every
clock tick.
[Bookwork. 1 mark for definition, 1 mark for limitation on clock speed., 1 mark for
consequence of a clock that’s too fast.]

(d) The following program takes two inputs: an integer x and a pointer header to a
list header. The list is represented by nodes. Each node is a record consisting of
two words: the first word value is an integer, and the second word next is a
pointer to the rest of the list. The last node in the list has nil in the next field (nil
is represented by 0). The value field of the list header is unused, and its next field
points to the first node with a value (if any).
p := header;
q := p;
p := (*p).next;
done := false;
while not done do
if p=nil || x<(*p).value
then { new := avail;
avail := (*avail).next;
(*new).value := x;
(*new).next := p;
(*q).next := new;
done := true; }
else { q := p;
p := (*p).next; }
Suppose the program is given x=5 and header points to a header for a list
containing the initial values [3, 8, 9]. After the program executes, what is the
value of the list that the header points to?
[4]
[3, 5, 8, 9]. If p points to a list where the values are in ascending order, then the program
inserts x into a position that retains the ascending order. Full marks if the value of the
list is correct; the explanation is not required.
[Problem solving.]


(e) Translate the program in part (d) 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. Just write the instructions that implement the
algorithm, but not the data statements.
[8]


; R1 = x
; R2 = p
; R3 = q
; R4 = done
Summer Diet -6- CS1S 2019 Solutions
load R2,header[R0] ; p := header
add R3,R2,R0 ; q := p
load R2,1[R2] ; p := (*p).next
add R4,R0,R0 ; done := false
loop
cmp R4,R0 ; compare done, false
jumpne finished[R0] ; if done then goto finished
cmp R2,R0 ; compare p, nil
jumpne moveon[R0] ; if p/=nil then goto moveon
load R5,0[R2] ; R5 := (*p).value
cmp R1,R5 ; compare x, (*p).value
jumpge moveon[R0] if x >= (*p).value then goto moveon
; insert x into list between *q *p
load R6,avail[R0] ; R6 := avail = new
load R7,1[R6] ; R7 := (*avail).next
store R7,avail[R0] ; avail := (*avail).next
store R1,0[R6] ; (*new).value := x
store R2,1[R6] ; (*new).next := p
store R6,1[R3] ; (*q).next := new
lea R4,1[R0] ; done := true
jump afterelse[R0] ; goto aftelse
; else: move q and p to next elements of list
moveon
add R3,R2,R0 ; q := p
load R2,1[R2] ; p := (*p).next
afterelse
jump loop[R0] ; goto loop
finished
[Problem solving. This problem, and a number of similar ones, has been covered in
lectures, tutorials, and exercises. 3 marks for pointer manipulations, 2 marks for loop
and conditional.]
(f) Define the term concurrent processes. Explain how concurrent processes are
implemented, and how the system ensures that all process continue to run even if
one of them goes into an infinite loop.
[4]


A process is a running program; the term means the dynamic behavior of the program as
it executes and interacts with the user. Concurrent processes are processes that are
running simultaneously at the time scale of a human user; i.e. over a period of 0.1 second
to one second, all the concurrent processes exhibit activity. However, concurrent
processes do not necessarily execute simultaneously at the time scale of individual
instructions. A single processor can execute only one instruction at a time (disregarding
instruction level parallelism, which is irrelevant for this question). Concurrent processes
are implemented by causing the processor to execute one process for a limited amount of
time, called a time slice, and then switch to give a time slice to a different process. Over
a long period of time (0.1 to 1 second) the processor may execute instructions belonging
to all the concurrent processes, so all are able to make progress at this time scale. To
implement concurrency, the hardware contains a timer that generates an interrupt after a
Summer Diet -7- CS1S 2019 Solutions
set amount of time. The operating system grants a time slice to a process by setting the
timer (e.g. to 0.05 second) and then jumping to the process. When the timer goes off it
generates an interrupt which transfers control from the running process back to the
operating system, which then gives a time slice to a different process. Even if a user
process has gone into an infinite loop, a timer interrupt will take control away from it so
the system can continue to operate.
[Bookwork. 2 marks for definition, 2 marks for implementation using interrupts. The
level of detail in the model solution is not required, but the main points should be given.]

欢迎咨询51作业君