|
|
|
Développement d’un système Maître-Esclave pour des calculs évolutionnaires |
Maîtrise |
Marc Dubreuil |
Marc Parizeau (Directeur) |
|
Problème: Les algorithme évolutionnaires nécessitent énormément de puissance de calcul pour résoudre des problèmes. Heureusement, les problèmes peuvent être aisément divisés en plusieurs parties et calculés en parallèle. Il est maintenant possible d'acheter à faible coût un ensemble d'ordinateurs qui ne sert qu'à distribuer des calculs. De plus, une multitude d'ordinateurs en réseau dorment de grandes parties de la journée, perdant ainsi de précieux cycles de CPU à faire fonctionner des écrans de veille futiles. Le problème est donc de concevoir un système distribué et parallèle pouvant répondre aux exigences des algorithmes évolutionnaires sur un LAN de stations de travail. Ce système doit être performant, tolérant aux erreurs, persistant avec les données, indépendant des différents types d'algorithmes évolutionnaires tout en permettant de minimiser les temps d'attente et de pouvoir fonctionner sur un grand nombre de systèmes d'exploitation. Enfin, le système devra être quantifié afin de connaître son rendement optimal et ses limites. |
Motivation: Ce projet entre dans le cadre de la recherche sur les algorithmes évolutionnaires du Laboratoire de Vision et Systèmes Numériques. Il se greffe au projet Open BEAGLE, un environnement logiciel d'algorithmes évolutionnaires. Ces algorithmes connaissent depuis quelques années un accroissement considérable du nombre d'adeptes qui recherchent les moyens de les appliquer à des problèmes complexes. Ces problèmes demandent parfois des jours à résoudre sur des ordinateurs séquentiel. Avec la venue de clusters d'ordinateurs abordables, il devient envisageable de paralléliser et de distribuer les problèmes les plus complexes. Ce projet à donc comme but ultime de diminuer le temps de calcul pour résoudre des problèmes complexes d'algorithmes évolutionnaires. |
Approche: Le projet est divisé en 3 étapes principales: la création de trois outils (serveur, coquille pour les clients et moniteur), la quantification du système et enfin sa validation avec des applications concrètes. Le premier outil, le serveur, est optimisé pour être robuste aux erreurs, c'est-à-dire que s'il tombe en panne, il doit pouvoir reprendre le travail là où il l'avait laissé et ce, avec un minimum de perte de données. De plus, une fonction de balançage des charges (Load Balancing) devra être implanté pour que chaque client finisse de calculer en même temps, peu importe leur différence de vitesse respective.
Le deuxième outil, la coquille du client, est responsable de prendre en charge les communications entre l'application et le serveur pour que tout le processus de parallèlisation soit le plus transparent possible pour un usager. Puisque qu'un client peut fonctionner sur une station de travail, lorsqu'il arrêtera de travailler (ex: quelqu'un désactive l'écran de veille), il devra signaler le serveur pour que ce dernier puisse envoyer le calcul à un autre client.
Le troisième outil, le moniteur n'intervient pas dans le processus évolutionnaire. Celui-ci a un rôle passif. Il doit pouvoir connaître l'état de la résolution du problème et être capable d'aller chercher les meilleurs données. C'est donc un outil indispensable lorsque la résolution de problèmes se comptent en jours puisqu'un suivi est donc possible.
Finalement, tous ces outils doivent être quantifiés pour connaître le nombre de clients avec qui le serveur peut communiquer des données avant que le travail séquentiel ne devienne plus avantageux. Par le fait même, à partir de combien de clients le système devient-il optimal. Cette quantification sera suivi de tests de validations. |
Défis: Il existe déjà plusieurs systèmes qui permettent de distribuer des données d'algorithmes évolutionnaires. Cependant, aucun n'est disponible ni optimisé pour des LANs de stations de travail et la quantification d'un tel sytème reste encore très peu documenté. C'est dans cette optique que le projet devient intéressant. En effet, puisque notre système est optimisé pour les LANs de stations de travail et qu'en plus il sera dans le domaine publique (« open source »), les utilisateurs sauront donc exactement combien de clients donnera le meilleur rendement pour leur problème. |
Applications: À court terme, ce système sera appliquée à deux projets de recherche en cours: un en reconnaissance de caractères manuscrits et l'autre pour le design de systèmes de lentilles. |
|
Calendrier: Septembre 2002 à Décembre 2004 |
|
|
Dernière modification: 2007/09/28 par dubreuil |
|
|