;;;;;;;;;;;;;; ;;; 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. ;;;;;;;;;;;;;; ;;; 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 -3 -127 83 ff fc 80 fd 81 == 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 -18.25 32.125 -12.4 20.2 == 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 1 11011111 111.....111 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. ;;;;;;;;;;;;;; ;;; 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)) ;;;;;;;;;;;;;; ;;; 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 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 # first paramter addiu $a2 $0 2 # second paramter jal 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. ;;;;;;;;;;;;;; ;;; QUESTION 6 ;;;;;;;;;;;;;; == 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 a) int mystery(int n) { if (n == 0) return 0; else return 2*mystery(n-1)+1; } b) The most blatant violation of MIPS conventions is that mistery assumes $a0 keeps its value when calling a function (itself). $a0 is a temporary register, and as such functions should assume its value will change when jal'ing. c) mistery(0) -> 0000 0000 0000 0000 0000 0000 0000 0000 mistery(1) -> 0000 0000 0000 0000 0000 0000 0000 0001 mistery(2) -> 0000 0000 0000 0000 0000 0000 0000 0011 mistery(3) -> 0000 0000 0000 0000 0000 0000 0000 0111 ... mistery(31) -> 0111 1111 1111 1111 1111 1111 1111 1111 mistery(32) -> 1111 1111 1111 1111 1111 1111 1111 1111 printf("%d", mistery(32)) will print -1 d) mistery(33) -> 2 * mistery(32) + 1 = 111....1110 + 1 = 111....111 mistery(34) -> 2 * mistery(33) + 1 = 111....1110 + 1 = 111....111 printf("%d", mistery(34)) will print -1 ;;;;;;;;;;;;;; ;;; QUESTION 7 ;;;;;;;;;;;;;; 0x0008000 addiu $v0, $0, 0 - I type addiu=0x9 rs=$0=0 rt=$v0=2 imm=0 001001 00000 00010 00...000 0x24020000 0x0008004 lw $v1, -4($a0) - I type lw=0x23 rs=$a0=4 rt=$v1=3 imm=-4 100011 00100 00011 11...11100 0x8c83fffc 0x0008008 beq $v1, $0, loop_exit - I type beq=0x4 rs=$0=0 rt=$v1=3 imm=+11 instructions = +44 bytes 000100 00000 00011 00...01011 0x1003000b 0x0008034 j while_loop - J type j=0x2 address=0x00080004, i.e., 0x020001 000010 0x020001 0x08020001 ;;;;;;;;;;;;;; ;;; QUESTION 8 ;;;;;;;;;;;;;; LI Resolve undefined labels using the relocation information and symbol table LO Copy the parameters (if any) to the main program onto the stack AS Change move $t0,$t1 into add $t0,$zero,$t1 ;;;;;;;;;;;;;; ;;; QUESTION 9 ;;;;;;;;;;;;;; The answer is yes, first-fit may succeed where best-fit fails. The simplest example is: first-fit best-fit C /*comment*/ LABEL 01234 01234 Instruction --------------------------------------------------------------------------- INIT: X--Y- X--Y- init XA-Y- X--YA A=malloc(1) XA-Y- XBBYA B=malloc(2) first-fit fails XACY- XBBYA C=malloc(1) best-fit fails Though is a little tricky, it was accepted (we didn't request you to avoid previous failures). Anyway, a cleaner solution is: first-fit best-fit C /*comment*/ LABEL 01234 01234 Instruction --------------------------------------------------------------------------- INIT: --X-Y --X-Y init A-X-Y --XAY A=malloc(1) A---Y ---AY free(X) A---- ---A- free(Y) ABBBB ---A- B=malloc(4) best-fit fails