Hello !
 
Je suis en train de développer un code de programmation dynamique relativement simple, mais potentiellement très gourmand en temps de calcul. Une des pistes pour ne pas avoir à attendre la Saint Glin-Glin à chaque simulation est de paralléliser les calculs. Je ne me suis pas encore trop penché sur la question, mais l'algo a des propriétés qui rendent de manière évidente (j'exagère, il faut que je creuse) la solution envisageable. Bon, je n'ai jamais fait ça mais j'ai des connaissances de base, acquises pendant mes études mais jamais mises en pratique, en programmation multithreads et en parallélisme. Si je partais sur un code devant tourner sur un unique PC multi-processeurs je m'en sortirais en lisant lire beaucoup de docs et aussi en faisant appel à vous / à d'autres.
 
Mais le client dispose d'un "cluster". Non, pour l'instant je n'en sais pas plus, j'imagine que ce sont des Sun mais voilà tout. Pour moi ce ne doit être rien d'autre qu'un paquet de machines en réseau, avec un environnement uniforme et dédiées aux calculs parallèles et des demandes administratives de réservation de temps d'utilisation à faire. Je peux me tromper. Avant que je ne me renseigne + avant : sur un unique PC, c'est "simple", on lance des threads, on les coordonne et on les fait communiquer en mémoire. Sur plusieurs machines, un certain nombre de questions d'intendance se posent : comment coordonner, d'un point de vue technique, les calculs à travers le réseau ? En partageant des répertoires sur lesquels les machines poseraient/liraient des fichiers de données et de commande ? Par des "sockets" (là, je n'y connais rien) ? Y'a-t-il des frameworks implémentant les réponses à ce genre de questions et permettant de se concentrer surtout sur les questions algorithmiques ?
 
Bon, voilà, mes premières recherches Google&Wikipedia n'ont pas été très fructueuses. La question n'est pas ultra-urgente et je ferai des recherches plus complètes dans quelques semaines (et le client en question aura sûrement des infos), mais si des gens ici sont intéressés dès maintenant pour partager leur savoir, chouette ! Cela m'intéresse aussi à titre personnel, pour ma culture générale.
 
Dernières précisions :  
* je suis en C++ sous Windows/VC++ 6.0 pour l'instant, mais porter le code sous un autre langage/un autre environnement ne me poserait pas de problème si cela me fait gagner du temps. De toutes façons, ça finira sous Unix...
* pas de réponse "ne pourrais-tu pas utiliser d'autres algos / optimiser le tien ?" svp, je maîtrise bien cet aspect du problème et le contexte blablabla

Des implémentations de directives parallèles pour MPI ou OpenMP permettent de pas avoir à se poser toutes les questions que tu te poses (ou en tout cas beacoup moins). Les deux ont des libs libres pour C++ (m'étonnerait que ça se trouve sous win par contre).
Avant de t'enfoncer plus là-dedans, regarde ce qui est utilisé sur le calculateur. Il existe d'autres solutions, moins bas niveau, parfois plus exotique...

+1 pour MPI
 
OpenMP n'est à mon avis utile que si tu disposes déjà d'une implémentation séquentielle et que tu veux la paralléliser à peu de frais.

 
Merci à tous les 2, j'avais repéré OpenMP mais pas MPI. Et je suis d'accord avec l'avis qui consiste à voir d'abord ce qui existe chez le client. Je ne suis pas sûr qu'ils me laisseront débarquer avec ma solution, tout ça doit être quand même relativement sévèrement administré.
 
Par contre, je n'avais pas idée que le fait de disposer en premier lieu d'une implémentation séquentielle pouvait faire une différence, pour moi il fallait "tout" recoder de toutes façons. Du coup, cela à un intérêt de savoir avant de coder en séquentiel si ça va "passer" ou non. On va me prendre pour un boulet mais j'avoue que j'ai toujours développé en séquentiel sans me poser de question (i.e. sans calcul de complexité poussé) avec la sensation que cela allait bien se passer et je ne me suis jamais gaufré. Mais là, j'ai un doute.
 
Du coup, autre question : imaginons que je fasse le calcul de complexité dans le pire cas jusqu'au bout (c'est faisable). Si je vais vraiment dans le détail, je vais me retrouver avec un truc du genre : mon calcul prend au pire O(T^2log(N)) additions, O(N^2) multiplications, etc... Comment je passe à un vrai temps de calcul en secondes ? Je suis obligé de comparer à un autre code + ou - analogue dont je connais la complexité et sur lequel j'ai fait des mesures, ou existe-t-il des "tables de correspondance" ? Aucun prof ne m'a jamais appris ça en cours d'algorithmique, je regrette de ne pas avoir demandé à l'époque.
 
Edit : j'ai un peu peur, j'ai la sensation que la question est très bête, mais je ne vois pas pourquoi.

En fait, openMP te permet de simplement ajouter des directives de précompilation qui parallélisent très localement une partie de ton code (par exemple les itérations d'une boucle sont partagées et distribuées aux process). Donc un programme openMP est majoritairement séquentiel, avec certaines sections parallèles au milieu.
Si tu disposes déjà du code séquentiel, ça te permettra de le paralléliser sans y passer trop de temps : tu fais un peu de profiling et tu parallélises petit à petit les parties les plus coûteuses du calcul. L'inconvénient, c'est que tu atteinds vite les limites du modèle et d'un seul coup il devient très difficile de gagner en efficacité.
Du coup, si tu n'as pas encore écrit ton code, je te conseille de passer directement à MPI, qui demande un peu plus d'investissement, mais qui te permettra d'atteindre de meilleures performances.
 

En général, ce qui est intéressant avec les complexités, c'est de les comparer, ou bien de voir comment elles croissent avec la quantité de données. Le facteur multiplicatif qui te permet de prédire approximativement le temps de calcul effectif ne sert à rien dans ce cas.  
Ce n'est qu'une fois que tu fais tourner des benchmarks que tu sais quel est ton temps de calcul réel.