---
# System prepended metadata

title: Parallel Programming HW2
tags: [Parallel Programming]

---

###### tags: `Parallel Programming`
# Parallel Programming HW2

## 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? (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.) Method: Threads is getting block of image
Ans: No, dividing the image blocks equally between threads will cause imbalance computation load between threads. Comparing the image of VIEW1 and VIEW2, VIEW2 has more equal computation load than VIEW1. Look at the picture example: VIEW1 has a clear different picture slices load compare to VIEW2.
Picture 1: how pictures is sliced for each thread.
![](https://i.imgur.com/ccjCsRi.png)
Picture 2: performance graph.
![VIEW1 VIEW2 Performance Graph](https://i.imgur.com/UGlTRDN.png)

## Q2: How do your measurements explain the speedup graph you previously created?
Ans:
The result of running parallel Mandelbrot computation using 3 thread:
| Thread Number | View1 Average Time | View2 Average Time |
| ------------- | ------------------ | ------------------ |
| 1             | 93.220 ms          | 124.592 ms         |
| 2             | 283.238 ms         | 79.627 ms          |
| 3             | 93.959 ms          | 74.483 ms          |
The time needed for each thread to compute is heavily loaded in thread#2. By using the picture in Question1's answer as reference, the graph clearly shows the imbalance computation loading for each thread.

## Q3: In your write-up, describe your approach to parallelization and report the final 4-thread speedup obtained.
Ans: The idea is to equally divide the computation loading for each thread.
Below is the illustration of the division of work using 4 threads.
Original: picture is divided into 4 big chunks.
| --------1-------- | --------2-------- | --------3-------- | --------4-------- |
| ----------------- | ----------------- | ----------------- | ----------------- |
New method: Picture is splitted into more smaller pieces and equally distribute between threads.
|1|2|3|4|1|2|3|4|1|2|3|4|1|2|3|4|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
The average computation time of each threads using 4 threads. 3.79x speedup compare to serial.
| Thread Number | View1 Average Time | View2 Average Time |
| ------------- | ------------------ | ------------------ |
| 1             | 121.426 ms         | 71.539 ms          |
| 2             | 121.378 ms         | 71.456 ms          |
| 3             | 121.293 ms         | 71.332 ms          |
| 4             | 121.220 ms         | 71.242 ms          |

## Q4: 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.)
Ans: No. Running on 8 threads performance: 3.78x~3.79x. It is because workstation server's cores only have 4 threads, it is unable to fully utilize 8 threads yet it can also suffer from context switching.