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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.16.134 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1493110722.A.BD1.html ※ 编辑: jason1218 (140.112.16.134), 04/25/2017 16:58:59 ※ 编辑: jason1218 (140.112.16.134), 04/25/2017 16:59:16