# 代写代考 AB18ED24 – cscodehelp代写

15-213 Introduction to Computer Systems
Final Exam May 10, 2007
Name: Model Solution ID: fp
Recitation Section:

• This is an open-book exam.
• Notes and calculators are permitted, but not computers. • Write your answer legibly in the space provided.
• You have 180 minutes for this exam.
Floating Point Assembly Language Optimization Cache Memory Signals Garbage Collection Threads Synchronization

1. Floating Point (20 points)
In this problem we consider properties of floating point operations. For each property state whether it is true or false. If false, give a counterexample as a (possibly negative) power of 2 within the range of precision for the variables. We assume that the variables on an x86 64 architecture are declared as follows
float x,y,z;
double d,e;
and initialized to some unknown value different from NaN, +∞, and −∞. We have given the first answer as an example.
(x + y) + z == x + (y + z)
x = 1,y = 2127,z = −2127
Ifx > 0thenx / 2 > 0
(x + y) * z == x * z + y * z
x = 2127,y = −2127,z = 2127
Ifx >= yandz <= 0thenx * z <= y * z Ifx > ythen(double)x > (double)y
Ifd > ethen(float)d > (float)e
d = 2129,e = 2128

2. Assembly Language (20 points)
In this problem we consider an illustrative program for multiplication of two unsigned int’s,returninganunsignedlong intholdingtheproduct.
unsigned long mult (unsigned i, unsigned k) {
unsigned long p = 0;
unsigned long q = k;
while (i != 0) {
if (i & 1)
p = p + q;
q = q << 1; i = i >> 1; }
return p; }
The following is the resulting machine code when compiled on an x86 64 machine with gcc -O2,omittingtwoinstructions.
xorl %ecx, %ecx
mov %esi, %edx
testl %edi, %edi
jmp .L8
leaq (%rcx,%rdx), %rax
testb \$1, %dil
_______________________
shrl %edi
_______________________
# missing conditional move
# missing move

1. (5 pts) For each register, give the value it holds during the iteration, expressed in terms of the C program.
C expression
2. (5 pts) Fill in the missing two instructions in the code.
3. (4 pts) Rewrite the loop to use a conditional jump instead of a conditional move.
testb \$1, %dil
movq %rax, %rcx
4. (3pts)Explainbrieflywhythecompilerpreferredtouseaconditionalmoveinstruc- tion.
cmovne %rax, %rcxandmovq %rcx, %rax
See one solution below; there are many others.
Because the branch misprediction penalty would make the loop slower, espe- cially since the outcome of test will be difficult to accurately predict.

5. (3 pts) Assume we declared and initialized
and called
m = (long)mult((unsigned)i, (unsigned)k);
using the above definition of mult. Will m hold the correct value of the signed product of i and k? Circle the correct answer.
For example, when multiplying 1 times −1, the negative 1 will actually be in- terpreted as 232 − 1 and the result will also be 232 − 1 instead of −1. However, the answer will be correct modulo 232 because on two’s-complement represen- tations, signed and unsigned addition and multiplication are identical: they operate in the ring of integers modulo 2w for the word size w (= 32, in this case).

3. Optimization (20 points)
Consider the following code for calculating the dot product of two vectors of double precision floating point numbers.
double dot_prod(double A[], double B[], int n) {
double r = 0;
int customers = 0;
void* customer() {
if (customers > N) {
return NULL;
customers += 1;
getHairCut();
customers -= 1;
return NULL;
void* barber() {
while(1) {
cutHair();

For the solution, we use three binary semaphores:
• customer to signal a customer is in the shop.
• barber to signal the barber is busy.
1. (5 points) Indicate the initial values for the three semaphores.
• customer • barber
2. (15 points) Complete the code above filling in as many copies of the following com- mands as you need, but no other code.
P(&mutex);
V(&mutex);
P(&customer);
V(&customer);
P(&barber);
V(&barber);

Solution: There are a number of solutions; below is one. Be careful to release the mutex beforeleaving.Forthissolution,initialvaluesaremutex = 1(variablecustomersmay beaccessed),customer = 0(nocustomers)andbarber = 0(barberisnotbusy).
void* customer() {
P(&mutex);
if (customers > N) {
V(&mutex);
return NULL;
customers += 1;
V(&mutex);
V(&customer);
P(&barber);
getHairCut();
P(&mutex);
customers -= 1;
V(&mutex);
return NULL;
void* barber() {
while(1) {
P(&customer);
V(&barber);
cutHair();