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

Problem 1

Suppose we have the following code snippet is running on an eight core processor:

1.   #pragma omp parallel for

2.   for(int i = 0; i <N; i++){

3.         for(int j = i; j < N; j++){

4.                     array[i*N + j] = sin(i) + cos(j);

5.         }

6.   }

(a) [5 points]  Given the code above, which schedule will be better in terms of performance: static? Or Dynamic? And Why?

(b) [5 points]  If we substitute line 1 with #pragma omp for will we get same? Better? or worse performance than the original code? Justify your answer.

(c) [5 points] If we move the pragma statement from the outer loop, line  1, to the inner loop, before line 3, will that give better performance? Justify your answer.

(d) [20 points, 5 for each bullet] Assume array[] is an array of int, cache block is 64 bytes,  and N is 4096. For each  statement below, to be used  in line  1  above, indicate whether there may be false sharing and why. Assume we have one thread per outer loop iteration.

•   #pragma omp parallel for schedule(static, 1)

•   #pragma omp parallel for schedule(static, 8)

•   #pragma omp parallel for schedule (static, 16)

•   #pragma omp parallel for schedule (dynamic)

Problem 2

Suppose we want to write a program to ask a user to enter a positive number N. After that, the program will ask the user to enter N integers. Then, for each one of the N numbers, the program calculates the factorial of that number and prints the results on the screen. For example, if the user enters N = 3 and then enters: 3, 7, and 9, the program must print on the screen the result of: 3!, 7!, and 9!.

We want to write that problem in OpenMP such that we have one thread responsible for each factorial. So, for the example above, we need three threads, one to calculate 3!, one for 7!, and one for 9!.

(a) [5 points] If you must choose between using sections and tasks, which technique will you use? And Why?  Do not write code.

(b)  [5 points]  If we decide to use  a for-loop  over the N numbers and each iteration calculates the factorial of one of the numbers, what will be the best schedule? And why?

(c) [5 points] Suppose that the N numbers the user entered are stored in an array. We want to create N threads. Each thread must go over each one of the N numbers and add to it 2x where x is the thread ID. So, thread with ID 0 will add 1, thread with ID 1 will add 2, thread with ID 2 will add 4, etc. If the user entered 3, 7, and 9, as above, then the first number will be updated by the three threads to be 3 + 20  + 21  + 22, the second number will be updated to be 7 + 20  + 21  + 22, etc. Now, as you can see, there is a race condition at each number of the N numbers (when more than one thread try to update the number). How will you deal with that issue? You have four choices: atomic, critical, critical with name, and locks. Which one will you pick and why?

Problem 3

Answer the following questions about GPUs and CUDA.

(a) [5 points] Suppose we have a GPU with 8 SMs. If we launch a kernel with 16 blocks, will that generate an error because the number of blocks is larger than the number of SMs? If yes, state why. If no, state what will happen.

(b) [5 points] If we have a GPU that has 64 SPs per SM. Can we launch a block with 128 threads? If no, state why. If yes, state how an SM with 64 SPs will deal with a block of 128 threads.

(c) [4 points] When knowing about the concept of warps you can write better CUDA programs. State two reasons for why knowing about warps can enhance your CUDA coding.

(d) [6 points] State three characteristics of a problem that makes it a good candidate for GPU instead of multicore.