Remerciements

 

        L'aventure de ce mémoire n'aurait pu se dérouler sans les personnes suivantes, que je tiens à remercier vivement :

 

        Enfin, je serais ingrat d'oublier tous ceux et toutes celles dont le soutien m'aura permis de surmonter les nombreuses difficultés qui n'ont jamais manqué d'arriver aux mauvais moments. Je ne nommerai que ma mère et correctrice impartiale (encore merci pour les feutres de couleurs pour les graphes), mon stock de CD et mon casque, Yannick Sustrac (si tu lis ça, c'est que j'ai réussi à le faire, ce programme :-D), les Toriphiles (Michelle, Barb, Jessi), la faune du Bocal (Dominique), les poissons d'APRIL... Ce n'est pas parce que j'ai oublié le nom des autres que j'ai oublié leur aide. En fait j'ai tellement de personnes à remercier individuellement que je ne sais plus par où commencer et je ne voudrais pas faire de jaloux...

 

 

Résumé

 

        L'objet de ce mémoire est d'expliquer certains aspects importants pour la performance d'un programme de calcul intensif. Le cadre précis est un programme interactif de simulation d'écoulements de fluides, sur une plateforme de type Intel Pentium. Le but du travail exposé ici est d'améliorer autant que possible les performances de ce programme, tant en vitesse qu'en flexibilité et en utilisabilité des résultats des calculs.

        La fonction de ce programme est de faciliter et rendre accessibles ces calculs à des personnes a priori non spécialistes en informatique ou qui ne peuvent pas passer de temps à optimiser ce type de programmes.

        Même s'il ne peut pas être exhaustif, ce mémoire aborde des sujets très variés autant théoriques que pratiques qui contribuent chacun à améliorer la performance du programme : physique, mécanique des fluides, mécanique statistique, structure des ordinateurs et des processeurs, fonctionnement des systèmes d'exploitation, assembleur, calculs booléens, synthèse logique, compilation, algorithmique, périphériques et interfaces...

        Ce mémoire s'adresse aux informaticiens, dans la perspective d'améliorer leurs programmes pour les processeurs de la cinquième génération et au-delà, et aux physiciens, pour leur procurer un outil efficace d'exploration des gaz sur réseau. De nombreux autres domaines peuvent néanmoins bénéficier des points de vue discutés ici.

        Nous étudions principalement un cas simple sans la prétention d'apporter d'amélioration directe dans le domaine scientifique. Le modèle étudié (FHP) sert de base, ou est proche des modèles plus évolués (Bolzman par exemple) qui peuvent bénéficier des améliorations décrites ici.

 

 

Quelques Remarques sur ce document

 

        Ce mémoire a été rédigé directement en HTML dans un simple éditeur de texte, afin de faciliter sa diffusion électronique et sa maintenance sans outil spécialisé.

        Le texte a été formaté pour être transformé par HTMLDOC dans le format PDF avant impression, ce qui explique la curieuse présentation du fichier HTML dans un brouteur. HTMLDOC est un programme diffusé sous licence GPL. Il a été réalisé par Mike Sweet et diffusé gratuitement à http://www.easysw.com/htmldoc/. Il est possible de générer aussi du POSTSCRIPT en modifiant les paramètres d'appel de HTMLDOC ou les fichiers .book.

        Pour tout renseignement, contacter whygee@f-cpu.org. Ce mémoire est disponible en ligne sur le serveur du département MIME à l'adresse http://www.mime.univ-paris8.fr/~whygee/memoire. Il est diffusé dans l'espoir qu'il soit utile.

        Aucune garantie n'est possible pour la reproductibilité des résultats, le fonctionnement d'un programme, l'exactitude des affirmations ou des formules. Il est destiné à un public averti des contraintes et des limites des modèles physiques utilisés qui doivent être utilisés dans un cadre soigneusement contrôlé. Toutes les marques déposées appartiennent à leurs propriétaires respectifs. Les programmes utilisent des fonctions de bas niveau qui peuvent être indisponibles selon les systèmes.

 

        (C) Yann Guidon, 1995-2000

 

Révisions :
- Première impression : 13 septembre 2000 (5 exemplaires dont 4 avec annexes)
- Deuxième impression : 26 septembre 2000, 6 exemplaires et de nombreuses corrections

 

 

Table des matières

 

Chapitre page

 

 
Introduction1
 
Partie I : Spécificités du Calcul Intensif  "approche épistémologico-socio-économico-culturelle"3
    I.1 : Les nouveaux défis du calcul intensif3
    I.2 : Les images réalistes3
    I.3 : A propos de l'"optimisation"4
    I.4 : La montée des "PC"5
    I.5 : Les PC ne permettent pas de soutenir la performance de crête6
    I.6 : La convergence des algorithmes, des plateformes et des modèles8
    I.7 : La mentalité de l'optimisation8
    I.8 : Importance de l'interactivité9
    I.9 : Petit résumé10
 
Partie II : Présentation du modèle physique11
    II.1 : Introduction11
    II.2 : Nomenclature11
    II.3 : Génèse11
    II.4 : Un premier modèle : HPP12
    II.5 : Caractéristiques du modèle HPP13
    II.6 : Le modèle FHP14
    II.7 : Les règles et les nouvelles propriétés de FHP-115
    II.8 : Les améliorations de FHP-217
    II.9 : Caractéristiques particulières du modèle FHP-317
    II.10 : Propriétés physiques des modèles FHP18
    II.11 : Extensions diverses20
    II.12 : Conclusion21
 
Partie III : Présentation des travaux antérieurs23
    III.1 : Introduction23
    III.2 : Idées de base23
    III.3 : Les plans temporaires24
    III.4 : Premier code de référence27
    III.5 : Influence de l'architecture29
    III.6 : Deuxième code de référence30
    III.7 : Conditions aux limites et effets de bords33
    III.8 : Remplissage et redimensionnement dynamique du tunnel35
    III.9 : Etude d'un cas réel : benchmark de von Karman36
    III.10 : Conclusion38
 
Partie IV : Réalisation39
    IV.1 : Introduction39
    IV.2 : Intel : la plateforme idéale malgré elle39
    IV.3 : Description de l'algorithme de strip mining43
    IV.4 : Nouvelle structure des données et méthode de calcul47
    IV.5 : Implémentation des parois49
    IV.6 : Algorithme d'affichage51
    IV.7 : Analyse booléenne de l'opérateur de collision54
    IV.8 : Techniques de programmation58
    IV.9 : Réalisation et résultats64
 
Partie V : Plateformes dédiées67
    V.1 : Introduction67
    V.2 : RAP-168
    V.3 : CAM-869
    V.4 : EXA71
    V.5 : "Fourmi"72
    V.6 : Carte ISA73
    V.7 : Anneau de strip mining77
    V.8 : tableau de PAL78
    V.9 : Conclusion81
 
Conclusion83
    1 : Avancées pour le domaine des gaz sur réseaux83
        1.1 : Approche globale du problème83
        1.2 : Organisation des données84
        1.3 : Strip mining85
        1.4 : Parois complexes86
        1.5 : Programmation en assembleur86
        1.6 : Une nouvelle formule87
        1.7 : Intégration complète de l'algorithme de visualisation dans celui du calcul87
        1.8 : Mesurer son code88
    2 : Conclusions des expériences88
        2.1 : FHP-3 est memory bound et CPU bound sur x8688
        2.2 : Il est possible de descendre à 3 cycles par octets89
        2.3 : A condition d'effectuer de nombreux efforts, il est possible d'utiliser des PC pour des calculs lourds89
        2.4 : Un PC équivaut presque à une CAM889
        2.5 : La loi de Moore est trompeuse89
        2.6 : Le sujet des gaz sur réseaux booléens est loin d'être tari90
    3 : Sujets des recherches futures90
        3.1 : Mesurer la pression90
        3.2 : Emission de particules90
        3.3 : Multi-CPU91
        3.4 : Extension du code et du modèle91
        3.5 : Langage script91
        3.6 : Evolution de la plateforme91
    4 : Applications92
        4.1 : Acoustique92
        4.2 : Cryptographie92
        4.3 : Réalité Virtuelle / jeux vidéo93
        4.4 : Education93
        4.5 : Industrie93
    4.6 : Derniers mots sur les applications des LGA94
    5 : Limites du projet95
    6 : Et maintenant ?96
 
Ressources bibliographiques97
 
Liens105
 
Annexe A : Sources des programmesA.1
    A.1 : fichier RESIZE.PASA.2
    A.2 : fichier LABELS3.PASA.2
    A.3 : fichier SP73.ASMA.5
 
Annexe B : Article paru dans PascalissimeB.1
 
Annexe C : Journal de bordC.1
 
Annexe D : Etude comparative de codes sourcesD.1
    D.1 : Sous X11D.2
    D.2 : En CellangD.9
    D.3 : En FORTRAND.11
    D.4 : En CD.13
    D.5 : Toujours en CD.15
    D.6 : Dans un hypercube iPSCD.22
    D.7 : ConclusionD.25