[Parallel Algo.] 平行程式設計技巧Index

Parallel Algorithm Index [未完]

1. Symmetry Breaking
因為 problem 有對稱性, 導致無法平行處理，於是先把問題的對稱性打破， 再去平行解

2. Brnet's Theorem
原本是很多個 processors 處理 M 工作量，花費的時間是 T 可以用較少的 P processors 來 simulate，時間變成 O(M / P + T)，藉此降低cost

3. Euler-Tour Technique

4. Tree Contraction
"同時"利用 rake operations 可以在 O(lg n) 回合後，把 tree 變成 3-node binary tree

5. Sampling
透過取樣來估計答案，或縮小答案可能的範圍

6. Overlapping
將 computation 和 communication (或 broadcasting) 結合，兩件事同時做

7. Multi-level
將一回合的暴力做法分成多個 stages, 降低暴力法的 cost

8. Divide & Conquer [click]
將輸入分成幾乎相同大小的子問題，平行且遞迴地解決每個子問題，將每個子問題的輸出結合在一起

9. Partition [click]
將問題分成p個獨立且大小幾乎一樣的子問題，同時解決p個問題，其中p是可使用的processor數量

10. Balanced Binary Tree Method [click]
用input以balanced binary tree的方式建起一棵樹並從root或往root尋訪整棵樹來找出答案
11. Pointer Jumping(Doubling) [click]
每次和距離乘以二的processor的資料做運算直到遇到self-loop root為止

12. Accelerated Cascading
13. Pipeline
14. Double Logarithm-depth Tree