NTHU- Homework 2: Mandelbrot Set Solved

GOAL
In this assignment, you are asked to parallelize the sequential Mandelbrot Set program, and learn the following skills:

Get familiar with thread programming using Pthread and OpenMP.
Combine process and thread to implement a hybrid parallelism solution .
Understand the importance of load balance.
2 PROBLEM DESCRIPTION
The Mandelbrot Set is a set of complex numbers that are quasi-stable when computed by iterating the function:

                                                                           𝑍𝑘 = 𝐶,               𝑘 = 0

𝑍𝑘 = 𝑍𝑘−12 + 𝐶, 𝑘 ≥ 1 ● C is some complex number: 𝐶 = 𝑎 + 𝑏𝑖 ● 𝑍 is the 𝑘𝑡ℎ iteration of the complex number ● if𝑘 for any , belongs to the Mandelbrot Set

                              𝑍 ≤ 2                𝑘 𝐶

What exact is the Mandelbrot Set?

It is fractal: An object that display self-similarity at various scale; magnifying a fractal reveals small-scale details similar to the larger-scale characteristics
After plotting the Mandelbrot Set determined by thousands of iterations:
For more information, please refer to lecture notes.

3 INPUT / OUTPUT FORMAT
3.1 Input specification
The input parameters are specified from the command line. There are no input files. Your programs should accept the following srun command:

srun -n $procs -c $t ./exe $out $iter $x0 $x1 $y0 $y1 $w $h

For example, the image in Sec.2 is created by:

srun -n1 -c1 ./hw2seq out.png 10000 -2 2 -2 2 800 800

The meanings of the arguments are:

$procs – int; [1, 48]; number of processes. Always 1 for the Pthread version.
$t – int; [1, 12]; number of threads per process. (technically, this is the number of CPUs you can use per process; you are allowed to use more or fewer threads) $out – string; the path to the output file.
$iter – int; [1, 2×108]; number of iterations. (the largest int is around 2.1×109) $x0 – double; [-10, 10]; inclusive bound of the real axis.
$x1 – double; [-10, 10]; non-inclusive bound of the real axis.
$y0 – double; [-10, 10]; inclusive bound of the imaginary axis.
$y1 – double; [-10, 10]; non-inclusive bound of the imaginary axis.
$w – int; [1, 16000]; number of points in the x-axis for output.
$h – int; [1, 16000]; number of points in the y-axis for output.
3.2    Output specification
Your programs should produce a PNG image at $out, visualizing the Mandelbrot Set in the given range.

We provide a sequential version to show how the pixels are rendered.

Example 1: srun ./exe $out $iter -2 2 -2 2 400 400

x axis:[-2 2), 400 pints = {-2, -1.99, -1.98, … 1.98, 1.99}

Example 2: srun ./exe $out $iter 0 2 -2 2 800 400

4 WORKING ITEMS
In this assignment, you are asked to parallelize the sequential Mandelbrot Set program by implementing the following two versions:

pthread: Single node shared memory programming using Pthread This program only needs to be run on a single node.
hybrid: Multi-node hybrid parallelism programming using MPI + OpenMP This program must be run across multiple nodes.MPI processes are used to balance tasks among nodes, and OpenMP threads are used to perform computations.
Pthread library could   also     be        used    to         create additional       threads           for communications.
Requirements:

Must follow the input/output file format and execution command line arguments specifications described in Section 3.
No mathematical optimization is permitted. That means the computations must be performed on each and every pixel.
5 REPORT
Your report must contain the following contents, and you can add more as you like.

1.         Title, name, student ID 2.  Implementation
Explain your implementations, especially in the following aspects:

How you implement each of requested versions, especially for the hybrid parallelism.
How do you partition the task?
What technique do you use to reduce execution time and increase scalability?
Other efforts you made in your program
3.     Experiment & Analysis
Explain how and why you do these experiments? Explain how you collect those measurements? Show the result of your experiments in plots, and explain your observations.

i、
Methodology

(a). System Spec (If you run your experiments on your own machine)

Please specify the system spec by providing the CPU, RAM, storage and network (Ethernet / InfiniBand) information of the system.

(b). Performance Metrics

How do you measure computing time of your programs? How do you compute the values in the plots?
ii、
Plots: Scalability & Load Balancing

(a). Conduct strong scalability experiments, and plot the speedup. The plot must contain at least 4 different scales (number of processes, threads) for both single node and multi-node environments.

(b). Design your own experiments to show how balanced it is in each of your experiments by plots.

(c). Make sure your plots are properly labeled and formatted.

(d). You are recommended to choose a proper problem size to ensure the experiment results are accurate and meaningful.
iii、 Discussion (must base on the results in the plots)

(a). Compare and discuss the scalability of your implementations.

(b). Compare and discuss the load balance of your implementations.

iv、 Others
You are strongly encouraged to conduct more experiments and analysis of your implementations.
4.     Experience & Conclusion
Your conclusion of this assignment.
What have you learned from this assignment?
What difficulties did you encounter in this assignment?
If you have any feedback, please write it here. Such as comments for improving the spec of this assignment, etc.