→ rod24574575 : 已收資訊系精華區! 09/18 23:10
課程名稱︰平行程式設計
課程性質︰選修
課程教師：劉邦鋒
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰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://www.ptt.cc/bbs/NTU-Exam/M.1442588965.A.BAC.html