# 2021 Parallel Programming HW2
309706008 李欣盈
### <font color="#0073FF"></font>

All plots available at: [PP HW2](https://docs.google.com/spreadsheets/d/10RDkF99o2d82xOlyK9vr0hqzayxay4UyOgTAPRL1lsI/edit?usp=sharing)

## <font color="#0073FF"> Q1 </font>
### <font color="#0073FF">Produce a graph of speedup compared to the reference sequential implementation as a function of the number of threads used for VIEW 1 and VIEW 2. </font>

The following figures are speedup and execution time based on different number of threads for view 1 and 2.

### View 1

mandelbrot serial

[mandelbrot serial]: [462.395] ms
Wrote image file mandelbrot-serial.ppm

thread = 2

[mandelbrot thread]: [236.736] ms
Wrote image file mandelbrot-thread.ppm
(1.95x speedup from 2 threads)
thread = 3

[mandelbrot thread]: [283.566] ms
Wrote image file mandelbrot-thread.ppm
(1.63x speedup from 3 threads)
thread = 4

[mandelbrot thread]: [194.707] ms
Wrote image file mandelbrot-thread.ppm
(2.38x speedup from 4 threads)
thread = 8

[mandelbrot thread]: [141.096] ms
Wrote image file mandelbrot-thread.ppm
(3.27x speedup from 8 threads)
thread = 16

[mandelbrot thread]: [127.580] ms
Wrote image file mandelbrot-thread.ppm
(3.62x speedup from 16 threads)

### View 2

mandelbrot serial

[mandelbrot serial]: [288.883] ms
Wrote image file mandelbrot-serial.ppm
thread = 2

[mandelbrot thread]: [172.775] ms
Wrote image file mandelbrot-thread.ppm
(1.67x speedup from 2 threads)
thread = 3

[mandelbrot thread]: [131.590] ms
Wrote image file mandelbrot-thread.ppm
(2.19x speedup from 3 threads)
thread = 4

[mandelbrot thread]: [111.025] ms
Wrote image file mandelbrot-thread.ppm
(2.60x speedup from 4 threads)

thread = 8

[mandelbrot thread]: [79.017] ms
Wrote image file mandelbrot-thread.ppm
(3.66x speedup from 8 threads)

thread = 16

[mandelbrot thread]: [77.061] ms
Wrote image file mandelbrot-thread.ppm
(3.75x speedup from 16 threads)

### <font color="#0073FF">Is speedup linear in the number of threads used? </font>
The speedup for **view 1 is not linear**. We can see that there is a decrease in speedup when number of threads is 3.
The speedup for view 2, however, seems to be linear.

### <font color="#0073FF">In your writeup hypothesize why this is (or is not) the case?</font>
Because of the different speedup behavior of view 1 and 2, we could possibly deduce that it could be related to **different pattern of the picture**.
We can see that, in view 1, there're more white pixels and the position of those white pixels are more close to each other.


According to the explanation of [drawing the Mandelbrot set](https://jonisalonen.com/2013/lets-draw-the-mandelbrot-set/).

> Plotting the Mandelbrot set is easy: map each pixel on the screen to a complex number, check if it belongs to the set by iterating the formula, and color the pixel black if it does and white if it doesn’t. Since the iteration may never end we set a maximum

In our code, the `mandel` function will decide the color of a pixel. The `count` is equal to `maxIterations`, which is 256. The calculation inside the for loop shown below will be executed ranging from 0-255 times.

0 represents black and 255 represents white. If a pixel shoud be painted white, the for loop will be executed more times as compare to a black pixel.


Due to the use of spatial decomposition, **the execution time of region with more white pixels could be higher**. This could possibly be related to the non-linear speedup behavior of view 1 using 3 threads. The middle part of the view 1 contains lots of white pixels and tasks are not equally divided to all 3 threads. The execution time of one of the thread will be higher, which results in the overall degraded speedup.

## <font color="#0073FF"> Q2 </font>
### <font color="#0073FF">Measure the amount of time each thread requires to complete its work. </font>
### View 1
We noticed a degraded speedup when thread number is 3. We stated that this could be related to different workload each thread has. If the area a thread need to compute includes more white pixels, the execution time could be higher.
We measure the time taken for each thread using `CycleTimer.h`. The following section shows execution time of each thread when thread number is 2, 3, 4 respectively. The computation regions each thread got are show in the tables.

#### 2 Threads
* Workload of two threads are equal. Execution time of each thread are basically the same.
* Thus, reached approximately 2x (1.95x) speedup.


Computation area of each thread

| Thread 0 | Thread 1 |
| -------- | -------- |
|||

#### 3 Threads
* The area thread 1 needed to compute has way more white pixels as compared to the other 2 threads. Therefore, the execution time of thread 1 is a lot higher than the other two threads.
* Due to the slow execution of thread 1, a declined speedup(1.63x) is noticed as compared to thread number is 2.


Computation area of each thread
| Thread 0 | Thread 1 | Thread 2 |
| -------- | -------- | -------- |
|||

#### 4 Threads
* The area thread 1 and 2 needed to compute has way more white pixels as cmopared to the other 2 threads. Therefore, thread 1 and 2 takes more time as compared to thread 0 and 3.
* The area comtaining more white pixels are equally divided to thread 1 and 2. Two threads collaborated to increase the program performance. Therefore, the speedup (2.38x) is higher compared to thread number is 2 and 3.


Computation area of each thread

| Thread 0 | Thread 1 | Thread 2 | Thread 3 |
| -------- | -------- | -------- | -------- |
|||||

### <font color="#0073FF"> How do your measurements explain the speedup graph you previously created? </font>

Through our experiment, we can conclude that the execution time of each thread is highly related to the ratio of white area it need to compute. In the 3 thread scenario, thread 1 need to compute areas with higher workload (more white pixels), resulting in degraded speedup.
So we can divided those high white/black ratio rows to each thread to increase the speedup.

### View 2
We further prove our idea through experiment with view 2.
We tried to divided view 2 into four segments. The top region contains more white areas as compared to all the other 3.

* Thread 0 received the top area, thus, has higher execution time.

Computation area of each thread

| Thread 0 | Thread 1 | Thread 2 | Thread 3 |
| -------- | -------- | -------- | -------- |
||||

## <font color="#0073FF"> Q3 </font>
### <font color="#0073FF">Resort to decomposition policy. In your write-up, describe your approach to parallelization</font>

We can divided those high white/black ratio rows to each thread to increase the speedup.


In our improved version, the first row each thread needed to compute is its own thread ID, e.g. thread 0 starts from row 0, thread 2 starts from row 2. The following row each thread need to compute is (last computed row + number of threads).

For example, there are 3 threads, thread 0 need to compute row 0, 3(0+3), 6(3+3).... We may refer to the figure below for the visualization of this approach.


We can assume that there are 10 rows.
* Thread 0 is responsible for row [0, 3, 6, 9]
* Thread 1 is responsible for row [1, 4, 7]
* Thread 2 is responsible for row [2, 5, 8]

So instead of dividing the whole picture into 3 sections(as shown below) in the previous approach, we are able to **distribute the middle part of the graph(contains lots of white pixels, higher workload) to different threads**. Through this decoupled task distrubution, we can increase the performance of our calculation.


### <font color="#0073FF">Report the final 4-thread speedup obtained </font>

### View 1
3.79x speedup from 4 threads

[mandelbrot thread]:            [122.095] ms
Wrote image file mandelbrot-thread.ppm
                                (3.79x speedup from 4 threads)

Compared with the previous implementation(Spatial Decomposition)

A: Spatial Decomposition
B: Improved Decomposition Policy

### View 2
3.77x speedup from 4 threads

[mandelbrot thread]:            [76.626] ms
Wrote image file mandelbrot-thread.ppm
                                (3.77x speedup from 4 threads)

Compared with the previous implementation(Spatial Decomposition)

A: Spatial Decomposition
B: Improved Decomposition Policy

Through comparison with the previous implementation (Spatial Decomposition/Block Partition), we see that we are able to achieve near-linear speedup performance using the improved decomposition policy(red line B).

## <font color="#0073FF"> Q4 </font>
### <font color="#0073FF">Now run your improved code with eight threads. Is performance noticeably greater than when running with four threads?</font>

The performance is **a bit degraded** when using 8 threads for both view 1 and view 2.
### View 1
3.79x speedup from 4 threads
3.71x speedup from 8 threads

[mandelbrot thread]:            [124.697] ms
Wrote image file mandelbrot-thread.ppm
                                (3.71x speedup from 8 threads)

### View 2
3.77x speedup from 4 threads
3.70x speedup from 8 threads

[mandelbrot thread]:            [78.258] ms
Wrote image file mandelbrot-thread.ppm
                                (3.70x speedup from 8 threads)

### <font color="#0073FF">Why or why not? (Notice that the workstation server provides 4 cores 4 threads.)
</font>

The 8 thread speedup is not noticeably greater than that of 4 thread speedup because the workstation server has only 4 cores.

If we `lscpu`, we see that the server has 1 CPU sockets, each CPU has, up to 4 cores and each core has 1 threads. The max thread count is, 1 CPU x 4 cores x 1 threads per core, 4.


Attempting to create more than 4 threads may introduce **context switch overhead**. Each task switch takes a certain amount of time for the CPU to change the process environment. This may reduce the speedup, resulting in higher execution time as compared to using only 4 threads.

:::info
Excellent! You are the god of reports.
Keep going in the future. 💪💪💪
>[name=TA]
:::