DidaWiki

Lab time 06/05/2016

• You can download current TBB on ottavinareale with

wget https://www.threadingbuildingblocks.org/sites/default/files/software_releases/linux/tbb44_20160413oss_lin.tgz

• Install TBB in your home directory on ottavinareale by unpacking the archive
• Set up your install dir of TBB inside the tbbvars.sh script or tbbvars.csh (depending on your shell)
• call tbbvars.sh intel64 linux from your shell profile script

Compute the Mandelbrot set like in the MPI lab farm exercise. Program parameters define a square n*n (or rectangular n*m) subset of the complex plane, the number of samples i,j for each coordinate, the max number of iterations per point MaxI.

The first exaple will not really be a farm: generate the input stream of points with a parallel for (either two nested or a single one with a 2D range). You will need to create appropriate range(s) for that.

The computation for each point is actually given by the mandelbrot function, which returns the number of iteration until the point diverges, or MaxI if the limit is exceeded.

Choose a plane region near the border of the mandelbrot set and getting some of the points of the set.

• measure the execution time and the speedup which varies with the iteration limit parameter;
• check what is the amount of parallelism choose by TBB
• check if the load is balanced
• check if you need to tune the grain size in order to achieve a good speedup when MaxI is low.
• try choosing a different amoutn of parallelism

Can you dynamically optimize the grain according to the input parameters?

• decide how you will provide the sequential mandelbrot function as loop body (via lambda or via a loop body class with () operator)
• decide if you want to set up two nested parallel_for loops or a single loop with a 2D range (it is useful to try both and compare)

Restructure the program to work with a stream of points (or sets of points) that are generated and enter a parallel_do; we still compute the mandelbrot set function, but the sequential function is modified such that the sequential function can take in input and result in poutput a partial computation on a point of the plane.

• an input parameter iter_grain is specified in the program
• the input of the sequential function contains
  • the original point (either as a couple of indexes or as a complex number)
  • the current coordinates (as a complex number)
  • the current interation number
• the function each time computes up to iter_grain iterations on the point (less, if MaxI is reached); if MaxI is reached, the point computation is completed, otherwise the point is emitted in output anyway (with its values updated)
• the output of the sequential function is the same as its input (better define some data structure)

You can compute on points in the stream and recycle them if the computation takes too long. Use the parallel_do methods to reinsert in the loop those points that are not completed, and let those that are completed flow out of the do_loop.

• Basic use of parallel do implies the grain is always 1. Design a data structure that can aggregate more points into a single parallel_do task. Minimize data copying required by the structure,

If you consider tha computation to have some grain (sets of points are provided to each paralle_do inner function) the approach lends itself to become a sort of divide and conquer, where the long computation of some points are considered “big tasks” that are feed back in input after some time. These tasks can be repacked to allow completed points in the same task to not uselessly flow back into the loop. Proper design of the task structure minimizes data copying in this phase too.