课程名称︰平行程式设计
课程性质︰资工系选修
课程教师︰刘邦锋
开课学院：电机资讯学院
开课系所︰资工所
考试日期（年月日）︰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%)