Author: Richard Middelkoop
On 29 July, I defended my bachelor thesis entitled “Parallel Algorithm Portfolios in Sparkle” after half a year of work following the project start in February 2021. For this project I was part of the ADA group and was supervised by Koen van der Blom and Holger Hoos.
In a parallel portfolio, a set of independent, non-communicating solvers solve problem instances in parallel. Within the thesis, insight is given into the design and implementation of parallel portfolios into Sparkle. Additionally, experiments show the validity of the implementation and the practical capabilities of parallel portfolios as implemented in Sparkle.
My work built on the existing platform created by the Sparkle development team. The thesis is of value to the platform since the state of the art is represented by a set of algorithms, and parallel algorithm portfolios allow for an easily accessible method to conduct experiments with such portfolios.
Below an example is outlined showing how parallel algorithm portfolios can be used in Sparkle. Once the platform is initialized, the needed components (problem instances, solvers) are added to Sparkle. Using these the portfolio can be constructed. With the constructed portfolio and a selection of instances, an experiment can be conducted. Finally, we generate a report that describes the used components and an empirical evaluation of the results from the experiment.
initialise.py
add_instances.py --run-solver-later --run-extractor-later PTN/
add_solver.py --run-solver-later --deterministic 0 CSCCSat/
add_solver.py --run-solver-later --deterministic 0 MiniSAT/
add_solver.py --run-solver-later --deterministic 0 PbO-CCSAT-Generic/
construct_sparkle_parallel_portfolio.py --nickname runtime_experiment
run_sparkle_parallel_portfolio.py --instance-paths Instances/PTN/ --portfolio-name runtime_experiment
generate_report.py
First results in the thesis suggest that parallelising up to 64 instances of a nondeterministic solver with different random seeds results in performance gains compared to lower numbers of instances. When using 128 solver instances performance is similar to 64 solver instances, and there no longer seems to be a benefit to using more solver instances. With 256 or more solver instances the overhead appears to increase and performance starts to drop again in this practical implementation.
If you are interested in the project, feel free to take a look at the bitbucket project page and try Sparkle for yourself.
ADA Research Group 