;;;;;;;;;;;;;;
;;; 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?

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.

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

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.

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.

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.

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.

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.

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...

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

* #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.

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.