# Parallel Programing Homework #2
Author: 312551015 Sean Wei
Spec: https://pp-f23.github.io/assignments/HW2/
Due date: Tue, Nov 14, 23:59

## Question 1

> 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?
> (You may also wish to produce a graph for VIEW 2 to help you come up with a good answer.
> Hint: take a careful look at the three-thread data-point.)

In my experiment, the time spent among the serial and {2, 3, 4} threads can be represented by the following graph:


This clearly demonstrates that there is not a linear relationship, especially in the case of 3 threads, which exhibits significantly slower performance.

This can be explained by the visual graphic of this assignment:


The central part contains more white pixels than the top or bottom blocks, which may result in a longer iteration time.

## Question 2

> How do your measurements explain the speedup graph you previously created?

We examined the time taken in the 3-thread version. As measured, the top and bottom blocks each took 90 ms, while the central part took 280 ms.

Clearly, the central part has become the bottleneck of this parallel program.

In the 4-thread version, the times for the four blocks are {44 ms, 186 ms, 186 ms, 44 ms}, respectively. The central blocks take more time to render.

## Question 3

> describe your approach to parallelization and report the final 4-thread speedup obtained.

My approach involves counting the horizontal line interleaving. Since the graphic is somewhat continuous, this method helps balance the workload of each thread.

In my experiment, this approach achieved a 3.75x speedup for the 4-thread version. The speedup results for {2, 3, 4} threads can be represented in the chart below:


## Question 4

> Now run your improved code with eight threads.
> Is performance noticeably greater than when running with four threads? Why or why not?
> (Notice that the workstation server provides 4 cores 4 threads.)

No, on the provided 4C4T (4 cores, 4 threads) shared workstation, using 5 or more threads results in worse performance than using 4 threads, and especially 5 threads have the lowest speed.

This is primarily due to the fact that we are assigning 5 jobs to 4 cores. The scheduling overhead and uneven sharing of computing time may lead to a decrease in performance.


-----

## Raw Data

[mandelbrot serial]:    [459.500] ms

$ ./mandelbrot
[mandelbrot thread]:    [237.950] ms    (1.93x speedup from 2 threads)
$ ./mandelbrot -t 3
[mandelbrot thread]:    [283.200] ms    (1.62x speedup from 3 threads)
$ ./mandelbrot -t 4
[mandelbrot thread]:    [193.900] ms    (2.37x speedup from 4 threads)

$ ./mandelbrot -t 2
[mandelbrot thread]:    [236.700] ms    (1.94x speedup from 2 threads)
$ ./mandelbrot -t 3
[mandelbrot thread]:    [159.800] ms    (2.88x speedup from 3 threads)
$ ./mandelbrot -t 4
[mandelbrot thread]:    [122.500] ms    (3.75x speedup from 4 threads)

### View 2

[mandelbrot serial]:    [290.000] ms

$ ./mandelbrot -v 2
[mandelbrot thread]:    [174.000] ms    (1.66x speedup from 2 threads)
$ ./mandelbrot -v 2 -t 3
[mandelbrot thread]:    [132.000] ms    (2.18x speedup from 3 threads)
$ ./mandelbrot -v 2 -t 4
[mandelbrot thread]:    [111.000] ms    (2.60x speedup from 4 threads)

$ ./mandelbrot -v 2
[mandelbrot thread]:    [149.300] ms    (1.94x speedup from 2 threads)
$ ./mandelbrot -v 2 -t 3
[mandelbrot thread]:    [100.500] ms    (2.88x speedup from 3 threads)
$ ./mandelbrot -v 2 -t 4
[mandelbrot thread]:    [77.000] ms     (3.76x speedup from 4 threads)

### Draw the graph

pbpaste | gzip -9 | base64 | fold -w120
pbpaste | base64 -d | gzip -d | pbcopy; pbpaste

Q1.d3.js (modified from: https://plotdb.com/chart/2008/)

H4sIADv1TWUCA+1ZW2/bNhR+36/gtBdpURQ7bR+WLBjaDt0GtFuRDCuGwA+0RNtcZEmj6ERq6v++w4skUjfL7VrsYQ9NZfLo43d4rqQev0Iox9ssJhdotUtC
TtPE9dAjDCN0jxmKac7RFYqeBAwna+I+RSfoDeabgKW7JHLVI06idAuvfYueeF6wxZlbY0U+BTjECN+xBGVxyqNlEGGOA7VssGI7yoM14S71LtHeu5RLa3nF
A6EVDnnKLtDtY4K3QNV5JQccHwmoC8lyv/C1NN4CN25Iv0xzbsmOcRzRbj6bSY77hVxpL7juxaoR3ZIkB6wLTbki/Ih4mQGFW635DWc0WS98WOzvHWVi13Gc
E+BG8rDWCwnezl7pU2nThvp1t10SZkJxtmuQnsvXEE0Q39BcE3LQvqIcpsmKrmu+acJf4S2NSxjRCy9xeLeWG9GMcVLwVzSODam0uBYyCcnzZjTnLL0DSo8R
WeFdDPSdb2azmWNNv6MR35gy53oauCUk5DfjIJbUIFaSRuSGvrdg5tbk+CqNyOASGY4isGqj/RazNU2a32J3NQc9UjwvaP4aL4mxkxmOCeeGUPmarLgpqN1Z
DCMxjuQEeDZYhQgzOWUtXvEvr+l604cix6fDiJGbTfpg0BNDv9PwTqj2C9iCDcz9tuO9c2/b+1Yv8mO6xXID670Wvt1+/6UODHNckn6b5pSraLSQK0ubRrB1
6rNLMaJnMaJnMahnMUnPoq1nLTSzcPq06t0G+YcmlA/ker7BIteLfKGysHgK8vu1KgA5iSHcXDnI0pR7Ac4y8BfXARHHM16RFH6C1JFpOAFSS4NsgDln7mMY
Y5E0HCyccJMy+h4CBYPPmWB1FBwLeE8Yp2EHro6HfwcvSzOJIrPyk2DDt7EaMzcKNtqBfJyTbXpPINDM0uNLaa+udfJntdlOwCmPCRASmdeNApXHNYGO8D2O
d4awKh1QsR10hgoHHlyjukE1g5oWBXlGSAQMzkR508hKRekwGWY5OewxoEi+26q3z87U3qg6nzLe1FrsL41au6woniKsH5seQEJIja5F66GcUKYo7YQSfqSS
RwakxqQrtwV7O1+gq6v2YrezhYe6kicnBjWRR/PKfw5zUZZr1FulzKVXM7FrV7NL+n0DE5NkzTeX9OSk8QqQMpe6pYvGuvW+I1tAvVPP7qsd+BqGPI04NyPd
ltcED1Kz11TOBDhPn30XPENnfZxNPiqIMGW5MrB8bOzb+OGSitJ00A0hFhQ8PJjBrWLkeRy7DoMHCQ6RIv5rrSZfBUej3NV5wJF5AOLWEbEFDaHKq64jhATI
jmE58AwiSKeONMMh5aVI1l7AZOC7nslMLpJAxXCbRCqYdZKPZOojE7CdfwLRpeQuQHqHlI9pQgLdOln6y43/YhvQUV3w6qhe8ezTfljFkLIQThZiT/5zFlbc
OopKrkfZWMYEI7lsK6eVczEI7Xq1a6I0iYPXC1ENoD95GVNgey0qide88CC63uqV6gegqOdGbkNkP6kF619CUv2wWwqtv04hD6q1VvBQrrICNkO9dlEh62H9
xj0lDy/SAo5DM3/myxd9JbgI/kopWA45XiWcwT4Rdk+eQ3YK+bWwJOx58YZGf8I/x6h4mmB4A3WeVFV9GbxVrXmQi+EgZbBdOFZOpc5RgW7erS6oAhG9k/Wi
p3kFkez/3Kac1DPytP0Cjp65e2uuo44WvmmOU9QVWHTasaZFYQ9QGGGkoSHZuQbpegZ6MlFunWXKebp16nFohO7+EJUx7yMfi+7T2p6mKUUfPoggs0SrRnXg
lWraWl003F15q0330eC8bNUtPN2k90PqSeuFvF9UNuu1YHXys2Srwf6WOQAD6M2Tgx2pn6vY6hIQZwr0gyEbpKtVTiCgEeSUTlfdcVCRhDHr+CfEGOS9he2c
2i91dJ52Cfb5pX/IV1V7fgSxp1+GVnUImRhGzfZ2QimGGWckVOxT/+RwKcfDJe8Kd721N67KA3FVHh9X5VBcTQ6X5hQ31SCNX3UswsTUqEnsO5T/bdJvE+ug
bqSxeqJX+p3uKbpszGxWiw9nNPtgb65fz/TLT2RQyw9SUMXzQO2GRqZnAw5W9GqwRXtxfBFZYvbObOrarF2zv0wicaU1rb+sDteGj6g7Za//+ijnJYSnI+RO
V1LQsd3YQFArjME019WnYRrLjwMmVjPttTpR4+Qg7k3q3lwHgOIn+mznQurcjgG/FqRx3JKp7su7LaZhK2s5efiAo/cWWltH/ogxB/V8NPO1h26GC1lPwfPg
UOM5PV1xRPMsxuUFGmojnGWchncOkucTOJ11lWiF/ERF3KlB4Umlj2BfHse+lTGOon90pEplPpsuhjsZ/qz7pNqlm5X6e0d1H92zoDdm9uMXLI9dsGWpL7Di
oIoZhmxt3VbUX7vMyDe+OKCpunwqdPEpqMUQ6sjtmRUxK/ldcOD+U60kK41xi432VQj0MVJjdXpVP09l4Dl9kjLMdGhYlzjblGWbgVscjV6MMy+Gmeu7C6u0
VnPlOGpzSqgv603k6gJkIsTMk5nnMC4r7ExjfsKtZcrDMvVt1bybj0av5D6v2zRfbKe4Tuv77ke6T3ik/8h6B+OVw5ydG0qFh9ymOcu4zecb08A9KkKjcnb+
EZZr3RdbWvftvvVVfooBup/xPzaE59NscDtbTDJDcT4Rbz4Nr5wfYVZBssey5fkxGPNejF7j77/a/wOetQ9SDCQAAA==

## Acknowledge

The work is completed on pp2 server. (140.113.215.197:10002)

After writing the answer, the grammar was fixed by ChatGPT.