Rutgers University CS 211 Sections 1 and 2, Fall 2005 Second Midterm Exam

Rutgers University CS 211 Sections 1 and 2, Fall 2005 Computer Architecture Second Midterm Exam

Read these instructions carefully. On the front of your bluebook, write your name and section number (1 or 2). Read all of the questions carefully and write all of your answers in the bluebook provided. You may keep this question paper.

What is the output of the following C program on x86 Linux? Recall that the 0x prefix for constants means that the constant is in hexadecimal.

#include <stdio.h>
                                                                                
int main () {
        unsigned int a, b, c;
        int d;
                                                                                
        a = 0x6fffffff;
        b = 0xafffffff;
        c = a + b;
        d = (a > c) || (b > c);
        printf ("%d\n", d);
        return 0;
}

(Question #1: 10 points)
Answer

1

What is the output of the following C program on x86 Linux?

#include <stdio.h>
                                                                                
int main () {
        struct foo {
                int     a;
                char    *b;
                double  c;
                char    d;
                int     e;
                char    f;
        } A[4];
        printf ("%d\n", sizeof (A));
        return 0;
}

(Question #2: 10 points)
Answer

112

What is the output of the following C program on x86 Linux? Recall that the %x format specifier for printf causes output to be printed in hexadecimal.

#include <stdio.h>
                                                                                
int main () {
        int     a, i;
        char    *p;
                                                                                
        a = 0x12345678;
        p = (char *) & a;
        for (i=0; i<sizeof(int); i++)
                printf ("%x\n", (unsigned int) *(p + i));
        return 0;
}

(Question #3: 10 points)
Answer

78
56
34
12

Answer the following questions about locality:

Both instructions and data exhibit two kinds of locality. What are they? Give a brief definition of each kind.

(Question #4 part 1: 8 points - 4 each)
Answer

Temporal locality - An object that is referenced tends to be referenced again
in the near future.

Spatial locality - If an object is references, then objects near that object
in memory tend to be referenced also.

The behavior of programs naturally leads to very good locality for instructions (as opposed to data). Why is that? Give two reasons.

(Question #4 part 2: 8 points - 4 each)
Answer

1.  Most accesses to instructions are sequential, so they naturally have good 
spatial locality.

2.  Loops are common in programs.  This causes the same small set of
instructions to be references many times contemporaneously, leading to
good temporal locality.

For each of the following statements, write T if it is true, or F if it is false.
```
(Question #5: 10 points - 1 point each)
```
1. The least significant bit of a binary number always 1 if the number is odd.
```
T
```
2. Addition of two n-bit binary numbers takes O(n) time.
```
T
```
3. Access to registers is always faster than access to main memory.
```
T
```
4. The gets function should not be used because it might cause a buffer overflow.
```
T
```
5. Moving a function call outside of a loop can potentially change the asymptotic running time of a program.
```
T
```
6. SRAM and DRAM are both volatile types of memories.
```
T
```
7. Using the << operator instead of the * operator to multiply by a power of 2 can potentially change the asymptotic running time of a program.
```
F
```
8. Hard disk is a volatile type of memory.
```
F
```
9. The pushfl places the condition codes into the %ebx register.
```
F
```
10. The adcl instruction adds three values: two memory locations and the %ebx register.
```
F
```

Consider the following C program:

#include <stdio.h>

int p (int a, int b, int c) {
	int d, e, f;

	f = 0;
	for (d=a; d<b; d++)
		for (e=b; e<c; e++)
			f += d + e;
	return f;
}

When compiled with a high level of optimization, it looks like this (with line numbers added for reference):

01 p:
02 	pushl	%ebp
03 	movl	%esp, %ebp
04 	pushl	%edi
05 	pushl	%esi
06 	movl	12(%ebp), %edi
07 	movl	8(%ebp), %ecx
08 	pushl	%ebx
09 	xorl	%ebx, %ebx
10 	cmpl	%edi, %ecx
11 	movl	16(%ebp), %esi
12 	jge	.L28
13 .L26:
14 	cmpl	%esi, %edi
15 	movl	%edi, %edx
16 	jge	.L30
17 .L25:
18 	leal	(%edx,%ecx), %eax
19 	incl	%edx
20 	addl	%eax, %ebx
21 	cmpl	%esi, %edx
22 	jl	.L25
23 .L30:
24 	incl	%ecx
25 	cmpl	%edi, %ecx
26 	jl	.L26
27 .L28:
28 	movl	%ebx, %eax
29 	popl	%ebx
30 	popl	%esi
31 	popl	%edi
32 	movl	%ebp,%esp
33 	popl	%ebp
34 	ret

Write the name of the register and the offset from %ebp corresponding to each of a, b, and c.

(Question #6 part 1: 6 points - 2 each)
Answer

a is %ecx and offset 8 from %ebp
b is %edi and offset 12 from %ebp
c is %esi and offset 16 from %ebp

Write the name of the register corresponding to each one of d,e, f, and the return value.

(Question #6 part 2: 6 points - 2 each)
Answer

d is %ecx (the register for a is re-used for d)
e is %edx
f is %ebx

Which line number corresponds to d = a;?

(Question #6 part 3: 1 point)
Answer

Line 7 assigns the a parameter from the frame to the register allocated for d.

Which line number is the last of the assembly statements that implements f += d + e;?
```
(Question #6 part 4: 4 points)
Answer

Line 20
```

If line 32 were removed, would the function still work properly? Why or why not?

(Question #6 part 5: 4 points)

Yes.  At this point in the code, everything that has been pushed since
%ebp was pushed on line 2 has also been popped, so the stack pointer
has the same value that it did when it was assigned to %ebp in line 3.
Moving %ebp into %esp does not change the stack pointer.  Thus, line 32
essentially does nothing and can be removed.