課題 : Computing the Mandelbrot set
簡介
Mandelbrot set 是一個由複數的函數 g(z)=z^2 + c , 在一區間內 ,將
所有的點帶入 g 函數中作80次疊代 , 如果在疊代的過程中超過
2 , 則紀錄在超過時所疊代的次數 , 在將這些不同的值用顏色畫
出 , 如下圖是一個在區間(x,y)x = [ -2 , 1 ] , y = [ -1.1 , 1.1 ] 的圖 ,
且在 x 的區間取 698點 , 在 y 的區間取512點的圖形 .
演算法
單CPU的演算法 :
如同簡介所表示 , 將所取的每一點帶入計算 , 檢查其值大於 2
時疊代的次數 , 即可求得 .
Step 1 : 取得區間及所取的點數
Step 2 : 將每一點逐一帶入 g(z) = z^2 +c 中作疊代 , 並記錄疊代
次數
多CPU的演算法 :
將點平分給多顆CPU去計算 , 不過由於在每個點所要疊代的次
數不一定 , 如果分塊切割 , 很容易造成計算量不平均 , 但如果是
對附近的點作切割 , 則可使計算量較平均
Step 1 : 取得區間及所取的點數 , 並傳給每顆CPU .
Step 2 : 將所有的點排成一個array , 第 i 點就由 i mod p (CPU總
數)負責計算
Step 3 : 在將每顆CPU的資料分批寫入檔案(耗很多時間)
Source code :
單CPU : sp.c
多CPU : mp.c
計算時間
CPU數量 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
時間(秒) |
15.782 |
8.582 |
5.663 |
4.412 |
3.871 |
3.293 |
2.971 |
2.411 |
以上為取 698x512 點計算的時間
CPU數量 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
時間(秒) |
3.282 |
2.260 |
1.512 |
0.989 |
0.859 |
0.775 |
0.683 |
0.593 |
以上為取 349x256 點計算的時間
紅線代表取點698x512
藍線代表取點349x256
( ps : 以上的數據都沒有加上寫入檔案的時間)
結論
在一般情況之下 , N 顆CPU所計算的時間會是 1 顆的1/N倍 , 因
為上述的分割方法是很單純的分割 , 不需要太大的Broadcast時
間 , 不過由於每個點計算量有差 , 且可能差很大 , 所以也無法估
計單顆CPU所需要的時間 , 但是因為是用較有效的分割 , 所以在
時間上也差不多是 1 顆CPU時間的1/N .