CSCI-UA.0480-051: Parallel Computing Final Exam

Problem 2

Assume the following three processes in MPI and the operations they do at each time step of the program. Also assume that the reduction operation is MPI_MIN. The ranks of the three processes (0,  1, and 2) are their ranks in MPI_COMM_WORLD, and all the APIs called in the table below use MPI_COMM_WORLD.

Fill in the following table with values of x and y in each process:

[6] After Step 1:

[6] After Step 2:

[6] After Step 3:

a.  [5] Suppose we have three communicators, including MPI_COMM_WORLD. How many ranks does each of the above three processes have? Explain in no more than two lines.

b. [7] If we have a quad-core processor, can these three processes use all the cores at the same time? Justify in 1-2  lines.  Assume each one of the four cores has superscalar capability but no hyperthreading capability. Of course, the code shown above for each process is just a small part of the full code of the process (i.e. the full code of each process is bigger than what is shown in this problem).

Problem 3

Suppose we have the following code snippet. Assume all variables and arrays have been declared and initialized earlier.

a.  [10]  Assume M  = N. What  do we have to write in  line  3  above to  get  as much performance as possible from the above code? You must not have race condition and at the same time get the best performance. No need to write any explanations, just the line of code.

b. [10] Repeat problem a, but assume M = 2N.

c. [5] Based on your answer in b, do we need to write anything in line 8 to make the code even faster? If no, then just say no. If yes, then write the line you will include in line 8.

d. [5] If M = 16, N = 8, and the multicore on which we run the code has  16 cores. How many threads do you think OpenMP runtime will create when executing line 1? Justify in no more than two lines. Assume no other processes/threads are using the multicore except the above code.

Problem 4

[15] Choose one answer only from the multiple choices for each problem. If you pick more than one answer, you will lose the grade of the corresponding problem.

1. Suppose a block, when launching a GPU kernel, is composed of 33 threads. How many warps will be created for this block?

a. 1      b. 2      c. 4       d.5       e. Depends on the total number of blocks.

2. Which of the following is NOT an advantage of warps?

a. reduces complexity of the GPU hardware

b. reduces penalty of thread divergence

c. decouples the dependence of the number of threads in a block on the number of SPs in the SM.

3. If we have a local variable in the GPU kernel, it will surely go to registers.

a. True             b. False            c. Depends on the compute capability of the GPU.

4.  More than one block from two different kernels can be assigned to the same SM at the same time.

a. True             b. False            c. Depends on the compute capability of the GPU.

5. If a critical section in OpenMP looks like { x += b;} what is the best mutual exclusion technique? Assume no other critical sections exist in the program.

a. lock             b. critical section         c. atomic

6. If a critical section in OpenMP looks like { x += c; y+=b; } what is the best mutual exclusion technique? Assume no other critical sections exist in the program.

a. lock             b. critical section         c. atomic

7. Sometimes, in OpenMP, we cannot know the number of critical sections in a program by just looking at the source code.

a. True             b. False

8. Suppose we launch a kernel as follows:    kernelname <<<4,4>>>(argument list …);

And suppose the kernel has a global variable x. How many instances of x will be created?

a. 16    b. 4      c. 8       d. 1   e. 2

9. An algorithm of O(n) can be faster than an algorithm of O(n2).

a. True             b. False

10. An algorithm of O(n2) can be faster than an algorithm of O(n).

a. True             b. False