Discussion :

[antoinelac]

Bonjour à tous,

Là où je travail, nous avons environ 30 ordinateurs qui dorment. Je m'explique, ces ordinateurs servent environ 5% du temps. Leurs capacités sont faiblement utilisées. Toutes ces machines sont branchées sur le réseau et exécutent des tâches de façon sporadiques selon les opérateurs dans l'usine.

D'un autre côté, dans les bureaux, j'ai 3 machines qui roulent beaucoup plus. Quelques fois, elles ont des tâches d'optimisation à accomplir. Pour l'instant, je limite en temps/nbr d'itérations/% d'optimisation ces tâches afin que l'optimiseur ne tourne pas éternellement.

La limite que j'impose à mon optimiseur me fais passer à côté de certaines solutions qui seraient plus optimales.

Mon idée serait la suivante. J'aimerais utiliser chacun des dormeurs pour exécuter quelques calculs lorsqu'ils ne sont pas occupés.




La façon de faire :

J'aurais un ordinateur "répartiteur" qui receverait les requêtes d'optimisation et ensuite les répartiraient dans sa liste de dormeur. Lorsque le dormeur aurait fini ces calculs, il retourne le résultat au répartiteur. Lorsque la requête d'optimisation est complétée, le résultat est retourné au demandeur.

Côté dormeur, il exécute ces fonctions "normales" et lorsqu'il à fini, il indique au répartiteur qu'il est en dormance. Lorsqu'un opérateur à besoin du dormeur, son statut change et le serveur ne peut plus lui envoyer de nouvelles requêtes tant qu'il ne dort pas.

Côté bureau, la machine envoie au répartiteur ses données à optimiser et ensuite devient un dormeur, mais uniquement pour sa propre requête et ce jusqu'à ce que l'optimisation soit complète.




Mes données :

Il s'agit de positionner et d'orienter des morceaux 2 dimensions (de type feuille de métal) de forme diverses dans une surface plus grande pour la découpe. La quantité de morceau varie (entre 1 et ±100), la forme et dimension totalement aléatoire (enfin, sur demande des clients -> imprévisibles et aucun morceau identique).




Mes questions :

Je me demande si les efforts que je vais mettre à monter ce système vont être récompensées.

1 : La vitesse de transfert sur le réseau, le traitement par le répartiteur, l'optimisation par les dormeurs (qui sont moins performant que mes ordinateur de bureaux, intel 2.0 GHz, 2 G RAM VS Intel Dual Core 3.06GHz, 4 G RAM, Windows XP dans tous les cas)

-> Mon optimiseur n'étant pas multithreadé, je n'utilise pas le dual core.

Peut-être avant de me casser la tête sur un système d'une telle ampleur, je suis mieux de rendre multi-thread mon optimiseur?


De plus, je ne suis pas vraiment un programmeur hors-pair, je suis plutôt du type débutant. Alors, peut-être vais-je plus nuire à la production/ralentir mes optimisations que d'autre chose.

J'aurais besoin de connaître vos avis sur les dangers d'un système à plusieurs ordinateurs, les dangers côté programmation, etc.

Merci à tous,

Antoine

[deadalnix]

De toute façon, il faudra rendre ton optimiseur multithread quelque soit la solution que tu choisis.

[antoinelac]

Bonjour,

Merci d'avoir pris le temps de lire et de répondre!


C'est pas bête! Je m'y applique immédiatement, si le multi-threading me donne des améliorations suffisantes, je pourrais penser à laisser le tout tel quel.

Cependant, mon optimiseur fait quelques simplifications afin de limiter les possibilitées. Je pourrais prendre en compte plus d'informations si je pousse le projet de système multi-ordinateur d'avant.


Quelqu'un a un terme plus technique/commun pour remplacer "système multi-ordinateur"?


Merci,

antoine

[deadalnix]

On parle de clustering quand on fait marcher plusieurs machines sur la même application.

Mais cela relève des mêmes problématique que le multithreading, avec des couts de synchro plus élevée, mais une puissance de calcul plus grande.

[3DArchi]

Salut,
En tout cas, l'idée est bien réfléchie. Cependant, comme tu l'as dit cela requiert un peu de connaissance avec de se lancer là dedans.
-> C'est quoi un traitement 'long' ? Plusieurs secondes, plusieurs minutes, plusieurs heures ?
-> Est-ce que tu sais ce qui dans le code prend du temps ? Calcul, accès E/S, etc. ? A mon avis la première chose serait d'instrumenter ton logiciel pour voir ce qui prend du temps.
-> Peux-tu optimiser ton soft ? Peux-tu déjà répartir des calculs gourmands (multithread, openMP, CUDA, etc.) sur la même machine ? Peut être que le gain sera déjà suffisant.
-> Jusqu'où peux-tu gonfler tes machines de calcul (RAM, disque, plus de coeur/process) ?

[antoinelac]

Bonjour,


-> C'est quoi un traitement 'long' ? Plusieurs secondes, plusieurs minutes, plusieurs heures ?

-J'ai ajusté mes critères d'optimisation de sorte qu'en moyenne le temps est de 20 à 30 sec pour environ 30 morceaux.

-- Ce temps semble peu, mais il faut prendre en considération que cette opération est exécutée environ 100 fois par jour et que quelques fois il peut y avoir + de 100 mcx ce qui peut entraîner un temps considérablement long (4 ou 5 min). Il ne s'agit pas de la seule étape que la personne accompli pour traiter les morceaux : vérification de stock, impressions d'étiquettes, impressions de documents divers, etc.

-- De plus, il y a certaines simplifications que j'ai fait afin de réduire un peu le temps d'optimisation, au détriment de l'efficacité de l'optimiseur. Il s'agit de ne pas essayer toutes les orientations possibles, seulement certaines qui sont plus "intéressantes". C'est logique, mais dans certain cas, plus rares, le rendu est effroyable (peut-être pourrais-je ajouter une option "essayer toutes les orientations" de façon manuelle pour l'utilisateur lorsque ce dernier s'apperçoit du résultat désastreux).

-> Est-ce que tu sais ce qui dans le code prend du temps ? Calcul, accès E/S, etc. ? A mon avis la première chose serait d'instrumenter ton logiciel pour voir ce qui prend du temps.

-Ouais, j'y avais pas pensé. Rapidement, existe-t-il des outils qui pourrait m'aider? Ou plutôt faut-il que j'enregistre à des points précis l'heure (avec les milisecondes) à l'aquelle le programme passe par là et j'enregistre le tout dans un vecteur que je fini par enregistrer dans un fichier excel que j'utilise pour faire des courbes?

-Je n'ai pas d'E/S (du moins pas lors de la portion optimisation). Il s'agit principalement de vérifier quelles pièces entrent dans l'espace restante, ensuite, je classe ces pièces selon les plus intéressantes en premier, j'essaie pour une des premières (choisi aléatoirement parmis les 5% meilleures) une orientation qui semble la plus intéressante. Ensuite je "place" le morceau à cet endroit pour ensuite analyser l'espace restante de la même façon jusqu'à tous les morceaux soient placés. À ce moment, j'enregistre la solution trouvé dans un vecteur.

-À chaque fois que je prend une décision, j'enregistre avant de prendre la décision, l'état de la situation. Lorsque tous les morceaux sont placés, je recommence à partir d'un état préalablement enregistré.

-Lorsque j'atteint un critère d'arrêt (temps, % d'optimisation, nbr d'itération, etc.), j'analyse le vecteur des solutions trouvées afin d'en retirer le meilleur.

-->En somme, il s'agit de vecteurs qui se construisent ou se détruisent.


-> Peux-tu optimiser ton soft ? Peux-tu déjà répartir des calculs gourmands (multithread, openMP, CUDA, etc.) sur la même machine ? Peut être que le gain sera déjà suffisant.

-J'avais mis de côté le multi-thread pour l'instant (je ne l'ai utilisé que quelque fois au paravent). Mais, je crois que ça été une erreur. Je crois que je vais ajouter un thread pour chaque décision importante.

-Il doit bien rester de l'optimisation à faire pour ce qui est du code (il y en a toujours...). Mais, disons que chaque étape est dans le bon ordre et n'est pas superflue. Je ne connais pas openMP, ni CUDA, mais je vais googler ça à l'instant.


-> Jusqu'où peux-tu gonfler tes machines de calcul (RAM, disque, plus de coeur/process) ?

-Pour ce qui est de la machine par elle-même, il ne suffit que de convaincre mon patron qu'un investissement d'environ 1000$CAN par machine permettrait d'avoir une meilleure optimisation et de sauver des pertes de matériel. Même que 1000$CAN me semble beaucoup (c'est le prix d'un nouveau PC).

-Cette option me semble très efficace, mais elle gâche le plaisir d'optimiser son code. Je crois quand même que je vais faire des tests sur ma machine (quad core 3.06Ghz, 4G RAM, WinXp) perso. lorsque le multi-thread va être implanté afin de pouvoir prouver que l'investissement en vaut le coût.


Merci de ton intervention, cela m'a fait beaucoup réfléchir.

En d'autres termes, l'option de construire un système qui utilise les machines dormeuses est intéressantes, mais il semblerait que je n'en suis pas encore rendu à ce point. La seule raison qui pourrait me rester pour le faire, c'est par plaisir et volonté d'apprendre.


Comme toujours, j'ai eu réponse à mes interrogations!


Merci à tous!!


antoine

[antoinelac]

J'oubliais,

merci deadalnix pour ta réponse sur le clustering,

ciao

antoine

[JolyLoic]

Pour découper du code sur plusieurs machines, il faut déjà le découper tout court. D'où l'intérêt de déjà le multithreader. Par exemple, dans ton cas, j'ai l'impression que chaque hypothèse de placement est indépendante des autres, ce qui permet de les explorer indépendamment les unes des autres. C'est un bon point de départ (peut-être en remplaçant une part d'aléatoire par du déterministe, afin de pouvoir plus facilement être assuré de mieux parcourir l'espace des solutions ?).

Ensuite, une fois le travail découpé en plusieurs threads, il faut passer par une distribution de ces tâches sur des machines différentes. Tu peux pour ça mettre en place ton propre protocole réseau, ou en utiliser un préexistant. MPI est un standard pour ce qui est du calcul distribué, mais je ne connais pas, je ne t'en parlerai donc pas plus.

Enfin, comme tu as un tout petit cluster, tu dois pouvoir te passer de la dernière tâche qui incombe généralement à ce genre d'infrastructures : Mettre en place un système permettant d'administrer plein de machines, d'en remplacer une sans interrompre les calculs...

[3DArchi]

Salut,
Un autre truc que j'ai oublié concerne le volume de données traitées et la façon dont elles sont organisées. Cela peut avoir des effets favorables ou préjudiciables pour le cache et impacter directement les perfs.

[antoinelac]

Bonjour!


Merci JolyLoic!


[...] Par exemple, dans ton cas, j'ai l'impression que chaque hypothèse de placement est indépendante des autres, ce qui permet de les explorer indépendamment les unes des autres.

C'est exacte, je prend tel ou tel autre morceau, la suite peut se dérouler en parallèle.



C'est un bon point de départ (peut-être en remplaçant une part d'aléatoire par du déterministe, afin de pouvoir plus facilement être assuré de mieux parcourir l'espace des solutions ?).

Au départ, je choisissais l'option qui semblait la meilleure (déterministe, calcul de certains ratios). Mais, en ajoutant une part d'aléatoire je donnais une chance à certain morceau d'être placé alors que mes ratios me disait qu'ils n'étaient pas les meilleurs (peut-être 3 ou 4ieme meilleurs).

La raison qui me permet de croire que c'est bon, c'est que mes ratios tiennent en compte certains facteurs de forme du morceau et de l'espace disponible, mais ne tiennent pas en compte la "personnalité" de l'ensemble de mes morceaux. Il faudrait que préalablement que je fasse une étude statistique de ma population afin de savoir si j'ai avantage à placer les petits rondelets avant les gros difformes, ou les simples carrés. Même si je prennais en compte cet aspect, je crois que mes conclusions ne seraient peut-être parfaites. Alors, sachant que ma façon de les classer (du meilleur candidat au pire ) n'est pas complète/parfaite, je donne une chance à d'autres morceaux de façon aléatoire (toujours dans les plus intéressants, je laisse de côté ceux qui me semblent moins intéressants).

Disons que je me suis souvent poser la question à savoir quel portion d'aléatoire inclure, dans quel portion du groupe que je désire le plus tomber souvent (5%-10%,20% des meilleurs??), dois-je ou non choisir systématiquement le "meilleur" choix, si oui, il n'y aura qu'une seule solution.

Comme tu l'as mentionné, avec le multi-thread et le déterministe je pourrais, disons, choisir les 4 meilleures options et partir en parallèle. Mais, je peux pas le faire à tout coup. Disons que j'ai 20 morceaux à placer, je vais avoir 4^16 situations parallélisables (ça se dit? Mon calcul est bon?). Alors, c'est là qu'il faut que je choisisse quand que je pars en parallèle ou non. Dans les 25% pièces, ou dans le 10%, difficile à dire. Une chose de certaine (peut-être pas tant certaine), c'est que je ne peux pas laisser le hazard décider.



[...]Tu peux pour ça mettre en place ton propre protocole réseau, ou en utiliser un préexistant. MPI est un standard pour ce qui est du calcul distribué, [...]

Intéressant, je garde l'information pour lorsque je serais rendu à cette étape, si je m'y rends. Je semble avoir encore beaucoup d'améliorations possibles avant de devoir utiliser les clusters.



Enfin, comme tu as un tout petit cluster, tu dois pouvoir te passer de la dernière tâche qui incombe généralement à ce genre d'infrastructures : Mettre en place un système permettant d'administrer plein de machines, d'en remplacer une sans interrompre les calculs...

Il reste toujours le "problème" que mes machines ne servent pas exclusivement à ces calculs, mais bon, c'est une autre histoire.



3DArchi,


Un autre truc que j'ai oublié concerne le volume de données traitées et la façon dont elles sont organisées. Cela peut avoir des effets favorables ou préjudiciables pour le cache et impacter directement les perfs.

C'est vrai que je traine un paquet d'information lors de mon optimisation, tel que le nom du client à qui va la pièce, le numéro de commande, la date de livraison, etc. qui sont loin d'être utile à l'optimiseur. J'ai un ménage à faire de ce côté.



Merci à tous!

Je viens de me trouver du travail pour un petit bout
(Pas que j'en manquais...) , mais surtout plein de belles possibilitées pour améliorer mon optimiseur!


ciao

Antoine

[antoinelac]

Il y un thread qui traite un peu du même sujet (dont certain acteurs sont les mêmes aussi), pour ceux qui suivent passionnément ce thread-ci :

http://www.developpez.net/forums/d83...iple-machines/

ciao

antoine

[Lightness1024]

MPI n'aidera probablement pas son probleme précis, alors que pour l'autre thread, c'est tout indiqué.
je dirais qu'ici il a besoin d'openMP et de déterminisme pour couvrir des champs de possibilités distincts par "bloc de boucle".
OU de lancer pleins de fois son programme avec des graines aléatoires. sur plusieurs processus. a la fin garder le meilleur choix, ce n'est pas autant scalable que la première solution.

attention, le parrallélisme est TRES dangereux pour des dixaines de raisons.

évidemment, il s'agit de 1 visualiser tous les cas de schemas d'ordonnancement possibles et de s'assurer que tout peut fonctionner sans foirer.
de deux il s'agit de bien connaitre la machine et ses problèmes: protocole MESI, lignes de cache de 64 octets, accès aux variables optimisés par le compilateur, bus mémoire exclusif, etc... ne pas tomber dans les facilités non portables de visual studio genre "volatile"... (c'est pourquoi je recommande openMP a un débutant).
sinon boost::thread, comme tout le monde en attendant C++0x.