CHAPITRE III. ALGORITHMES EVOLUTIONNAIRES
PARALLÈLES
Figure III.4 - Distribution de calculs de
performance.
III.2.2 Distribution du calcul de performance
- Distribution synchrone. Cette technique
consiste à paralléliser l'étape d'évaluation. Une
station maître gère tout l'algorithme (sélection,
remplacement et opérateurs génétiques), sauf les calculs
de performance qui doivent être envoyés à des stations
esclaves. Dans ces conditions, si le temps de calcul de fitness varie d'un
processeur à l'autre (hétérogénéité
des processeurs), l'ensemble des processeurs doivent alors attendre le plus
lent d'entre eux, et le gain apporté par ce modèle peut se
dégrader. Pour donner une reboutasse à ce modèle, une
solution peut être possible, si on pense à la gestion de la
distribution des calculs et à l'aide d'une liste de calculs à
effectuer, un processeur reçoit un nouveau calcul dés la fin du
calcul précédent, ceci permet de limiter le
phénomène d'attente sans complètement le supprimer, car si
un processeur s'arrête, le maître se mettra en attente du
résultat manquant. A noter que, dans ce modèle, l'algorithme
parallèle se comporte comme un algorithme séquentiel. Cependant,
pour des tailles de population ne dépassant pas quelques multiples du
nombre de processeurs disponibles, le facteur d'accélération
devient très proche du nombre de processeurs lorsque le ratio
évaluation-évolution augmente.
- Distribution asynchrone.Cette technique
utilise un schéma d'évolution asynchrone, chaque processeur
esclave effectue son calcul de performance, renvoie le résultat au
maître et reçoit immédiatement un nouveau calcul, ainsi les
étapes de « sélec-tion/remplacement »peuvent être
effectuée individu par individu. Dans ces conditions, Le schéma
stationnaire (steady-state) est la cible de ce modèle, chaque fois qu'un
esclave renvoie la performance d'un enfant, le maître effectue
l'étape de remplacement, de sélection et de l'application des
opérateurs génétiques, et envoi le nouveau enfant à
évaluer à l'esclave en question. L'inconvénient de ce
modèle est que si le calcule de fitness d'un individu sur un processeur
donné est plus long, il impliquera soit une population anachroniques ou
l'élimination de cet individus avant d'avoir été
sélectionné pour reproduction.
31
| 
