;;;;;;;;;;;;;;

;;; QUESTION 1

;;;;;;;;;;;;;;

== What we are trying to test:

There are 4 big ideas that we want you to have branded into your minds. As far
as purely theoretical questions go, this is the first thing we want to ask: what
rules do good engineers follow?

== Answer

The main design principles that instruction set programmers abide by are the
following (they are heavily stressed in the book at pages 187-188):

Simplicity favors regularity

- fixed size instructions, 3 register operands in every arithmetic operation,
keeping the register fields at the same place in every instruction format.

(Smaller is faster)

(- 32 registers only.)

Good design demands good compromises

- Larger addresses and constants in instructions and keeping all instructions
the same length.

Make the common case fast

- PC-relative addressing for branches and immediate addressing for constant
operands.

== How we graded:

Getting one of the 3 main design principles above in the left box got you 1
point. Getting at least one of the corresponding MIPS instances of that
principle got the other point. If you did not get a point for the left box, you
could not get one for the right box.

;;;;;;;;;;;;;;

;;; QUESTION 2

;;;;;;;;;;;;;;

a)

== What we are trying to test:

Even though two's complement is the defacto standard for integer manipulation,
we want you to show you are able to play with a given number of bits for any
arbitrary number representation. Here in particular, we actually refer to one's
complement and sign-magnitude which, although legacy, correspond to
simple/intuitive ideas that were inefficient in hardware.

== Answers

VERSION 0

-3 -127

83 ff

fc 80

fd 81

VERSION 1

-15 -126

8f fe

f1 82

f0 81

VERSION 2

-127 -5

ff 85

80 fa

81 fb

VERSION 3

-126 -7

fe 87

82 f9

81 f8

== How we graded:

0.5 per box

If you didn't follow the 8bit or hex requirement, then you lost 0.5 for that
specific box, but lost at most 1 point if you repeated that mistake across
several boxes.

b)

== What we are trying to test:

Even though most of you will remember that for any given number, that number can
be represented in any of an infinity of bases, it is usually a pitfall to think
that only decimal can use the "decimal point". Here we want to check that you
understand that a decimal point is necessary and can be used to represent any
fractional part of a number, in any base

== Answers

VERSION 0

-18.25 32.125

-12.4 20.2

VERSION 1

16.25 -64.75

10.4 -40.C

VERSION 2

-33.5 48.125

-21.8 30.2

VERSION 3

64.25 -28.75

40.4 -1c.c

== How we graded:

0.5 per box

You didn't lose points if you forgot the sign or switched the boxes.

;;;;;;;;;;;;;;

;;; QUESTION 3

;;;;;;;;;;;;;;

a)

== What we are trying to test:

We want you to be as knowledgeable with floating point as you are with two's
complement. That means knowing what the representations of successive FP numbers
are, which requires you to play with both the exponent and mantissa fields
(unlike two's complement which really contains one big such field). Also, you
need to know to count backwards for negative numbers.

== Answers

VERSION 0

1 11011111 111.....111

VERSION 1

1 11001011 111.....111

VERSION 2

1 10111111 111.....111

VERSION 3

1 11111011 111.....111

== How we graded:

2 points, all or nothing. No partial credit for any mistake.

b)

== What we are trying to test

One big idea behind floating point is that although the range is wider than
two's complement, its precision is limited to 24 significanT digits (for single
rpecision, 53 for double). That means, as you saw in lab, that sometimes adding
a small number and a big one can lead the small one to have no influence on the
result. This is part of the concept of rounding, one of the pitfalls of floating
point.

== Answer

0 01100111 111.....111

== Explanation

To add two numbers, we first need to make sure they have the same exponent, in
order for us to add up their mantissae in an aligned manner. If the smaller
number falls beyond the 24th bit of precision of the result, then it will be
lost to truncation. Therefore for X+1=1, X must be smaller than 2^(-23), since
2^(-23) would still fall into the last bit of 1's mantissa. So 2^(-24) comes to
mind as the answer. However we want the largest number that is smaller than
2^(-23), which is obtained by setting all the mantissa bits to 1 as well, thus
getting 2^(-24) + 2^(-25) + 2^(-26) + ... + 2^(-46) + 2^(-47), or the answer
above.

== How we graded:

This is more difficult, so we gave 6 points.

Any answer resembling zero, a denormalized number, or a extremely small number
got zero (you have no idea of the answer).

You only got credit if your answer or your work showed that you got the idea
that the exponent had to be around -24. Once you got that, we gave four points
for the right exponent (127 - 24 = 103 = 01100111b), and 2 points for the right
mantissa (11....11b).

A mistake encoding the exponent takes out 1 point.

Not biasing the exponent takes out 2 points.

Using -23 or -25 instead of -24 got out another point. Previous rules apply.

The mantissa was graded all or nothing.

;;;;;;;;;;;;;;

;;; QUESTION 4

;;;;;;;;;;;;;;

== What we are trying to test:

Much time has been spent on K&R and being able to manipulate strings and
pointers should now be your forte. We wanted to check whether you are confident
with pointer arithmetic, as well as able to understand the functionality of a
10-line program quickly enough to make modifications to it.

== Answer

A: OK

B: Buggy

- c2 is not being declared as char *, but as char only

- FIX: char * c1, * c2;

C: Buggy

- string[loc] returns a character... but strlen takes in a POINTER to a
character

- FIX: either 'string[loc]', or 'strlen(&string[loc])', or 'strlen(string+loc)',
or 'loc < strlen(string)'

D: Buggy

- We want to progress through a substring character by character from our
current location (given by loc). string&loc or string|loc doesn't give us a
location at all.

- c2 = string+loc

E: Buggy

- We need a test statement in order for the loop to be valid. We want to stop
when we get to the end of the substring (ie when the current substring character
is '\0')

- FIX: *c1 or c1[0]

F: OK

G: Buggy

- the current code compares POINTERS c1 and c2. Since c1 and c2 are pointing to
two different memory locations, chances are this if statement is never going to
be true. What we need to do is to compare the characters that they point TO.

- FIX: if(*c1 != *c2) or if(c1[0] != c2[0])

H: Buggy

- The test in the if statement is trivially wrong. We want to return loc only if
we successfully reached the end of the substring (ie we matched each character
of it). If this is the case, then c1 MUST be pointing at a null character.

- FIX: if(!(*c1))

== How we graded:

Each section was worth 2 points.

"OK" Sections:

All or nothing for selecting the right choide

"BUGGY" Sections:

1 point for the correct selection

0.5 points for correctly identifying the bug.

0.5 points for correctly fixing the code.

Common mistakes:

Forgetting to dereference the c1,c2 pointers.

Many students felt that the bug in C was because strlen() returned an int, not a
boolean. In C, any non-0 value is TRUE. Saying 'blah !=0' in a conditional is
just the same as saying 'blah'

Many students forgot to add loc to the start of string when fixing D

;;;;;;;;;;;;;;

;;; QUESTION 5

;;;;;;;;;;;;;;

a)

== What we are trying to test:

Translation of C to MIPS without internal function calls, as well as the
handling of pointers in assembly. Also testing your knowledge of argument and
return value conventions.

== Answer

replaceInt: lw $t0 0($a0)

beq $t0 $0 endLoop #if *array is null, we exit from the for loop

beq $t0 $a1 doReplace #if *array == toReplace, we goto doReplace

addiu $a0 $a0 4 #otherwise we array++

j replaceInt #and reiterate

doReplace: sw $a2 0($a0) #doReplace stores replaceWith into array[0]

move $v0 $a0 #and sets the return value to array

j ret

endLoop: move $v0 $0 #return NULL

ret: jr $ra

== How we graded:

One point off for each line with mistake.

One point off using $s registers.

Multiple points not taken off for same mistakes.

b)

== What we are trying to test:

Function calling conventions, especially expected argument order in $a..
registers.

== Solution:

lw $a0 8($sp) #or la $a0 8($sp) or addi(u) $a0 $sp 8

#note that the first answer actually reads from memory, and is thus a different
answer. However the question was vague enolugh to be open to interpretation.

addiu $a1 $0 1 #(or 5, 9, 4, depending on VERSION)

addiu $a2 $0 2 #(or 6, 3, 7)

jal replaceInt

== How we graded

One point for setting up $a0 correctly

One point for setting up $a1 and $a2

One point for using jal to replaceInt

c)

== What we are trying to test:

This is where we evaluate your purely technical MIPS coding skills. Nothing
tells us more about that than having you optimize code, since it requires deep
knowledge of program flow and of calculated use of instructions.

== Answer

Move line 8 to 0.5 (and change the first branch label (line 1) to ret)

Delete line 7

It was also possible to remove 2 lines, by using $v0 instead of $t0, which would
then allow to delete line 8 as well.

== How we graded

Two possible ways:

1) If $t0 was used in the first couple lines, then moving the endloop line to
the top of the program would obviate the "j ret" line.

2) If $v0 was used in the first couple lines, then the "j ret" line and
"endloop" line can both be deleted.

Common pitfall:

Some people moved beq lines to bne lines, thereby changing the for loop into a
do-while loop. This changes the logic of the program. Therefore, it is
incorrect.

The grading standard is that producing correct result gets 3 points or otherwise
nothing. However, if the answer clearly falls in 1) or 2) and there are minor
mistakes, we give discretionary 1 or 2 points.

;;;;;;;;;;;;;;

;;; QUESTION 6

;;;;;;;;;;;;;;

a)

== What we are trying to test:

This one really tests your understanding of MIPS program flow. The concept is
that if you understand what a mips program does (no matter if it follows
conventions or not) and can reconstruct corresponding code in any high-level
language, then it means you have mastered MIPS as a standalone programming
language.

== Solution

int mystery(int n) {

if (n == 0)

return 0;

else

return (mystery(n-1) + mystery(n-1) + 1);

}

/* or, optimized */

int mystery(int n) {

if (n == 0)

return 0;

else

return 2*mystery(n-1)+1;

}

/* or, optimized even further */

int mystery(int n) {

return(n ? 2*mystery(n-1)+1 : 0);

}

Side note: The original code was taken from a CS3 example in which we were
trying to compute the number of moves for the Tower of Hanoi problem with n
disks.

== How we graded

We accepted as full credit any code that effectively did the same thing as the
procedure shown above. Many people had an extra n++ at the end (translating the
MIPS to C directly not realizing that doesn't do anything).

In terms of dividing up the 10 points...lots of partial credit available.

+2 = base case and correct return value for n==0.

+3 = mystery(n-1)

+4 = second mystery(n-1)

+1 = the last +1 in the return value

-1 for saying "n=0" in your test

-2 for anything extra (i.e., n*mystery(n-1), mystery(mystery(n-1))) -1 for
having n-2 instead of n-1 in your second call

== Common errors

Most people 'got it'. Some had (n-2) in their second call. Some thought we were
multiplying n*mystery(n-1)...

b)

== What we are trying to test:

As you can see from this MIPS program example, not following conventions can
make code quite harder to understand. Also in general cases, it can lead to
hard-to-debug, buggy code, especially if the caller and callee code is written
by separate programmers. This question really was meant to reveal your
understanding of the procedure call register convention. What it served to do
was to highlight ANY confusions about this topic quite explicitly. Our feeling
was that this was the best question on the test for this reason, and students
might expect more short-answer questions in the future as a result...

== Answer

Line 9 violates register conventions, since it assumes that $a0 contains a
sensible/valid value upon this (second) jal call. However nothing certifies that
the first jal call didn't overwrite $a0 with a different value.

== How we graded

+2 = Saying effectively that (but you could have chosen another line

+number,

e.g., line 7 for NOT saving $a0 before it since it'd be used later,

or line 13 for compensating for this.

Most people who said line 13 didn't talk about the essential problem, which is
really line 9's expectations. Most people who chose line 9 had the right
reasons.

+1 = Getting really close to the reason but missing a small fact, or

not saying it in a way that showed they really knew it.

Very briefly, the register conventions are:

* Caller sets a0,a1,... to valid argument values before jal calls

* Caller saves volatile registers if they contain information before jal calls

* Callee, if it needs saved registers (which all start with 's'), must save

them before munging on them and then restore before returning

* Callee puts return values in $v0,$v1

* Caller cannot trust non-saved registers (other than $v0-1) upon return

from jal call

* We don't touch or use registers other than the ones we discussed:

$s0-7, $t0-9, $a0-3, $v0-1, $sp, $ra, $0

Most students (the vast majority) received a 0 on this question. Their

answers included:

* #6 - You can't modify the argument $a0

Comment: Completely false. All we know is that it's been set with

our argument. Once we're the callee, we can use it as we like.

* #9 - You have to save $ra again before the second call

Comment: This really shows confusion. $ra is the place we the

subroutine need to return to, so if we are going to do a jal

ourselves (and taken on the role of the callER) then that jal

call will overwrite it. BUT, once we've saved the place we need

to return to, we can make a bazillion jal calls to all kinds of

subroutines and as long as we've saved $ra before the first jal

and restore it before we use it to return with jr $ra, we don't

need to think about it again.

* #11 - It should be addi

Comment: If we're talking TAL, that's true. If we're just looking

at 'MIPS', that assumes MAL, which means we can be sloppy with our

argument types. We know the accepting, graceful assembler will fix

it for us (as well as expand them to lui/ori if the immediate is too

big)

* #10 - We need to restore 0($sp) into $v0 instead of $t0

Comment: We've just made a second jal call, which means there's

a value in $v0. "lw $v0 0($sp)" would clobber that value. There's

nothing that says officially that we need to be symmetric about

the registers we use to store into and load from memory.

We were very pleased to see these misconceptions be revealed so blatantly so
that students can correct them early on in the semester...

c) and d)

== What we are trying to test:

Your understanding of recursive functions, and of 32-bit signed integers.

== Answer

Both answers are -1

== Explanation

Most people looked at the pattern of the first few numbers (always a

great place to start) and saw:

n mystery(n) mystery(n) in binary

0 0 0

1 1 1

2 3 11

3 7 111

4 15 1111

. ... ...

32 2^32-1 11...111

... or basically, mystery(n) fills that many low-order bits with all 1s. Many
also saw that this corresponded to the function mystery(n)= 2^n - 1. We can see
this works because we always double the previous value (in

effect, shifting the values to the left by one and adding 1, leaving all 1s in
the lower bits).

Whether the input to mystery was 32, 33, 34, 35, 36 etc, in all cases you ended
up having to fit a very large power of 2 (> 31) -1 into an 32-bit two's
complement.

Let's take 32 as an example for the recursive call. The first call to mystery(n)
returns 1 + two of mystery(n-1), which in turn return 1 + two of the next lower
level, etc. This gives us a pyramid scheme:

32 1

31 1 1

30 1 1 1 1

...

1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0

Since there are 32 levels of ones, each corresponding to a successive power of
2, that means that the sum of all the ones (and therefore the return value of
mystery(n)) is:

2^32 + 2^31 + 2^30 + ... + 2^2 + 2^1 + 2^0

which is 2^33 - 1

Now trying to fit this last number into a 32-bit signed int, we see that we are
short of space to actually represent it. As you know, when numbers are too big
to be represented after the biggest positive signed integer 2^31 - 1, things
wrap around and start over from the negative side. Here there are two tricks to
find out which actual number 2^33 - 1 will be displayed as:

mod by 2^32: since there are 2^32 different numbers representable in two's
complement 32bit, modding by this number gives us the actual bucket any number
will fall into.

(2^33 - 1)%2^32 = 2^33%2^32 - 1%2^32 = -1

2^33 - 1 is really (2 * 2^32 - 1). Since 2^32 is represented as 100000...0000,
adding that binary number to itself gets you 0. Then you are left with -1.

You can see that the above strategies are applicable to any of the versions of
the exam.

== How we graded

c)

+4 -1

+2 2^32-1 (correct, but didn't recognize that %d => signed int => -1)

+1 Question (a) wrong but did the right arithmetic to get a correct ans The
reason we didn't give more points for the correct answer was that it would be
possible to have your C code be mystery(int n){return(1)}; and that person would
have received credit for putting 1 in both slots. So, in some sense, this is a
'cascading' question, in that you have to get an earlier part right to get the
later part right, and in general it's best to avoid cascading questions, but
this follow-up to question (a) was so rich we thought it unavoidable.

+0 overflow (remember, C doesn't overflow! And, the MIPS inst that did

the additions were addu's, which themselves don't overflow either.)

d)

+2 -1

+2 2^32-1 (recognizing that this answer would be the same as (c)) because it
wraps

+1 2^33-1 (or whatever your version said, replace 33 with 34,35,35)

+0 overflow (remember, C doesn't overflow! And, the MIPS inst that did the
additions were addu's, which themselves don't overflow either.)

Meta-note: We saw students' papers filled with calculations. If we say 'no
calculators' and you find yourself doing lots of hand-calculations, that's a
sign you're going down the wrong path... Just a tip for the future.

;;;;;;;;;;;;;;

;;; QUESTION 7

;;;;;;;;;;;;;;

== What we are trying to test:

This is the only question that tests your knowledge of the R/I/J-formats for
MIPS instructions: how to fill the different fields, and how they are
represented as machine code.

== Solutions

0x8C83FFFC

0x1060000B (for "10 instructions" before the jump, or 0x1060000D for 12)

0x08020001

== Explanations

Except from simple copying from the textbook to fill in the opcodes, etc., there
are a couple pitfalls you should be aware of:

- the jump instruction encodes its jump address as a WORD address, which
requires you to divide 0x00080000 by 4, then add 1 for while_loop

- branch instructions encode their target address as a WORD OFFSET *from the
next line* (ie count the number of lines from the next until you reach the
label)

== How we graded

There are three blank lines. Each line is worth two points.

First Line:

2 points for the correct answer and some work (in binary or decimal) 1 point for
an incorrect answer, but you have the list (35,4,3,-4); many people figured out
the fields correctly, but then made a mistake translating to hexadecimal

0 points otherwise

Second Line:

2 points for the correct answer and some work (in binary or decimal) 1 point for
an incorrect answer, but you have the list (4,3,0,11 or 13) 0 points for an
incorrect answer and an incorrect list

NOTE: You get 0 points for an off-by-one error (if you use 10, 12 or 14 (A, C or
E) instead of 11 or 13)

Third Line:

2 points for the correct answer

0 points otherwise (no partial credit: it has to be exact)

;;;;;;;;;;;;;;

;;; QUESTION 8

;;;;;;;;;;;;;;

== What we are trying to test:

Instead of having you work on detailed (line-by-line) object file creation
(symbol tables, relocations tables, ...) and linking, we wanted to make sure you
had the general ideas behind each part of the compiling process, as seen in
lecture.

== Solution

ASSEMBLER changes move $t0, $t1 into add $t0, $zero, $t1

LINKER resolves undefined labels using the relocation information and the symbol
table

LOADER copies the parameters (if any) to the main program onto the stack

== Howe we graded

1 point each

No partial credit

;;;;;;;;;;;;;;

;;; QUESTION 9

;;;;;;;;;;;;;;

== What we are trying to test:

Abstracting away from details of the implementation of the free list (e.g. buddy
system, etc), you get to show you know how specific allocation policies work,
and how there are situations where they aren't optimal. First-fit and best-fit
are very common policies that you will encounter in a lot of other settings, so
they're one thing we really want you to remember from 61c.

== Solution

There are many possible answers to this one, as long as you get Best-fit stuck
along the way

Example:

First Best

--A-B --A-B

C-A-B --ACB C=malloc(1)

CDA-B D-ACB D=malloc(1)

CDA-- D-AC- free(B)

CDAEE X E=malloc(2)

== How we graded

Any "no" answer got 0 points.

Any "yes" answer with some justification (better than "I do know it") got 1
point.

Any valid answer, even requiring 11 malloc/free's (yes, there are 11-instruction
cases), got full credit.

Mistakes in the algorithms application got 2 points out.