平行演算法期末報告

指導教授: 楊昌彪

8624623 楊家豪

題目：Computing the Minimum Spanning Tree

MST 演算法：

單 CPU：使用 Prim Algorithm.

Prim 演算法：先將第一點放到 spanning tree ，然後找最近的點放入
tree，之後再找距離tree最近的點放入，直到所有點都放到tree。其時
間複雜度為 O(n²)。

多 CPU：使用 EREW MST Algorithm.

多CPU的方法是將 nodes 均分成 N（# of processors）個部分，然後每
一個部分平行去做比較。其時間複雜度為 O(n^1+x)，其中 x 為 N=n^1-x
的 x。

測試環境：

單 CPU：IBM 26 及 SP2
多 CPU：IBM SP2 (MPI)

Input 為 1680 個 nodes 的圖形，以矩陣方式儲存圖形結構。

測試結果：

下列表格是在 SP2 下的結果：

# of processors	1	2	3	4	5	6	7	8
1680 個 vertices	0.264	0.148	0.093	0.07	0.058	0.05	0.041	0.036

測試時間是以 profile 取得的，因為用 time 所測的時間差異蠻大，有
很多變因。在做測試時因為每個 processor 的效能不一，而且在執行時
有別的 job 在 run 也會影響時間，所以只能取看起來認為可靠的數據。
由上面的數據以及圖形，我們可以看出效率是有提升，當 processor增加
的時候；在理論上，結果也是如此。因為在取數據時只取認為合理的，所
以看起來比較符合理論吧！

測試環境	IBM 26	IBM SP2
840 個 vertices	0.091	0.066
1680 個 vertices	0.360	0.264

由上表可看出在不同環境下，執行的效率已不同，這應該是取決於機器的
效能吧！

問題討論：

在做測試時，若使用 time去取時間，會發覺在多 CPU 版的時間會和
processor 個數成正比，因為程式在執行時是以讀檔方式讀入資料，
當資料量大時，會嚴重影響執行速度，這也是影響整體執行的時間；
還有在做 Broadcast 時，其他 processor 等待的時間也會影響整體
速度，因而降低效能的提升。

Source code

單CPU版： s_mst.c

多CPU版： m_mst.c