Parallélisation d’un algorithme à l’aide de OpenMp et Boost
L’objectif de mon projet est de paralléliser un code séquentiel cherchant le plus près de la meilleure solution possible au problème du voyageur de commerce. L’algorithme utilisé est basé sur le principe des colonies de fourmis. Le code séquentiel a été implémenter suite à une suggestion du professeur Jean Goulet dans le cadre d’un travail pratique du cours structure de données (ift-339) visant à trouver une solution au problème du voyageur de commerce.
Puisque la parallélisation de l’algorithme s’est avéré plus simple que prévu, deux solutions au problème seront présentés. Ce sera ainsi l’occasion pour moi d’explorer deux outils de parallélisation et de prendre le temps pour chacun d’eux de lire la documentation et de faire une synthèse des éléments importants des deux outils. La première solution utilisera l’outil de programmation parallèle en mémoire partagée OpenMP, alors que la seconde utilisera la bibliothèque pour la gestion des fils d’éxécutions de boost.
Dans un premier temps, les deux outils de programmations seront présentés. Ensuite, l’algorithme séquentiel basé sur les colonies de fourmis sera présenté ainsi que les modifications nécessaire à l’implémentation d’une solution parallèle. Finalement, la performance de la version séquentielle et des deux versions parallèles seront comparées.