# Programming Assignment II: Multi-thread Programming<font size=3>`109550039 楊富翔`</font>
##### Parallel Programming by Prof. Yi-Ping You @NYCU 2023,Fall

## Part1

### Execution time

109550039@pp7:~/HW2/HW2/part1$ time (./pi.out 3 100000000; ./pi.out 4 100000000)
Pi: 3.141453
Pi: 3.141560

real    0m0.519s
user    0m1.767s
sys     0m0.004s

## Part2

### Execution code

void workerThreadStart(WorkerArgs *const args)
{

    int height = args -> height / args -> numThreads;
    int startRow = height * (args -> threadId);
    mandelbrotSerial(
            args -> x0, args -> y0, 
            args -> x1, args -> y1, 
            args -> width, args -> height, 
            startRow, height, 
            args -> maxIterations, args -> output);
}

**I split the image into n region along the Y-axis.
Each thread copes with one sub-image like the following demonstration image.**


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

### 1. <font color=#008000 > Produce the speed up figure in View 1 and View 2. </font>

* **View 1**

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 2
[mandelbrot serial]:            [460.360] ms
[mandelbrot thread]:            [236.090] ms
                                (1.95x speedup from 2 threads)
                                                 
109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 3
[mandelbrot serial]:            [461.012] ms
[mandelbrot thread]:            [283.135] ms
                                (1.63x speedup from 3 threads)
                                
109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 4
[mandelbrot serial]:            [460.847] ms
[mandelbrot thread]:            [193.291] ms
                                (2.39x speedup from 4 threads)

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 5
[mandelbrot serial]:            [460.599] ms
[mandelbrot thread]:            [189.624] ms
                                (2.44x speedup from 5 threads)
                                

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 6
[mandelbrot serial]:            [460.843] ms
[mandelbrot thread]:            [148.733] ms
                                (3.10x speedup from 6 threads)

* **View 2**

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 2 -v 2
[mandelbrot serial]:            [290.244] ms
[mandelbrot thread]:            [173.165] ms
                                (1.68x speedup from 2 threads)
                                
109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 3 -v 2
[mandelbrot serial]:            [290.353] ms
[mandelbrot thread]:            [131.689] ms
                                (2.20x speedup from 3 threads)
                                
109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 4 -v 2
[mandelbrot serial]:            [290.450] ms
[mandelbrot thread]:            [110.665] ms
                                (2.62x speedup from 4 threads)

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 5 -v 2
[mandelbrot serial]:            [290.294] ms
[mandelbrot thread]:            [96.621] ms
                                (3.00x speedup from 5 threads)


109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 6 -v 2
[mandelbrot serial]:            [290.374] ms
[mandelbrot thread]:            [85.138] ms
                                (3.41x speedup from 6 threads)

### 2. <font color=#008000 > Compare with 2 line charts </font>

<center class="half">
<img src="https://hackmd.io/_uploads/rJjrBOcXT.png" alt="drawing" width="350"/>
<img src="https://hackmd.io/_uploads/ry3ZBuc7p.png" alt="drawing" width="350"/>
</center>

### 3. <font color=#008000 > Observation </font>
:::success
1. **In View 1, speedup is not linear in the number of threads.** Conversely, speedup decreases and hit a plateau when the number of threads are 3 and 5.
2. **In View 2, speedup is linear in the number of threads.**
:::

### 4. <font color=#008000 > Hypothesis </font>

:::warning

When we see the image, we can find the white pixels in View 1 are clustered in specific region, but they distribute evenly in View 2. Also, we can find light color needs more iterations to compute in code. As a result, I suggest that some threads are responsible for more white pixels, so they would spend more time on it.

**The pixel distribution is not equivalent, which causes that some thread would cope with more pixels.**
:::

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

### 1. <font color=#008000 >Compute the execution time in each thread</font>
|2 threads|3 threads|4 threads|5 threads|6 threads|
|---|---|---|---|---|
|<img src="https://hackmd.io/_uploads/HkNXPF9Xp.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/ByKIvY9Qa.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/S1EjLK97T.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/Hk75vK5X6.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/Hyy6Pt5mp.png" alt="drawing" width="120"/>|
|t 0 : 235.872 ms<br>t 1 : 236.397 ms<br>|t 0 : 93.219 ms<br>t 1 : 283.055 ms<br>t 2 : 93.853 ms|t 0 : 45.388 ms<br>t 1 : 192.433 ms<br>t 2 : 193.465 ms<br>t 3 : 45.878 ms|t 0 : 33.330 ms<br>t 1 : 122.878 ms<br>t 2 : 189.139 ms<br>t 3 : 123.187 ms<br>t 4 : 21.916 ms|t 0 : 12.742 ms<br>t 1 : 82.529 ms<br>t 2 : 145.539 ms<br>t 3 : 146.182 ms<br>t 4 : 86.487 ms<br>t 5 : 25.074 ms|
||||||
|t 0 : 173.368 ms<br>t 1 : 124.481 ms|t 0 : 132.036 ms<br>t 1 : 87.179 ms<br>t 2 : 79.928 ms|t 0 : 110.538 ms<br>t 1 : 66.155 ms<br>t 2 : 64.885 ms<br>t 3 : 61.324 ms|t 0 : 96.214 ms<br>t 1 : 77.227 ms<br>t 2 : 55.711 ms<br>t 3 : 50.078 ms<br>t 4 : 65.314 ms|t 0 : 85.111 ms<br>t 1 : 78.099 ms<br>t 2 : 65.299 ms<br>t 3 : 44.933 ms<br>t 4 : 65.068 ms<br>t 5 : 50.818 ms|

### 2. <font color=#008000 >Clonclusion</font>
:::success
**In View 1, the middle threads always take more time because of the light pixels. On the other hand, because the light pixels equally distribute in View 2, the threads spend roughly equivalent time.**
:::

## Q3: In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained.

### Execution code

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

Because light pixels are clustered together, so I split the image into smaller pieces. **Each thread would be responsible for 1 row.** After the end of thread, I distribute new row to first thread. Following figure demonstrate what I am talking about.


* ### <font color=#008000 >Compute the execution time in each thread</font>

|2 threads|3 threads|4 threads|5 threads|6 threads|
|---|---|---|---|---|
|<img src="https://hackmd.io/_uploads/HkNXPF9Xp.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/ByKIvY9Qa.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/S1EjLK97T.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/Hk75vK5X6.png" alt="drawing" width="120"/>|<img src="https://hackmd.io/_uploads/Hyy6Pt5mp.png" alt="drawing" width="120"/>|
|t 0 : 234.891 ms<br>t 1 : 236.213 ms<br>|t 0 : 158.798 ms<br>t 1 : 159.235 ms<br>t 2 : 158.820 ms|t 0 : 120.948 ms<br>t 1 : 120.821 ms<br>t 2 : 120.988 ms<br>t 3 : 121.603 ms|t 0 : 143.729 ms<br>t 1 : 96.719 ms<br>t 2 : 97.622 ms<br>t 3 : 97.041 ms<br>t 4 : 135.771 ms|t 0 : 129.804 ms<br>t 1 : 80.821 ms<br>t 2 : 80.555 ms<br>t 3 : 80.701 ms<br>t 4 : 116.355 ms<br>t 5 : 127.804 ms|
||||||
|t 0 : 148.404 ms<br>t 1 : 148.451 ms|t 0 : 100.442 ms<br>t 1 : 100.542 ms<br>t 2 : 100.334 ms|t 0 : 76.338 ms<br>t 1 : 76.563 ms<br>t 2 : 76.210 ms<br>t 3 : 76.147 ms|t 0 : 84.344 ms<br>t 1 : 61.299 ms<br>t 2 : 60.937 ms<br>t 3 : 61.064 ms<br>t 4 : 86.382 ms|t 0 : 78.769 ms<br>t 1 : 50.892 ms<br>t 2 : 50.873 ms<br>t 3 : 57.868 ms<br>t 4 : 68.840 ms<br>t 5 : 79.077 ms|

* ### <font color=#008000 >Performance</font>
:::success
In this approach, the difference in max spending time and min spending time is smaller than first approach. Moreover, **the performance are better in both View 1 and View 2**.
:::

<center class="half">
<img src="https://hackmd.io/_uploads/SJo_1sqX6.png" alt="drawing" width="350"/>
<img src="https://hackmd.io/_uploads/H1WMys576.png" alt="drawing" width="350"/>
</center>

:::warning
The performance decrease in thread 5 and 6 is relartive to Q4.
Because the server only has 4 core, it can only parallelize for 4 threads at the same time. Extra threads won't improve performance.
:::

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

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 4
[mandelbrot serial]:            [460.708] ms
[mandelbrot thread]:            [121.570] ms
                                (3.79x speedup from 4 threads)
                                

109550039@pp7:~/HW2/HW2/part2$ ./mandelbrot -t 8
[mandelbrot serial]:            [460.600] ms
[mandelbrot thread]:            [124.621] ms
                                (3.70x speedup from 8 threads)

:::success
**As I mentioned aboved,the workstation has 4 cores and 4 threads, meaning that at any given time, only 4 threads can operate simultaneously. Therefore, even if there are 8 threads, only 4 can run concurrently, and the presence of 8 threads also introduces "context switch overhead", which results in slightly worse performance compared to having just 4 threads.**
:::