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

一開始的作法如下。將總共需要計算的row數量```NumRows```平均分給每個thread並計算各自的起點跟終點即可。

// 一開始的作法
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

- t = 3

- t = 4
- graph

### View 2
- t = 2
- t = 3
- t = 4
- graph

### 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

- t=3

- t=4

發現在t=2時，兩個thread的計算時間很平均，但是當thread是3或4的情況的時候，中間部分的thread花費時間都會比較高。於是推測會不會是每個row的計算時間其實不太一樣，可能靠近中間部分的計算是比較花時間的?接著觀察實際計算的的函式```mandel()```。發現在裡面的for loop中，有一個判斷條件

if (z_re * z_re + z_im * z_im > 4.f)
      break;

觀察view 1跟view 2的圖片，也能發現view 1的計算量確實偏重於中間的部分，反觀view 2是較平均的
 

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

舉例來說，在t=3的時候，如果把工作根據row數量平均切成3等分，則第一份跟第三份工作量會較輕，而第二份工作量最重，這也是為甚麼在t=3的時候，第二個thread花費的時間是283ms，而其他兩個thread只要93,94ms。
# 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時)，所以在最後面有加一個處理剩餘行數的機制

    // 修正後的做法 
    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
- t = 3
- t = 4
- graph

### view 2
- t = 2
- t = 3
- t = 4
- graph
在修改完分配任務的機制後，view 1跟view 2的速度在多個thread時都能有顯著提升

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