Optimisation combinatoire : Affectation optimale de tâches sur des
processeurs répartis
Personnes impliquées : Yskandar Hamam
L'affectation optimale de tâches sur les processeurs d'un système
réparti est un problème dont la résolution effective
est importante durant toutes les phases du développement de tels
systèmes : au cours de la phase de conception, elle permet d'aider
à la détermination de la configuration permettant d'atteindre
un niveau de performance souhaité ; pendant la phase de fonctionnement,
elle facilite l'optimisation des ressources disponibles ; au cours d'une
reconfiguration, elle aide à la réaffectation des modules
en fonction des changements affectant le système.
Le problème est souvent traité à différent
niveaux de complexité :
-
affectation tenant compte de la vitesse de traitement des processeurs uniquement
;
-
affectation tenant compte de la vitesse de traitement et la capacité
en mémoire des processeurs ;
-
affectation avec contraintes sur les processeurs et la capacité
des réseaux ;
-
affectation tenant compte des contraintes précédentes et
des contraintes d'ordonnancement.
Ce problème, dans ses diverses versions, fait l'objet d'une importante
littérature pour la configuration des systèmes parallèles
et multi-processeurs. Les algorithmes existants relèvent des catégories
suivantes :
-
algorithmes exacts appliqués à des problèmes simplifiés
;
-
algorithmes heuristiques sous-optimaux appliqués aux problèmes
complets ou simplifiés ;
-
algorithmes exacts appliqués aux problèmes complets.
Cependant, le problème étant NP-complet, sa résolution
exacte nécessite un traitement adapté. Les méthodes
sur lesquelles nous travaillons pour cette résolution sont :
-
développement d'une méthode de séparation et évaluation
formulant le problème d'évaluation comme un problème
de programmation linéaire ;
-
développement des coupes valides pour accélérer la
méthode de séparation et évaluation ;
-
développement d'une méthode basée sur le recuit simulé.
Nous avons actuellement de bons résultats avec la méthode
de recuit simulé (cf. section sur nos résultats des travaux
de recherche). Des travaux dans ce domaine sont actuellement en cours de
développement avec l'équipe architecture de notre laboratoire
pour l'affectation de tâches aux processeurs dans le cadre d'architectures
parallèles.
Dernière mise à jour :
par François Rocaries.