[SOLVED] CS542200 Homework 2-Mandelbrot Set

Mandelbrot Set

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

  𝑍=𝑍 2+𝐶, 𝑘≥1

𝑘 𝑘−1

• ●  C is some complex number: 𝐶 = 𝑎 + 𝑏𝑖
• ●  𝑍𝑘 is the 𝑘𝑡h iteration of the complex number
• ●  if 𝑍 ≤ 2 for any 𝑘, 𝐶 belongs to the Mandelbrot Set | 𝑘|

  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

Last Update: 2021.11.01

1

● 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.

Last Update: 2021.11.01

2

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

Last Update: 2021.11.01

3

4 WORKING ITEMS

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

1. pthread: Single node shared memory programming using Pthread ● This program only needs to be run on a single node.

2. 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.

Last Update: 2021.11.01

4

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

1. (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.
2. (b).  Design your own experiments to show how balanced it is in each of your experiments by plots.
3. (c).  Make sure your plots are properly labeled and formatted.
4. (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.