Passer au contenu principal
Accueil
UNIVERSITE
FACULTES et ECOLES
ENSEIGNEMENT
RECHERCHE
INTERNATIONAL
L'UMONS à CHARLEROI
LA CULTURE
Go Search
English
Bannière
 
 

Jan Gyms

Best paper award pour les travaux de doctorat de Jan Gmys

Un Best Paper Award de "11th International Conference on Parallel Processing and Applied Mathematics" (PPAM'2015, Krakow, September 6-9) a été attribué à Jan Gmys, Mohand Mezmaz, Nouredine Melab et Daniel Tuyttens pour leur article intitulé "IVM-based Work Stealing for Parallel Branch-and-Bound on GPU".

Le travail présenté rentre dans le cadre de la thèse de Jan Gmys de l'Université de Mons en cotutelle avec l'Université Lille 1.

Dans de nombreux domaines d’application, le décideur est confronté au problème de la recherche d'une permutation optimale dans un ensemble d’éléments. Le branch-and-bound (B&B) est un des algorithmes les plus utilisés pour trouver cette permutation optimale.  Cet algorithme, très gourmand en temps de calcul, explore un énorme arbre dont la structure est fortement irrégulière. De nos jours, le recours au co-processeur graphique GPU, composé de plusieurs milliers de coeurs de calcul, au lieu du processeur principal CPU, composé de quelques cœurs, est un des moyens utilisés pour paralléliser et donc accélérer les algorithmes.

Cependant, le GPU est connu pour son architecture régulière adaptée davantage au calcul graphique dont les opérations de base sont fortement régulières. La contribution de ce papier est le développement d'une nouvelle structure de données, appelée IVM, pour faciliter la parallélisation et donc le déploiement de la structure irrégulière du B&B sur l'architecture régulière du GPU. Durant la résolution, les cœurs du GPU utilisent la technique de vol de travail (work stealing) afin d’équilibrer la charge de travail entre les cœurs de calcul.

Plus d'infos sur le Groupe Informatique et Gestion de la Faculté Polytechnique de Mons? www.ig.fpms.ac.be