====== Guillaume Lameynardie ======
Je suis venu étudier à Polytechnique Montréal en maîtrise dans le cadre d'un double diplôme proposé par [[https://www.imt-mines-albi.fr/|IMT Mines Albi-Carmaux]] (France), à laquelle je suis rattaché. Je suis arrivé en août 2018, et je prévois de finir en août 2020.

Directeur : [[groupe-dfo-bbo:acteurs:profs:charles-audet:main-page|Charles Audet]], Co-directeur : [[groupe-dfo-bbo:acteurs:profs:sebastien-le-digabel:main-page|Sebastien Le-Digabel]]

Contact : [[mailto:guillaume.lameynardie@polymtl.ca|guillaume.lameynardie@polymtl.ca]]
=====Sondes locales intensives lors de l'exécution de l'algorithme MADS dans un environnement parallèle=====

====Project overview====

===Context===
<callout color="#fdb120">
Underuse of parallel ressources arises in two cases : 

<grid>
<col md="10">
  * when the execution is sequential, one processor do all the job
  * when there is more processors available than workload units
</col>

<col md="2">
{{.:parallel.jpg?200| sonde locale non parallélisée}}
</col>
</grid>

During the poll step of the MADS algorithm, the objective and constraints functions are evaluated near the best incubent following directions of a positive spanning set in the search space. As a performance issue, the software NOMAD 4 that implements MADS, uses a positive basis, which is a positive spanning set of minimal cardinality. For a problem of dimension **n**, this positive basis is composed of **2n** orthogonal directions and so the poll step leads to **2n** evaluations of the objective and constraints. Nowadays, access to massively parallel ressources is easier. For instance, the research laboratory of Hydro-Québec ([[http://www.hydroquebec.com/innovation/fr/institut-recherche.html|IREQ]]) owns a supercomputer made of 152 nodes and 36 CPUs per node. In this context, at the poll step, the execution of **NOMAD 4** leads to an underuse of the available ressources. Indeed, the number of evaluations is far lower than the number of available processors. It seems relevant to evaluate the objective and constraints in a larger number of polling directions.

</callout>

===Research axis===

<callout title="Intensives polling strategies" color="#f66555">

Three points generation strategies are described in order to generate more than **2n** points. Those strategies differs in the geometry given to the polling points.
  * Multi poll aims to generate the neighbours of neighbours polling points. For positive basis of **2n** points, this strategy generates **(2n+1)x2n** points. 
  * Oignon poll aims to reflect the behaviour of **MADS** when the algorithm is failing to improve the objective function several times in a row. Polling points are generated on frames of different size, all centerd on the best incubent. 
  * Enriched poll aims to generate more than *2n* points by generating points inside the poll frame. 

{{.:multi-poll.png?200| multi poll}}
{{.:oignon-poll.png?200| oignon poll}}
{{.:enriched-poll.png?400| enriched poll}} 

</callout>

<callout title="Dynamic intensification" color="#f66555">
The number of points generated with Oignon and Enriched poll can be decided at each iteration **k** of **MADS**. A criterion on increasing the number of polling directions is set up in order to feed processors with more evaluations only when it seems to be relevant. Hence, one avoid generating too much evaluations when improving the objectif function seems to be easy. The intensification factor is said to be linear when **2n** polling directions are added between two iterations that fails to improve the objective function. It is said to be exponential when the number of polling directions is multiplied by 2 between two iterations that fails to improve the objective function

When an iteration successfully improves the objective function, it is possible to reduce the number of polling directions. The intensification is said to be without memory if when a success is met, the number of polling directions of the next iteration is reset to 0. With memory, the number of polling directions is reduced the same way it is increased with the intensification factor.
</callout>

<callout title="Efficient ordering of the evaluation stack" color="#f66555">
The generation of a larger amount of points per iteration lead to the problem of evaluating those points. Those evaluaitons represents a workload that one can order by deciding which evaluaution must be completed on which processor. This ordering is relevant when the operator has access to an easy estimation of the time or the workload of each evaluation.
</callout>

----
====Liens utiles====
[[https://moodle.polymtl.ca/course/view.php?id=999|Cours sur les systèmes parallèles suivi à la session d'automne 2019]]

[[https://slurm.schedmd.com/documentation.html | Documentation Slurm : environnement parallèle utilisé à l'IREQ ]]

[[https://github.com/Guillaume5255/Benchmark_NOMAD.git| github repository for data exploitation generated with the polling strategies]]

[[https://github.com/Guillaume5255/nomad.git| github repository for the implementation of the strategies on NOMAD 4]]

[[http://www.labunix.uqam.ca/~tremblay/INF7235/Materiel/7235.pdf | Cours sur les systèmes parallèles donné par Guy Tremblay à l'UQAM (hiver 2017)]]

====Suivi des travaux====

[[.retours-memoire:redaction-memoire|Mémoire]]

[[.retours-article:redaction-article|Article]]

----

<- [[..:..:|Étudiants]]