課程名稱︰平行程式設計 課程性質︰選修 課程教師：劉邦鋒 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2013.04.17 考試時限（分鐘）： 試題 : Parallel Programming Midterm Examination 04/17/2013 The first part of the examination is a written test. Please supply sufficient details so that we can be certain that you derive your answer with scientific deduction, not random guessing. (50%) 1. Suppose that f(n) = f(n-1) + 2f(n-2) + 3f(n-3), and f(1) = f(2) = f(3) = 1, please compute f(i) for all i less or equal to n. You will be given p processors to speed up the process. Please design an efficient parallel algorithm, and prove that it is efficient by analyzing its complexity, both in communication and computation. (15%) 2. Describe and compare multiprocessor and multicomputer. Give an example for each. (8%) 3. Describe and compare data and task parallelism. Give an example for each. (8%) 4. Describe and compare SIMD and MIMD computers. Give an example for each. (8%) 5. The interconnection of K computer is called TOFU. Why is that? (6%) 6. What is the purpose of firstprivate cluse in OpenMP? Please give an example that firstprivate is useful. (5%) The second part of the examination is programming. (50%) 1. Write a program to solve the partition problem. A partition problem is defined as follows. We are given a set of n numbers, and we would like to know the number of a sets of these numbers who's sum is no more than a given number m. For example, we are given a set = {2, 3, 4, 7}, and m = 6, and we would like to find the number of integers no more than m which can be the sum of a subset of S. In this example 2, 3, 4, 5, and 6 are possible so the answer is 5. We know we can get 2, 3, and 4 because we have them, we can also get 5 since we have 2, and 3. We can also get 6 since we have 2, and 4. Now write a sequential program to solve this problem. We will keep updating a sequence Q to find the answer. The initial value of the Q is (0, 0, 0, 0, 0, 0), which means we are not sure if we can find a subset of sum 1, 2, 3, 4, 5, and 6 respectively, and we will use Q[i] to denote the i-th element of Q. Now consider the first number S, which is 2. We can now update our Q to be (0, 1, 0, 0, 0, 0) now, since now we know we can get a subset of sum 2, since we have a 2. Now consider the second number 3. Let us consider Q[4]. If we want to set it to 1 now, that means the previous numbers in the set S must be able to add to 4 - 3 = 1. Unfortunately Q[1] is now 0, which means we cannot make it to 4, so Q[4] will remain 0. On the other hand, let us consider Q[5]. If we want to set it to 1, that means the previous numbers in the set S must be able to add to 5 - 3 = 2. This time we do know that Q[2] is 1, so we can set the fifth element in Q to 1. So in general Q[i] is 1 if it was 1 in the previous iteration, or Q[i-k] was 1 in the previous iteration, if k is the current number. If we use P[t][i] to denote Q[i] the t-th iteration, then P[t][i] is 1 if P[t-1][i] is 1, or P[t-1][i-k] is 1. Otherwise P[t][i] is 0. We now consider numbers in S one at an iteration. After considering all numbers in S, Q will be (0, 1, 1, 1, 1, 1), so the answer is 5, because 2, 3, 4, 5, and 6 (five of them) can be the sum of numbers in S. Now write a sequential program to solve this partition problem. The first line of the input is the number of test cases (1 <= T <= 5000). The first line of a test case has two integer - n (1 <= n <= 20000), and m (1 <= m <= 2000000). Each of the next n lines has a positive integer, which is an element in the set S. The output for each test case is the number of positive integers between 1 and m that can be the sum of a subset of S. (15%) 2. Write a parallel program for the partition problem with OpenMP. Note that we assume that the n and m in all test cases are roughly the same, which means all test cases will take roughly the same time to solve. If this is the case, how to easily parallelize the computation to solve all test cases? (5%) 3. Write a parallel program for the partition problem with OpenMP. Note that we assume that now we have only one very large case. This test case is so large we need to parallelize it to get performance. If this is the case, how to parallelize the computation? (10%) 4. Now image that we have several very large cases and a lot of small test cases. How do we parallelize the entire computation with OpenMP? Write a parallel program to solve these mixed sized input. (10%) 5. Redo the second problem with PThread. (10%) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.207.40 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1442588965.A.BAC.html