15-213 Introduction to Computer Systems
Exam 1 February 27, 2007
Name: ID: Recitation Section:
• This is an open-book exam. Notes are permitted, but not computers. • Write your answer legibly in the space provided.
Copyright By PowCoder代写 加微信 powcoder
• You have 80 minutes for this exam.
Integers Floating Point Assembly Language Calling Conventions Structures and Alignment Out-of-Order Execution
1. Integers (10 points)
For each of the following propositions, write in all comparisons that make it always true
among the four possibilities:
If none are guaranteed to hold, please indicate that explicitly by marking it with an X. We have filled in the first two for you as examples. Assume the variables are declared with
and initialized to some unknown values. You may assume that int’s are 32 bits wide, char’s are 8 bits wide and that right shift is arithmetical on signed numbers and logical on unsigned numbers.
I f x > y t h e n y < x
!= Ifx<0thenx+1 X 0
Ifx>0thenx+1 0
If(x>>31)<0thenx 0
If ((x << 31) >> 31) < 0 then x & 1
Ifx>ythen(unsigned)x
If ((unsigned char)x >> 1) < 64 then (char)x
2. Floating Point (15 points)
1. (10 pts) Fill in the blank entries in the following table. We assume an IEEE repre- sentation of floating point numbers with 1 sign bit, k = 3 bits for the exponent and n = 4 bits for the fractional value. This means the bias is 23−1 − 1 = 3.
We are only considering positive numbers.
Form M × 2E for1≤M <2
Hexadecimal representation
Decimal fraction
Smallest denorm.
Smallest norm.
Largest norm.
2. (5 pts) With standard single precision floating point numbers with 1 sign bit, k = 8 bits for the exponent, and n = 23 bits for the significand, what is the smallest positive value for n declared with int n; such that
(int)(float)n != n ?
3. Assembly Language (15 points)
Consider the following recursive C program that sorts a segment of an integer array into ascending order in place.
/* qsort(A, low, high) sorts subarray A[low]..A[high] */ void qsort (int* A, int low, int high) {
int pivot, i, k;
if (low >= high) return; pivot = A[high];
while (i < k) {
if (A[i] < pivot) { i++;
A[k] = A[i];
A[i] = A[k];
A[k] = pivot;
qsort(A, low,
qsort(A, k+1,
k-1); high);
The while loop is compiled to the following assembly language instructions. Hint: The entry point of the loop is at label .L8. Hint: Do not try to fill in the missing instructions until you have answered questions 1 and 2 on the next page.
incl %edx
jmp .L8
movslq %edx, %rcx
movl (%rbp,%rcx,4), %eax cmpl %r8d, %eax
movl %eax, (%rbp,%rdi,4) decl %ebx
___________________________
___________________________ movl %eax, (%rbp,%rcx,4)
cmpl %ebx, %edx jl .L7
1. (5 pts) Complete the following table associating C variable or expressions with reg- isters.
2. (5pts)Theregister%eaxholdstemporaryvaluesduringtheloopcomputation.List all the expressions in the original C program whose values it holds.
3. (5 pts) Fill in the two missing instructions.
C Expression
4. Calling Conventions (10 points)
After the code of the while loop shown before, we find the following instructions to implement the first recursive call.
movl %r8d, (%rbp,%rdi,4) leal -1(%rbx), %edx
movq %rbp, %rdi
call qsort
1. (5 pts) By the x86-64 calling conventions, which of the mentioned registers are guar- anteed to have the same value when qsort returns as right before the call? Write yes or no into the space.
We are surprised that following the first recursive call, we find no further recursive call, but instead the instructions
leal 1(%rbx), %esi jmp .L14
where .L14 is a label near the beginning of the qsort procedure. The compiler used an optimization to eliminate the second recursive call in favor of a jump instruction.
2. (5 pts) Complete the following rendering of the compiler’s optimization in C in the form of a new while loop.
void qsort (int* A, int low, int high) {
int pivot, i, k;
/* eliminated here: if (low >= high) return; */ while (___________) {
pivot = A[high];
while (i < k) { ... as before ... } A[k] = pivot;
qsort(A, low, k-1);
___________________
/* was: qsort(A, k+1, high); */
5. Structures and Alignment (10 points)
This question concerns alignment on an x86-64 architecture and pointer arithmetic. Con- sider the following C structure declaration.
struct box {
int tag; /* 0 = int, 1 = long, 2 = float, 3 = double */ union {
} data; };
1. (3 pts) What is the total size of a box structure on an x86-64, expressed in bytes?
2. (2 pts) An element of type struct box must be aligned at 0 modulo .
3. (5 pts) Write a C function int high4 (long x); that extracts the high 4 bytes of a long as an int. For example, high (0x1234567890abcdef) should return 0x12345678. Use a box structure and pointer arithmetic. Your code may ignore the tag field.
6. Out-of-Order Execution (15 points)
We now return to the earlier quicksort procedure. If the array is already sorted, the first conditional branch instruction in the code fragment below will always be taken.
1. (5 pts) Assume that the processor correctly predicts this, as well as the second branching instruction (for example, because they both go backwards). On the right- hand side, show the translation of the assembly language instructions into execution unit operations with register renaming. Do not rename registers that are invariant throughout multiple loop iterations. We have already filled in the translations of the conditional branches; the unconditional jump is handled by the instruction fetch unit. Consider .L7 as the starting point of an iteration.
| %edx, %rcx | (%rbp,%rcx,4), %eax |
| jl-taken cc.1a |
| jl-taken cc.1b
%ebx, %edx
| (handled in fetch unit)
%r8d, %eax
2. (7 pts) Complete the labeling in the following timed data dependency diagram. We have already filled in the registers that are not renamed and one register move op- eration.
Iteration 1
3. (3 pts) What is the theoretical CPE for this loop, assuming perfect branch prediction and no resource limitions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com