CS 61CL (Clancy/Culler) Solutions and grading standards for exam 2 Fall 2008 A 149 students took the exam. The average score was 42.3; the median was 44. Scores ranged from 7 to 60. There were 71 scores between 46 and 60, 60 between 31 and 45, 16 between 16 and 30, and 2 between 7 and 15. (Were you to receive scaled grades of 23 out of 30 on your two in-class exams and 46 out of 60 on the final exam, plus good grades on homework and lab, you would receive an A–; similarly, a test grade of 16 may be pro-jected to a B–.) There were two versions of the test. (The version indicator appears at the bottom of the first page.) If you think we made a mistake in grading your exam, describe the mistake in writing and hand the description with the exam to your lab t.a. or to Mike Clancy. We will regrade the entire exam. Problem 0 (2 points) You lost 1 point on this problem if you did any one of the following: • you earned some credit on a problem and did not put your login name on the page, • you did not adequately identify your lab section, or • you failed to put the names of your neighbors on the exam. The reason for this apparent harshness is that exams can get misplaced or come unsta-pled, and we want to make sure that every page is identifiable. We also need to know where you will expect to get your exam returned. Finally, we occasionally need to verify where students were sitting in the classroom while the exam was being administered. Problem 1 (10 points) Parts a and b, worth 2 points each, involved isolating the Rs field (in version A) or the Rt field (in version B) of an instruction. Here are solutions. isolating Rs isolating Rt C // two-shift version return (inst << 6) >> 27; // shift-and-mask version return (inst >> 21) & 0x1F; // two-shift version return (inst << 11) >> 27; // shift-and-mask version return (inst >> 16) & 0x1F; assembly language # two-shift version sll $v0,$a0,6 srl $v0,$v0,27 jr $ra # shift-and-mask version srl $v0,$a0,21 andi $v0,$v0,0x1F # two-shift version sll $v0,$a0,11 srl $v0,$v0,27 jr $ra # shift-and-mask version srl $v0,$a0,16 andi $v0,$v0,0x1F More of you provided the two-shift version, though (we think) the shift-and-mask version is somewhat simpler. Each error lost 1 point. The most common bug was misunderstand-ing of the shift and masking operations.2 Part c, worth 3 points, involved a C program segment to convert a lower-case letter to upper-case (version A) or vice versa (version B). You were to translate the C code to as-sembly language. Here's a solution to version A. li $t1,'a' li $t2,'z' blt $t0,$t1,ok # ch < 'a' if branch bgt $t0,$t2,ok # ch > 'z' if branch sub $t0,$t0,$t1 # compute ch – 'a' addi $t0,$t0,'A' # compute ch – 'a' + 'A' ok: Correct logic was worth 2 points and the computation 1 point. This generally worked out to –1 per error. Finally, part d involved translating a C switch to assembly language. It was also worth 3 points, and was the same on both versions. Here's a solution. li $t1,'y' bne $t0,$t1,checkn li $v0,1 j switchend checkn: li $t1,'n' bne $t0,$t1,default li $v0,0 j switchend default: li $v0,-1 switchend: The 3 points were divided into 2 for the logic, 1 for the return value. Again, this generally worked out to –1 per error. Problem 2 (4 points) In this problem, you were to translate machine language instructions to assembly lan-guage. In version A, the instructions were 8D28FFF8 and 01022020; in version B, they were AD09FFF8 and 00881020. We start by expressing each instruction as binary, in order to access the instruction's bit fields. hexadecimal binary 8D28FFF8 100011 01001 01000 1111111111111000 01022020 000000 01000 00010 00100 00000 100000 AD09FFF8 101011 01000 01001 1111111111111000 00881020 000000 00100 01000 00010 00000 100000 We observe from the op codes that 8D28FFF8 is lw, AD09FFF8 is sw, and the others are R-format instructions. The function fields of the latter indicate that each is an add. In an assembly language lw and a sw, the Rt field is the first operand. Rt is the second operand in machine language. The offset for each is –8. (Note that the offset is in bytes, unlike the operand in a branch or jump, which is a word offset or address.)3 The resulting instructions are lw $8,-8($9) sw $9,-8($8) In the assembly language add instructions, the operands are Rd, Rs, and Rt. In machine language, they appear in the order Rs, Rt, Rd. Thus 01022020 translates to add $4,$8,$2 and 00881020 translates to add $2,$4,$8 Each instruction was worth 2 points. 1 point partial credit was given only for the follow-ing, in which all the bit fields were parsed correctly but operands were out of order. hexadecimal 1 point partial credit answer 8D28FFF8 lw $9,-s($8) 01022020 add $8,$2,$4 AD09FFF8 sw $8,-8($9) 00881020 add $4,$8,$2 Most of you got this correct. Problem 3 (4 points) This problem involved translation of truth table values to Boolean expressions. It was the same in both versions. Answers are U0 = N2 + N1 + N0 U4 = N2 N1 N0 U2 = !N2 N1 N0 + N2 !N1 !N0 + N2 !N1 N0 (sum of products) = N2 + N1 N0 (simplified) Each part was worth 1 point. You didn't need to simplify U4 or U0, and you didn't need to simplify U2 all the way. Some of you provided a sum-of-products expression for U0, which was maximally unsimplified! Common errors mainly involved faulty simplifica-tion of U2. Problem 4 (4 points) In this problem, you were to provide a simplified Boolean expression representing a given circuit. The circuits differed slightly in the two versions: in version A, the bottom multiplexor had A and 0 as the 0 and 1 inputs, while in version B those inputs were ex-changed.4 A good approach is to make a truth table: version A version B S 0 1 A 0 0 0 1 0 1 S 0 1 A 0 0 0 1 1 0 Simplifying, we find that the output X = S A (version A) or X = !S A (version B), You received 1 point out of 4 for getting started; you received 3 points out of 4 for an in-sufficiently simplified expression. Problem 5 (6 points) Here, you had to supply arguments to an assembly language version of snprintf. This problem was the same on both versions. (We announced at the exam that the format string should be changed to "%s%d %c", i.e. with no blank after the "%s".) Here is a so-lution. # argument 4 (in $a3): the string "N = " la $a3,chars+5 # argument 5 (on the stack): the integer 112 lb $t0,more sw $t0,0($sp) # argument 6 (on the stack): the character
View Full Document
Unlocking...