# CS代考 CS 15-213, Fall 2001 Final Exam – cscodehelp代写

Andrew login ID: Full Name:
CS 15-213, Fall 2001 Final Exam
December 13, 2001
Instructions:

Copyright By cscodehelp代写 加微信 cscodehelp

Make sure that your exam is not missing any sheets, then write your full name and Andrew login ID on the front.
Write your answers in the space provided below the problem. If you make a mess, clearly indicate your final answer.
The exam has a maximum score of 120 points.
This exam is OPEN BOOK. You may use any books or notes you like. You may use a calculator, but no laptops or other wireless devices. Good luck!
TOTAL (120):
Page 1 of 18

Problem 1. (20 points):
We are running programs on a machine with the following characteristics:
Values of type int are 32 bits. They are represented in two’s complement, and they are right shifted
arithmetically. Values of type unsigned are 32 bits.
Values of type float are represented using the 32-bit IEEE floating point format, while values of
type double use the 64-bit IEEE floating point format.
We generate arbitrary values x, y, and z, and convert them to other forms as follows:
/* Create some arbitrary values */ int x = random();
int y = random();
int z = random();
/* Convert to other forms */
ux = (unsigned) x;
uy = (unsigned) y;
dx = (double) x;
dy = (double) y;
dz = (double) z;
For each of the following C expressions, you are to indicate whether or not the expression always yields 1. If so, circle “Y”. If not, circle “N”. You will be graded on each problem as follows:
If you circle no value, you get 0 points.
If you circle the right value, you get 2 points.
If you circle the wrong value, you get points (so don’t just guess wildly).
Expression
Always True?
(x-y)
((x+y)<<4) + y-x == 17*y+15*x ̃x+ ̃y+1 == ̃(x+y) ux-uy == -(y-x) (x >= 0) || (x < ux) ((x >> 1) << 1) <= x (double)(float) x == (double) x dx + dy == (double) (y+x) dx + dy + dz == dz + dy + dx dx * dy * dz == dz * dy * dx Page 2 of 18 Problem 2. (10 points): A C function looper and the assembly code it compiles to on an IA-32 machine running Linux/GAS is shown below: pushl %ebp movl %esp,%ebp pushl %esi pushl %ebx movl 8(%ebp),%ebx movl 12(%ebp),%esi xorl %edx,%edx xorl %ecx,%ecx cmpl %ebx,%edx movl (%esi,%ecx,4),%eax cmpl %edx,%eax movl %eax,%edx cmpl %ebx,%ecx movl %edx,%eax movl %ebp,%esp int looper(int n, int *a) { int i; int x = ______________; for(i = ____________; ________________; if (___________________) x = _________________; ____________________; return x; } Based on the assembly code, fill in the blanks in the C source code. Notes: You may only use the C variable names n, a, i and x, not register names. Use array notation in showing accesses or updates to elements of a. Page 3 of 18 Problem 3. (10 points): Consider the following incomplete definition of a C struct along with the incomplete code for a function func given below. typedef struct node { _______________ x; _______________ y; struct node *next; struct node *prev; void func() { node_t *m; m = ______________________; m->y /= 16;
When this C code was compiled on an IA-32 machine running Linux, the following assembly code was generated for function func.
pushl %ebp
movl n+12,%eax
movl 16(%eax),%eax
movl %esp,%ebp
movl %ebp,%esp
shrw \$4,8(%eax)
Given these code fragments, fill in the blanks in the C code given above. Note that there is a unique answer. The types must be chosen from the following table, assuming the sizes and alignment given.
Size (bytes)
Alignment (bytes)
char short unsigned short int unsigned int double
1 2 2 4 4 8
1 2 2 4 4 4
Page 4 of 18

Problem 4. (8 points):
Consider the source code below, where M and N are constants declared with #define. int array1[M][N];
int array2[N][M];
void copy(int i, int j) {
array1[i][j] = array2[j][i];
Suppose the above code generates the following assembly code:
pushl %ebp
movl %esp,%ebp
pushl %ebx
movl 8(%ebp),%ecx
movl 12(%ebp),%eax
leal 0(,%eax,4),%ebx
leal 0(,%ecx,8),%edx
subl %ecx,%edx
sall \$2,%eax
movl array2(%eax,%ecx,4),%eax
movl %eax,array1(%ebx,%edx,4)
movl %ebp,%esp
What are the values of M and N? M=
Page 5 of 18

The following problem will test your understanding of the runtime stack. You are given the following declarations on an x86 architecture:
struct file_spec {
int fs_tag, parent_dir, size;
struct l_node {
struct l_node *next;
struct l_node get_list_head() {
/* some irrelevant code */ }
void make_alias(…, …, …, …, …) {
/* some more irrelevant code */ }
void save_file(struct file_spec *file, int len, char *descriptor) {
int result = 0;
struct l_node root = get_list_head();
make_alias(…, …, …, …, …);
/* yet more irrelevant code */ }
On the next page, you have the diagram of the stack immediately before the call assembly instruction formakealias()insavefile()isexecuted. Argumentdescriptorgiventosavefile()is stored at 0xbffff5c0. You can make the following assumptions:
The function make alias() takes exactly five arguments.
The allocation order of local variables on the stack corresponds to their definition order in the source
The compiler does not insert any additional unused space on the stack apart from unused space re- quired for alignment restrictions of variables.
No registers (apart from %ebp) are being saved on the stack.
Page 6 of 18

Feel free to make comments or notes in the third column of the table – they will not be graded.
Numeric Value
0xbffff5c0
0xbffff7a0
0xbffff5bc
0x000feedb
0xbffff5b8
0xbffff780
0xbffff5b4
0x080459ec
0xbffff5b0
0xbffff630
0xbffff5ac
0x00000000
0xbffff5a8
0x83045c30
0xbffff5a4
0x00000045
0xbffff5a0
0xbffff5ac
0xbffff59c
0x83045c30
0xbffff598
0x00000045
0xbffff594
0xbffff780
0xbffff590
0x000feedb
0xbffff58c
0xbffff7a0
Page 7 of 18

Problem 5. (12 points):
A. Give the current value of the frame pointer (machine register %ebp).
B. Thedeclarationofmakealias()ismissingthetypesofitsparameters.Givethetypesintheorder they would appear in the source code. The names of the parameters do not matter.
C. List the arguments passed to make alias() in save file(), in the order they would appear in the source code.
makealias( , , , , );
Page 8 of 18

Problem 6. (6 points):
The following table gives the parameters for a number of different caches, where is the number of physical address bits, is the cache size (number of data bytes), is the block size in bytes, and is the number of lines per set. For each cache, determine the number of cache sets ( ), tag bits ( ), set index bits ( ), and block offset bits ( ).
Page 9 of 18

Problem 7. (14 points):
Consider a direct mapped cache of size 64K with block size of 16 bytes. Furthermore, the cache is write- back and write-allocate. You will calculate the miss rate for the following code using this cache. Remember that sizeof(int) == 4. Assume that the cache starts empty and that local variables and computations take place completely within the registers and do not spill onto the stack.
A. Now consider the following code to copy one matrix to another. Assume that the src matrix starts at address 0 and that the dest matrix follows immediately follows it.
void copy_matrix(int dest[ROWS][COLS], int src[ROWS][COLS]) {
for (i=0; i 0) {
counter += 2;
printf(“counter = %d
”, counter); }
What is the output of this program?
Page 15 of 18

Part III (4 points)
int counter = 0;
void handler(int sig)
counter ++; }
int main() {
signal(SIGCHLD, handler);