rosa/README.md

# 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
```