# Parallel Programming HW2 @ NCTU, Fall 2020
## Programming Assignment II: Multi-thread Programming
0857206 林以真

### Q1: 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?
幾乎是，在thread數目增加時，speedup接近線性成長，但是隨著thread數目增加，線性成長的speedup的幅度會些微下降，thread 1,2,3,4的speedup分別為1,1.95,2.9,3.78。因為在thread數目增加時，單一圖像計算量被切分為全部的(1/thread數目)的計算量，但是因為增加thread時所需要的OS內部時間，所以結果為接近線性成長。

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

隨著thread數目增加，單個thread執行時間變短。thread 1,2,3,4的平均單個thread執行時間分別為0.4597786, 0.2361373, 0.158515, 0.1216466。

2threads單個thread執行時間為 1thread單個thread執行時間的0.513589149倍，3threads單個thread執行時間為 1thread單個thread執行時間的0.344763762倍，4threads單個thread執行時間為 1thread單個thread執行時間的0.264576472倍，約等於(1/thread數目)倍的時間。


### Q3: In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained.
在workerThreadStart中，將height切為四塊做計算也就是下方程式1,speedup為X2.41。若改為下方程式2,也就是height 依序循環分配給thread 1234，則speedup為X3.78，有明顯提升。

程式1

int hi=args->height/num;
    int hi1=hi*(id+1);
    if  (id==num-1)hi1=args->height;
    for (int i=id*hi; i<hi1; i++) {
       mandelbrotSerial(args->x0, args->y0, args->x1, args->y1, args->width, args->height,
                     i,1, args->maxIterations, args->output);
    }

程式2

for (int i = args->threadId; i<(args->height); i = i+args->numThreads) {
    mandelbrotSerial(args->x0, args->y0, args->x1, args->y1, args->width, args->height,
                     i,1, args->maxIterations, args->output);
    }

### Q4: Now run your improved code with eight threads. Is performance noticeably greater than when running with four threads? Why or why not?

在使用程式1時，使用threads數量增加，speadup有提升，在thread number = 8時，speadup為3.47。但是在使用程式2時，使用threads數量增加，speadup沒有提升反而些微下降，在thread number = 8時，speadup為3.56。
程式1隨著thread number增加height切分越細，speadup增加，程式2則沒有，程式2隨著thread number增加反而增加OS的負擔，導致speadup些微下降。