# HW2
## Part1：Parallel Counting PI Using Pthreads

### 1.Correctness:
不使用平行化計算出pi的值，精準度有在小數點三位數以上


當我們提高thread從1到2時可以看到運行速度確實有提升


### 2.Scalability
由上圖可以看到不同thread都可以順利運行
### 3.Performance
效能的部分可以看到我們的運行速度會隨著我們的thread越高而有一個先減少時間，隨後增加時間的一個趨勢，那原因是因為我們在平行的過程之中，需要把計算好的pi值存進pi變數裏頭，導致又讀又寫，那這麼一來就會造成race condition，而我們現在就是要避免此類問題，所以可以使用busy wait 或者是mutex的方式去避免race condition 發生，但因為在使用上述兩種方法的同時，我們都會損失一點效能，所以才會導致thread越多時間反而有增多的趨勢，但也可能是因為我們的計算問題是比較簡單的，當計算複雜度提升，此類的做法就可以有效避免race condition 且在thread增加時也會降低運算時間。
### 小結
為了避免race condition而使用上述方法，會在thread越多時增加越多時間，所以使用平行化後並非所有問題運算時間都會降低，主要還是得衡量計算複雜度是否可以透過平行化降低運算時間。

## Part 2: Parallel Fractal Generation Using std::thread

### Q1: In your write-up, produce a graph of speedup compared to the rference sequential implementation as a function of the number of threads used FOR VIEW 1.

由上圖可以看到加速幅度與thread之間，並非是線性相關。

### Q2: How do your measurements explain the speedup graph you previously created?

| Thread | Speed Up | time (ms) |
| ------ | -------- | -------- |
| 1 | - |867.709 |
| 2 | 1.94x|446.780 |
| 3 | 1.66x|524.378 |
| 4 | 2.42x| 358.731 |
| 5 | 2.49x|348.959 |
| 6 | 3.08x|282.540 |
| 8 | 3.43x| 252.725|
| 16 | 3.62x | 239.541 |

由上述表格可以看到，照理來說加速的速度會隨著thread越多而加倍增加，但是因為會有overhead的問題所以當overhead的問題造成時間增加比不上thread的增加而貢獻的加速時就會降低加速的速度，由thread3可以看到overhead所導致的降低時間大於thread增加所貢獻的速度，就會導致加速下降，所以可以知道，加速與thread之間並非是一個線性關係，與Q1的圖片所示符合。

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

當所有data可以被thread平均分配時就將所有的data平均分配到各個thread裏頭，但有些時候會有例外比如有100個data但無法被7平均分配，就看餘數是多少
將其在平均分配到各個thread裏頭去，如上述例子就可以知道，每個thread原本只有14個值，但有兩個未被分配到，所以放到thread1、2裏頭，就會使thread1、2變成有15個值剩餘的依然是14個值，當資料平行好後，再去進行各個thread的計算，最後在把他們join起來，就會完成所有計算了。
下表就運用2~4個thread所進行的加速以及耗時統計表。

| Thread | Speed Up | time (ms) |
| ------ | -------- | --------- |
| 2 | 1.94x | 446.780 |
| 3 | 1.66x | 524.378 |
| 4 | 2.42x | 358.731 |

### Q4: 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.)

| Thread | Speed Up | time (ms) |
| ------ | -------- | --------- |
| 4 | 2.42x | 358.731 |
| 8 | 3.43x| 252.725|

上述表為4個thread以及8個thread所做出來的表現差異，可以看到透過增加平行的數量，確實可以增加運算性能，原因是因為thread越多可以平行計算的程度就越大，但當然有時候也會出現thread越多反而降低運算性能的情形，原因就是因為有overhead的情形出現，而此情形所造成的降低效能幅度大於增加thread所貢獻的提升效能幅度，就會使整題speed up 比相對少thread時的速度低。