---
# System prepended metadata

title: Parallel Programming HW2

---

# 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後，執行速度都有顯著提升。如下圖
![](https://i.imgur.com/M3htybD.png)
![](https://i.imgur.com/Cbp94T5.png)
這些圖為從我的程式結果所繪出的圖，可以看出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]
:::