# Parallel Programming HW2
## Question 1
(1)In your write-up, produce a graph of speedup compared to the reference sequential implementation as a function of the number of threads used FOR VIEW 1.

【ANS】
Serial Programming的時間消耗為873.024，使用Parallel Programming後，執行速度都有顯著提升。如下圖
這些圖為從我的程式結果所繪出的圖，可以看出Speed和Thread並非線性關係。

(2)Is speedup linear in the number of threads used?
(3)In your writeup hypothesize why this is (or is not) the case? (You may also wish to produce a graph for VIEW 2 to help you come up with a good answer. Hint: take a careful look at the three-thread data-point.)

【ANS】
(1)
(2) Speedup並非是Thread的線性函數。
(3) 原因是使用平行化，其中可能會產生overhead，造成程式的額外成本，因此會使平行化的加速所小，進而使Speedup並非是Thread的線性函數。

:::info
The main reason is not this. Take more careful look at the view1 or the mandelbrot set computation code. You can understand why 3 threads runs slower than 2 threads.(HINT: the "white" part of the picture does not uniformly distribute in the view1)
>[name=TA]
:::

## Question 2
How do your measurements explain the speedup graph you previously created?

【ANS】
| Thread | 耗費時間 | Speedup |
| ------ | -------- | -------- |
| 2 | 448.363 | 1.94x |
| 3 | 525.496 | 1.65x |
| 4 | 361.880 | 2.40x |
| 5 | 390.814 | 2.22x |
| 6 | 307.504 | 2.90x |
| 7 | 279.208 | 3.11x |
| 8 | 254.545 | 3.41x |
| 9 | 256.188 | 3.39x |
| 10 | 260.901 | 3.33x |
| 11 | 294.983 | 3.03x |
| 12 | 294.912 | 3.02x |
| 13 | 246.649 | 3.52x |
| 14 | 278.867 | 3.20x |
| 15 | 281.861 | 3.16x |
| 16 | 235.293 | 3.68x |

每一次的耗費時間跟Speedup會因為電腦本身的記憶體或硬體狀況等，而使結果不一致，因此上表僅是提供執行一次的結果。

而從上表中可得知，Speedup確實不是Thread的線性函數，且隨著Thread上升，Speedup有明顯的upper bound狀況(upper bound就是linear in number of thread used)。跟上一題的結果相符合

:::info
I think you misunderstood the question. We asked you to measure the execution time of each thread when ThreadNum = 3 or 4, not the execution time of different number of threads.
>[name=TA]
:::

## Question 3
In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained.

【ANS】
先計算出平均每個Thread要計算的Height有多少以及未分配到Thread的Height餘數，將Height餘數部分分配給部分Thread去平行運算，以此達到平行化。
例如：Height為75，然後有7個Thread。我會把75先拆分成每個Thread各10 Heiight去計算，剩餘的5 Height，在分配給7個Thread中的5個Thread去執行。
| Thread | 耗費時間 | Speedup |
| -------- | -------- | -------- |
| 13 | 246.649 | 3.52x |
| 14 | 278.867 | 3.20x |
| 15 | 281.861 | 3.16x |
| 16 | 235.293 | 3.68x |

:::info
In my opinion, this method doesn't solve the problem that the speedup is not linear when number of threads grows from 2 to 4 in view 1. (HINT: cyclic partition)
>[name=TA]
:::

## Question 4
Now run your improved code with eight threads. Is performance noticeably greater than when running with four threads? Why or why not? (Notice that the workstation server provides 4 cores 4 threads.)

【ANS】
結果如下圖：
| Thread | 耗費時間 | Speedup |
| ------ | -------- | ------- |
| 4 | 361.880 | 2.40x |
| 8 | 254.545 | 3.41x |
可以看出8 Thread確實有明顯比4 Thread執行速度更快的現象

:::info
If your improved code was implemented properly, your 4 threads version should also have speedup close to 3.5-4x.
>[name=TA]
:::