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.
Problem 4
Some interesting questions about MPI
(a) [6 points] Suppose, in MPI_COMM_WORLD, there are two different processes of
rank x and y. Suppose there is a communicator, produced by MPI_Comm_split applied to
MPI_COMM_WORLD, with the name NEWCOMM. Is there a possibility that each
process, x and y, broadcasts a value to NEWCOMM (for example process x broadcasts
integer value 10 and process y broadcasts float value 3.14) but none of these two
processes receive each other’s value? If yes, explain how. If no, explain why. Assume no
deadlock happens. The original number of processes in MPI_COMM_WORLD is not
relevant to the solution of this question.
(b) [6 points] Suppose process x sends two messages to process y. That is, process x
executes two consecutive MPI_Send; and process y executes two consecutive MPI_recv.
We know that MPI_Recv is blocking. Also, there may be a probability that the two
messages sent by process x arrive to process y out of order (i.e. the second message
arrives first).
• Why the messages may arrive out of order?
• Does process y face a problem of being blocked forever if messages arrive out of
order? Justify your answer.
(c) [6 points] If each process in a communicator call MPI_Reduce twice. That is, two
reduction operations one after the other. Can some of the processes finish the first
reduction operation and move to the next one before the other processes finish theirs?
Justify. This question is not related to the questions (a) and (b) above.
(d) [4 points] Why do MPI processes not suffer from cache coherence overhead?
(e) [8 points] If we have four processes in MPI generated with mpiexec -n 4. Each one
has a fraction F of its code that is inherently sequential and cannot be parallelized. The
sequential code in each process is the same in all the four processes. Using Amdahl’s
law, what is the theoretical speedup we get from using four processes over one process,
assuming F = 20%? Show all your steps to get full credit.