Alexis Pereda
caf2a692f9

2 years ago  

bench/graspels  2 years ago  
celero  2 years ago  
data  2 years ago  
examples  2 years ago  
inc  2 years ago  
results  2 years ago  
rtbenchmarks  2 years ago  
scripts  2 years ago  
src  2 years ago  
.gitignore  2 years ago  
CMakeLists.txt  2 years ago  
LICENSE  2 years ago  
README.md  2 years ago 
README.md
About
ROSA (in french "Recherche Opérationnelle grâce aux Squelettes Algorithmiques", i.e. Operational Research with Algorithmic Skeletons). It relies on alsk for the algorithmic skeletons. This is part of the work done for my Ph.D. thesis.
Brief
The main algorithm implemented and presented is GRASP×ELS. This metaheuristic can be represented as below:
When implemented as an algorithmic skeleton, its representation becomes this tree:
Obtained using the following source code.
For the internal ELS:
template<typename InitLS, typename Mutate, typename LS, typename InnerSelect, typename OuterSelect>
using SkelElsStruct =
S<alsk::Serial,
InitLS, // LSI
S<IterSel,
S<FarmSel,
S<Serial,
Mutate, LS // M then LS
>,
InnerSelect // Sel3
>,
OuterSelect // Sel2
>
>;
template<typename Solution>
using SkelElsLinks =
L<Serial, R<1>(Solution const&),
Solution(P<0>),
L<IterSel, Solution(R<0> const&),
L<FarmSel, Solution(Solution),
L<Serial, R<1>(P<0>),
Solution(P<0>, RNG&),
Solution(R<0> const&)
>,
Solution(Solution const&, Solution const&)
>,
Solution(Solution const&, Solution const&)
>
>;
template<
typename Solution,
typename InitLS, typename Mutate, typename LS, typename InnerSelect, typename OuterSelect
>
using SkelEls = BuildSkeleton<SkelElsStruct, SkelElsLinks>::skeleton<
Pack<InitLS, Mutate, LS, InnerSelect, OuterSelect>,
Pack<Solution>
>;
For the GRASP:
template<typename CH, typename LS, typename Select>
using SkelGraspStructure =
S<FarmSel,
S<Serial, CH, LS>,
Select // Sel1
>;
template<typename Problem, typename Solution>
using SkelGraspLinks =
L<FarmSel, Solution(Problem const&),
L<Serial, R<1>(P<0>),
Solution(P<0>, RNG),
Solution(R<0>)
>,
Solution(Solution, Solution)
>;
template<typename Problem, typename Solution, typename CH, typename LS, typename Select>
using SkelGrasp = BuildSkeleton<SkelGraspStructure, SkelGraspLinks>::skeleton<
Pack<CH, LS, Select>,
Pack<Problem, Solution>
>;
Then the GRASP×ELS can be constructed:
// All arguments are defined types or functions, see full source code
using ELS = SkelEls<
tsp::Solution,
Descent,
Move2Opt, Descent,
FN(selectMin)
>;
using GRASPxELS = SkelGrasp<
tsp::Problem, tsp::Solution,
RGreedy<tsp::Solution>, ELS,
FN(selectMin)
>;
Performances
The measures shown below are from using the GRASPxELS algorithm to solve an instance of TSP with 194 nodes. Various execution policies are used:
 "hw_seq": handwritten sequential implementation;
 "hw_par": handwritten parallel implementation;
 "sk_seq": skeleton without parallelisation;
 "sk_firstlevel": skeleton with parallelisation of the first level;
 "sk_staticpool": skeleton with parallelisation using a thread pool with static task distribution;
 "sk_dynamicpool": skeleton with parallelisation using a classical thread pool with dynamic task distribution;
 "sk_thread": skeleton with parallelisation using dynamically created threads.
For an execution with only one allotted core, meaning that there is no parallelisation done, we obtain the data below. Note that this data set do not use the legend shown above. All subsequent images use it.
For parallel executions, measures give the following data.
With 24 iterations for the outmost parallel loop:
With only 4 iterations for the outmost parallel loop:
Related publications
 "Repeatability with Random Numbers Using Algorithmic Skeletons", ESM 2020 (https://hal.archivesouvertes.fr/hal02980472);
 "Modeling Algorithmic Skeletons for Automatic Parallelization Using Template Metaprogramming", HPCS 2019 (IEEE) 10.1109/HPCS48598.2019.9188128;
 "Processing Algorithmic Skeletons at CompileTime", ROADEF 2020 (https://hal.archivesouvertes.fr/hal02573660);
 "Algorithmic Skeletons Using Template Metaprogramming", ICAST 2019;
 "Parallel Algorithmic Skeletons for Metaheuristics", ROADEF 2019 (https://hal.archivesouvertes.fr/hal02059533).
Organisation
Main directories:
src
: sources;src/rosa
: the library sources;rtbenchmarks
: scripts for compiletime/runtime benchmarking;results
: results presented in the thesis, obtained using mentioned scripts and codes.
Usage
To produce the Makefile
and build the project:
mkdir build
cd build
cmake DCMAKE_BUILD_TYPE=Release ..
make