lasher a écrit 2731 commentaires

Ben non. Comme on le dit plus bas, Cryptonomicon, malgré quelques fantaisies vaguement « cyberpunkesques », est plutôt cohérent et bien informé (en fait, la partie où Stephenson explique le principe du modulo et son importance en crypto serait à faire lire à n'importe quel lycéen en terminale S, pour lui faire une bonne intro).

De plus, pour donner un ordre d'idée, entre « Angel & Demons » / « The Da Vinci Code » et « Le pendule de Foucault », il y a un monde, et le côté ésotérique/érudit/recherche historique n'est certainement pas poussé de la même manière entre Brown et Eco ...

D'où ma question. Évidemment ce n'est pas un livre de crypto, mais est-il assez bien écrit pour que quelqu'un qui a l'habitude de lire des machins techniques, des romans de SF, etc., le trouve intéressant ?

En pratique, ce sont évidemment des gens qui savent de quoi ils parlent qui font les programmes. Mais quand il s'agit d'optimiser les codes, les numériciens ne sont pas nécessairement les plus à même de le faire, et là, les informaticiens (chercheurs et ingénieurs), qui eux maîtrisent la plate-forme sur laquelle s'exécute le code, entrent en scène.

Bon, Dan Brown, pour ce que j'ai lu de lui, m'a beaucoup déçu. Comment le situes-tu par rapport à un vrai bon livre qui parle crypto, à savoir « Cryptonomicon » de Neal Stephenson (un excellent roman), ou bien « Histoire des codes secrets » de Simon Sing (un bouquin à la narration bien foutue, qui explique les principales étapes de la crypto de l'antiquité à nos jours) ?

« contrairement à ce qu'affirme la SNCF, la prime de charbon existe encore, même les stagiaires y ont droit »

D'où tiens-tu cette information ? C'est vraiment énorme d'affirmer ça sans source, alors que tous ceux que je connais bossant à la SNCF (certes, ils ne sont pas nombreux) m'affirment le contraire, et que certains ont publié leurs fiches de paie, et que ça n'apparaît nulle part.

Hé dis, tu peux me dire à combien tu peux prétendre au bout de 10 ans de carrière en tant qu'ingénieur ? Juste pour rire. :-)

Tu veux dire à part faire péter des bombes ? Ben euh, à faire des simulations sismologiques (ben oui, une fois que la bombe a pété, faut bien déterminer l'impact - c'est le cas de le dire - au niveau sismique).

La loi de Moore ne parle que du doublement du nombre de transistors sur une même surface, pas de la puissance intrinsèque d'un processeur.

Par définition, Grid 5000 est une ... grille. Donc un ensemble de clusters distribués. Donc une « machine » pas du tout faite pour le même genre de résolution de problèmes que pour un supercalculateur. Les deux façons de fonctionner ont leur intérêt, mais ils ne jouent pas du tout sur les mêmes paramètres (comme tu l'as si bien fait remarquer, la latence change beaucoup la donne, et dans certains cas, si tu veux que ton programme ne passe que 2 semaines à calculer et pas 2 et demi, ... :-) ).

C'est tellement pris en compte qu'à une époque pas si éloignée, le scheduler de linux avait un léger problème : il migrait « automatiquement » des threads même quand il n'en avait pas besoin (heureusement depuis le comportement a été corrigé). Ça donnait quelque chose du genre :

cpu0 - thread 0 fait qq chose.
cpu1 - « rien » à faire.

[INT - on repasse dans l'ordonnanceur, qui s'aperçoit que cpu1 ne fait rien.]
sched: Bon, on va lui filer du boulot hein. Hey, thread 0, va donc sur cpu1 !
thread0 : Euh mais en fait, je bosse déjà sur cpu 0 moi.
sched : On ne discute pas ! On partage le travail ici, monsieur ! Il faut que tout le monde bosse la même charge ! Et n'oublie pas de remplir les formulaires de changement de bur^Wcontexte !
thread0 : OK chef.

[INT - cpu0 ne fout « rien »]
sched: Hey, thread 0, va donc bosser avec cpu0 !
thread 0 : hein ? Mais vous m'avez dit d'aller voir cpu1 !
sched: ON NE DISCUTE PAS !
thread 0 : bureaucrate à la con ...
[thread 0 change de contexte, avec remplissage des formulaires correspondants ...]

Blague à part, je ne fais que fixer un thread sur un processeur/coeur donné, rien de plus, rien de moins. L'ordonnanceur du noyau a tout loisir de préempter ce thread pour y faire passer un job de plus haute priorité s'il en a le besoin. En pratique c'est assez rare que ça arrive, parce que je bosse sur un cluster : je lance mon batch, ça attaque un noeud dont je connais par avance la topologie (important ça, parce que certains noeuds sont NUMA et d'autres non, ce qui change beaucoup la stratégie de parallélisation).

La première chose que fait l'openmp d'intel (qui n'est pas mal du tout, avec un overhead assez minime comparé à d'autres implémentations que je connais) c'est de spawner des pthreads (donc un « bête » pthread_create()) et de les fixer sur des processeurs, parce que l'objectif quand tu fais de la programmation parallèle, c'est d'optimiser à fond la localité des données, et de bien séparer les tâches/les ensemble de données sur lesquelles tu veux bosser.

Ta référence à « thread private », etc., n'est valable que pour OpenMP (qui peut être très bien hein, mais qui a aussi de sérieuses limitations).

« De plus, vu l'architecture Intel, le goulot d'étranglement doit rapidement être la RAM. »
Sur Montecito on a 12 Mo de cache L3, et une architecture plutôt très bien foutue dans le cas des calculs flottants et de calcul sur des flux de données. La bande-passante mémoire est plutôt bonne (de l'ordre de 10Gio/s), donc non, ce n'est pas particulièrement gênant.

Je crois que tu ne saisis pas bien la nature de mon travail, et les outils avec lesquels je bosse. :-) Les pthreads sont gérés par linux, mais par contre j'ai des threads de niveau utilisateur (ce qui revient peu ou prou à un ensemble de couples [pointeur de fonction, pointeur sur arguments à traiter]), qui ont donc un overhead quasi-nul pour mon calcul, mais que je peux affecter au thread noyau qui m'intéresse (et donc au processeur qui m'intéresse, puisque mes threads sont vissés sur un proc particulier). Ça me permet de faire des opérations très fines sur mes sections parallèles (et comme je suis au cycle près, j'ai besoin de ce niveau de contrôle, car même comme ça, il existe de nombreux effets indésirables qui peuvent survenir et qui sont difficiles à diagnostiquer : cache thrashing, faux partage, alignement des données ...).

Tout dépend de ce que tu appelles ordonnancement. Les threads noyaux sont ordonnancés par l'OS, sauf si tu lui demandes gentiment de faire autrement (en passant par les cpusets, en l'occurrence).

Les performances (au moins dans le cas du calcul scientifique) sont clairement meilleures lorsque les threads sont fixés sur un processeur, tout simplement parce qu'un changement de contexte sur un même processeur peut se faire à un coût relativement réduit, alors que migrer un thread d'un processeur à un autre implique la recopie (et donc très certainement de l'utilisation du bus mémoire) pour recopier l'intégralité du contexte d'exécution d'un thread.

D'autre part, je parle d'ordonnancement de threads utilisateur, et pas des threads noyaux en tant que tels (par définition, c'est le noyau qui décide de la préemption ou pas), si ce n'est pour cette histoire de fixer les threads sur un proc donné.

« Bref, si tu as une machine linux avec qq centaines de processeurs, je laisserais faire l'OS. »
Honnêtement, heureusement que les gens ne t'écoutent pas sur les centres de calcul :-)

Migration de thread d'un proc à l'autre => transfert du contexte (comme dit précédemment), mais aussi pollution des caches, et en cas de modèle NUMA, accès distant à la RAM, ou alors overhead dû à la nécessité de recopier les pages mémoire vers la nouvelle mémoire locale ...

« Je n'imagine pas faire du scheduling à la main pour des raisons de "thoughput" (de bande passante), »

Si je fais de l'ordonnancement statique, c'est entre autres parce que la façon dont mes threads utilisateur sont ordonancés, j'ai une pollution plus ou moins grande des caches entre les processeurs (par exemple, l'ensemble de données sur lequel je bosse est subdivisé en sous-ensembles plus élémentaires et indépendants, mais suivant la façon dont je fais ma découpe, les différents threads vont potentiellement écrire dans les mêmes lignes de cache, et du coup un gros traffic va être mis en oeuvre pour régler la cohérence, ce qui n'arrive pas si je fais travailler mes threads sur des portions de données qui n'entrent pas en conflit dans les caches). Comme j'ai des E/S quasi-nulles, c'est le fait de devoir sortir de mes caches qui est le facteur le plus limitant (et quand tu multiplies des matrices, du genre (5000,128)x(128,5000), ça prend un certain temps. Pour te donner un ordre d'idée, en changeant ma façon d'ordonnancer les threads, je suis passé de 8-10 GFLOPS sur 4 coeurs itanium 2 à 18-22 GFLOPS (sur les 25,2 théoriques).

Hep au fait, Briaeros007. Tu te souviens du long fil où nous étions empoignés à propos de l'attente active sur une variable volatile ? J'ai enfin eu le fin mot de l'histoire. Nous avions tous les deux raisons (enfin j'avais un peu plus tort, vu que je n'avais raison que sur mon cas particulier).

Donc, quand on déclare une variable « volatile » sur Itanium 2, en pratique le compilateur génère des instructions qui garantissent que l'ordre d'accès des lectures et écritures est conservé (en gros, il s'agit d'une sorte de « acquire » suivi d'un « release »), ce qui permet de faire du busy wait bête et méchant (évidemment, ça n'empêche pas d'affamer des threads en cas d'activation de l'hyperthreading sur montecito).

En l'occurrence pour Tera 10, la consommation électrique est de l'ordre de 2MW uniquement pour le cluster, auxquels il faut rajouter 1,7MW pour le refroidissement si je ne m'abuse.

Concernant ta remarque sur l'utilité des clusters : si on excepte les simulations d'explosion nucléaire (après tout, on parle du cluster du CEA/DAM - Direction des Applications Militaires), il ne faut pas oublier tout ce qui a trait à la sismologie et aux applications industrielles (le cluster sert quand même avant tout à faire de la simulation numérique, qu'on parle de machins nucléaires ou pas).

Oui, il s'agit de problèmes d'ordonnancement, mais c'est quelque chose d'extrêmement important quand on parle processus/threads, tu en conviendras.

Maintenant non, je n'ai pas besoin de temps réel, mais le vol de tâche permet d'équilibrer la charge de calcul sur une machine parallèle.

Typiquement, dans un cas tu dois prévoir avec un ordonnancement statique l'intégralité d'une section parallèle car tu veux que la charge soit bien équilibrée sur tous les threads/coeurs/processeurs (sans parler de la gestion des mémoires plus ou moins locales) ; dans l'autre, tu dois quand même équilibrer correctement au début, mais ensuite, tu peux éventuellement continuer à rajouter des jobs dans les queues (en essayant quand même d'équilibrer la charge entre les processeurs), mais si un thread/processeur se retrouve à court de boulot dans sa liste de tâches, il peut toujours aller voir dans les listes de tâches des threads voisins, et leur piquer leur boulot (ce qui soulage un thread d'une tâche, et permet de mieux utiliser les unités fonctionnelles de la totalité de la machine parallèle).

C'est assez drôle, parce que ça ressemble beaucoup à ce que nous faisons : nous avons un prototype de bibliothèque à 2 niveaux, où les threads utilisateur sont en fait une liste de tâches à accomplir par thread noyau (ce dernier étant « vissé » sur un processeur).

Une extension non standard dans l'implémentation OpenMP d'intel a un peu la même façon de procéder.

Bref, ça me semble plutôt bien, vu que j'utilise approximativement la même méthode. ;-)

En fait le seul problème pour ce que j'ai lu de COP (qui est aussi une limitation de notre implémentation aussi), c'est qu'il n'y a absolument aucune préemption (dans le cadre du calcul scientifique c'est plutôt bien), ni de possibilité de vol de tâche (et ça par contre, c'est potentiellement moins bien). Mais comme je n'ai pas lu jusqu'au bout, peut-être que je me trompe. :-)

Oui d'ailleurs, il serait temps que tu te décides à m'envoyer un mail et qu'on aille prendre une bière pour parler geekeries. Si si.

Un programme OpenMP tu fais juste un
#pragma omp parallel for
(avec éventuellement quelques ajouts pour dire ce qui doit être privatisé, public, les chunks en termes d'itérations à faire, quelles variables servent à faire des réductions, etc), alors qu'un programme MPI doit explicitement déclarer toutes ses communications, et donc le programmeur effectue nécessairement bien plus de boulot à lui tout seul.

Le problème avec OpenMP, c'est qu'on a nécessairement une barrière implicite à la fin d'une section parallèle. On peut tenter de s'en dépatouiller en utilisant « nowait » comme mot-clef dans certains cas, mais cela ne fait que retarder le moment où il faudra synchroniser les accès.

Le problème avec MPI, c'est qu'en plus d'avoir à tout faire à la main, je ne connais pour le moment aucune implémentation qui soit thread-safe ET efficace.

À mon avis, il faut un peu plus chercher du côté d'OpenMP, et revenir à des bibliothèques de threads à deux niveaux (MxN), où on fixe des threads noyau sur les coeurs/processeurs, et où on spawne des threads utilisateur à chaque nouvelle section parallèle (ce qui permettrait peut-être de « coller » au modèle fork/join d'OpenMP, tout en ayant un overhead minimal, et en assurant une possibilité d'avoir des « sections parallèles récursives »).

MPI est super efficace, mais bien trop contraignant à mon goût.

C'est pas exactement ça de ce que je crois me rappeler. Dans mes souvenirs c'est l'architecture de l'Itanium qui s'amuse à respecter (ou pas) les conventions IEEE (arrondis, etc.). Et en pratique, que ce soit avec ifort ou icc, il existe bien un flag pour activer ou pas la « simplification » (il faudrait que je redemande à des gens plus au courant que moi).

Je bosse sur de gros calculateurs, et je fais du C tous les jours (et j'aime ça, oOoOoh oui, tripoter la pile de mes threads, AHHHHHHHHHHHH).

N'empêche que pas mal de problèmes parallélisables sont bien plus facilement exprimés en termes fonctionnels qu'impératifs. Si on rajoute les bons mots clef aux langages (impératifs ou fonctionnels) pour gérer une forme explicite de parallélisme, je pense qu'on peut faire de très jolies choses (cf Erlang, par exemple, même s'il induit trop de synchros pour le genre de calculs que je fais).

Dans le cas de Earth Simulator, le bâtiment était prévu exprès pour pouvoir récupérer l'air chaud et le refaire circuler dans mes souvenirs. Mais bien sûr, je peux me tromper.

« soit g95 est vraiment (très très très très)^50 mauvais. »
Ben oui. Il faudrait tester avec ifort (le compilateur d'Intel), mais en l'occurrence, g95 était loin d'être un foudre de guerre en termes d'optimisation ...

C'est ce qui est fait pour les calculateurs du genre de Blue Gene, ou Earth Simulator : on essaie de récupérer l'air chaud, de le faire circuler dans le bâtiment où se trouve le calculateur, afin de le refroidir, et de le « réinjecter » afin d'économiser un peu en refroidissement.

Les deux mon capitaine. J'entends beaucoup parler de l'utilisation de différents langages pour tout plein de choses dans le domaine du calcul scientifique (notamment l'utilisation de certains langages fonctionnels), mais au final malheureusement, la plupart des langages offrent des performances vraiment moins bonnes que des langages intrinsèquement peu sûrs (genre C ou FORTRAN).

Après, tout dépend de l'application qu'on veut faire. Je dirais que, mis à part le calcul scientifique, ou en tout cas les noyaux de calcul ou la conception d'OS, il serait de bon ton de lâcher le plus possible des langages tels que C ou FORTRAN, car ils sont (enfin je trouve) extrêmement difficiles à maîtriser correctement.

Pour ceux que la prog fonctionnelle ne gêne pas, programmer avec OCaml permet d'obtenir de très bonnes perfs tout en ayant un système de vérification des types extrêmement bon (et le pattern matching de code est un super outil). Pour les autres, tout dépend de ce qu'on veut faire, mais je trouve que les langages dits de 4è génération sont plutôt bons et permettent d'éviter pas mal d'erreurs car le code est simple à écrire et à relire (beaucoup plus simple qu'en C/C++/FORTRAN/etc).

Enfin, ce n'est que mon avis. :)

Euh, déjà, Ada est fortement typé (tout comme OCaml, d'ailleurs -- je crois que c'est le cas aussi pour Haskell, mais je ne suis pas sûr). Donc tout comme pour les langages dont tu parles, énormément de vérifications sont possibles à la compilation.

De plus, même si j'aime beaucoup les langages fonctionnels [1], il n'en demeure pas moins que la machine, elle, reste bêtement impérative dans son fonctionnement et son architecture. Vouloir à tout prix passer par du fonctionnel n'est pas toujours la bonne idée.

[1] Serait-ce une sorte de syndrôme de Stockholm ? :-)

Euh. Le fait est que l'utilisation de FORTRAN tient à plusieurs choses, mais 3 retiennent particulièrement mon attention :

1/ Beaucoup des bibliothèques d'analyse numérique ont leur API en FORTRAN [1], ce qui force le programmeur/utilisateur à comprendre un minimum comment fonctionne ce langage (et dans le cas de pas mal de numériciens et physiciens, ils ont carrément appris la programmation avec ce langage, car il permet certaines constructions très pratiques qui n'existent pas nativement en C, comme par exemple les instructions vectorielles « natives »).

2/ En F77, comme il n'y a pas de pointeur, il n'y a aucun risque d'aliasing, c'est-à-dire de pointeurs différents dont les zones mémoires pointées se recouvriraient. C'est une propriété extrêmement importante en ce qui concerne les transformations optimisantes qu'un compilateur peut appliquer sur un code.
Avec FORTRAN 90 et ses successeurs, il est toujours possible de signaler qu'il n'y a pas de recouvrement de zones mémoires (tout comme en C avec certains compilateurs d'ailleurs), mais là ça devient la responsabilité du programmeur de s'en assurer a priori.

Comme je l'ai dit précédemment, on a aussi la présence d'instructions « vectorielles », qui permettent d'effectuer une même opération entre deux tableaux, de façon transparente, et qui simplifie du coup énormément l'écriture de programmes.

3/ À cause de 1/ et 2/, le FORTRAN se prête déjà bien à tout ce qui est analyse numérique, mais tout ça, on pourrait certainement le dire avec Haskell ou LISP, en effet. Ce qui différencie FORTRAN du reste des langages, c'est qu'en plus, il est, tout comme le C, proche de la machine, ce qui est extrêmement important.

Enfin, une petite remarque : FORTRAN est lui aussi « issu des maths ». :-)

[1] Ce qui est gênant, car il m'arrive de voir parfois des implémentations en f77 qui sont sémantiquement correctes, mais à des années lumières de l'optimisation souhaitée pour les architectures actuelles.

C'eut été sympa de commenter ton code, histoire de comprendre ce que tu faisais.