15-213 Introduction to Computer Systems
Final Exam May 10, 2007
Name: ID: Recitation Section:
• This is an open-book exam.
Copyright By PowCoder代写 加微信 powcoder
• Notes and calculators are permitted, but not computers. • Write your answer legibly in the space provided.
• You have 180 minutes for this exam.
Problem Max
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
Ifx >= yandz <= 0thenx * z <= y * z
Ifx > ythen(double)x > (double)y
Ifd > ethen(float)d > (float)e
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
_______________________
addq %rdx, %rdx
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.
4. (3pts)Explainbrieflywhythecompilerpreferredtouseaconditionalmoveinstruc- tion.
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. yes no
Briefly explain your answer.
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;
for (i = 0; i < n; i++)
r = r + A[i] * B[i];
Assume that multiplication has a latency of 12 cycles and addition a latency of 7 cycles and load 4 cycles. Also assume that there are an unlimited number of functional units. [Hint: Under this assumption, theoretically optimal performance is dominated by the critical data dependency path.]
1. (5 points) What is the theoretically optimal CPE for this loop?
2. (10 points) Show the code for the loop unrolled by 2. You may apply associativity and commutativity of multiplication and addition, assuming that rounding errors are insignificant.
double dot_prod2(double A[], double B[], int n) {
double r = 0;
return r; }
3. (5 points) What is the theoretically optimal CPE for this loop? 6
4. Cache Memory (20 points)
In this problem we explore the operation of a basic TLB as a cache. Assume the following
• Virtual addresses are 32 bits.
• The virtual page number (VPN) is 24 bits.
• The physical page number (PPN) is 32 bits.
• The TLB is 2-way set associative containing a total of 512 lines.
1. (6 points) Please fill in the following blanks by giving a bit range, such as “0–15”.
(a) The VPO of a virtual address consists of bits (b) The VPN of a virtual address consists of bits
(c) The PPO of a physical address consists of bits (d) The PPN of a physical address consists of bits
(e) The TLB index (TLBI) consists of bits (f) The TLB tag (TLBT) consists of bits
of the VA. of the VA.
of the PA. of the PA.
of the VPN. of the VPN.
We show a part of the TLB relevant to the next two questions.
1 0x083E 0xAB18ED24
0x083F 0x0913ABDE
1 0x083F 0xAB18ED24
1 0x083F 0xAB18ED24
0xAB18ED24
0xF3E9 0x0913ABDE
0x409A 0x0913ABDE 0x083E 0x0913ABDE
2. (7 points) Assume the virtual address is 0x083F3E9A. Fill in the following table in hexadecimal notation. Write U for any value that is unknown, that is, not deter- mined from the parameters and the table above.
Cache Hit? (Y/N/U) PPN
3. (7 points) Assume the virtual address is 0x083E409B. Fill in the following table in hexadecimal notation. Write U for any value that is unknown, that is, not deter- mined from the parameters and the table above.
Cache Hit? (Y/N/U) PPN
5. Signals (20 points)
Consider the following program.
int counter = 0;
void handler (int sig) {
counter++;
int main() {
signal(SIGUSR1, handler);
signal(SIGUSR2, handler);
int parent = getpid();
int child = fork();
if (child == 0) {
/* insert code here */
exit(0); }
waitpid(child, NULL, 0);
printf("Received %d USR{1,2} signals\n", counter);
For each of the following four versions of the above code, list the possible outputs of this program, assuming that all function and system calls succeed and exit without error. You may also assume no externally issued signals are sent to either process.
1. (5 pts)
kill(parent, SIGUSR1);
kill(parent, SIGUSR1);
2. (5 pts)
kill(parent, SIGUSR1);
kill(parent, SIGUSR1);
kill(parent, SIGUSR1);
3. (5 pts)
kill(parent, SIGUSR1);
kill(parent, SIGUSR2);
4. (5 pts)
kill(parent, SIGUSR1);
kill(parent, SIGUSR2);
kill(parent, SIGUSR1);
kill(parent, SIGUSR2);
6. Garbage Collection (20 points)
In this problem we consider a tiny list processing machine in which each memory word consists of two bytes: the first byte is a pointer to the tail of the list and the second byte is a data element. The end of a list is marked by a pointer of 0x00. We assume that the data element is never a pointer.
We start with the memory state on the left, where the range 0x10–0x1F is the from- space and the range 0x20–0x2F is the to-space. All addresses and values in the diagram are in hexadecimal.
Write in the state of memory after a copying collector is called with root pointers 0x10 and 0x12, in this order. You may leave cells that remain unchanged blank.
Please be sure to use the proper breadth-first traversal algorithm covered in lecture.
Addr Ptr Data Addr
1014A210 121A1F12 141E0214 161E2016 18003318 1A 18 BC 1A 1C 12 DF 1C 1E108F1E
Addr Ptr Data 20
22 24 26 28 2A 2C 2E
After garbage collection, free space starts at address
7. Threads (20 points)
Consider three concurrently executing threads in the same process using two semaphores s1 and s2. Assume s1 has been initialized to 1, while s2 has been initialized to 0.
What are the possible values of the global variable x, initialized to 0, after all three threads have terminated?
/* thread A */
/* thread B */
/* thread C */
8. Synchronization (20 points)
We explore the so-called barbershop problem. A barbershop consists of a n waiting chairs and the barber chair. If there are no customers, the barber waits. If a customer enters, and all the waiting chairs are occupied, then the customer leaves the shop. If the barber is busy, but waiting chairs are available, then the customer sits in one of the free chairs.
Here is the skeleton of the code, without synchronization.
extern int N; /* initialized elsewhere to value > 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:
• mutex to control access to the global variable customers.
• 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);
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com