---
# System prepended metadata

title: Parallel Programming HW-2

---

# Parallel Programming HW-2

:::info
<font color=#4381FA>***Q1***</font>: 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**. Is speedup linear in the number of threads used? In your writeup hypothesize why this is (or is not) the case?
:::
:::success
(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.)
:::

|                     **View 1**                     |
|:--------------------------------------------------:|
|      ![View 1](https://imgur.com/1mAPAjx.png)      |
|                     **View 2**                     |
|      ![View 2](https://imgur.com/9bGe9Ch.png)      |
|                **Speed up compare**                |
| ![Speed up compare](https://imgur.com/CJZCBMR.png) |

* **Is speedup linear in the number of threads used?**
    View 1 : nonlinear.
    View 2 : linear.
* **In your writeup hypothesize why this is (or is not) the case?**
    照理來說，我們 speedup 應該要隨著 threads 數的增加而提升，但在 view 1、threads 數為 3 時我們可以看到他的 speed up 甚至比 threads 數為 2 時還低，因此我們可以很合理的推斷，有可能是因為每個thread 的 workload 不平衡所導致．


:::info
<font color=#4381FA>***Q2***</font>: How do your measurements explain the speedup graph you previously created?
:::

|View 1|View 2|
|:---:|:---:|
|![View 1](https://imgur.com/3zYNCtQ.png)|![View 2](https://imgur.com/0QBvn4o.png)|
* **How do your measurements explain the speedup graph you previously created?**
    在觀看上方的曲線圖及 View 1 和 View 2的圖，我們可以合理推斷以下．

    View 1 : 在 threads 數為 3 時，效能提升下降的較為明顯，甚至比 threads 數為 2 時還低．   
    
    當 threads 數為 2 時，我們依 **spatial decomposition** 的策略將上半及下半交由兩個不同的 theread 執行，可以看到圖片中的兩部分是對稱的，因此 1.95 的 speed up 算是合理的 (扣掉 threads 的調用及溝通的成本)．
    
    
    而在 threads 數為 3 時，我們會將其拆成上、中、下三個部分，由此便可以很直覺的感受到， speed up 的下降是因為 workloads 不平衡所導致的．
    
    View 2 : 我們觀察到在 view 2 中幾乎是 linear 的關係，接著看圖片也可得知，並沒有哪個 thraed 會得到特別多的 workloads (白色部分似乎會需要特別多的計算)，因此 speed up 有隨著 threads 數而增加．

:::info
<font color=#4381FA>***Q3***</font>: In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained.
:::
* **In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained**
    我們需要改變我們的策略，不行粗暴的直接將某一個區塊交給某個 thread 做，這樣比較有機會造成不平均的分配．

    因此，我們可以將分配改成如下方法．每個 thread 將自己的 threadID 作為起頭，並將整體 threads的數量作為 step（需處理餘數的問題）。這樣就可以較平均的分配．

    thread 0 : 0 4 8  ...
    thread 1 : 1 5 9 ...
    thread 2 : 2 6 10 ...
    thread 3 : 3 7 11 ...


|                **Speed up compare**                |
|:--------------------------------------------------:|
| ![Speed up compare](https://imgur.com/LYOFqb3.png) |

由上圖我們可以觀察到，兩者的speed up 幾乎一樣，也符合 threads 數上升的關係．

:::info
<font color=#4381FA>***Q4***</font>: Now run your improved code with eight threads. Is performance noticeably greater than when running with four threads? Why or why not? 
:::

:::success
(Notice that the workstation server provides 4 cores 4 threads.)
:::
![Speed up compare](https://imgur.com/kaGu2qB.png)

由上圖可知，我們並沒有隨著提高 threads 的數量而得到更多 speedup．合理的解釋是因為 server 的 CPU 是 4 cores 4 threads ，因此，高於 4 個 threads 我們便無法全部的分配下去．需要等待前一個所執行完．我們也可以得知，在此 CPU 上最佳的數量是採用 4 個 threads ，這樣我們也可以減少 CPU threads 在切換時所造成的成本．
