CSCI-UA.0480-003 Parallel Computing
Midterm Exam
(60 minutes)
- This exam contains 6 questionswith a total of 30 points.
- If you must make assumptions to continue solving a problem, state your assumptions clearly.
1. 并行计算考试代考
Assume we have the following task graph. A task can be thought of as function/procedure. An arrow from a task to another means that the first task generates data needed by the second one. Do not make anyassumptions regarding cache misses, coherence, etc. The table indicates the time taken by each task.
| Task# | Duration |
| 1 | 5 |
| 2 | 10 |
| 3 | 10 |
| 4 | 100 |
| 5 | 20 |
| 6 | 5 |
a. [2 points] What is the smallest number of cores needed to get the best performance? Explain.
b. [2 points] Based on the number of cores you picked in part (a) above, what is the total run time?
c. [2 points] If we use 6 cores, what will be the efficiency?
d. [2 points] What is the span for the above graph? what is the work?
e. [1 point] What is the parallelism of that graph?
f. [1 point] What does the number you calculated in (e) mean?
g. [2 points] Suppose that task 2 takes 100 units of time instead of 10, what will be your answer to question (a) above? Justify
2.[3 points] 并行计算考试代考
We have studied Amdahl’s law in class. Suppose that the fraction of the sequential part of your program is 50% and we have four cores. What is the best action to get better performance: trying to reduce the sequential part to 20%? Or keeping it at 50% but use five cores instead of four? Justify your answer using Amdahl’s law.
3.[4 points]
Suppose you have an MPI program and a sequential program. State two reasons that can make the MPI running with p processes slower than the sequential code (p > 1). [Note: You will be penalized for a wrong statement.]
4.[3 points] 并行计算考试代考
Suppose we want to parallelize factorial n (that is, n!), using MPI, with p processes. Assume that n is divisible by p and n > p. State the steps needed to do it such that the result is at process 0? Initially, only process 0 has the value of n. Do not write code but you can mention the name of the APIs you will use. Put your answer in a numbered list (step 1, step 2, ….).
5.[2 points]
As we increase the number of processes in MPI, does coherence protocol overhead becomes more severe? Justify.
6.[6 points] 并行计算考试代考
Assume the following three processes in MPI and the operations they do at each time step of the same program. Also assume that the destination is always process 0 and that the reduction operation is MPI_SUM.
| Time | Process 0 | Process 1 | Process 2 |
| 0 | x = 2; y = 3; | x = 3; y = 4; | x = 4; y = 5; |
| 1 | MPI_Reduce(&x, &y, …) | MPI_Reduce(&y, &x, …) | MPI_Reduce(&x, &y, …) |
| 2 | MPI_Reduce(&y, &x, …) | MPI_Reduce(&y, &x, …) | MPI_Reduce(&y, &x, …) |
Fill in the following table with values of x and y in each process
After Step 1:
| Process 0 | Process 1 | Process 2 | |
| x | 2 | 3 | 4 |
| y | 10 | 4 | 5 |
After Step 2:
| Process 0 | Process 1 | Process 2 | |
| x | 17 | 3 | 4 |
| y | 10 | 4 | 5 |
更多代写：cs代上网课机构 雅思作弊 英国法学博士代写 代写Essay抄袭 代写assignment作业 并行计算考试代做
