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 !