HW2
===
###### tags: `Parallel Programming 2020`
# Q1
## view1
## view2

可以看到不管是在 view1 還是 view2 跑出來的 speedup 結果都不是線性的，
而且還可以觀察到在 view1 中，跑 3 個 threads 的時候還比跑 2 個 threads 的效率還要差

我一開始認爲會不會是對齊的問題，以爲是 3 threads 切的範圍沒有對齊，但是又看到 view2 的 3-thread 時間是正常的又否定了自己的想法。因此就想說可不可能是某個 thread 的工作量特別大拖慢了其他 threads。

# Q2
除了計算每個 thread 花的個別的時間之外，我還畫了圖表，就是測試在 $n$ 個 threads 底下，**每個 thread 需要做的計算量與時間畫成圖表**（假設是照 row 來切不同 thread 要計算的 range）

分成 view1 與 view2 兩種 （先計算次數，再時間）

### view1
這是 2-thread 的時候

這是 3-thread 的時候：

這是 4-thread 的時候

這是 200-thread 的時候（假設有 200 個 thread）

### view2

這是 2-thread 的時候

這是 3-thread 的時候：

這是 4-thread 的時候

這是 200-thread 的時候（假設有 200 個 thread）

### Conclusion
看完圖表就可以知道爲什麼 view1 中 3-thread 會特別的慢，
就是因爲第 2 個 thread 所需要的運算量遠大於其他兩個的運算量，而程式必須等第二個 thread 算完才能結束，所以就造成它拖慢整個程式的速度。

而在 view2 中，因爲都是第一個計算量特別大，所以不管是幾個 threads 都會讓第一個 thread 特別慢，因此 view2 的 3-thread 就看起來跟其他的點很協調（因爲 n-thread 都很慢）。

然後看 200 個 thread 的圖表，view 1 的個整個走向就是中間特別大，然後兩側特別小；view2 的走向就是一開始特別大，後來的都上上下下的。

可是我不知道這可不可以用函數圖形表示？因爲看起來有一點碎型重複的感覺

## Q3

## 最初
我的想法是說因爲中間的計算量總是特別大，所以要想辦法把中間的計算量分配給兩側的 thread ，實際上就是想辦法平均所有工作量。

但是不計算完全部的圖片，就不知道所有的工作量，所以我折衷，把工作量再繼續往更小切，然後再平均分配。

所以想法上就是維護一個 workqueue ，裏面裝了很多工作，讓每個 thread 都去拿某一段範圍來計算，如果算完了再往裡面拿。

## 後來
但是後來看到 spec 說不需要 synchronization 就能作到，就發現因為 view1 的圖是對稱的，所以可以把後半段反轉，然後覆蓋上去，但是這對 view2 完全沒轍。

所以我還是決定把工作量切成很小，但不用分配工作了，而是每個人拿固定間隔來計算。
例如 3-thread 切 9 份，第 1 個 thread 拿 0, 3, 6, 第二個拿 1, 4, 7, 第三個拿 2, 5, 8，這樣實測跑起來效果也很不錯。

但是究竟要把所有的工作量切成幾份呢？ 這裡我又跑了測試並畫圖

3-thread，view = 1, 測試切 2 * 3 ~ 64 * 3 = 6 ~ 192 份的時間：

4-thread, view = 1, 測試切 2 * 4 - 64 * 4 = 8 ~ 256 份的時間：

雖然看圖有點不明顯，但是看數據會發現在 120 chunks 都是在低谷，所以我選切成 120 塊

最後 4-thread 的結果 speedup 爲 **3.78x**

[mandelbrot serial]:            [456.384] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot thread]:            [120.692] ms
Wrote image file mandelbrot-thread.ppm
                                (3.78x speedup from 4 threads)

## Q4
在 PP 工作站 跑 8-thread 的結果 speedup 爲 **3.69x**
反而還比 4-thread 還慢，因爲工作站上只有 4 個 threads ，而 8 個實質上還是以 4 個 thread 在運行的，因此沒有變快，反而還多了一些 create 時的 overhead 所以變更慢。

[mandelbrot serial]:            [456.526] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot thread]:            [123.814] ms
Wrote image file mandelbrot-thread.ppm
                                (3.69x speedup from 8 threads)