CS:2630, Exam 3, Fall 2019

The distributions shown here exclude 3 students who did not take the final exam and 4 more students who earned no credit for any machine problem, as these students did not meet the criteria for consideration as having participated in the class, as announced in the course policy handout at the start of the semester and discussed on in lecture.

Exam 3 (Final)

Total Exams 1 — 3

Machine Problems 1 – 6

Top 10 Scores From Homeworks 1 – 12

Total

Note that no student scoring below 46 demonstrated significant competence as a programmer by getting a solution to at least one machine problem to work reasonably well, while students scoring below 38 generally did little more than create syntactically correct but non-functional code.

Solutions and Commentary

A problem: Here are some binary values. Give the interpretation of each value, in the indicated number system expressed as a decimal number. (2 points)

Binary values	`11000110`	`10010110`	`01110111`	`11111001`	`01100000`	`01101100`
scratch space	`________`	`________`	`________`	`________`	`________`	`________`
scratch space	`________`	`________`	`________`	`________`	`________`	`________`
1's complement	`__-57___`	`_-105___`	`__119___`	`___-6___`	`___96___`	`__108___`
2's complement	`__-58___`	`_-106___`	`__119___`	`___-7___`	`___96___`	`__108___`

Over 1 in 3 did perfect work here, while around 1 in 4 had serious trouble with -105, -106 and 119, and around 1 in 6 had trouble with -58, -7 as a 2's complement number and 96 and 108 as one's complement numbers. Why -6 (as a 1's complement value) was easy while -7 (as a 2's complement value) was hard is a puzzle.

This problem should have been trivial. It was offered as a second chance on a problem that gave people troube on the first midterm. Students who could not master that problem then needed that skill to master just about everything after that in this course.

A problem: For each SMAL Hawk instruction below, give the source addressing mode: (1 point)

LIS     R3,12           _____immediate________

MOVE    R4,R3           _____register_________

LOADS   R5,R4           _____short_indexed____

LOAD    R6,WHERE        _____pc_relative______

LOAD    R7,R6,THING     _____indexed__________

1 in 3 got this perfectly. 1 in 10 earned no credit. Among those earning partial credit, the most common error was to refer to register mode as short-indexed mode.

As discussed in class, a question about addressing modes is a classical job interview question to determine if the applicant actually knows anything about computer architecture.

Small problems: For each of the following, give the exact answer in hex and a reasonable decimal approximation of that value (unless you give the exact decimal value). (2 points)

a) Throughout the semester, we have used the sequence LIL R1,AAA followed by JSRS R1,R1 to call external subroutines. Give the smallest memory address AAA where this does not work.

Hex: ____800000__________ Decimal: ___8,000,000________

1 in 20 got this right, 1 in 10 had off by one or off by a factor of 2 errors, earning partial credit. Over 1 in 3 left the problem blank. It seems that an awful lot of students had difficulty remembering that the LIL instruction has a 24 bit address field, or inferring from this the bound on the values it can load.

Forgetting that the constant AAA is sign extended to 32 bits is natural, but students who did the programming assignments should have a hard time forgetting that it is a 24 bit constant.

b) Give the largest value of BBB for which ADDI R3,R3,BBB works.

Hex: ______7FFF__________ Decimal: ______32,000________

1 in 20 got this, 1 in 10 earned partial credit, and 1 in 3 left this blank, as above.

Again, forgetting that the constant is sign extended to 32 bits is natural, but every student should know that it is a 16-bit constant.

b) Give the largest value of CCC for which ADDSI R3,CCC works.

Hex: _________8__________ Decimal: ___________8________

1 in 6 got this, while 1 in 10 earned partial credit for off-by-one errors or focusing on the unconventional binary representation for 8 in this instruction.

This is a little tricky, because CCC is a 4-bit signed constant with a special case to allow +8 to be encoded. Also, the question asked about the value of CCC as an assembly language source-code value, not the binary encoding in the machine code.

c) Give the largest value of DDD for which SRU R3,DDD works.

Hex: ________10__________ Decimal: __________16________

1 in 8 got this, while 1 in 7 earned partial credit for off-by-one errors or focusing on the unconventional binary representation of 16 in this instruction.

This is a little tricky, because DDD is a 4-bit unsigned constant with a special case to allow +16 to be encoded. Also, the question asked about the an assembly language source-code value, not the machine code encoding.

Some code:

__D5_ __1F_  L1:     LIS     R5,31        1 in 4 had trouble with 1F

__25_ __54_          SUB     R5,R5,R4

__0C_ __0D_          BLTU    L3           1 in 2 had trouble with 0D

__15_ __D2_          BTRUNC  R5,2

__A3_ __01_          SL      R3,1

__A3_ __01_          SL      R3,1

__A3_ __01_          SL      R3,1

__95_ __02_          SR      R5,2

__15_ __D2_          BTRUNC  R5,2

__A3_ __04_          SL      R3,4

__A3_ __04_          SL      R3,4

__A3_ __04_          SL      R3,4

__90_ __45_          BITTST  R4,4          2 in 3 had difficulty here
                       
__0C_ __01_          BBR     L2            2 in 3 had difficulty here

__A3_ __00_          SL      R3,16         1 in 2 had the wrong shift count

__F0_ __B1_  L2:     JUMPS   R1            1 in 6 had trouble here

__D3_ __00_  L3:     LIS     R3,0

__00_ __FD_          BR      L2            1 in 2 had trouble here

a) The BITTST and BBR instructions above are derived instructions. Give the equivalent SMAL Hawk code for the instructions they really stand for. (0.4 points)

________ADDSR___R0,R4,5_______________________________________________

________BCR_____L2____________________________________________________

1 in 30 got this, 1 in 8 earned partial credit with the wrong shift count and a similar number earned partial credit with the wrong destination register. A smattering of students earned partial credit with other errors, while over half earned no credit.

Some students were clearly confused by the notion of derived instructions in the SMAL Hawk assembly language. This is a central feature of the language, where NEG is really SUB and JUMP is really JSR. Admittedly, BITTST was discussed only briefly, but this question was, in significant part, intended to test students' ability to look things up. This question also lays groundwork for the next part.

b) Hand assemble this code giving each instruction as two bytes in hex, just like a normal SMALL assembly listing. (5 lines are duplicates so should take no extra work.) (2.3 points)

In addition to the problems with individual instructions outlined above, 1 in 2 gave the two bytes of each instruction in the wrong order.

Students who did MP6 had their copies of the assembly listing of their solution in hand while solving this question, so "just like an assembly listing" was not asking for much.

This question was another "second chance" question based on the first midterm, where many students had difficulty hand assembling a piece of code. It is quite clear that the lowbyter architecture of the Hawk causes trouble for a significant number of students (presumably, they would be equally baffled by the Intel commodity architecture found on PCs), and PC relative addressing is still a big problem for many students.

c) What register(s) does this code expect to hold parameters? (0.4 points)

________R3,_R4________________________________________________________

Almost 1 in 2 did perfectly here, while 1 in 6 earned no credit. Among those earning partial credit, 1 in 6 omitted R3, 1 in 15 omitted R4, and 1 in 4 included R5.

The only registers the code uses are R1, R3, R4 and R5. R1 is obviously the return address, and the code begins by initializing R5, leaving only R3 and R5, both of which are used by the code and therefore must be parameters.

d) What register(s) does this code use to return results? (0.4 points)

________R3____________________________________________________________

3 in 5 got this, while 1 in 4 earned no credit.

R3 is intensively modified in this code, so that is a trivial guess. R4 is unchanged, so it is not a candidate for a result register. R5 is computed and then partly destroyed in this code, all in the process of selecting how to modify R3, so it seems to be an intermediate value in the computation.

e) What does it do? Hint: This code does something simple and it has been tested. (0.5 points)

________R3_=_R3_<<_R4_________________________________________________

________SL______R3,R4_(if_the_Hawk_allowed_that)______________________

1 in 30 got this. 1 in 4 left it blank, while almost 1 in 2 gave nonsense answers. Among the minority who earned partial credit, the most common answer was that the code multiplies or expnentiates. A few students tried to write long essays that included strong hints that they understood the code while obscuring that fact in baffling verbiage.

In fact, this code is close to the fastest code possible on the Hawk for shifting by a variable amount, and this was expected to be a hard question because this code is tricky.

Background: Here is the floating point format given on the second midterm:


s	exp			mnt

sign of mantissa

exp

biased exponent
111 – not a number, infinity if m=0
011 – represents zero
000 – non-normalized values (hidden bit = 0)

mnt

mantissa with hidden bit in 1's place

Give the binary representation and its decimal equivalent for: (2 points)

a) The smallest nonzero value: _______000001_______ = ___0.0625____

b) The most positive non-infinite: _______011011_______ = __14.0_______

c) The most negative non-infinite: _______111011_______ = _-14.0_______

d) 1.0: _______001100_______ = ___1.0_______

1 in 3 got part a), while 1 in 2 got each of the other parts. Clerical errors were common, but aside from that, it is hard to generalize about the kinds of errors students made.

Another "second chance" question. Clarification was given for part a) during the exam when a student wondered if the value there could be negative — no, it is positive, otherwise part c) would have the same answer.

Background: Conside machine problem 6, a trap handler used to emulate the LOADNA dst,x,disp instruction. The body of the posted solutions to this problem never explicitly mentions any register in the range R8 to R15, yet the prologue to the trap handler carefully saves the values of all of these registers and the epilogue carefully restores all of them. (2 points)

a) Explain why it was necessary to save all of the registers before the LOADNA instruction could be emulated. Hint: An example LOADNA instruction can be used to illustrate the need to do so.

________Consider_LOADNA_R5,R9,XXX_for_example_________________________

________This_needs_the_saved_value_of_the_user's_R9_to_comput_EA______

1 in 4 did well here, while 1 in 6 gave unclear explanations that might have been right and could have been clarified by an example (an example could also have demonstrated that those answers were in fact wrong). Close to 1 in 10 gave answers that were so verbose that they were penalized.

1 in 6 gave answers such as "everything must be saved so it can all be restored." this ignored the flat statement in the background statement that the trap handler does not make any explicit use of R8 and up.

b) Explain why it was necessary to restore all of the registers before the trap handler returns. Hint: An example LOADNA instruction can be used to illustrate the need to do so.

________Consider_LOADNA_R9,R3,XXX_for_example_________________________

________This_needs_to_change_the_saved_value_of_the_user's_R9_________

Only 1 in 10 gave good answers here, while 1 in 6 could have earned more credit with a well chosen illustration or a less verbose answer.

1 in 5 gave answers such as "everything must be restored to undo any changes made by the trap handler." This ignores the flat statement in the background statement that the trap handler does not make any explicit use of R8 and up. Furthermore, by stating that they are undoing changes made by the trap handler, they defeate the actual purpose of restoring these registers, which is to force the side effects of the LOADNA instruction to be visible to the user on return from trap.

Background: On most computers, different instructions may require different numbers of pages of memory to be referenced during one fetch-execute cycle. (2 points)

a) How big is a page of memory on the Hawk (in bytes)?

____4k________________________________________________________________

1 in 10 got this, while 1 in 12 earned partial credit.

Wild answers such as 4 and 256 suggested that many students didn't bother to study the Hawk MMU.

b) Give examples of Hawk instructions that require at most one page reference?

____MOVE,_SL,_EXTB_(and_16-bit_instr_that_doesn't_reference_memory)___

1 in 6 got this, giving at least 2 example instructions. 1 in 4 gave just one instruction, for partial credit.

c) Give examples of Hawk instructions that require at most two page references?

____LIL,_LEA,_LOADS_(long_non_memory_ref,_short_memory_ref)___________

Only 1 in 30 got this, and an additional 1 in 30 gave just one instruction.

Here, note that an instruction that occupies two halfwords may (but usually won't) span a page boundary, and a memory reference instruction may (and probably will) refer to an operand in a different page.

d) Give examples of Hawk instructions that require at most three page references?

____LOAD,_STORE_(long_memory_reference)_______________________________

1 in 12 got this, while 1 in 11 gave just one example.

Here, note that these two instructions both occupy two halfwords that may span a page boundary, and they are memory reference instructions. These are the only two Hawk instructions that may need 3 pages in order to execute.

Here is a C version of the posted solution to MP5;

void putfloat( float num, int places ) {     1
    int inum;                                2
    if (num < 0.0) {                         3
        num = -num;                          4
        putchar( ' ' );                      5
    }                                        6
    inum = (int)num;                         7
    printf( "%1d", inum );                   8
    putchar( '.' );                          9
    while (places > 0) {                    10
        num = (num - (float)inum) * 10.0;   11
        inum = (int)num;                    12
        putchar( '0' + inum );              13
        places = places - 1;                14
    }                                       15
}                                           16

a) Assume that num is in R3. Give fast code for line 4. (1.5 points)

____CMP_____R3,R3___;_sets_the_C_bit__________________________________

____ADJUST__R5,CMSB_;_adds_it_to_the_sign_bit_________________________

______________________________________________________________________

______________________________________________________________________

1 in 5 gave a variation on the above answer, probably having studied the posted solution to MP5 if they did not use this answer in their code.

Any code that adds, subtracts or exclusive-ors 80000000₁₆ to R3 will work; the above is the fastest way to do this.

The other popular answer, given by 1 in 8 involved loading zero into a floating-point register and then doing a floating point subtract. This is much slower but gives exactly the same result. These students probably did something similar in their solutions to MP5.

1 in 4 used NEG (2's complement negate) must not have managed to debug a solution to MP5 and not bothered to look at posted solutions. IEEE floating format does not use the 2's complement number system and therefore cannot be negated using an integer negate operation. Thse may well have made the same error mon MP5 and did not bother looking at their returned assignments or the posted solution.

b) Most of the arithmetic operations used above are supported by the Hawk or by the Hawk floating-point coprocessor. Which lines contain operations that must be implemented by nontrivial algorithms on the Hawk? (0.5 points)

____7_and_12__________________________________________________________

1 in 20 got this, 1 in 2 earned no credit. Penalties were assigned for each wrong line suggested.

Anyone who solved MP5 (or bothered to read the posted solution) will have noticed that the floating-to-integer conversions on lines 7 and 12 were done by calls to FTOI in the Hawk monitor, while integer-to-floating conversion is done by the FPINT coprocessor operation.

Those who mentioned calls to putchar or printf didn't read the question, where it asked about "arithmetic operations." Those who considered the expression on line 11 complex also ignored the fact that it is made up of multiple simple arithmetic operations, each of which is implemented by one Hawk instruction.

c) Lines 8 and 13 both output inum as a decimal number. What is it about inum that allows the simple fast code on line 13? (0.5 points)

____it_is_guaranteed_to_be_only_one_digit_____________________________

1 in 8 got this. There was little partial credit.

1 in 12 asserted that it works because INUM is an integer, but that is as true on line 8, where printf (in C) or PUTDECU in the Hawk monitor are required to handle multi-digit numbers.

d) How many words must be in the activation record of putfloat? (0.5 points)

____4_(return_address,_num,_places,_inum)_____________________________

1 in 5 got this, while almost 1 in 2 earned no credit. The most common error, made by 1 in 12, was to forget to allow for inum. (note, the algorithm can be rewritten so this does not need to be saved, but as written, it must be saved through line 8.)

No penalty or credit was assigned for those who explicitly saved and restored the coprocessor state, since that is not required by the statement of the exam question.

Background: Consider this C statement: a = b->c[d] where b points to a structure with a field c that is an array of integers. Assume that a, b and d are local variables. Write SMAL Hawk code equivalent to this C statement: (2 points)

________LOAD____R3,R2,B_________;_get_value_of_the_pointer_b__________

________LEA_____R3,R3,C_________;_get_address_of_field_b->c___________

________LOAD____R4,R2,D_________;_get_value_of_d______________________

________ADDSL___R4,R3,2_________;_get_address_of_b->c[d]______________

________LOADS___R3,R4___________;_get_value_of_b->c[d]________________

________STORE___R3,R2,A_________;_assign_value_to_a___________________

______________________________________________________________________

Just one student did perfect work. An average of 1 in 6 omitted each of the instructions listed above, entitling the student to partial credit. The ADDSL and STORE instructions were omitted less frequently than the others. 1 in 5 left the problem blank and over 1 in 3 gave answers that were nonsensical. The award for weirdness goes to the student who found a need to write an answer incorporating a loop.

This was offered as a simple question of the type that would have been entirely fair on the second midterm. Of course, nothing in the problem statement said what registers to use. The above solution uses as few registers as possible.

Exam 3: Final

Solutions and Commentary

Grade Distributions

Exam 3 (Final)

Total Exams 1 — 3

Machine Problems 1 – 6

Top 10 Scores From Homeworks 1 – 12

Total

Solutions and Commentary