【ADS】Parallel Algorithm

发表于 | 分类于 ， | | 阅读次数:

Parallel Random Access Machine (PRAM)

  • EREW PRAM模型(Exclusive-Read Exclusive-Write)。每次只允许一台处理机读或写某一共享单元内容。
  • CREW PRAM模型(Concurrent-Read Exclusive-Write)。每次可允许多台处理机同时读同一个共享单元内容，但每次只允许一台处理机向某个共享单元写内容。
  • ERCW PRAM模型。 每次可允许多台处理机同时写同一个共享单元内容，但每次只允许一台处理机向某个共享单元读内容。
  • CRCW PRAM模型。每次允许多台处理机同时读和同时写同一共享单元内容。 该模型又可进一步分为：
    • Common rule。每次允许多台处理机写相同值到某一共享单元中。
    • Arbitrary rule。每次如果有多台处理机写值到某一共享单元中，则任选一台作为优胜者，它的值写到该共享单元中。
    • Priority rule。每次如果有多台处理机写值到某一共享单元中，则选处理机编号最小者作为优胜者，它的值写到该共享单元中。

Work load – total number of operations: W(n)
Worst-case running time: T(n)


Summation problem

​ B(h, i) := B(h-1, 2i-1) + B(h-1, 2i)

​ T(n) = O(logn), W(n) = O(n)


Prefix-Sums: Balanced Binary Trees, C(h,i)

​ T(n) = O(logn), W(n) = O(n)


Merging problem: Partitioning(partitioning, actual work)

i. Merging Ranking: RANK(j, A) ,RANK(i, B)

​ BinSearch: T(n) = O(logn), W(n) = O(nlogn);

​ Serial Ranking: T(n) = O(n), W(n) = O(n);

ii.Parallel Ranking（p=n/logn)

​ T(n) = O(logn), W(n) = O(n)


Maximum Finding：

Compare all pairs（find B(i) == 0）

T(n) = O(1), W(n) = O(n*n)

i. Doubly-logarithmic Paradigm: Partition by $n^{1/2}$

​ T(n) = O(loglogn), W(n) = O(nloglogn)

ii. Partition by h = log log n

​ T(n) = O(loglogn), W(n) = O(n)

iii. Random Sampling

​ $M(n^{7/8})$ ~ T(n) = O(1), W(n) = O(n)


Exercises

ex1

ex2