devoo - info pour les ours

J'ai fait une petite présentation de mon travail, que va utiliser mohamed pour sa présentation lors d'un prochain séminaire. Apparement, ma présentation est un peu trop technique et je vais donc certainement allégé le contenu. Le plan est on ne peut plus simple :

1. cluster et librairie parallèle : état de l'art
   
2. cluster : solutions testées et solution retenue
   
3. librairies : solutions testées et solutions retenues
   
4. application répartie de test : présentation générale
   
5. analyse des résultats : efficacité du cluster
   
6. implémentation réelles : comment paralléliser des algos basés sur des AG
   

J'ai eu de plus le plaisir de faire cette présentation deux fois, mon portable n'ayant plus de batterie 5 min avant mon arrêt et avant que j'ai eu le temps de la sauver...(je sais c'est boulet...)

Cette après-midi, j'ai pas mal avancé dans la configuration du serveur temporaire du cluster. J'ai fait une install de debian propre ! J'ai jamais autant pris le soin de configurer une install. A côté mon portable me dit :

et moi quand-est-ce que tu me configure comme ça ?

Enfin, depuis le temps que j'attendais la sortie de la version 1.9 d'OpenSSI (sortie vendredi dernier mais prévue à l'origine pour mi-mars :D) ! Pendant un moment, j'ai eu un peu peur qu'elle ne sorte pas avant la fin de mon stage...ouf !
Ca fait du bien d'avancer un peu, ca me change du vieux rapport (enfin des vieux rapports) qu'il va falloir que je termine tout de même...(ce week-end ?)...(argh)

Sinon j'ai assisté à la thèse d'Haiyan Housroum qui soutenait sur le sujet : Approche évolutionniste dynamique de la gestion des tournées avec fenêtres de temps (dynamic VRPTW).
J'ai eu l'occasion de travailler avec lui lors de mon stage de DUT, ou j'avais fait une appli php/xml/javascript/java qui permettait de fédérer différents programmes et qui sortait un parcours au format svg. A l'époque j'avais été bien impressionné par son travail (et son appli de killer) qui donnait déjà de (très) bons résultats. Deux ans se sont passés, apparemment les résultats qu'il obtient aujourd'hui montrent que les AG sont une façon efficace (plus efficace que les autres types d'algo) pour résoudre les problèmes dynamiques de VPRTW et ceux s'y approchant.
Bref, il a eu sa thèse avec mention très honorable. Félicitation et bonne chance pour la suite !

Le résultat de ma journée peut se résumer par la question : comment se connecter via ssh d'une machine windows vers une machine linux, sans demander de mot de passe.
Après quelques tests, j'ai réussie à le faire mais je dois toujours spécifier mon nom d'utilisateur dans putty, sinon le serveur ssh me demande le login sous lequel je veux me connecter.
Le problème est que sous proactive, lorsque je spécifie un utilisateur, celui-ci ne semble pas être reconnu.
Pour ne pas passer plus de temps sur un problème de configuration de mon serveur ssh ou de configuration de mon descriptor, j'ai envoyé un message sur la mailing-list de ProActive. Avec Tiente, on a aussi étoffé les objectifs de mon stage :

• installation et configuration d'openMosix
• installation et configuration d'OpenSSI
• guide complet de programmation sous ProActive (ex sur la communication inter-process, méthodes d'io, outils de monitoring/debuggage ...)
• réalisation d'une appli sous ProActive (le solveur tsp)
• même appli en C en utilisant MPI
• comparatif MPI/ProActive (logiciel) et sous differentes architecture (portable, 1 node, 2 nodes, tous les pc du labo, ...) (materiel)
• pouvoir eventuellement choisir la facon de resoudre le probleme (methode exacte, algo génétique, ...) dans l'appli.

Pour la fin des vacances, il faut que je puisse avoir fini le guide sur ProActive et j'aimerais aussi avoir bien avancé en C.

-EDIT- apperement le problème que je rencontre avec ssh est un bug de la version 2.1 de ProActive (résolu dans la version 2.2) ... comme quoi.

Enfin le cluster donne un résultat interessant ! Suite à mon problème de la semaine dernière, j'ai commencé à debuguer l'application.
Je me suis rendu compte, que je n'utilisais pas le cout optimal trouvé au fur et à mesure, mais uniquement celui trouvé au début (méthode des plus proches voisins). Voila donc la cause des ralentissements incompréhensibles qui m'avait un peu frustré la semaine dernière.
J'ai en même temps vu que ma méthode de distribution des contraintes n'est vraiement pas optimale, puisque les workers ne sont pas crée à chaque fois, mais qu'on leur attribue des taches successives. On pourrait alors facilement gagner quelques secondes en ne calculant qu'une seule fois les vecteurs de distances. Ceci étant, j'imagine que dans un cas général, notamment le cas du dtsp (ou d signifie ici Dynamic et pas Distributed), les contraintes évoluent à chaque pallier de programme. J'ai donc décidé de garder les contraintes contenu dans les taches.
J'ai aussi pensé à la création des taches : il n'est parfois pas possible (en terme de ressources mémoire principalement) de créer toutes les taches d'un coup. Il faudrait donc prévoir un tampon de taches (de taille fixée) que l'on pourrait remplir lorsque celui-ci attendrait une taille limite.
Je donnerais les chiffres demain, j'ai oublié mon bench "papier" au labo, mais cela devient possible de rester devant le pc pour voir évoluer le meilleur chemin sans s'endormir ou avoir envie de filer un jean levi's depuis l'atelier clandestin de couture (private joke inside).

Il me reste à faire communiquer les workers entre-eux afin que ceux-ci soient mis au courant dès qu'un d'entre eux trouve une meilleure solution. Le mechanisme de communication de proactive à l'air assez efficace et ce rapproche des solutions théoriques que l'on a pu voir en cours de systèmes cette année.
Je pensais au début avoir une communication type client<->serveur de ce type :

1. un worker trouve une solution meilleure que la solution actuelle et envoie la solution au serveur.
2. le serveur prend acte de la solution trouvée et peut dès lors créer de nouvelles taches bornée à cette solution.
3. le serveur envoie la solution à tous ses fils (sauf eventuellement celui qui l'a trouvée)
4. les autres workers prennent connaissance de la mise à jour de la nouvelle solution optimle et limite donc leur descente dans l'arbre en consequence.

Cette méthode est simple mais elle oblige à passer par le père pour communiquer la nouvelle solution.

La méthode que je suis en train de mettre en place est la suivante :

1. création d'un groupe de communication entre les workers (avant le début des calcul).
2. dès qu'un worker trouve une solution, celui-ci l'envoie au groupe.
3. les membres du groupes sont averti de la nouvelle solution et mettent à jour leur variables
4. le père recupère le résultat dès qu'un worker termine une tache

Cette solution par contre implique que le père n'est au courant de la nouvelle solution que lorsqu'un des fils se termine. Il est alors indispensable de bien gérer la durée moyenne d'une tache.

So, w8nC !

Le précédant test de performance sur le solveur porté en Java s'était avéré catastrophique : environ deux heures pour un problème qui se résolvait en 4 min sur mon portable.
J'ai donc modifié mon code afin que celui-ci n'utilise plus de structure de stockage objet (Vector, ArrayList). Si ces structures sont très faciles (et très agréables) à utiliser, elles entrainent une diminution significative des performances (environ x4 dans mon exemple).
La seconde modification est algorithmique. Comme en C, je precalcule le cout de tous les troncons possibles. Cette méthode évite le calcule de la distance entre deux point, étape très couteuse.
L'utilisation de ces deux "améliorations" permet de résoudre le même problème en 8 min (gain x16). Les erreurs de réallocation dans le cas de la résolution successives de plusieurs problèmes étant résolus, je peux plus ou moins dire que mon programme Java est prêt à être porter sous ProActive.
Ce portage va se faire en plusieurs étapes :

• création des classes permettant de générer les tâches selon un nombre défini de villes fixés au départ.
• création de la class Task representant une tâche à envoyer.
• création des classes permettant de distribuer les tâches.
• modification de la classe TspSolve en un package worker.
• serialisation de toutes les classes pouvant être utiliser par le(s) worker(s)
• ecriture de la classe/fonction permettant de remonter au manager une solution trouvée localement
• ecriture de la classe/fonction permettant d'informer les workers d'une nouvelle solution optimale
• test en local sur un worker
• test en local avec plusieurs workers
• test reseau avec plusieurs workers

Il reste encore pas mal de boulot. Mon objectif est de finir ces étapes avant les vacances, afin de :

• pouvoir faire un compte-rendu avant ou pendant les vacances
• pouvoir étudier l'installation et la configuration d'OpenSSI pendant mes jours de congés.

Ah quel bonheur de travailler avec eclipse. Quand ça marche du moins. Eclipse est un bel outil (merci au meilleur prof du semestre pour nous l'avoir fait découvrir) mais certains problèmes de configuration sont quand même un peu génants.
Aujourd'hui, j'ai eu droit au problème du plantage en cours de déplacement des fichiers :) Heureusement que :

• j'avais déja sauvé les fichiers ailleurs
• les fichiers n'étaient pas importants

Bref ce petit incident de destruction de fichiers m'a permis de changer de projet. Plutôt que de faire un petit programme de merde test pour évaluer en detail ProActive, je vais directement coder le solveur TSP en Java.
Je continue donc directement mon appli définie ici : solveur TSP Java

Autre petit détail du jour, mon solveur C TSP met 3 min (sur 10min) à celui de mon tuteur. Avec l'optimisation que j'ai fait hier, la semaine prochaine je lui prends 5 min :)