Parallel Programing Homework #2

# 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: ![Fig 1. split into N blocks](https://hackmd.io/_uploads/ByNtHa07T.png) 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: ![Fig 2. split Mandelbrot into 3 blocks](https://hackmd.io/_uploads/ry-GOqnX6.png) 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: ![Fig 3. interleaving method](https://hackmd.io/_uploads/H1jfS6Rma.png) ## 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. ![Fig 4. using more than 4 threads](https://hackmd.io/_uploads/r12qhTRm6.png) ----- ## 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 ```bash 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.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.