Exam 1 Solutions
15-213 / 18-213 Fall 2011
*********
Problem 1
*********
1-c 2-b 3-c 4-c 5-d 6-c 7-b 8-c
*********
Problem 2
*********
umax: 63
tmin: -32
(unsigned) ((int) 4): 4
(unsigned) ((int) -7): 57
((unsigned) 0x21) << 1) & 0x3f: 0x02
(int) (20 + 12): -32
12 && 4: 1
(! 0x15) > 16: 0
*********
Problem 3
*********
Value FP bits Rounded value
1 100 10 3 normalized, exact
9 110 00 8 normalized, round down, because 10 is odd
3/16 000 11 3/16 exact, denorm
15/2 110 00 8 normalized, round up, change exponent
*********
Problem 4
*********
1st blank: n == 0 or n < 1
2nd blank: n >> 1 or n / 2
*********
Problem 5
*********
Part A:
+--------------------------------+
| unknown | 0xffff1008
+--------------------------------+
| 18 | 0xffff1004
+--------------------------------+
| 213 | 0xffff1000
+--------------------------------+
| unknown | 0xffff0ffc
+--------------------------------+
| unknown | 0xffff0ff8
+--------------------------------+
| unknown | 0xffff0ff4
+--------------------------------+
| unknown | 0xffff0ff0
+--------------------------------+
| 15 | 0xffff0fec
+--------------------------------+
| 18 | 0xffff0fe8
+--------------------------------+
| 0x080483b7 | 0xffff0fe4
+--------------------------------+
| 0xffff0ff8 | 0xffff0fe0
+--------------------------------+
| unknown | 0xffff0fdc
+--------------------------------+
| unknown | 0xffff0fd8
+--------------------------------+
| 3 | 0xffff0fd4
+--------------------------------+
| 15 | 0xffff0fd0
+--------------------------------+
| 0x080483b7 | 0xffff0fcc
+--------------------------------+
| 0xffff0fe0 | 0xffff0fc8
+--------------------------------+
| unknown | 0xffff0fc4
+--------------------------------+
| unknown | 0xffff0fc0
+--------------------------------+
| 0 | 0xffff0fbc
+--------------------------------+
| 3 | 0xffff0fb8
+--------------------------------+
| unknown | 0xffff0fb4
+--------------------------------+
| unknown | 0xffff0fb0
+--------------------------------+
Part B:
esp: 0xffff0fcc
ebp: 0xffff0fe0
Grading Rubric:
Part A (8):
Let m be the number of mistakes. The following is a
non-exhaustive list of possible mistakes:
- An entry is left blank, although it should contain a value.
- An entry is filled in, although it should remain blank.
- An entry contains an incorrect value.
- The stack is shifted up or down by four bytes. (If the stack
is shifted by more than four bytes, count the number of times
it is shifted.)
In general, 8 - ceil(m / 2) points should be awarded for this
subproblem. However, at the grader's discretion, one or two
extra points can be awarded for solutions that display some
knowledge of x86 stack conventions, or one or two extra points
can be deducted for solutions that betray only feeble knowledge
of x86 stack conventions.
Part B (2):
One point each for %esp and %ebp. The addresses must be
consistent with the values provided in the stack diagram.
*********
Problem 6
*********
Part A:
+----+----+----+----+----+----+----+----+
| a | XX | XX | XX | XX | XX | XX | XX |
+----+----+----+----+----+----+----+----+
| b | b | b | b | b | b | b | b |
+----+----+----+----+----+----+----+----+
| c | c | XX | XX | XX | XX | XX | XX |
+----+----+----+----+----+----+----+----+
|d[0]|d[0]|d[0]|d[0]|d[0]|d[0]|d[0]|d[0]|
+----+----+----+----+----+----+----+----+
|d[1]|d[1]|d[1]|d[1]|d[1]|d[1]|d[1]|d[1]|
+----+----+----+----+----+----+----+----+
|e[0]|e[1]|e[2]| XX | f | f | f | f |end
+----+----+----+----+----+----+----+----+
Part B:
(gdb) disassemble foo
Dump of assembler code for function foo:
0x00000000004004e4 <+0>: sub $0x8,%rsp
0x00000000004004e8 <+4>: movb $0x65,(%rdi)
0x00000000004004eb <+7>: movq $0x0,0x18(%rdi)
0x00000000004004f3 <+15>: movw $0x213,0x10(%rdi)
0x00000000004004f9 <+21>: movzbl 0x29(%rdi),%ecx
0x00000000004004fd <+25>: lea 0x2c(%rdi),%rdx
0x0000000000400501 <+29>: mov 0x8(%rdi),%rsi
0x0000000000400505 <+33>: mov $0x40062c,%edi
0x000000000040050a <+38>: mov $0x0,%eax
0x000000000040050f <+43>: callq 0x4003e0
0x0000000000400514 <+48>: add $0x8,%rsp
0x0000000000400518 <+52>: retq
End of assembler dump.
Part C:
Most compact ordering is 40 bytes. for example: b, d, f, e, a, c
*********
Problem 7
*********
int test(int x, int y, int z)
{
int result = 3;
switch(z)
{
case 0:
x = x & 25;
case 3:
case 7:
result = x;
break;
case 5:
result = 2 * x;
case 4:
result = result + y;
break;
default:
result = y;
}
return result;
}
*********
Problem 8
*********
Answer: (B) 8.
For (A) the sequence of accesses will result in M H M M M M, hit rate = 0.16
For (B) the sequence of accesses will result in M H H M M M, hit rate = 0.33
For (C) the sequence of accesses will result in M H H H M M, hit rate = 0.5
Hence, the answer is (B)
*********
Problem 9
*********
The unstated assumption is that C[i][j] is stored in a register.
However, the question as written is ambiguous because it doesn't state
this assumption clearly. Thus we will accept a miss rate of either 1/2
or 1/4 for part A.
Part A:
16 floats in a block
For row-wise A: Pattern is 1 miss, 15 hits, 1 miss, 15 hits, ...
For col-wise B: Pattern is miss, miss, miss, ...
For C[i][j] not in register: pattern is miss, hit, hit, hit, hit, ...
If C[i][j] in register, then there are zero memory accesses to C[i][j] during
each inner loop.
If you assumed that C[i][j] is in a register, then there are only
accesses to A and B in the inner loop. Thus, the miss rate = 17/32 ~
1/2
If you assumed that C[i][j] is not in a register, then we have to
include the accesses to C in the miss rate calulation: Thus, the miss
rate = 17/48, which is closer to 1/4 than 1/2.
Part B:
For row-wise A, B: Pattern is 1 miss, 15 hits, 1 miss, 15 hits, ...
If you assumed that C[i][j] is in a register, then the miss rate is
2/32 = 1/16.
If you assumed that C[i][j] is not in a register, then the miss rate
is 2/48 = 1/24, and the closest rate on the answer key is still 1/16.