15-213 Fall, 2004 Exam 1 SOLUTIONS 1. Intended Solution (Bias = +7) Entries: -0, 15/1024, -17/1024, 13, -248, +infty Solution for Bias = -7 Entries: -0, 240, -272, 212,992, -24,063,232, +infty 2. A. 1...1 for x < 0, 0...0 for x >= 0 B. -2 for x < 0, 0 for x >= 0 C. x >= 0 D. opt_abs(x) == abs(x) - 1 E. Compute return value as: comp-mask F. 0 and TMin 3. A. Register Variable %eax l, A[j], j %ebx r, j %ecx i %edx A[i], t %esi A %edi x %esp stack pointer %ebp stack frame pointer B. These are callee save registers. C. static int bunny(int l, int r, int *A) { int x = A[l]; int i = l - 1; int j = r + 1; while(i < j) { do { j--; } while(A[j] > x); do { i++; } while(A[i] < x); if(i < j) { int t = A[i]; A[i] = A[j]; A[j] = t; } } return j; } D. draft_horse() { if() { bunny(); draft_horse(); draft_horse(); } return; } E. This is the code for quicksort. 4. A. In the original code, strlen(str) must be called on every iteration due to potential side-effects. Moving it to line 3 reduces the number of calls from 'n' calls to a single call. B. Yes. In this code, the length of str is never changed, therefore strlen(str) will return the same value for each iteration of the loop. Additionally, strlen(str) has no side-effects. These two properties make it safe to move. C. In the original code, each iteration of the loop has a multiplication that depends on the single variable hash. By unrolling the loop, each iteration can perform two multiplications in parallel because they depend on separate variables. Note that in modern processors, accurate branch prediction will make loop overheads negligable in both cases (as the increment and jump instructions can be performed in parallel to the ongoing multiplication). D. Yes. Many compilers have an option to perform loop unrolling. In this case there are no potential side effects of a loop iteration, and thus loop unrolling would be safe to perform. E. Another optimization is replacing the * 32 with >> 5, a form of strength reduction. Because the shift operation is faster than multiply, this should improve performance. 5. A. |<---------------- buf ---------------->| +----+----+----+----+----+----+----+----+----+----+----+----+----+ | | 69 | 6c | 75 | 76 | 32 | 31 | 33 | 00 | | | | | +----+----+----+----+----+----+----+----+----+----+----+----+----+ ^ %ebp B. |<---------------- buf ---------------->| +----+----+----+----+----+----+----+----+----+----+----+----+----+ | | xx | xx | xx | xx | xx | xx | xx | xx | st | qr | op | mn | +----+----+----+----+----+----+----+----+----+----+----+----+----+ |<-- Ret addr ----->| |<---- arg -------->| +----+----+----+----+----+----+----+----+----+----+----+----+----+ | e2 | 83 | 04 | 08 | xx | xx | xx | xx | 13 | 52 | 01 | 00 | | +----+----+----+----+----+----+----+----+----+----+----+----+----+ 6. A. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | WID | name |//| address | balance | |////////| note | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ^ | domestic B. typedef struct { short WID; char name[5]; char domestic; Location address; double balance; char *note; } Compact; C. 24 D. typedef struct { short WID; char name[5]; char domestic; double balance; Location address; char *note; } Win_Compact; E. 0x004e4143 7. T, F, T, F, F, T, F