关键词 > CSCI-UA.0480
CSCI-UA.0480-051: Parallel Computing Final Exam 2022
发布时间：2024-06-14
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSCI-UA.0480-051: Parallel Computing
Final Exam (May 12th, 2022)
Total: 100 points
Problem 1
a. [5] A programmer is developing a program for a company. The programmer has parallelized 90% of the program. The programmer has been informed that the problem size will remain the same no matter how many cores will be used. What is the expected speedup on 10 cores? Show your steps. Make any needed assumptions if any. Round the speedup to the nearest single digit after the floating point.
b. [5] A programmer was able to write a parallel program, running on four cores, and obtain a speedup of 2. What is the fraction of the sequential part of this program? Show all the steps to get full credit. Assume the cores are superscalar but not with hyperthreading capability.
c. [15] State three reasons as to why coherence protocol has a negative effect on performance in a shared-memory machine.
Problem 2
Suppose we have 4 processes. Each one has an array of int called A. Assume these are the only processes in a communicator called NEWCOMM. Each array consists of four int, and initialized as follows:
|
|
Initial values in each process’s array A |
|||
|
Process 0 |
1 |
8 |
9 |
8 |
|
Process 1 |
2 |
7 |
10 |
15 |
|
Process 2 |
3 |
6 |
11 |
14 |
|
Process 3 |
4 |
5 |
12 |
13 |
a. [7] Each of the four processes has another array of four int called B. Array B in each process are not initialized. There is a function call that all processes made. The result of this call is that the content of arrays B changed to the following values. Write down that call with all its arguments. It is one line not more.
|
|
Values in each process’s array B after the call |
|||
|
Process 0 |
0 |
0 |
8 |
8 |
|
Process 1 |
0 |
0 |
8 |
8 |
|
Process 2 |
0 |
0 |
8 |
8 |
|
Process 3 |
0 |
0 |
8 |
8 |
b. [3] What is the minimum number of communicators that each one of these four processes can be a member of? Justify.
c. [5] Suppose we execute the above processes on a machine with 16 cores, each one is 2- way hyperthreading. Is there any chance these four processes will fully use all the cores simultaneously? Explain.
Problem 3
a. [5] We know that statements: #pragma omp single and #pragma omp master both make its following statement be executed by only one thread. Give a scenario where we must use the #pragma omp master and not the other one.
b. [5] Given the following nested-loops, is it more beneficial to parallelize (using OpenMP), the outer loop? or the inner loop? And why?
for (i=1; i < n; i++) {
for (j = 0; j < n; j++) {
v[j][i] = (v[j][i-1] + v[j][i] + v[j][i+1])/4);
}
}
c. [20] For each one of the following scenarios, state whether you will use atomic, critical, or locks in OpenMP to deal with critical sections. If there are several possible choices in a scenario, pick the one that gives the best performance. If there are several possible solutions for a scenario, each of which gives the same performance as the others, then write all of them. Be as specific as possible. No justifications are needed for your choices.
|
Scenario |
What will you use? |
|
Several critical sections, each one consists of several lines of code, and we know the number of critical sections at programming time. |
|
|
Several critical sections, each one consists of one line of code in the form of “variable++” (where variable is any variable name), and we know the number of critical sections at programming time. |
|
|
We don’t know the exact number of critical sections at programming time, but we know them at execution time. |
|
|
Only one critical section that consists of several lines of code |
|
Problem 4
Suppose we have the following code snippet. The programmer launches the kernel with:
printing<<<3,2>>>( );
|
__global__ printing(){ __shared__ int x = 7; if(blockIdx.x > 0) printf(“%d”, blockIdx.x); else printf(“x”); synchthreads(); printf(“%d”, threadIdx.x); } |
a. [12 points] For each one of the following statements, specify whether it is a “possible” output or “not possible” output (i.e. can never be printed on the screen no matter how many times we execute the kernel). No need to justify your choice, just write (a. , b. , … ) and next to each one (“possible”, or “not possible”).
a. 770100010001 b. 000100011101 c. 701020711121
d. 777000000111 e. 000000011177 f. 001077010001
b. [6 points] If we remove the shared keyword, which ones of your answers above will change? Justify.
c. [6 points] If we remove the synchthreads(), which ones of your answers (in part a) above will change? Justify.
d. [6 points] How many warps are created when the kernel is launched? Explain.
