---
# System prepended metadata

title: <center>Parrallel Programming Hw2

---

# <center>Parrallel Programming Hw2
Assignment：https://nctu-sslab.github.io/PP-f20//HW2/#part1_requirements
0783404 黃揚
# Q1

一開始的作法如下。將總共需要計算的row數量```NumRows```平均分給每個thread並計算各自的起點跟終點即可。
```cpp
// 一開始的作法
int NumRows = (args->height) / (args->numThreads);
mandelbrotSerial(
            args->x0,
            args->y0,
            args->x1,
            args->y1,
            args->width,
            args->height,
            args->threadId*NumRows, // 從哪個row開始 
            NumRows, // 一次要算幾個row
            args->maxIterations,
            args->output
        );
```

以下觀察使用不同的thread數量，對於速度的影響狀況：
### View 1
- t = 2
![](https://i.imgur.com/UwkkjOS.png)


- t = 3
![](https://i.imgur.com/5lqHvS6.png)

- t = 4
![](https://i.imgur.com/bCE7vCA.png)
- graph
![](https://i.imgur.com/eqOjkzk.png)

### View 2
- t = 2
![](https://i.imgur.com/0zcG7XZ.png)
- t = 3
![](https://i.imgur.com/Z39MFnr.png)
- t = 4
![](https://i.imgur.com/HnrcRFB.png)
- graph
![](https://i.imgur.com/P85TTg6.png)


### Is speedup linear in the number of threads used?
- view 1：發現隨著thread數量上升，速度並不會跟著變快，3 threads反而比2 threads還慢，從1.95倍降到1.63倍。
- view 2：速度的確會隨著thread變多而上升


為了探究view 1為何會有這樣的現象，用```CycleTimer```把每個thread的所需時間計算並印出來如下。
- t=2
![\label{各個thread時間}](https://i.imgur.com/zwmzLGt.png)

- t=3
![](https://i.imgur.com/vDwiBAr.png)

- t=4
![](https://i.imgur.com/tbe8L82.png)

發現在t=2時，兩個thread的計算時間很平均，但是當thread是3或4的情況的時候，中間部分的thread花費時間都會比較高。於是推測會不會是每個row的計算時間其實不太一樣，可能靠近中間部分的計算是比較花時間的?接著觀察實際計算的的函式```mandel()```。發現在裡面的for loop中，有一個判斷條件
```cpp
if (z_re * z_re + z_im * z_im > 4.f)
      break;
```
觀察view 1跟view 2的圖片，也能發現view 1的計算量確實偏重於中間的部分，反觀view 2是較平均的
![](https://i.imgur.com/T0qUNaq.png) ![](https://i.imgur.com/ehCqvIr.png)


# Q2 
各個thread的時間已呈現在Q1中。到這邊可以確定，在不同的row的確會有不同的計算量。推測是在靠近中間的地方需要跑多次一點才能得到結果，所以在t=3, t=4的時候才會因為工作量分配不均而導致有些thread已經做完了，而其他thread還沒，所以會閒置等待。

舉例來說，在t=3的時候，如果把工作根據row數量平均切成3等分，則第一份跟第三份工作量會較輕，而第二份工作量最重，這也是為甚麼在t=3的時候，第二個thread花費的時間是283ms，而其他兩個thread只要93,94ms。
![](https://i.imgur.com/vDwiBAr.png)
# Q3
### describe your approach to parallelization
為了修正工作量不均的問題，用for loop讓每個thread都是跳動式的在計算。
- 原本的作法
舉例：用3個threads來計算1200個rows
    1. 計算每個thread要算幾個row->1200/3=400
    2. 分配工作：讓thread 0算0~399行，而thread 1算400~799行，thread 2算800~1199行。
- 改良後
    1. 計算每個thread要算幾個row->1200/3=400
    2. 以thread數量當作間隔去分配任務：thread 0負責算0,3,6,9...1197行，thread 1負責算1,4,7,10...1198行，thread 2負責算2,5,8,11...1199行
    3. 另外，因為有可能發生rows數量沒辦法被thread數量整除(例如t=7時)，所以在最後面有加一個處理剩餘行數的機制
    ```cpp
    // 修正後的做法 
    int NumRows = (args->height) / (args->numThreads); // 分工之後每個thread要算幾個rows
    for (int p=0; p< NumRows; p++){
        mandelbrotSerial(
            args->x0,
            args->y0,
            args->x1,
            args->y1,
            args->width,
            args->height,
            p * (args->numThreads) + args->threadId, // 從哪個row開始
            1, // 一次要算幾個row
            args->maxIterations,
            args->output
        );
    }
    // 如果不整除且目前是最後一個thread了，就把剩下的rows都交給他處理
    if (((args->height) % (args->numThreads) != 0) && (args->threadId == (args->numThreads-1))){
        int RowsLeft = ((args->height) % NumRows);
        mandelbrotSerial(
            args->x0,
            args->y0,
            args->x1,
            args->y1,
            args->width,
            args->height,
            NumRows * (args->numThreads), // 從哪個row開始
            RowsLeft, // 一次要算幾個row
            args->maxIterations,
            args->output
        );
    }
    ```
### report the final 4-thread speedup obtained.

# Q4
### view 1
- t = 2
![](https://i.imgur.com/dcOUp0q.png)
- t = 3
![](https://i.imgur.com/Ji671hZ.png)
- t = 4
![](https://i.imgur.com/DVaxYvK.png)
- graph
![](https://i.imgur.com/UL7yG61.png)

### view 2
- t = 2
![](https://i.imgur.com/BlcnPXw.png)
- t = 3
![](https://i.imgur.com/nt4JB6F.png)
- t = 4
![](https://i.imgur.com/rJlnuwx.png)
- graph
![](https://i.imgur.com/rf4uVv9.png)
在修改完分配任務的機制後，view 1跟view 2的速度在多個thread時都能有顯著提升

# Q4
### Is performance with 8 threads greater than with 4 threads?
- view 1
![](https://i.imgur.com/vkDNS4v.png)
t=4時速度是3.79x，反而還比t=8的3.73x快
- view 2
![](https://i.imgur.com/Ui9sPUc.png)
t=4時速度是3.79x，反而還比t=8的3.77x快
### Why?
由於工作站的CPU是4核心的，但是若我們使用8個thread去執行，反而會發生額外的context switch overhead的情形，因此要開幾個thread必須視cpu核心數量而定，若工作站是8核心的話，那使用t=8理論上就會比t=4還要快。