課程名稱︰平行程式設計
課程性質︰資工系選修
課程教師︰劉邦鋒
開課學院：電機資訊學院
開課系所︰資工所
考試日期（年月日）︰2017/04/25
考試時限（分鐘）：180
試題 :
Please answer the following questions in details.
1. Describe SIMD and data parallelism, and their connection. (20%)
2. Generalize the concept of dependency graph so that every task (node) has
a positive integer units of workload, and all tasks are non-preemptive.
i.e., each task must run on one processor from start to finish. Here we
assume that there are p processors, n tasks, and a processor can complete
a unit of workload per time step.
a. Based on this model, describe TWO lower bounds on the total time to
complete all tasks. The first lower bound is based on the idea of
"critical path," and the second lower bound is based on the idea that
all p processors can complete at most p units of work per time step.
(10%)
b. Now consider another model in which multiple processors can run a task
in parallel. That is, it allows two processors to complete a task of
eight units in four time steps. Will the two lower bounds still hold?
Explain your answers. (10%)
3. Describe the parallel prefix algorithm and analyze its time complexity and
speedup. Give a formal proof why the algorithm is correct. Also it seems
that this computation is inherently sequential, i.e., we cannot know the
i-th term before we actually computed the i-1'th term. However, we obtain
an algorithm that is faster than the lower bound n, where n is the number
of data. Explain the anomaly. (20%)
4. Describe Gustafson's Law. In particular describe the assumptions when it
will be valid. Also describe its implications. (20%)
5. Describe the importance of workload balancing in parallel computing. What
can you do to balance the load of iteration loops in an OpenMP program?
Describe two techniques and explain why they work. (20%)