跳转至

14 Parallel Algorithms

说明

  1. 本文档仅涉及部分内容，仅可用于复习重点知识
  2. 本文档部分图片来源于教学课件
  1. Parallel Random Access Machine (PRAM)
  2. Work-depth measurement

1 The summation problem

Img 1
Img 2

在 Work-depth measurement 中，定义

\[ W = T_1 = \Theta(n)\\ D = T_{\infty} = \Theta(\log n) \]

在此问题中，W 等于树中节点总数即 n，D 等于树的高度即 \(\log n\)

Brent's theorem

下界：\(\dfrac{W}{p} \leqslant T_p\)

上界：\(T_p \leqslant \dfrac{W}{p} + D\)

在此问题中，\(\Theta(\dfrac{n}{p}) \leqslant T_p \leqslant \Theta(\dfrac{n}{p} + \log n)\)

PTA 14.3

To evaluate the sum of a sequence of 16 numbers by the parallel algorithm with Balanced Binary Trees, B(1,6) is found before B(2,1).

T
F

答案

T

详见上图，计算 B 的时候是从下往上，从左往右计算的

2 Prefix-Sums

Img 3
Img 4
PTA 14.2

To evaluate the Prefix-Sums of a sequence of 16 numbers by the parallel algorithm with Balanced Binary Trees, C(4,1) is found before C(2,2).

T
F

答案

T

详见上图，计算 C 的时候是从上往下计算的

PTA 14.6

The prefix-min problem is to find for each i, 1≤i≤n, the smallest element among A(1), A(2), ⋯, A(i). What is the run time and work load for the following algorithm?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
for i, 1≤i≤n pardo
  B(0, i) = A(i)
for h=1 to log(n)
  for i, 1≤i≤n/2^h pardo
    B(h, i) = min {B(h-1, 2i-1), B(h-1, 2i)}
for h=log(n) to 0
  for i even, 1≤i≤n/2^h pardo
    C(h, i) = C(h+1, i/2)
  for i=1 pardo
    C(h, 1) = B(h, 1)
  for i odd, 3≤i≤n/2^h pardo
    C(h, i) = min {C(h + 1, (i - 1)/2), B(h, i)}
for i, 1≤i≤n pardo
  Output C(0, i)

A. \(O(n), O(n)\)
B. \(O(\log n), O(\log n)\)
C. \(O(\log n), O(n)\)
D. \(O(n), O(\log n)\)

答案

C

Depth：第一个 for 循环 \(O(1)\)，第二个 \(O(\log n)\)，第三个 \(O(\log n)\)，第四个 \(O(1)\)，所以是 \(O(\log n)\)

work：分别为 \(O(n), O(n), O(n), O(n)\)，所以是 \(O(n)\)

3 Merge two non-decreasing arrays

Img 5
Img 6
Img 7
Img 8
PTA 14.9

Which one of the following statements about the Ranking problem is true? (Assume that both arrays contain N elements.)

A. There exists a serial algorithm with time complexity being O(logN).
B. Parallel binary search algorithm can solve the problem in O(1) time.
C. When partitioning the problem into sub-problems and solving them in parallel, choosing loglogN as the size of each sub-problem can reduce the work load and the worst-case time complexity to O(logN).
D. There is a parallel algorithm that can run in O(logN) time and O(N) work.

答案

D

A. 应为 \(O(n + m)\)

B. \(O(\log n)\)

C. \(O(n)\)

时间复杂度分析上面图片里都有

4 Maximum finding

Img 9
Img 10
Img 11
Img 12
Img 13
PTA 14.4

In order to solve the maximum finding problem by a parallel algorithm with T(n)=O(1) , we need work load \(W(n)=Ω(n^2)\) in return.

T
F

答案

F

采用 random sampling，可以 W 可以达到 O(n)

PTA 14.5

To solve the Maximum Finding problem with parallel Random Sampling method, O(n) processors are required to get T(n)=O(1) and W(n)=O(n) with very high probability.

T
F

答案

T

详见上面的图片

PTA 14.7

Which one of the following statements about the Maximum Finding problem is true?

A. There exists a serial algorithm with time complexity being O(logN).
B. No parallel algorithm can solve the problem in O(1) time.
C. When partitioning the problem into sub-problems and solving them in parallel, compared with \(\sqrt{N}\), choosing loglogN as the size of each sub-problem can reduce the work load and the worst-case time complexity.
D. Parallel random sampling algorithm can run in O(1) time and O(N) work with very high probability.

答案

D

A. 最好的也就是 \(O(n)\)，达不到 \(O(\log n)\)

B. compare all 和 random sampling 可以

C. depth 时间复杂度降低不了，仍为 \(O(\log \log n)\)

详见上面的图片

PTA 14.1

While comparing a serial algorithm with its parallel counterpart, we just concentrate on reducing the work load.

T
F

答案

F

减少 worst-case 的 time 也很关键

PTA 14.8

Sorting-by-merging is a classic serial algorithm. It can be translated directly into a reasonably efficient parallel algorithm. A recursive description follows.

MERGE−SORT( A(1), A(2), ..., A(n); B(1), B(2), ..., B(n) )

Assume that \(n = 2^l\) for some integer l≥0

if n = 1 then return B(1) := A(1)

else call, in parallel, MERGE−SORT( A(1), ..., A(n/2); C(1), ..., C(n/2) ) and

  • MERGE−SORT(A(n/2+1), ..., A(n); C(n/2+1), ..., C(n) )
  • Merge (C(1),...C(n/2)) and (C(n/2 + 1),...,C(n)) into (B(1), B(2), ..., B(n)) with time O(n)

Then the MERGE−SORT runs in __ .

A. \(O(n\log n)\) work and \(O(\log^2 n)\) time
B. \(O(n\log n)\) work and \(O(\log n)\) time
C. \(O(n\log^2 n)\) work and \(O(\log^2 n)\) time
D. \(O(n\log^2 n)\) work and \(O(\log n)\) time

答案

C

run time: \(O(1) + O(\log n) + O(\log n) + O(1) = O(\log n)\)

work load: \(O(n) + O(n) + O(n) + O(n) = O(n)\)

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问