• Parallelise the sub graham scans using either MPI or openMP.
• Build a simple environment where we can run scaling against number of cores.
• Create python script which reads in the produced data and creates strong and weak scaling plots.
• Think about how we could further parallelise.

• have an output folder to store all output files / create if not exist before every run
• delete all output files inside before every run

@leper
The input data should be split in a way such that the different subsets are not almost equal but hold different regions of the 2d particles such that one can distinguish the various subhulls. For n parts, split the data into n regions but apply some overlap of points at the region boundary.

Chose run_config file from old run rather than the standard run, e.g. if one wants to reproduce a run with the exact same settings but doesn't want to retype all the stuff and risk potential typos.

Based on the run_config.py and the json param files of the single runs and the timing files of the subruns, write a generic data loader class which puts all this information in a nice dictionary which then can be passed to post processing module to do some neat plots and shit.

Implement functionality for the "post_process_params" in the run_config file.
Therefore the Benchmark class has to be generalized.

• Possibility to see multiple graham sub scans running at the same time (or one after the other).
• Display final state before starting Jarvis March

As stated in the email, we should compare against existing work. Could someone do reasearch on the topic and get comparisons for runtimes and speedups, note what they did such that we can do appropriate runs to compare against theirs?

Job file for Euler which submits the whole damn thing.

Graham scan works just fine. The total hull around all graham sub hulls however leaves out some of the points: We need to check the tangent function. @jakobbeckmann

@polly95
Put it in an own JarvisMarch class for easy calling from main.cpp.

@jakobbeckmann : Create Quickhull class in dphc-project/src and add it to main.cpp to be selectable via a command line argument.

In the main output folder of a grid run: Place json file with keys sub run indeces holding all parameters of the subruns.

Algorithm variations

Note that all parallel variations do not require much code to be written they consists of a few functions calls to the correct algorithms and some data passing which is the same for all variations.

Serial

Parallel (all subversions of Chan)

Follows the format algo1-algo2 where algo1 is the algo run in parallel on different nodes/processors and algo2 is the algorithm used on the hulls obtained from algo1.

Notice all of the above come in two versions:

1. Full merge: merge combines all hulls from algo1 in one go,
2. Binary-tree merge: merges are performed 2-by-2. If the number of subhulls is odd, the last hull is merged last with the combination of all others.

Reflections

1. Technically, unless performed for 2-by-2 merging, binary Jarvis will always be faster than regular Jarvis for merging. Therefore is it useful to actually build merges with regular Jarvis?
2. Binary-tree merging, if not performed based on finish times (not implemented right now) will nearly always be slower than a regular merge. This is definitively the case of variations with Graham in algo1 as all Graham Scans performed in parallel take about the same time (this can different significantly for Quickhull). Is binary-tree merging useful? Or should it be used as a "proof of concept"?

@polly95

For divide-and-conquer approached based algorithms:

• Divide input data into chunks and send those to different nodes
• On each node run the algorithm using openMP and merge
• Send merged subhull back to main node and merge all subhulls
• test on Euler

Think about what we want to show and implement. E.g.

• runtime plots
• strong scaling
• runtime bar plot comparison for different input images
• weak scaling
• error bars for timing
• check data normality
• put all speedup plots into one figure with appropriate legends
• runtime plots for different n cores depending on the part size

Write 2D random point distribution class. Keep all points in a range of 0 to 1 and save them in a vector.

1. step

• Write all initial points AND the points which end up in the hull to a file (in chan2d.cpp).
• Read into python module and do final static visualization.

2. step

• Write all interim steps of the algorithm in the file and label them
• Do animated python visualization

Write hull output files for run iterations into indexed files and cross check for correctness.

Since the reading of the input file takes the longest time (1M points: 13sec, 500K points 6sec, ...), all runs which use a common input file should be done in a grid run controller in c++. So all the outer controlls, like param files, folder etc. is still handled by GridRunHandler.py, however the c++ loop controller fills the folders appropriately. Should save tons of time, especially for debugging.