163 lines
5.5 KiB
Markdown
163 lines
5.5 KiB
Markdown
|
# About
|
|||
|
|
|||
|
ROSA (in french "**R**echerche **O**pérationnelle grâce aux **S**quelettes **A**lgorithmiques",
|
|||
|
i.e. [Operational Research](https://en.wikipedia.org/wiki/Operations_research) with [Algorithmic Skeletons](https://en.wikipedia.org/wiki/Algorithmic_skeleton)).
|
|||
|
It relies on [alsk](https://phd.pereda.fr/dev/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:
|
|||
|
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/graspels.png" width="800"></div>
|
|||
|
|
|||
|
When implemented as an algorithmic skeleton, its representation becomes this tree:
|
|||
|
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/treegraspels.png" width="500"></div>
|
|||
|
|
|||
|
Obtained using the following source code.
|
|||
|
|
|||
|
For the internal ELS:
|
|||
|
```cpp
|
|||
|
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:
|
|||
|
```cpp
|
|||
|
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:
|
|||
|
```cpp
|
|||
|
// 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](https://en.wikipedia.org/wiki/Travelling_salesman_problem) with 194 nodes.
|
|||
|
Various execution policies are used:
|
|||
|
<ul>
|
|||
|
<li>"hw_seq": handwritten sequential implementation;
|
|||
|
<img src="https://phd.pereda.fr/assets/rosa/rt_legend.png" width="250" align="right">
|
|||
|
</li>
|
|||
|
<li>"hw_par": handwritten parallel implementation;</li>
|
|||
|
<li>"sk_seq": skeleton without parallelisation;</li>
|
|||
|
<li>"sk_firstlevel": skeleton with parallelisation of the first level;</li>
|
|||
|
<li>"sk_staticpool": skeleton with parallelisation using a thread pool with static task distribution;</li>
|
|||
|
<li>"sk_dynamicpool": skeleton with parallelisation using a classical thread pool with dynamic task distribution;</li>
|
|||
|
<li>"sk_thread": skeleton with parallelisation using dynamically created threads.</li>
|
|||
|
</ul>
|
|||
|
|
|||
|
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.
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/rt_graspels_qa194_24_20_20_seq.png" width="500"></div>
|
|||
|
|
|||
|
For parallel executions, measures give the following data.
|
|||
|
|
|||
|
With 24 iterations for the outmost parallel loop:
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/rt_graspels_qa194_24_20_20_par.png" width="500"></div>
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/rt_graspels_qa194_20_20_20_speedup.png" width="500"></div>
|
|||
|
|
|||
|
With only 4 iterations for the outmost parallel loop:
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/rt_graspels_qa194_v4_20_20_par.png" width="500"></div>
|
|||
|
<div align="center"><img src="https://phd.pereda.fr/assets/rosa/rt_graspels_qa194_4_20_20_speedup.png" width="500"></div>
|
|||
|
|
|||
|
## Related publications
|
|||
|
|
|||
|
- "Repeatability with Random Numbers Using Algorithmic Skeletons", ESM 2020 (https://hal.archives-ouvertes.fr/hal-02980472);
|
|||
|
- "Modeling Algorithmic Skeletons for Automatic Parallelization Using Template Metaprogramming", HPCS 2019 (IEEE) [10.1109/HPCS48598.2019.9188128](https://doi.org/10.1109/HPCS48598.2019.9188128);
|
|||
|
- "Processing Algorithmic Skeletons at Compile-Time", ROADEF 2020 (https://hal.archives-ouvertes.fr/hal-02573660);
|
|||
|
- "Algorithmic Skeletons Using Template Metaprogramming", ICAST 2019;
|
|||
|
- "Parallel Algorithmic Skeletons for Metaheuristics", ROADEF 2019 (https://hal.archives-ouvertes.fr/hal-02059533).
|
|||
|
|
|||
|
## Organisation
|
|||
|
|
|||
|
Main directories:
|
|||
|
- `src`: sources;
|
|||
|
- `src/rosa`: the library sources;
|
|||
|
- `rtbenchmarks`: scripts for compile-time/run-time benchmarking;
|
|||
|
- `results`: results presented in the thesis, obtained using mentioned scripts and codes.
|
|||
|
|
|||
|
## Usage
|
|||
|
|
|||
|
To produce the `Makefile` and build the project:
|
|||
|
```bash
|
|||
|
mkdir build
|
|||
|
cd build
|
|||
|
cmake -DCMAKE_BUILD_TYPE=Release ..
|
|||
|
make
|
|||
|
```
|