\@writefile{lof}{\select@language{french}}\r
\@writefile{lot}{\select@language{french}}\r
\@writefile{toc}{\contentsline {part}{I\hspace {1em}PARTIE I: Contexte scientifique et revue de l'\IeC {\'e}tat de l'art}{3}{part.1}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {1}Cadre de travail et contexte scientifique}{5}{chapter.1}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {1}Cadre de travail et contexte scientifique}{7}{chapter.1}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {1.1}Classe des algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les \IeC {\`a} large \IeC {\'e}chelle dans une grille de calcul}{5}{section.1.1}}\r
-\newlabel{eq:1}{{1.1}{5}{Classe des algorithmes itératifs parallèles à large échelle dans une grille de calcul}{equation.1.1.1}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.1.1}Partitionnement du probl\IeC {\`e}me}{6}{subsection.1.1.1}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.1}{\ignorespaces D\IeC {\'e}coupage d'une matrice tridimensionnelle entre deux clusters form\IeC {\'e}s de 18 processeurs chacun}}{6}{figure.1.1}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.2}{\ignorespaces D\IeC {\'e}composition en domaines 1D, 2D et 3D}}{6}{figure.1.2}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.1.2}Modes d'ex\IeC {\'e}cution synchrone et asynchrone}{7}{subsection.1.1.2}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.3}{\ignorespaces Mod\IeC {\`e}le de communication synchrone}}{8}{figure.1.3}}\r
-\newlabel{fig:sync}{{1.3}{8}{Modèle de communication synchrone}{figure.1.3}{}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {1.1}Classe des algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les \IeC {\`a} large \IeC {\'e}chelle dans une grille de calcul}{7}{section.1.1}}\r
+\newlabel{eq:1}{{1.1}{7}{Classe des algorithmes itératifs parallèles à large échelle dans une grille de calcul}{equation.1.1.1}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.1.1}Partitionnement du probl\IeC {\`e}me}{8}{subsection.1.1.1}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.1}{\ignorespaces D\IeC {\'e}coupage d'une matrice tridimensionnelle entre deux clusters form\IeC {\'e}s de 18 processeurs chacun}}{8}{figure.1.1}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.2}{\ignorespaces D\IeC {\'e}composition en domaines 1D, 2D et 3D}}{8}{figure.1.2}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.1.2}Modes d'ex\IeC {\'e}cution synchrone et asynchrone}{9}{subsection.1.1.2}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.3}{\ignorespaces Mod\IeC {\`e}le de communication synchrone}}{9}{figure.1.3}}\r
\@writefile{lof}{\contentsline {figure}{\numberline {1.4}{\ignorespaces Mod\IeC {\`e}le de communication asynchrone}}{9}{figure.1.4}}\r
-\newlabel{fig:async}{{1.4}{9}{Modèle de communication asynchrone}{figure.1.4}{}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {1.2}M\IeC {\'e}thodes de r\IeC {\'e}solution parall\IeC {\`e}les du probl\IeC {\`e}me de Poisson et de l'algorithme two-stage multisplitting de Krylov}{9}{section.1.2}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{9}{subsection.1.2.1}}\r
-\newlabel{eq:2}{{1.8}{9}{Algorithme de Jacobi}{equation.1.2.8}{}}\r
-\newlabel{eq:3}{{1.9}{10}{Algorithme de Jacobi}{equation.1.2.9}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{10}{subsection.1.2.2}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{11}{figure.1.5}}\r
-\newlabel{algo:01}{{1.5}{11}{Algorithme itératif de Jacobi}{figure.1.5}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{11}{subsection.1.2.3}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {1.3}Simulateurs d'ex\IeC {\'e}cution d'algorithmes parall\IeC {\`e}les MPI dans une grille de calcul}{11}{section.1.3}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{11}{subsection.1.3.1}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.6}{\ignorespaces Architecture d'une grille de calcul}}{12}{figure.1.6}}\r
-\newlabel{fig:gridA}{{1.6}{12}{Architecture d'une grille de calcul}{figure.1.6}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.7}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{13}{figure.1.7}}\r
-\newlabel{fig:grid5000RG}{{1.7}{13}{Grid'5000 : Répartition géographique}{figure.1.7}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{13}{subsection.1.3.2}}\r
-\newlabel{eqsim}{{1.11}{14}{Généralités sur la simulation}{equation.1.3.11}{}}\r
-\@writefile{lot}{\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{15}{table.1.1}}\r
-\newlabel{table1}{{1.1}{15}{Quelques outils de simulation pour une grille de calcul}{table.1.1}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{15}{subsection.1.3.3}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.8}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{16}{figure.1.8}}\r
-\newlabel{fig:MPI}{{1.8}{16}{Groupes et communicateur (a) - MPI - Opérations collectives (b)}{figure.1.8}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{17}{subsection.1.3.4}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {1.9}{\ignorespaces SIMGRID : Les \IeC {\'e}l\IeC {\'e}ments de la plateforme de simulation}}{18}{figure.1.9}}\r
-\newlabel{fig:simgrid1}{{1.9}{18}{SIMGRID : Les éléments de la plateforme de simulation}{figure.1.9}{}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {1.4}Conclusion partielle}{19}{section.1.4}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{21}{chapter.2}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {1.2}M\IeC {\'e}thodes de r\IeC {\'e}solution parall\IeC {\`e}les du probl\IeC {\`e}me de Poisson et de l'algorithme two-stage multisplitting de Krylov}{10}{section.1.2}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{10}{subsection.1.2.1}}\r
+\newlabel{eq:2}{{1.8}{10}{Algorithme de Jacobi}{equation.1.2.8}{}}\r
+\newlabel{eq:3}{{1.9}{11}{Algorithme de Jacobi}{equation.1.2.9}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{11}{subsection.1.2.2}}\r
+\newlabel{eq:Krylov}{{1.11}{11}{Méthode de résolution GMRES}{equation.1.2.11}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{12}{figure.1.5}}\r
+\newlabel{algo:01}{{1.5}{12}{Algorithme itératif de Jacobi}{figure.1.5}{}}\r
+\newlabel{eq:residu}{{1.12}{12}{Méthode de résolution GMRES}{equation.1.2.12}{}}\r
+\newlabel{eq:proj}{{1.13}{12}{Méthode de résolution GMRES}{equation.1.2.13}{}}\r
+\newlabel{eq:residu}{{1.14}{12}{Méthode de résolution GMRES}{equation.1.2.14}{}}\r
+\newlabel{eq:hessen}{{1.15}{12}{Méthode de résolution GMRES}{equation.1.2.15}{}}\r
+\newlabel{eq:hessen1}{{1.16}{13}{Méthode de résolution GMRES}{equation.1.2.16}{}}\r
+\newlabel{eq:residu1}{{1.2.2}{13}{Méthode de résolution GMRES}{equation.1.2.16}{}}\r
+\newlabel{eq:norme1}{{1.2.2}{13}{Méthode de résolution GMRES}{equation.1.2.16}{}}\r
+\newlabel{eq:norme2}{{1.17}{13}{Méthode de résolution GMRES}{equation.1.2.17}{}}\r
+\newlabel{eq:q_1}{{1.18}{13}{Méthode de résolution GMRES}{equation.1.2.18}{}}\r
+\newlabel{eq:q1}{{1.2.2}{13}{Méthode de résolution GMRES}{equation.1.2.18}{}}\r
+\newlabel{eq:q_1j}{{1.2.2}{13}{Méthode de résolution GMRES}{equation.1.2.18}{}}\r
+\newlabel{eq:q_f}{{1.19}{13}{Méthode de résolution GMRES}{equation.1.2.19}{}}\r
+\newlabel{eq:norme3}{{1.20}{13}{Méthode de résolution GMRES}{equation.1.2.20}{}}\r
+\newlabel{eq:proj1}{{1.2.2}{13}{Méthode de résolution GMRES}{equation.1.2.20}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.6}{\ignorespaces Algorithme it\IeC {\'e}ratif GMRES avec red\IeC {\'e}marrage}}{14}{figure.1.6}}\r
+\newlabel{algo:02}{{1.6}{14}{Algorithme itératif GMRES avec redémarrage}{figure.1.6}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{14}{subsection.1.2.3}}\r
+\newlabel{eq:13bis}{{1.21}{15}{Solveur multisplitting}{equation.1.2.21}{}}\r
+\newlabel{eq:13}{{1.22}{15}{Solveur multisplitting}{equation.1.2.22}{}}\r
+\newlabel{eq:14}{{1.23}{15}{Solveur multisplitting}{equation.1.2.23}{}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {1.3}Simulateurs d'ex\IeC {\'e}cution d'algorithmes parall\IeC {\`e}les dans une grille de calcul}{15}{section.1.3}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille de calcul}{15}{subsection.1.3.1}}\r
+\newlabel{algo:03:send}{{6}{16}{Solveur multisplitting}{equation.1.2.23}{}}\r
+\newlabel{algo:03:recv}{{7}{16}{Solveur multisplitting}{equation.1.2.23}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.7}{\ignorespaces Solveur Multisplitting utilisant la m\IeC {\'e}thode GMRES en local (version parall\IeC {\`e}le)}}{16}{figure.1.7}}\r
+\newlabel{algo:03}{{1.7}{16}{Solveur Multisplitting utilisant la méthode GMRES en local (version parallèle)}{figure.1.7}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.8}{\ignorespaces Architecture d'une grille de calcul}}{17}{figure.1.8}}\r
+\newlabel{fig:gridA}{{1.8}{17}{Architecture d'une grille de calcul}{figure.1.8}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{17}{subsection.1.3.2}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.9}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{18}{figure.1.9}}\r
+\newlabel{fig:grid5000RG}{{1.9}{18}{Grid'5000 : Répartition géographique}{figure.1.9}{}}\r
+\newlabel{eqsim}{{1.24}{18}{Généralités sur la simulation}{equation.1.3.24}{}}\r
+\@writefile{lot}{\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{19}{table.1.1}}\r
+\newlabel{table1}{{1.1}{19}{Quelques outils de simulation pour une grille de calcul}{table.1.1}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{19}{subsection.1.3.3}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.10}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{20}{figure.1.10}}\r
+\newlabel{fig:MPI}{{1.10}{20}{Groupes et communicateur (a) - MPI - Opérations collectives (b)}{figure.1.10}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{21}{subsection.1.3.4}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {1.11}{\ignorespaces SIMGRID : Les \IeC {\'e}l\IeC {\'e}ments de la plateforme de simulation}}{22}{figure.1.11}}\r
+\newlabel{fig:simgrid1}{{1.11}{22}{SIMGRID : Les éléments de la plateforme de simulation}{figure.1.11}{}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {1.4}Conclusion partielle}{23}{section.1.4}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{25}{chapter.2}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{21}{section.2.1}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{21}{subsection.2.1.1}}\r
-\newlabel{eq:5}{{2.1}{21}{Performance de l'application parallèle et scalabilité}{equation.2.1.1}{}}\r
-\newlabel{eq:6}{{2.2}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.2}{}}\r
-\newlabel{eq:7}{{2.3}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.3}{}}\r
-\newlabel{eq:8}{{2.4}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.4}{}}\r
-\newlabel{eq:9}{{2.5}{23}{Performance de l'application parallèle et scalabilité}{equation.2.1.5}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{23}{subsection.2.1.2}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{23}{subsection.2.1.3}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{24}{figure.2.1}}\r
-\newlabel{fig:scaling}{{2.1}{24}{Weak vs Strong scaling: Temps d'exécution et Speedup}{figure.2.1}{}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {2.2}Probl\IeC {\'e}matique sur la pr\IeC {\'e}diction \IeC {\`a} large \IeC {\'e}chelle de la performance des applications}{24}{section.2.2}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{25}{subsection.2.2.1}}\r
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{26}{subsubsection.2.2.1.1}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{27}{figure.2.2}}\r
-\newlabel{fig:cpumulti}{{2.2}{27}{Architecture des CPU multicoeurs}{figure.2.2}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{28}{figure.2.3}}\r
-\newlabel{fig:MIMDDM}{{2.3}{28}{Modèle MIMD Distribué}{figure.2.3}{}}\r
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{28}{subsubsection.2.2.1.2}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{29}{figure.2.4}}\r
-\newlabel{fig:MIMDSM}{{2.4}{29}{Modèle MIMD partagé}{figure.2.4}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{30}{figure.2.5}}\r
-\newlabel{fig:MIMDHY}{{2.5}{30}{Modèle MIMD hybride}{figure.2.5}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{31}{figure.2.6}}\r
-\newlabel{fig:power}{{2.6}{31}{Evolution de la puissance de calcul mondiale}{figure.2.6}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{32}{figure.2.7}}\r
-\newlabel{fig:UMA}{{2.7}{32}{Mémoire MIMD: Architecture UMA}{figure.2.7}{}}\r
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{32}{subsubsection.2.2.1.3}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{32}{subsection.2.2.2}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{33}{figure.2.8}}\r
-\newlabel{fig:NUMA}{{2.8}{33}{Mémoire MIMD: Architecture NUMA}{figure.2.8}{}}\r
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{33}{subsubsection.2.2.2.1}}\r
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{33}{subsubsection.2.2.2.2}}\r
-\newlabel{eq:10}{{2.6}{33}{Performance de la parallélisation}{equation.2.2.6}{}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{34}{figure.2.9}}\r
-\newlabel{fig:COMA}{{2.9}{34}{Mémoire MIMD: Architecture COMA}{figure.2.9}{}}\r
-\newlabel{eq:11}{{2.7}{34}{Performance de la parallélisation}{equation.2.2.7}{}}\r
-\newlabel{eq:12}{{2.8}{34}{Performance de la parallélisation}{equation.2.2.8}{}}\r
-\newlabel{eq:12}{{2.9}{35}{Performance de la parallélisation}{equation.2.2.9}{}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{36}{section.2.3}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{36}{subsection.2.3.1}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{36}{subsection.2.3.2}}\r
-\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{37}{figure.2.10}}\r
-\newlabel{fig:anaperf}{{2.10}{37}{Classification des techniques d'analyse de la performance}{figure.2.10}{}}\r
-\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{38}{subsection.2.3.3}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {2.4}M\IeC {\'e}thodes de pr\IeC {\'e}diction de la performance des applications parall\IeC {\`e}les}{39}{section.2.4}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {2.5}Conclusion partielle}{39}{section.2.5}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {3}Motivations}{41}{chapter.3}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{25}{section.2.1}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{25}{subsection.2.1.1}}\r
+\newlabel{eq:5}{{2.1}{25}{Performance de l'application parallèle et scalabilité}{equation.2.1.1}{}}\r
+\newlabel{eq:6}{{2.2}{26}{Performance de l'application parallèle et scalabilité}{equation.2.1.2}{}}\r
+\newlabel{eq:7}{{2.3}{26}{Performance de l'application parallèle et scalabilité}{equation.2.1.3}{}}\r
+\newlabel{eq:8}{{2.4}{26}{Performance de l'application parallèle et scalabilité}{equation.2.1.4}{}}\r
+\newlabel{eq:9}{{2.5}{27}{Performance de l'application parallèle et scalabilité}{equation.2.1.5}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{27}{subsection.2.1.2}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{27}{subsection.2.1.3}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{27}{figure.2.1}}\r
+\newlabel{fig:scaling}{{2.1}{27}{Weak vs Strong scaling: Temps d'exécution et Speedup}{figure.2.1}{}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {2.2}Probl\IeC {\'e}matique sur la pr\IeC {\'e}diction \IeC {\`a} large \IeC {\'e}chelle de la performance des applications}{28}{section.2.2}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{29}{subsection.2.2.1}}\r
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{30}{subsubsection.2.2.1.1}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{31}{figure.2.2}}\r
+\newlabel{fig:cpumulti}{{2.2}{31}{Architecture des CPU multicoeurs}{figure.2.2}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD M\IeC {\'e}moire Distribu\IeC {\'e}}}{32}{figure.2.3}}\r
+\newlabel{fig:MIMDDM}{{2.3}{32}{Modèle MIMD Mémoire Distribué}{figure.2.3}{}}\r
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{32}{subsubsection.2.2.1.2}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD M\IeC {\'e}moire partag\IeC {\'e}}}{33}{figure.2.4}}\r
+\newlabel{fig:MIMDSM}{{2.4}{33}{Modèle MIMD Mémoire partagé}{figure.2.4}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{34}{figure.2.5}}\r
+\newlabel{fig:MIMDHY}{{2.5}{34}{Modèle MIMD hybride}{figure.2.5}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{35}{figure.2.6}}\r
+\newlabel{fig:power}{{2.6}{35}{Evolution de la puissance de calcul mondiale}{figure.2.6}{}}\r
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{35}{subsubsection.2.2.1.3}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{35}{subsection.2.2.2}}\r
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{35}{subsubsection.2.2.2.1}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{36}{figure.2.7}}\r
+\newlabel{fig:UMA}{{2.7}{36}{Mémoire MIMD: Architecture UMA}{figure.2.7}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{36}{figure.2.8}}\r
+\newlabel{fig:NUMA}{{2.8}{36}{Mémoire MIMD: Architecture NUMA}{figure.2.8}{}}\r
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{36}{subsubsection.2.2.2.2}}\r
+\newlabel{eq:10}{{2.6}{36}{Performance de la parallélisation}{equation.2.2.6}{}}\r
+\newlabel{eq:11}{{2.7}{36}{Performance de la parallélisation}{equation.2.2.7}{}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{37}{figure.2.9}}\r
+\newlabel{fig:COMA}{{2.9}{37}{Mémoire MIMD: Architecture COMA}{figure.2.9}{}}\r
+\newlabel{eq:12}{{2.8}{37}{Performance de la parallélisation}{equation.2.2.8}{}}\r
+\newlabel{eq:12}{{2.9}{37}{Performance de la parallélisation}{equation.2.2.9}{}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{38}{section.2.3}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{38}{subsection.2.3.1}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{39}{subsection.2.3.2}}\r
+\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{39}{figure.2.10}}\r
+\newlabel{fig:anaperf}{{2.10}{39}{Classification des techniques d'analyse de la performance}{figure.2.10}{}}\r
+\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{41}{subsection.2.3.3}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {2.4}M\IeC {\'e}thodes de pr\IeC {\'e}diction de la performance des applications parall\IeC {\`e}les}{41}{section.2.4}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {2.5}Conclusion partielle}{43}{section.2.5}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {3}Motivations}{45}{chapter.3}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{43}{part.2}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {4}Comparaison par simulation \IeC {\`a} large \IeC {\'e}chelle de la performance de deux algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les en mode asynchrone}{45}{chapter.4}}\r
+\@writefile{toc}{\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{47}{part.2}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {4}Comparaison par simulation \IeC {\`a} large \IeC {\'e}chelle de la performance de deux algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les en mode asynchrone}{49}{chapter.4}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{45}{section.4.1}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{45}{section.4.2}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {4.3}Conclusion partielle}{45}{section.4.3}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {5}Simulation avec SIMGRID de l\textquoteright ex\IeC {\'e}cution des solveurs lin\IeC {\'e}aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\IeC {\'e}s}{47}{chapter.5}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{49}{section.4.1}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{49}{section.4.2}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {4.3}Conclusion partielle}{49}{section.4.3}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {5}Simulation avec SIMGRID de l\textquoteright ex\IeC {\'e}cution des solveurs lin\IeC {\'e}aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\IeC {\'e}s}{51}{chapter.5}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{47}{section.5.1}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{47}{section.5.2}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {5.3}Conclusion partielle}{47}{section.5.3}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {6}Mod\IeC {\`e}le de pr\IeC {\'e}diction de la performance \IeC {\`a} large \IeC {\'e}chelle d'un algorithme it\IeC {\'e}ratif parall\IeC {\`e}le}{49}{chapter.6}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{51}{section.5.1}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{51}{section.5.2}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {5.3}Conclusion partielle}{51}{section.5.3}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {6}Mod\IeC {\`e}le de pr\IeC {\'e}diction de la performance \IeC {\`a} large \IeC {\'e}chelle d'un algorithme it\IeC {\'e}ratif parall\IeC {\`e}le}{53}{chapter.6}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{49}{section.6.1}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{49}{section.6.2}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {6.3}Conclusion partielle}{49}{section.6.3}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{51}{chapter.7}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{53}{section.6.1}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{53}{section.6.2}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {6.3}Conclusion partielle}{53}{section.6.3}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{55}{chapter.7}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{51}{section.7.1}}\r
-\@writefile{toc}{\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{51}{section.7.2}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{55}{section.7.1}}\r
+\@writefile{toc}{\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{55}{section.7.2}}\r
\bibstyle{phdthesisapa}\r
\bibdata{biblio.bib}\r
-\@writefile{toc}{\contentsline {part}{III\hspace {1em}Annexes}{65}{part.3}}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{67}{appendix.A}}\r
+\@writefile{toc}{\contentsline {part}{III\hspace {1em}Annexes}{69}{part.3}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{71}{appendix.A}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
-\@writefile{toc}{\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{69}{appendix.B}}\r
+\@writefile{toc}{\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{73}{appendix.B}}\r
\@writefile{lof}{\addvspace {10\p@ }}\r
\@writefile{lot}{\addvspace {10\p@ }}\r
\select@language {french}\r
\addvspace {10\p@ }\r
-\contentsline {figure}{\numberline {1.1}{\ignorespaces D\IeC {\'e}coupage d'une matrice tridimensionnelle entre deux clusters form\IeC {\'e}s de 18 processeurs chacun}}{6}{figure.1.1}\r
-\contentsline {figure}{\numberline {1.2}{\ignorespaces D\IeC {\'e}composition en domaines 1D, 2D et 3D}}{6}{figure.1.2}\r
-\contentsline {figure}{\numberline {1.3}{\ignorespaces Mod\IeC {\`e}le de communication synchrone}}{8}{figure.1.3}\r
+\contentsline {figure}{\numberline {1.1}{\ignorespaces D\IeC {\'e}coupage d'une matrice tridimensionnelle entre deux clusters form\IeC {\'e}s de 18 processeurs chacun}}{8}{figure.1.1}\r
+\contentsline {figure}{\numberline {1.2}{\ignorespaces D\IeC {\'e}composition en domaines 1D, 2D et 3D}}{8}{figure.1.2}\r
+\contentsline {figure}{\numberline {1.3}{\ignorespaces Mod\IeC {\`e}le de communication synchrone}}{9}{figure.1.3}\r
\contentsline {figure}{\numberline {1.4}{\ignorespaces Mod\IeC {\`e}le de communication asynchrone}}{9}{figure.1.4}\r
-\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{11}{figure.1.5}\r
-\contentsline {figure}{\numberline {1.6}{\ignorespaces Architecture d'une grille de calcul}}{12}{figure.1.6}\r
-\contentsline {figure}{\numberline {1.7}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{13}{figure.1.7}\r
-\contentsline {figure}{\numberline {1.8}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{16}{figure.1.8}\r
-\contentsline {figure}{\numberline {1.9}{\ignorespaces SIMGRID : Les \IeC {\'e}l\IeC {\'e}ments de la plateforme de simulation}}{18}{figure.1.9}\r
-\addvspace {10\p@ }\r
-\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{24}{figure.2.1}\r
-\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{27}{figure.2.2}\r
-\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{28}{figure.2.3}\r
-\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{29}{figure.2.4}\r
-\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{30}{figure.2.5}\r
-\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{31}{figure.2.6}\r
-\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{32}{figure.2.7}\r
-\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{33}{figure.2.8}\r
-\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{34}{figure.2.9}\r
-\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{37}{figure.2.10}\r
+\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{12}{figure.1.5}\r
+\contentsline {figure}{\numberline {1.6}{\ignorespaces Algorithme it\IeC {\'e}ratif GMRES avec red\IeC {\'e}marrage}}{14}{figure.1.6}\r
+\contentsline {figure}{\numberline {1.7}{\ignorespaces Solveur Multisplitting utilisant la m\IeC {\'e}thode GMRES en local (version parall\IeC {\`e}le)}}{16}{figure.1.7}\r
+\contentsline {figure}{\numberline {1.8}{\ignorespaces Architecture d'une grille de calcul}}{17}{figure.1.8}\r
+\contentsline {figure}{\numberline {1.9}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{18}{figure.1.9}\r
+\contentsline {figure}{\numberline {1.10}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{20}{figure.1.10}\r
+\contentsline {figure}{\numberline {1.11}{\ignorespaces SIMGRID : Les \IeC {\'e}l\IeC {\'e}ments de la plateforme de simulation}}{22}{figure.1.11}\r
+\addvspace {10\p@ }\r
+\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{27}{figure.2.1}\r
+\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{31}{figure.2.2}\r
+\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD M\IeC {\'e}moire Distribu\IeC {\'e}}}{32}{figure.2.3}\r
+\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD M\IeC {\'e}moire partag\IeC {\'e}}}{33}{figure.2.4}\r
+\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{34}{figure.2.5}\r
+\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{35}{figure.2.6}\r
+\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{36}{figure.2.7}\r
+\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{36}{figure.2.8}\r
+\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{37}{figure.2.9}\r
+\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{39}{figure.2.10}\r
\addvspace {10\p@ }\r
\addvspace {10\p@ }\r
\addvspace {10\p@ }\r
-This is pdfTeX, Version 3.14159265-2.6-1.40.16 (MiKTeX 2.9) (preloaded format=pdflatex 2015.11.9) 8 JAN 2016 11:30\r
+This is pdfTeX, Version 3.14159265-2.6-1.40.16 (MiKTeX 2.9) (preloaded format=pdflatex 2015.11.9) 6 FEB 2016 19:10\r
entering extended mode\r
**These_RCE.tex\r
(These_RCE.tex\r
\c@upmmytheorem=\count166\r
(These_RCE.aux\r
\r
+LaTeX Warning: Label `eq:residu' multiply defined.\r
+\r
+\r
LaTeX Warning: Label `eq:12' multiply defined.\r
\r
)\r
] (These_RCE.toc\r
LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <12> not available\r
(Font) Font shape `OT1/phv/b/n' tried instead on input line 2.\r
-\r
-Underfull \vbox (badness 1259) has occurred while \output is active []\r
-\r
- [7]\r
-Underfull \vbox (badness 10000) has occurred while \output is active []\r
-\r
- [8])\r
+ [7] [8])\r
\tf@toc=\write4\r
-\r
-[9] [10\r
+ [9] [10\r
\r
] [1\r
\r
-] [2] [3\r
+]\r
+[2] [3\r
\r
-] [4]\r
-Chapitre 1.\r
+] [4] [5] [6\r
\r
-LaTeX Warning: Reference `fig:decoupage' on page 5 undefined on input line 283.\r
+]\r
+Chapitre 1.\r
\r
+LaTeX Warning: Reference `fig:decoupage' on page 7 undefined on input line 288.\r
\r
-[5\r
\r
-]\r
-<"3D data partitionning btw 2 clusters".pdf, id=421, 521.95pt x 347.2975pt>\r
+[7]\r
+<"3D data partitionning btw 2 clusters".pdf, id=429, 521.95pt x 347.2975pt>\r
File: "3D data partitionning btw 2 clusters".pdf Graphic file (type pdf)\r
\r
<use "3D data partitionning btw 2 clusters".pdf>\r
Package pdftex.def Info: "3D data partitionning btw 2 clusters".pdf used on inp\r
-ut line 290.\r
+ut line 295.\r
(pdftex.def) Requested size: 156.49014pt x 104.12645pt.\r
\r
-<"1D-2D-3D Domain decomposition".pdf, id=422, 229.85875pt x 520.94624pt>\r
+<"1D-2D-3D Domain decomposition".pdf, id=430, 845.1575pt x 597.23125pt>\r
File: "1D-2D-3D Domain decomposition".pdf Graphic file (type pdf)\r
\r
<use "1D-2D-3D Domain decomposition".pdf>\r
Package pdftex.def Info: "1D-2D-3D Domain decomposition".pdf used on input line\r
- 295.\r
-(pdftex.def) Requested size: 156.49014pt x 354.6839pt.\r
+ 303.\r
+(pdftex.def) Requested size: 156.49014pt x 110.57718pt.\r
+ [8 <./3D data partitionning btw 2 clusters.pdf> <./1D-2D-3D Domain decompositi\r
+on.pdf, page is rotated 90 degrees>]\r
\r
-Underfull \vbox (badness 10000) has occurred while \output is active []\r
-\r
- [6 <./3D data partitionning btw 2 clusters.pdf> <./1D-2D-3D Domain decompositi\r
-on.pdf>]\r
+LaTeX Warning: Reference `fig:Decompo' on page 9 undefined on input line 370.\r
\r
-LaTeX Warning: Reference `fig:Decompo' on page 7 undefined on input line 362.\r
-\r
-<"Synchronous iterations model".pdf, id=432, 597.51233pt x 845.0471pt>\r
+<"Synchronous iterations model".pdf, id=446, 409.53pt x 98.61844pt>\r
File: "Synchronous iterations model".pdf Graphic file (type pdf)\r
\r
<use "Synchronous iterations model".pdf>\r
Package pdftex.def Info: "Synchronous iterations model".pdf used on input line \r
-382.\r
-(pdftex.def) Requested size: 227.62231pt x 227.6242pt.\r
-\r
+395.\r
+(pdftex.def) Requested size: 156.49014pt x 37.68456pt.\r
\r
-LaTeX Warning: `h' float specifier changed to `ht'.\r
-\r
-<"Asynchronous iterations model".pdf, id=433, 546.04pt x 131.49126pt>\r
+<"Asynchronous iterations model".pdf, id=447, 546.04pt x 131.49126pt>\r
File: "Asynchronous iterations model".pdf Graphic file (type pdf)\r
\r
<use "Asynchronous iterations model".pdf>\r
Package pdftex.def Info: "Asynchronous iterations model".pdf used on input line\r
- 384.\r
-(pdftex.def) Requested size: 227.61887pt x 227.63321pt.\r
+ 403.\r
+(pdftex.def) Requested size: 156.49014pt x 37.68405pt.\r
\r
\r
-LaTeX Warning: `h' float specifier changed to `ht'.\r
+LaTeX Warning: Reference `fig:sync' on page 9 undefined on input line 434.\r
+\r
+\r
+LaTeX Warning: Reference `fig:async' on page 9 undefined on input line 450.\r
\r
\r
Overfull \hbox (142.95473pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.1. CLASSE DES ALGORITHMES IT[]ERATIFS PARALL[]ELES []A L\r
-ARGE []ECHELLE DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 7\r
+ARGE []ECHELLE DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 9\r
[]\r
\r
-[7]\r
-Underfull \vbox (badness 10000) has occurred while \output is active []\r
+[9 <./Synchronous iterations model.pdf> <./Asynchronous iterations model.pdf>]\r
+[10]\r
+Overfull \hbox (318.41437pt too wide) has occurred while \output is active\r
+\OT1/phv/m/sl/10.95 1.2. M[]ETHODES DE R[]ESOLUTION PARALL[]ELES DU PROBL[]EME\r
+ DE POISSON ET DE L'ALGORITHME TWO-STAGE MULTISPLITTING DE KRYLOV \OT1/phv/m/n/\r
+10.95 11\r
+ []\r
+\r
+[11]\r
+Underfull \hbox (badness 10000) in paragraph at lines 610--612\r
+\r
+ []\r
+\r
+[12]\r
+Underfull \hbox (badness 10000) in paragraph at lines 698--701\r
+\r
+ []\r
\r
- [8 <./Synchronous iterations model.pdf>]\r
-Overfull \hbox (312.32625pt too wide) has occurred while \output is active\r
+\r
+Overfull \hbox (318.41437pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.2. M[]ETHODES DE R[]ESOLUTION PARALL[]ELES DU PROBL[]EME\r
DE POISSON ET DE L'ALGORITHME TWO-STAGE MULTISPLITTING DE KRYLOV \OT1/phv/m/n/\r
-10.95 9\r
+10.95 13\r
[]\r
\r
-[9 <./Asynchronous iterations model.pdf>] [10]\r
-Underfull \hbox (badness 10000) in paragraph at lines 584--585\r
+[13] [14]\r
+Underfull \hbox (badness 10000) in paragraph at lines 824--825\r
\r
[]\r
\r
-<"Grid architecture".png, id=484, 449.42906pt x 176.15813pt>\r
-File: "Grid architecture".png Graphic file (type png)\r
+<"Grid architecture".pdf, id=513, 399.74344pt x 156.585pt>\r
+File: "Grid architecture".pdf Graphic file (type pdf)\r
\r
-<use "Grid architecture".png>\r
-Package pdftex.def Info: "Grid architecture".png used on input line 586.\r
-(pdftex.def) Requested size: 227.62164pt x 227.62123pt.\r
+<use "Grid architecture".pdf>\r
+Package pdftex.def Info: "Grid architecture".pdf used on input line 826.\r
+(pdftex.def) Requested size: 227.62204pt x 89.16357pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 588--591\r
+Underfull \hbox (badness 10000) in paragraph at lines 828--831\r
\r
[]\r
\r
\r
-Overfull \hbox (107.96115pt too wide) has occurred while \output is active\r
+Overfull \hbox (86.17162pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES \r
-MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 11\r
+DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 15\r
[]\r
\r
-[11] <"Grid5000 sites".png, id=493, 292.09125pt x 231.86626pt>\r
+[15] <"Grid5000 sites".png, id=525, 292.09125pt x 231.86626pt>\r
File: "Grid5000 sites".png Graphic file (type png)\r
\r
<use "Grid5000 sites".png>\r
-Package pdftex.def Info: "Grid5000 sites".png used on input line 594.\r
-(pdftex.def) Requested size: 227.62967pt x 227.62715pt.\r
+Package pdftex.def Info: "Grid5000 sites".png used on input line 834.\r
+(pdftex.def) Requested size: 227.62204pt x 180.69572pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
- [12 <./Grid architecture.png>]\r
-Underfull \hbox (badness 10000) in paragraph at lines 602--604\r
+ [16]\r
+Underfull \hbox (badness 10000) in paragraph at lines 842--844\r
\r
[]\r
\r
\r
-Overfull \hbox (107.96115pt too wide) has occurred while \output is active\r
+Overfull \hbox (86.17162pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES \r
-MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 13\r
+DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 17\r
[]\r
\r
-[13 <./Grid5000 sites.png>]\r
-LaTeX Font Info: Try loading font information for OT1+txtt on input line 612\r
+[17 <./Grid architecture.pdf>]\r
+LaTeX Font Info: Try loading font information for OT1+txtt on input line 852\r
.\r
\r
("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\ot1txtt.fd"\r
File: ot1txtt.fd 2000/12/15 v3.1\r
)\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
-LaTeX Font Info: Try loading font information for OML+phv on input line 612.\r
+LaTeX Font Info: Try loading font information for OML+phv on input line 852.\r
\r
("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\psnfss\omlphv.fd"\r
File: omlphv.fd \r
)\r
LaTeX Font Info: Font shape `OML/phv/m/n' in size <10.95> not available\r
-(Font) Font shape `OML/cmm/m/it' tried instead on input line 612.\r
+(Font) Font shape `OML/cmm/m/it' tried instead on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-LaTeX Warning: Command \textless invalid in math mode on input line 612.\r
+LaTeX Warning: Command \textless invalid in math mode on input line 852.\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 615--618\r
+Underfull \hbox (badness 10000) in paragraph at lines 855--858\r
\r
[]\r
\r
+[18 <./Grid5000 sites.png>]\r
LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <8> not available\r
-(Font) Font shape `OT1/phv/b/n' tried instead on input line 634.\r
+(Font) Font shape `OT1/phv/b/n' tried instead on input line 874.\r
\r
-Overfull \hbox (41.8198pt too wide) in paragraph at lines 631--659\r
+Overfull \hbox (41.8198pt too wide) in paragraph at lines 871--899\r
[][] \r
[]\r
\r
-[14]\r
-Overfull \hbox (107.96115pt too wide) has occurred while \output is active\r
+\r
+Overfull \hbox (86.17162pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES \r
-MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 15\r
+DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 19\r
[]\r
\r
-[15]\r
-Underfull \hbox (badness 10000) in paragraph at lines 682--683\r
+[19]\r
+Underfull \hbox (badness 10000) in paragraph at lines 922--923\r
\r
[]\r
\r
-<"MPI".pdf, id=520, 614.295pt x 794.97pt>\r
+<"MPI".pdf, id=553, 418.56375pt x 175.40532pt>\r
File: "MPI".pdf Graphic file (type pdf)\r
<use "MPI".pdf>\r
-Package pdftex.def Info: "MPI".pdf used on input line 684.\r
-(pdftex.def) Requested size: 227.62303pt x 227.62413pt.\r
- [16 <./MPI.pdf>]\r
-Overfull \hbox (107.96115pt too wide) has occurred while \output is active\r
+Package pdftex.def Info: "MPI".pdf used on input line 924.\r
+(pdftex.def) Requested size: 227.62204pt x 95.38657pt.\r
+ [20 <./MPI.pdf>]\r
+Overfull \hbox (86.17162pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES \r
-MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 17\r
+DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 21\r
[]\r
\r
-[17]\r
+[21]\r
\r
pdfTeX warning: pdflatex (file ./Simgrid - In a nutshell.pdf): PDF inclusion: f\r
ound PDF version <1.7>, but at most version <1.5> allowed\r
-<"Simgrid - In a nutshell".pdf, id=543, 298.2091pt x 132.36852pt>\r
+<"Simgrid - In a nutshell".pdf, id=568, 298.2091pt x 132.36852pt>\r
File: "Simgrid - In a nutshell".pdf Graphic file (type pdf)\r
\r
<use "Simgrid - In a nutshell".pdf>\r
-Package pdftex.def Info: "Simgrid - In a nutshell".pdf used on input line 723.\r
-(pdftex.def) Requested size: 227.62411pt x 227.63707pt.\r
- [18 <./Simgrid - In a nutshell.pdf>]\r
-[19] [20\r
+Package pdftex.def Info: "Simgrid - In a nutshell".pdf used on input line 963.\r
+(pdftex.def) Requested size: 227.62204pt x 101.03737pt.\r
+\r
+Underfull \vbox (badness 10000) has occurred while \output is active []\r
+\r
+ [22 <./Simgrid - In a nutshell.pdf>] [23] [24\r
\r
]\r
Chapitre 2.\r
-[21] [22] <"Weak vs Strong scaling".pdf, id=573, 617.30624pt x 188.705pt>\r
+[25] [26] <"Weak vs Strong scaling".pdf, id=598, 617.30624pt x 188.705pt>\r
File: "Weak vs Strong scaling".pdf Graphic file (type pdf)\r
\r
<use "Weak vs Strong scaling".pdf>\r
-Package pdftex.def Info: "Weak vs Strong scaling".pdf used on input line 902.\r
-(pdftex.def) Requested size: 227.61792pt x 227.62253pt.\r
-\r
-\r
-LaTeX Warning: `h' float specifier changed to `ht'.\r
-\r
-\r
-Underfull \vbox (badness 6859) has occurred while \output is active []\r
-\r
- [23]\r
-Underfull \vbox (badness 1655) has occurred while \output is active []\r
-\r
- [24 <./Weak vs Strong scaling.pdf>]\r
+Package pdftex.def Info: "Weak vs Strong scaling".pdf used on input line 1142.\r
+(pdftex.def) Requested size: 284.52756pt x 86.9781pt.\r
+ [27 <./Weak vs Strong scaling.pdf>] [28]\r
Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
-LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 25\r
+LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 29\r
[]\r
\r
-[25]\r
+[29]\r
\r
-LaTeX Warning: Reference `fig:4' on page 26 undefined on input line 1084.\r
+LaTeX Warning: Reference `fig:4' on page 30 undefined on input line 1324.\r
\r
-[26]\r
-<"Architecture des CPU multi-coeurs".pdf, id=596, 275.0275pt x 173.64874pt>\r
+<"Architecture des CPU multi-coeurs".pdf, id=617, 275.0275pt x 173.64874pt>\r
File: "Architecture des CPU multi-coeurs".pdf Graphic file (type pdf)\r
\r
<use "Architecture des CPU multi-coeurs".pdf>\r
Package pdftex.def Info: "Architecture des CPU multi-coeurs".pdf used on input \r
-line 1087.\r
-(pdftex.def) Requested size: 227.63069pt x 227.6299pt.\r
+line 1327.\r
+(pdftex.def) Requested size: 227.62204pt x 143.723pt.\r
+\r
+\r
+LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-<"MIMD Distributed Memory".pdf, id=597, 928.46875pt x 474.77374pt>\r
+<"MIMD Distributed Memory".pdf, id=618, 928.46875pt x 474.77374pt>\r
File: "MIMD Distributed Memory".pdf Graphic file (type pdf)\r
\r
<use "MIMD Distributed Memory".pdf>\r
-Package pdftex.def Info: "MIMD Distributed Memory".pdf used on input line 1100.\r
-\r
-(pdftex.def) Requested size: 227.61142pt x 227.62076pt.\r
+Package pdftex.def Info: "MIMD Distributed Memory".pdf used on input line 1340.\r
\r
+(pdftex.def) Requested size: 227.62204pt x 116.3894pt.\r
+ [30]\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-<"MIMD Shared memory - SMP".pdf, id=598, 624.3325pt x 483.8075pt>\r
+<"MIMD Shared memory - SMP".pdf, id=624, 624.3325pt x 483.8075pt>\r
File: "MIMD Shared memory - SMP".pdf Graphic file (type pdf)\r
\r
<use "MIMD Shared memory - SMP".pdf>\r
-Package pdftex.def Info: "MIMD Shared memory - SMP".pdf used on input line 1102\r
+Package pdftex.def Info: "MIMD Shared memory - SMP".pdf used on input line 1342\r
.\r
-(pdftex.def) Requested size: 227.6175pt x 227.6258pt.\r
+(pdftex.def) Requested size: 227.62204pt x 176.38525pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-<"MIMD Hybride".pdf, id=599, 564.1075pt x 358.33875pt>\r
+<"MIMD Hybride".pdf, id=625, 564.1075pt x 358.33875pt>\r
File: "MIMD Hybride".pdf Graphic file (type pdf)\r
\r
<use "MIMD Hybride".pdf>\r
-Package pdftex.def Info: "MIMD Hybride".pdf used on input line 1104.\r
-(pdftex.def) Requested size: 227.61873pt x 227.62459pt.\r
+Package pdftex.def Info: "MIMD Hybride".pdf used on input line 1344.\r
+(pdftex.def) Requested size: 227.62204pt x 144.59055pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
\r
-Underfull \vbox (badness 4291) has occurred while \output is active []\r
-\r
-\r
-Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
-\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
-LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 27\r
- []\r
-\r
-[27 <./Architecture des CPU multi-coeurs.pdf>]\r
-<"Evolution de la puissance de calcul mondiale".pdf, id=613, 702.625pt x 489.83\r
+<"Evolution de la puissance de calcul mondiale".pdf, id=630, 702.625pt x 489.83\r
pt>\r
File: "Evolution de la puissance de calcul mondiale".pdf Graphic file (type pdf\r
)\r
<use "Evolution de la puissance de calcul mondiale".pdf>\r
Package pdftex.def Info: "Evolution de la puissance de calcul mondiale".pdf use\r
-d on input line 1138.\r
-(pdftex.def) Requested size: 227.62137pt x 227.61911pt.\r
+d on input line 1378.\r
+(pdftex.def) Requested size: 227.62204pt x 158.68462pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-[28 <./MIMD Distributed Memory.pdf>]\r
-<"UMA architecture".pdf, id=623, 400.49625pt x 172.645pt>\r
-File: "UMA architecture".pdf Graphic file (type pdf)\r
\r
-<use "UMA architecture".pdf>\r
-Package pdftex.def Info: "UMA architecture".pdf used on input line 1205.\r
-(pdftex.def) Requested size: 227.62523pt x 227.626pt.\r
+Underfull \vbox (badness 10000) has occurred while \output is active []\r
+\r
\r
Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
-LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 29\r
+LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 31\r
[]\r
\r
-[29 <./MIMD Shared memory - SMP.pdf>]\r
+[31 <./Architecture des CPU multi-coeurs.pdf>]\r
+<"UMA architecture".pdf, id=643, 400.49625pt x 172.645pt>\r
+File: "UMA architecture".pdf Graphic file (type pdf)\r
+\r
+<use "UMA architecture".pdf>\r
+Package pdftex.def Info: "UMA architecture".pdf used on input line 1445.\r
+(pdftex.def) Requested size: 227.62204pt x 98.12415pt.\r
+\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-<"NUMA architecture".pdf, id=632, 429.605pt x 223.83624pt>\r
+<"NUMA architecture".pdf, id=644, 429.605pt x 223.83624pt>\r
File: "NUMA architecture".pdf Graphic file (type pdf)\r
\r
<use "NUMA architecture".pdf>\r
-Package pdftex.def Info: "NUMA architecture".pdf used on input line 1207.\r
-(pdftex.def) Requested size: 227.62401pt x 227.62685pt.\r
+Package pdftex.def Info: "NUMA architecture".pdf used on input line 1447.\r
+(pdftex.def) Requested size: 227.62204pt x 118.59848pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-<"COMA architecture".pdf, id=633, 333.245pt x 278.03876pt>\r
+<"COMA architecture".pdf, id=645, 333.245pt x 278.03876pt>\r
File: "COMA architecture".pdf Graphic file (type pdf)\r
\r
<use "COMA architecture".pdf>\r
-Package pdftex.def Info: "COMA architecture".pdf used on input line 1209.\r
-(pdftex.def) Requested size: 227.62566pt x 227.62415pt.\r
+Package pdftex.def Info: "COMA architecture".pdf used on input line 1449.\r
+(pdftex.def) Requested size: 199.16928pt x 166.17543pt.\r
\r
\r
LaTeX Warning: `h' float specifier changed to `ht'.\r
\r
-\r
+[32 <./MIMD Distributed Memory.pdf>]\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
- [30 <./MIMD Hybride.pdf>]\r
-Underfull \vbox (badness 10000) has occurred while \output is active []\r
-\r
-\r
-Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
-\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
-LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 31\r
- []\r
\r
-[31 <./Evolution de la puissance de calcul mondiale.pdf>] [32 <./UMA architectu\r
-re.pdf>]\r
Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 33\r
[]\r
\r
-[33 <./NUMA architecture.pdf>] [34 <./COMA architecture.pdf>]\r
+[33 <./MIMD Shared memory - SMP.pdf>]\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
-\r
+ [34 <./MIMD Hybride.pdf>]\r
Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 35\r
[]\r
\r
-[35] <"Performance Analysis techniques".pdf, id=669, 505.89pt x 287.0725pt>\r
+[35 <./Evolution de la puissance de calcul mondiale.pdf>] [36 <./UMA architectu\r
+re.pdf> <./NUMA architecture.pdf>]\r
+Overfull \hbox (138.89304pt too wide) has occurred while \output is active\r
+\OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL\r
+LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 37\r
+ []\r
+\r
+[37 <./COMA architecture.pdf>] [38]\r
+<"Performance Analysis techniques".pdf, id=690, 505.89pt x 287.0725pt>\r
File: "Performance Analysis techniques".pdf Graphic file (type pdf)\r
\r
<use "Performance Analysis techniques".pdf>\r
Package pdftex.def Info: "Performance Analysis techniques".pdf used on input li\r
-ne 1473.\r
-(pdftex.def) Requested size: 227.62523pt x 227.62581pt.\r
-\r
-\r
-LaTeX Warning: `h' float specifier changed to `ht'.\r
-\r
-[36]\r
-Underfull \vbox (badness 6268) has occurred while \output is active []\r
-\r
+ne 1713.\r
+(pdftex.def) Requested size: 227.62204pt x 129.16829pt.\r
\r
Overfull \hbox (22.54312pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.3. TECHNIQUES D'ANALYSE DE PERFORMANCE DES APPLICATIONS \r
-PARALL[]ELES \OT1/phv/m/n/10.95 37\r
+PARALL[]ELES \OT1/phv/m/n/10.95 39\r
[]\r
\r
-[37 <./Performance Analysis techniques.pdf>] [38]\r
+[39 <./Performance Analysis techniques.pdf>]\r
+Underfull \vbox (badness 10000) has occurred while \output is active []\r
+\r
+ [40]\r
Overfull \hbox (54.373pt too wide) has occurred while \output is active\r
\OT1/phv/m/sl/10.95 2.4. M[]ETHODES DE PR[]EDICTION DE LA PERFORMANCE DES APPL\r
-ICATIONS PARALL[]ELES \OT1/phv/m/n/10.95 39\r
+ICATIONS PARALL[]ELES \OT1/phv/m/n/10.95 41\r
[]\r
\r
-[39] [40\r
+[41]\r
+Underfull \vbox (badness 10000) has occurred while \output is active []\r
+\r
+ [42]\r
+[43] [44\r
\r
]\r
Chapitre 3.\r
\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
- [41]\r
-[42] [43\r
+ [45]\r
+[46] [47\r
\r
-] [44]\r
+] [48]\r
Chapitre 4.\r
-[45\r
+[49\r
\r
-] [46\r
+] [50\r
\r
]\r
Chapitre 5.\r
-[47] [48\r
+[51] [52\r
\r
]\r
Chapitre 6.\r
-[49] [50\r
+[53] [54\r
\r
]\r
Chapitre 7.\r
-[51] [52\r
+[55] [56\r
\r
]\r
No file These_RCE.bbl.\r
-[53\r
+[57\r
\r
-] [54]\r
+] [58]\r
LaTeX Font Info: Font shape `OT1/phv/m/it' in size <10.95> not available\r
-(Font) Font shape `OT1/phv/m/sl' tried instead on input line 1608.\r
+(Font) Font shape `OT1/phv/m/sl' tried instead on input line 1862.\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 1628--1630\r
+Underfull \hbox (badness 10000) in paragraph at lines 1882--1884\r
[]\OT1/phv/m/n/10.95 [12] M. Du-bois and X. Vi-gou-roux. Un-leash your HPC per-\r
for-mance with\r
[]\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 1628--1630\r
+Underfull \hbox (badness 10000) in paragraph at lines 1882--1884\r
\OT1/phv/m/n/10.95 Bull. \OT1/phv/m/sl/10.95 Maxi-mi-zing com-pu-ting per-for-m\r
ance while re-du-cing po-wer consump-tion\OT1/phv/m/n/10.95 .\r
[]\r
\r
\r
-Underfull \hbox (badness 1286) in paragraph at lines 1633--1634\r
+Underfull \hbox (badness 1286) in paragraph at lines 1887--1888\r
[]\OT1/phv/m/n/10.95 [15] C. Har-ris et al. HPC Tech-no-logy Up-date. \OT1/phv/\r
m/sl/10.95 Paw-set Su-per-com-pu-ting Cen-ter -\r
[]\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 1635--1637\r
+Underfull \hbox (badness 10000) in paragraph at lines 1889--1891\r
[]\OT1/phv/m/n/10.95 [16] A. J. van der Steen, J. J. Don-garra. Over-view of Re\r
cent Su-per-\r
[]\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 1635--1637\r
+Underfull \hbox (badness 10000) in paragraph at lines 1889--1891\r
\OT1/phv/m/n/10.95 com-pu-ters. \OT1/phv/m/sl/10.95 Aca-de-mic Com-pu-ting Cent\r
re Utrecht, the Ne-ther-lands, De-part-\r
[]\r
\r
\r
-Underfull \hbox (badness 10000) in paragraph at lines 1635--1637\r
+Underfull \hbox (badness 10000) in paragraph at lines 1889--1891\r
\OT1/phv/m/sl/10.95 ment of Com-pu-ter Science, Uni-ver-sity of Ten-nes-see, Kn\r
ox-ville, Ma-the-ma-ti-\r
[]\r
\r
\r
-Underfull \hbox (badness 2460) in paragraph at lines 1635--1637\r
+Underfull \hbox (badness 2460) in paragraph at lines 1889--1891\r
\OT1/phv/m/sl/10.95 cal Sciences Sec-tion, Oak Ridge, Na-tio-nal La-bo-ra-tory,\r
Oak Ridge\OT1/phv/m/n/10.95 . http ://ci-te-\r
[]\r
\r
\r
-Underfull \hbox (badness 3078) in paragraph at lines 1644--1646\r
+Underfull \hbox (badness 3078) in paragraph at lines 1898--1900\r
[]\OT1/phv/m/n/10.95 [19] M. Ewan. Ex-plo-ring Clus-te-red Pa-ral-lel File Sys-\r
tems and Ob-ject Sto-rage.\r
[]\r
\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
- [55]\r
-Underfull \hbox (badness 2680) in paragraph at lines 1649--1651\r
+ [59]\r
+Underfull \hbox (badness 2680) in paragraph at lines 1903--1905\r
[]\OT1/phv/m/n/10.95 [21] G. Bal-lard et Al. Com-mu-ni-ca-tion Op-ti-mal Pa-ral\r
-lel Mul-ti-pli-ca-tion of Sparse\r
[]\r
\r
\r
-Underfull \hbox (badness 1960) in paragraph at lines 1649--1651\r
+Underfull \hbox (badness 1960) in paragraph at lines 1903--1905\r
\OT1/phv/m/n/10.95 Ran-dom Ma-trices". \OT1/phv/m/sl/10.95 UC Ber-ke-ley, IN-RI\r
A Pa-ris Roc-quen-court, Tel-Aviv Uni-ver-sity\OT1/phv/m/n/10.95 .\r
[]\r
\r
Underfull \vbox (badness 10000) has occurred while \output is active []\r
\r
- [56]\r
-[57] [58\r
+ [60]\r
+Underfull \hbox (badness 10000) in paragraph at lines 1951--1952\r
+[]\OT1/phv/m/n/10.95 [44] GMRES : Ge-ne-ra-li-zed mi-ni-mal re-si-dual me-thod.\r
+\r
+ []\r
+\r
+\r
+Underfull \hbox (badness 5548) in paragraph at lines 1953--1956\r
+[]\OT1/phv/m/n/10.95 [45] G. Fas-shauer - Nu-me-ri-cal li-near al-ge-bra - Illi\r
+-nois Ins-ti-tute of Tech-no-\r
+ []\r
+\r
+\r
+Underfull \hbox (badness 5008) in paragraph at lines 1953--1956\r
+\OT1/phv/m/n/10.95 logy - De-part-ment of Ap-plied Ma-the-ma-tics - Chi-cago. 2\r
+006. Cha-pitre 14 -\r
+ []\r
+\r
+[61] [62\r
\r
] (These_RCE.lof)\r
\tf@lof=\write5\r
- [59] [60\r
+ [63] [64\r
\r
] (These_RCE.lot)\r
\tf@lot=\write6\r
\r
showing upmdefinition\r
-[61] [62\r
+[65] [66\r
\r
-] (These_RCE.loe) [63] [64\r
+] (These_RCE.loe) [67] [68\r
\r
-] [65] [66]\r
+] [69] [70]\r
Annexe A.\r
-[67\r
+[71\r
\r
-] [68\r
+] [72\r
\r
]\r
Annexe B.\r
-[69] [70\r
+[73] [74\r
\r
-] [71]\r
+] [75]\r
\r
pdfTeX warning: pdflatex (file ./spimufcphdthesis-backpage.pdf): PDF inclusion:\r
found PDF version <1.6>, but at most version <1.5> allowed\r
-<spimufcphdthesis-backpage.pdf, id=848, 597.432pt x 844.83629pt>\r
+<spimufcphdthesis-backpage.pdf, id=876, 597.432pt x 844.83629pt>\r
File: spimufcphdthesis-backpage.pdf Graphic file (type pdf)\r
\r
<use spimufcphdthesis-backpage.pdf>\r
-Package pdftex.def Info: spimufcphdthesis-backpage.pdf used on input line 1709.\r
+Package pdftex.def Info: spimufcphdthesis-backpage.pdf used on input line 1980.\r
\r
(pdftex.def) Requested size: 600.04684pt x 900.02122pt.\r
\tf@loe=\write7\r
-Package atveryend Info: Empty hook `BeforeClearDocument' on input line 1709.\r
- [72\r
+Package atveryend Info: Empty hook `BeforeClearDocument' on input line 1980.\r
+ [76\r
\r
<./spimufcphdthesis-backpage.pdf>]\r
-Package atveryend Info: Empty hook `AfterLastShipout' on input line 1709.\r
+Package atveryend Info: Empty hook `AfterLastShipout' on input line 1980.\r
\r
(These_RCE.aux)\r
-Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 1709.\r
-Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 1709.\r
+Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 1980.\r
+Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 1980.\r
\r
Package rerunfilecheck Info: File `These_RCE.out' has not changed.\r
-(rerunfilecheck) Checksum: D21A0DE433E48EB3AE5D5C0B7498F849;5228.\r
+(rerunfilecheck) Checksum: 42DC8267356BBDEF6243E2A33F57C79C;5234.\r
\r
\r
LaTeX Warning: There were undefined references.\r
\r
LaTeX Warning: There were multiply-defined labels.\r
\r
-Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 1709.\r
+Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 1980.\r
) \r
Here is how much of TeX's memory you used:\r
- 12008 strings out of 493673\r
- 180096 string characters out of 3141524\r
- 301797 words of memory out of 3000000\r
- 14797 multiletter control sequences out of 15000+200000\r
- 67017 words of font info for 119 fonts, out of 3000000 for 9000\r
+ 12055 strings out of 493673\r
+ 180634 string characters out of 3141524\r
+ 300118 words of memory out of 3000000\r
+ 14821 multiletter control sequences out of 15000+200000\r
+ 69709 words of font info for 123 fonts, out of 3000000 for 9000\r
1025 hyphenation exceptions out of 8191\r
- 65i,17n,41p,1782b,642s stack positions out of 5000i,500n,10000p,200000b,50000s\r
+ 65i,17n,41p,1784b,642s stack positions out of 5000i,500n,10000p,200000b,50000s\r
{C:/Program Files (x86)/MiKTeX 2.9/fonts/enc/dvips/fontname/8r.enc}<C:/Progra\r
m Files (x86)/MiKTeX 2.9/fonts/type1/public/txfonts/rtxmi.pfb><C:/Program Files\r
(x86)/MiKTeX 2.9/fonts/type1/public/txfonts/rtxr.pfb><C:/Program Files (x86)/M\r
gram Files (x86)/MiKTeX 2.9/fonts/type1/urw/helvetic/uhvro8a.pfb><C:/Program Fi\r
les (x86)/MiKTeX 2.9/fonts/type1/urw/times/utmr8a.pfb><C:/Program Files (x86)/M\r
iKTeX 2.9/fonts/type1/urw/times/utmri8a.pfb>\r
-Output written on These_RCE.pdf (82 pages, 5103422 bytes).\r
+Output written on These_RCE.pdf (86 pages, 4941243 bytes).\r
PDF statistics:\r
- 943 PDF objects out of 1000 (max. 8388607)\r
- 184 named destinations out of 1000 (max. 500000)\r
+ 974 PDF objects out of 1000 (max. 8388607)\r
+ 203 named destinations out of 1000 (max. 500000)\r
538 words of extra memory for PDF output out of 10000 (max. 10000000)\r
\r
\select@language {french}\r
\addvspace {10\p@ }\r
-\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{15}{table.1.1}\r
+\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{19}{table.1.1}\r
\addvspace {10\p@ }\r
\addvspace {10\p@ }\r
\addvspace {10\p@ }\r
\BOOKMARK [2][]{subsection.1.2.1}{1.2.1 Algorithme de Jacobi}{section.1.2}% 7\r
\BOOKMARK [2][]{subsection.1.2.2}{1.2.2 M\351thode de r\351solution GMRES}{section.1.2}% 8\r
\BOOKMARK [2][]{subsection.1.2.3}{1.2.3 Solveur multisplitting}{section.1.2}% 9\r
-\BOOKMARK [1][]{section.1.3}{1.3 Simulateurs d'ex\351cution d'algorithmes parall\350les MPI dans une grille de calcul}{chapter.1}% 10\r
-\BOOKMARK [2][]{subsection.1.3.1}{1.3.1 Calcul sur grille}{section.1.3}% 11\r
+\BOOKMARK [1][]{section.1.3}{1.3 Simulateurs d'ex\351cution d'algorithmes parall\350les dans une grille de calcul}{chapter.1}% 10\r
+\BOOKMARK [2][]{subsection.1.3.1}{1.3.1 Calcul sur grille de calcul}{section.1.3}% 11\r
\BOOKMARK [2][]{subsection.1.3.2}{1.3.2 G\351n\351ralit\351s sur la simulation}{section.1.3}% 12\r
\BOOKMARK [2][]{subsection.1.3.3}{1.3.3 MPI - Message Passing Interface}{section.1.3}% 13\r
\BOOKMARK [2][]{subsection.1.3.4}{1.3.4 Simulateur SIMGRID - SMPI}{section.1.3}% 14\r
%% The second mandatory parameter is the date of the PhD defense.
%% The third mandatory parameter is the reference number given by
%% the University Library after the PhD defense.
-\declarethesis[Sous-titre]{Titre}{17 septembre 2012}{XXX}
+\declarethesis[]{Simulations à très large échelle d'algorithmes parallèles numériques itératifs et asynchrones}{XX XXX 2016}{XXX}
%%--------------------
%% Set the author of the PhD thesis
-\addauthor[email]{Prénom}{Nom}
+\addauthor[email]{C. E.}{RAMAMONJISOA}
%%--------------------
%% Add a member of the jury
\part{PARTIE I: Contexte scientifique et revue de l'état de l'art}
+Cette première partie met en exergue d'une part, le contexte scientifique de nos travaux et d'autre part, une revue de l'état de l'art dans le domaine de la recherche concerné ainsi que les travaux associés existant actuellement. \\
+Elle introduit ainsi dans un premier chapitre, la classe des algorithmes itératifs parallèles de systèmes d'équations linéaires ou non à large échelle et les méthodes de résolution particulièrement, dans un environnement de type grille. Différents algorithmes seront présentés et les étapes d'approche pour exécuter l'application, en particulier, le problématique du partitionnement du problème ainsi que les mécanismes des communications synchrone et asynchrone seront rappellés. Une section de ce chapitre montre les interêts et principes de la simulation d'exécution des algorithmes de calcul sur grille. Différents outils de simulation seront présentés et comparés en insistant particulièrement sur SIMGRID, l'outil choisi pour réaliser nos travaux. Comme les algorithmes utilisés sont écrits en MPI (Message Passing Interface), les primitives MPI les plus utilisés sont passées en revue. Enfin, le chapitre se ferme sur l'utilisation du module SMPI (Simulation MPI) de SIMGRID qui simule le comportement et l'exécution réelle des applications MPI.\\
+Un second chapitre est consacré à l'étude de la performance des applications parallèles et distribuées, en particulier, la classe d'algorithmes qui nous interesse. Deux volets principaux sont concernés par cette étude : l'analyse de la performance et la prédiction de cette même performance à grande échelle. L'analyse de la performance de l'application essaie de déterminer le comportement du code selon les différents environnement d'exécution, mais aussi de chercher à optimiser le code en identifant les parties du code les plus consommatrices de ressources (CPU, mémoire, communications, ...) tout en éliminant certains bugs du code. Par ailleurs, la prédiction de la performance, comme son nom l'indique, essaie de reporter le comportement du code à grande échelle à partir de benchmarks effectués à moindre echelle. Surtout, les indicateurs de temps de calcul et de communication dans la grille sont capturés lors d'une telle prédiction. Une telle opération peut se faire sur une plateforme difficilement accessible dans la pratique ou même encore inexistante. Plusieurs outils d'analyse de la performance du code seront présentés ainsi qu' une méthode pour la prédiction de la performance du code. \\
+Le dernier chapitre de cette première partie avance nos motivations sur les contributions dans ce domaine choisi, pour la simulation de l'exécution des algorithmes concernés sur une grille de calcul afin d'analyser leurs performances mais surtout de pouvoir simuler et prédire les résultats d'exécution à grande échelle avec une grille composée de plus en plus de grappes d'ordinateurs et de plus en plus de processeurs et de coeurs.
+
\chapter{Cadre de travail et contexte scientifique}
\section{Classe des algorithmes itératifs parallèles à large échelle dans une grille de calcul}
X^{k+1} = \text{f ( } X^k \text{ ), k = 0,1, \dots{} }
\end{equation}
-où chaque $x_k$ est un vecteur à n dimension et f une fonction de $R^n$ vers
+où chaque $X_k$ est un vecteur à n dimension et f une fonction de $R^n$ vers
$R^n$.
La solution du problème sera donc le vecteur X{*} tel que X{*} = f
consiste au découpage (partitionnement) du problème en plus petits
morceaux (ou blocs) et d'assigner chaque bloc à une
unité de calcul. Chaque processeur tourne le même algorithme de façon
-concourante jusqu'à la détection de la convergence
+conccurente jusqu'à la détection de la convergence
locale qui peut être obtenue soit par l'atteinte d'un
nombre maximum fixé d'itérations soit que la différence
entre les valeurs du vecteur inconnu entre deux itérations successives est devenue
inférieure à la valeur résiduelle convenue. Cette condition de convergence
locale peut être écrite comme suit :
\begin{equation}
- (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)
+ (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|\leq\epsilon)
\end{equation}
La convergence globale sera déclarée lorsque tous les processeurs
ont atteint leur convergence locale. De façon générale, plusieurs
matrice initiale entre deux clusters constitués chacun de 18 processeurs, soit un total de 36 processeurs.
\begin{figure}[!ht]
-%\centering
-\begin{minipage}[t]{5.5cm}
+\centering
+\begin{minipage}[t]{6.5cm}
\centering
\includegraphics [ width =5.5cm]{"3D data partitionning btw 2 clusters"}
\caption {Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun}
\end{minipage}
-\begin{minipage}[t]{5.5cm}
+\begin{minipage}[t]{1.4cm}
+\centering
+\end{minipage}
+\begin{minipage}[t]{6.5cm}
\centering
\includegraphics [ width =5.5cm]{"1D-2D-3D Domain decomposition"}
\caption {Décomposition en domaines 1D, 2D et 3D}
partitionnement du problème. Le temps de communication est impacté
sur la façon dont les échanges sont effectués.
-\mfigure[h]{width=8cm, height=8cm}{"Synchronous iterations model"} {Modèle de communication synchrone} {sync}
-\mfigure[h]{width=8cm, height=8cm}{"Asynchronous iterations model"} {Modèle de communication asynchrone} {async}
+\begin{figure}[!ht]
+\centering
+\begin{minipage}[t]{6.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"Synchronous iterations model"}
+\caption {Modèle de communication synchrone}
+\end{minipage}
+\begin{minipage}[t]{1.4cm}
+\centering
+\end{minipage}
+\begin{minipage}[t]{6.5cm}
+\centering
+\includegraphics [ width =5.5cm]{"Asynchronous iterations model"}
+\caption {Modèle de communication asynchrone}
+\end{minipage}
+%\caption{Partitionnement du problème}
+\end{figure}
+
+
%\begin{figure}[h]
%\begin{subfigure}{0.5\textwidth}
l'algorithme two-stage multisplitting de Krylov}
Afin de valider les résultats de simulation d'applications distribuées parallèles effectuée dans le cadre de nos travaux, différents algorithmes, largement utilisés dans différents domaines scientifiques, écrits en MPI/C ont été utilisés. Ils font partie de la classe des méthodes de résolution numérique itérative qui, en opposition aux méthodes directes et par approches successives,calcule par approximation la solution du problème posé avec une erreur connue d'avance après l'initialisation d'une valeur initiale. Les méthodes itératives permettent la résolution des systèmes linéaires mais aussi non linéaires. Elles se prêtent à une parallèlisation plus aisée et supportent mieux le passage à l'echelle [4].
-Les sections suivantes vont décrire les algorithmes considérés à savoir la méthode de résolution de Jacobi et l'algorithme de Krylov avec deux variantes : le classique GMRES en mode native et la version "two-stage" d'une part et la variante multi-décomposition(multisplitting) d'autre part.
+Les sections suivantes vont décrire les algorithmes considérés à savoir la méthode de résolution de Jacobi et l'algorithme de Krylov avec deux variantes : le classique GMRES en mode native d'une part et la variante multi-décomposition(multisplitting) d'autre part.
\subsection{Algorithme de Jacobi}
L'algorithme de Jacobi est une des plus simples méthodes de résolutions d'un système d'équations linéaires [3,4].
\> et b un vecteur constant.\\
\end{tabbing}
-Ainsi, \eqref{eq:2} peut s'écrire :
+\eqref{eq:2} peut s'écrire :
\begin{equation*}
\left(\begin{array}{ccc}
\State Charger $A_{ij}$, $b_{i}$, $n$,
\State Assigner la valeur initiale $x^0$
-\State \textbf{repeat} {jusqu'à l'obtention de la condition de convergence} \textbf{do}
+\State \textbf{repeat}
\For {$i=0,1,2,\ldots (n-1)$}
\State $x_i \leftarrow 0$
\For {$j=0,1,2,\ldots (n-1) \hspace{0.1cm} et \hspace{0.1cm} j \neq i$}
\State $xOld_{i} \leftarrow ( b_{i} - x_{i} ) \quad {/} \quad A_{ii}$
\EndFor
\EndFor
-\State \textbf{end repeat}
+\State \textbf{Until} {( Obtention de la condition de convergence )}
\Statex
\end{algorithmic}
\subsection{Méthode de résolution GMRES}
-Native
+La méthode native GMRES ou "Generalized Minimal Residual", développée par Saad et Schultz en 1986, est une des méthodes itératives les plus utilisées pour résoudre un système d'équations linéaires ou non [3,4,43,44,45]. Elle est basée sur la minimisation de la norme euclidienne d'un vecteur résidu obtenu à chaque itération par une projection sur un espace de Krylov. Plus précisement, soit le système d'équations \eqref{eq:2}. Un sous-espace de Krylov d'ordre {m} est défini comme suit :
+
+\begin{equation}
+\label{eq:Krylov}
+K_m = Vect \{ b, Ab, A^2b, ..., A^{m-1}b \}
+\end{equation}
+
+où : Vect désigne l'espace généré par les vecteurs en argument.
+
+Il est démontré [3,..] que le vecteur projeté $x_m$ sur $K_m$ donne une valeur approchée de la solution exacte du système d'équations en minimisant le résidu $r_m$ tel que :
+
+\begin{equation}
+\label{eq:residu}
+r_m = Ax_m - b
+\end{equation}
+On suppose que les vecteurs de l'équation \eqref{eq:Krylov} sont linéairement indépendants. Comme le montre cette équation, la taille des vecteurs de base augmente linéairement avec m qui varie de 0 à $n-1$ (n étant la taille initiale de la matrice A) entrainant à chaque itération un besoin de stockage de plus en plus grand. \\
+
+Afin de réduire et optimiser l'algorithme, on peut combiner avec d'autres méthodes telles que les itérations de Arnoldi [] utilisant la procédure d'orthogonalisation de Gram-Shmidt [] pour trouver une base orthonormée de l'espace $K_m$ notée $Q_m = [q_1, ..., q_m]$. On peut donc écrire :
+
+\begin{equation}
+\label{eq:proj}
+\forall x_m \in K_m, x_m = Q_m y
+\end{equation}
+
+et le résidu dont la norme est à minimiser peut s'écrire :
+\begin{equation}
+\label{eq:residu}
+r_m = A Q_m y - b
+\end{equation}
+
+D'après cette procédure, il existe une matrice de Hessenberg $H_m$ de taille m telle que :
+\begin{equation}
+\label{eq:hessen}
+H_m = Q^T_m A Q_m
+\end{equation}
+En introduisant la matrice notée $\tilde{H}_m$ obtenue par l'ajout d'une ligne supplémentaire à $H_m$ avec la seule valeur non nulle est celle à la position (m+1,m), on démontre qu'on a la relation suivante [3,43,44,45] :
+
+\begin{equation}
+\label{eq:hessen1}
+A Q_m = Q_{m+1} \tilde{H}_m
+\end{equation}
+
+Ainsi, le résidu donné par l'équation \eqref{eq:residu} peut s'écrire en utilisant \eqref{eq:hessen1} :
+\begin{equation*}
+\label{eq:residu1}
+(r_m = Q_{m+1} \tilde{H}_m y - b) \\
+\Leftrightarrow (\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\|)
+\end{equation*}
+
+Comme la norme ne change pas après la multiplication avec la matrice unitaire $Q^{-1}_m$, on a :
+\begin{equation*}
+\label{eq:norme1}
+\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\| = \|Q^{-1}_m Q_{m+1} \tilde{H}_m y - Q^{-1}_m b\|
+\end{equation*}
+
+Ou :
+
+\begin{equation}
+\label{eq:norme2}
+\|r_m\| = \|\tilde{H}_m y - Q^{-1}_m b\|
+\end{equation}
+
+Or :
+\begin{equation}
+\label{eq:q_1}
+Q^{-1}_m b = \left( \begin{array}{c}
+q^{-1}_1 b \\
+q^{-1}_2 b \\
+\vdots \\
+q^{-1}_{m+1} b
+\end{array}\right)
+\end{equation}
+
+Et comme les colonnes $q_j$ de $Q_m$ forment une base orthonormale de l'espace de Krylov $K_m$, on a :
+
+\begin{equation*}
+\label{eq:q1}
+q_1 = \frac{b}{\|b\|}
+\end{equation*}
+et :
+\begin{equation*}
+\label{eq:q_1j}
+\forall j > 1, q^{-1}_{j} b = 0 \text { et } q^{-1}_1 b = \|b\|
+\end{equation*}
+Donc, l'équation \eqref{eq:q_1} peut s'ecrire :
+
+\begin{equation}
+\label{eq:q_f}
+Q^{-1}_m b = \|b\| e_1 \text{ avec } e_1 = (1,0, ..., 0)^T
+\end{equation}
+
+Finalement, la norme du résidu à minimiser peut s'écrire à partie de \eqref{eq:norme2} et \eqref{eq:q_f} :
+
+\begin{equation}
+\label{eq:norme3}
+\|r_m\| = \| \tilde{H}_m y - \text { } \|b\| \text { } e_1 \|
+\end{equation}
+La méthode des moindres carrés peut être utilisée pour effectuer cette minimisation et trouver $y$. On utilise après la relation \eqref{eq:proj} pour déterminer la valeur approchée de la solution à l'itération m.
+
+\begin{equation*}
+\label{eq:proj1}
+x_m = Q_m y
+\end{equation*}
+L'algorithme de GMRES repose sur ces deux dernières equations.
+Une autre amélioration de l'algorithme, surtout en terme de réduction des vecteurs à maintenir en mémoire mais aussi en termes de temps de calcul pour atteindre la convergence, est le "redémarrage" [43]. Il s'agit de "redémarrer" l'algorithme après une tranche de k itérations, k étant fixé par l'utilisateur au départ. A chaque redémarrage, la valeur initiale $x_0$ est remplacée par le dernier $x_m$ trouvé et $r_0$ par le dernier $r_m$. \\
+
+Le pseudo-code de l'algorithme GMRES optimisé avec les itérations d'Arnoldi avec un redémarrage est donné à la Figure~\ref{algo:02}.
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input \\
+$A_{ij}$ (Matrice d'entrée), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, \\
+$m$ (Nombre d'itérations avant redémarrage), $h_{ij}$ (Matrice de Hessenberg), \\
+$q_i$(Suite de vecteurs constituant une base orthonormée de l'espace de Krylov $K_i$), \\
+$w_i$ (variable intermédiaire)
+\Output $x_{m}$ (Vecteur solution)\medskip
+
+\State Charger $A_{ij}$, $b_{i}$, $n$,
+\State Assigner la valeur initiale $x^0$
+\State $r_0 \leftarrow b - Ax_0$
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$
+\State \textbf{repeat}
+\For {$j=0,1,2,\ldots m$}
+\For {$i=1,2,\ldots j$}
+\State $h_{i,j} = (A q_j, q_i)$
+\State $x_i \leftarrow 0$
+\State $w_{j+1} = A q_j - \sum_{i=1}^j h_{i,j} q_i$
+\State $h_{j+1,j} = \| w_{j+1} \|$
+\State $h_{i,j} = \frac {w_{j+1}} {h_{j+1,j}}$
+\EndFor
+\EndFor
+\State Calculer la solution approchée $x_{m}$
+\State $x_{m} = x_0 + Q_m y_m \hspace{0.1cm} tel \hspace{0.1cm} que \hspace{0.1cm} y_m \hspace{0.1cm} minimise \hspace{0.1cm} \| \tilde{H}_m y - \hspace{0.1cm} \|b\| \hspace{0.1cm} e_1 \|, y \in R^m.$
+\State Redémarrage
+\State $r_m \leftarrow b - Ax_m$
+\State Réinitialiser pour le redémarrage
+\State $x_0 \leftarrow x_m$
+\State $r_0 \leftarrow r_m$
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$
+\State \textbf{Until} {( Obtention de la condition de convergence : $\| r_m \|$ \hspace{0.1cm} est satisfaisant )}
+\Statex
+\end{algorithmic}
+\caption{Algorithme itératif GMRES avec redémarrage}
+\label{algo:02}
+\end{figure}
-Version « two-stage »
+%%%% ?? Version « two-stage »
\subsection{Solveur multisplitting}
-Version simple
+Dans cette classe des méthodes itératives de résolution de système d'équations linéaires $AX=B$, le solveur "multisplitting" reste une des plus utilisées et une des plus efficaces en version parallèle. On suppose qu'on va répartir le traitement de la résolution du problème entre les $L$ clusters d'une grille de calcul donné. La base de la méthode est de trouver un découpage efficient de la matrice initiale $A$ en plusieurs sous-matrices $(A_{lm}), l,m \in \{1,...,L\}$ de taille $n_l \times n_m$ [3,4,5]. Ce découpage doit se faire sans recouvrement et doit être exhaustif, c'est-à-dire on doit retrouver la matrice $A$ avec l'union des sous-matrices, c'est-à-dire $\sum_l n_l = \sum_m n_m = n$. A chaque sous-matrice sera associé d'une part, les sous vecteurs $X_l$ du vecteur inconnu $X$ et $B_l$, sous vecteur du deuxième membre $B$, tous les deux de taille $n_l$. Ainsi, l'équation initiale peut s'écrire après découpage :
+
+Ainsi, \eqref{eq:2} peut s'écrire :
+
+\begin{equation}
+ \label{eq:13bis}
+ \left(\begin{array}{ccc}
+ A_{1,1} & \cdots & A_{1,L} \\
+ \vdots & \ddots & \vdots\\
+ A_{n,1} & \cdots & A_{L,L}
+ \end{array} \right)
+ \times
+ \left(\begin{array}{c}
+ X_1 \\
+ \vdots\\
+ X_L
+ \end{array} \right)
+ =
+ \left(\begin{array}{c}
+ B_1 \\
+ \vdots\\
+ B_n
+ \end{array} \right)
+\end{equation}
+
+Une fois le découpage effectué, chaque sous-système \ref{eq:13bis} est attribué à un cluster pour sa résolution indépendante de façon itérative dans ce que la méthode de multisplitting décrit comme les $"iterations$ $internes"$ (interne au cluster). Dans le cadre de nos travaux, l'algorithme GMRES, précédemment étudié, est utilisé pour résoudre localement le sous-système \ref{eq:13}.
+
+\begin{equation}
+ \label{eq:13}
+ \left\{
+ \begin{array}{l}
+ A_{\ell\ell}X_\ell = Y_\ell \text{, tel que}\\
+ Y_\ell = B_\ell - \displaystyle\sum_{\substack{m=1\\ m\neq \ell}}^{L}A_{\ell m}X_m
+ \end{array}
+ \right.
+\end{equation}
+Les résultats intermédiaires sont échangés entre les clusters voisins à la fin de chaque itération de la $"boucle$ $externe$. Le pseudo-code décrit dans la figure Figure~\ref{algo:03} montre les étapes essentielles de l'algorithme de multisplitting en parallèle.\\
+La convergence globale de l'algorithme sera détectée dès que la convergence locale dans chaque cluster est atteinte. La condition de convergence est donnée par \ref{eq:14} où à chaque itération externe k, $X^k_l$ et $X^{k+1}_l$ donne le résidu entre deux résultats consécutifs $k$ et $k+1$ au niveau du cluster $l$, $\epsilon$ le seuil d'erreur accepté et $MaxIter$ le nombre maximum d'itérations convenu.
+
+\begin{equation}
+ \label{eq:14}
+ (k=\MI) \text{ or } (\|X_\ell^k - X_\ell^{k+1}\|\leq\epsilon)
+\end{equation}
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input $A_\ell$ (Matrice d'entrée), $B_\ell$ (Vecteur du membre droit)
+\Output $x_{m}$ (Vecteur solution)\medskip
+
+\State Charger $A_\ell$, $B_\ell$
+\State Assigner la valeur initiale $x^0$
+\For {$k=0,1,2,\ldots$ jusqu'à la convergence globale}
+\State Redémarrer la boucle d'iterations externes $x^0=x^k$
+\State Boucle d'iterations internes : \Call{InnerSolver}{$x^0$, $k+1$}
+\State\label{algo:03:send} Envoyer les éléments partagés $X_\ell^{k+1}$ aux clusters voisins
+\State\label{algo:03:recv} Recevoir les éléments partagés dans $\{X_m^{k+1}\}_{m\neq \ell}$
+\EndFor
+
+\Statex
+
+\Function {InnerSolver}{$x^0$, $k$}
+\State Calculer le membre droit local $Y_\ell$:
+ \begin{equation*}
+ Y_\ell = B_\ell - \sum\nolimits^L_{\substack{m=1\\ m\neq \ell}}A_{\ell m}X_m^0
+ \end{equation*}
+\State Résoudre le sous-système $A_{\ell\ell}X_\ell^k=Y_\ell$ avec la méthode GMRES parallèle
+\State \Return $X_\ell^k$
+\EndFunction
+\end{algorithmic}
+\caption{Solveur Multisplitting utilisant la méthode GMRES en local (version parallèle)}
+\label{algo:03}
+\end{figure}
-Version améliorée
+%%%%Version améliorée
-\section{Simulateurs d'exécution d'algorithmes parallèles MPI dans une grille de calcul}
+\section{Simulateurs d'exécution d'algorithmes parallèles dans une grille de calcul}
-\subsection{Calcul sur grille}
+\subsection{Calcul sur grille de calcul}
Une grille de calcul est caractérisée par "un type de système parallèle et distribué qui permet le partage, la sélection et l'aggrégation de ressources distribuées géographiquement selon leurs capacités" [25] afin de résoudre un problème complexe donné. Ainsi, une grille est composée d'un ensemble de grappes de machines interconnectées entre elles à travers un réseau de communication qui peut s'étendre sur des zones géographiques éloignées (Figure \figref{gridA}). Les capacités de calcul, les mémoires, les applications et les systèmes de stockage sont partagées par les applications parallèles et distribuées. Le calcul sur une grille est caractérisé par un environnement "hétérogène, dynamique et scalable". \\
-\mfigure[h]{width=8cm, height=8cm}{"Grid architecture"} {Architecture d'une grille de calcul} {gridA}
+\mfigure[h]{width=8cm}{"Grid architecture"} {Architecture d'une grille de calcul} {gridA}
-L'hétérogénéité montre la variété des éléments composant la grille de calcul. On peut être en présence de différentes architectures de processeurs dans les machines d'une grappe ou entre les grappes. Les fréquences d'horloge de ces processeurs peuvent être aussi différentes. De même, l'architecture ou la méthode d'accès des mémoires (DRAM, stockage) utilisées dans la grille de calcul peut être aussi être aussi de types différents. Enfin, la topologie ainsi que la performance des réseaux de communications interconnectant les éléments de la grille peuvent être aussi avoir des débits complètement hétérogènes. \\
+L'hétérogénéité montre la variété des éléments composant la grille de calcul. On peut être en présence de différentes architectures de processeurs dans les machines d'une grappe ou entre les grappes. Les fréquences d'horloge de ces processeurs peuvent être aussi différentes. De même, l'architecture ou la méthode d'accès aux mémoires (DRAM, stockage) utilisées dans la grille de calcul peut être aussi être aussi de types différents. Enfin, la topologie ainsi que la performance des réseaux de communications interconnectant les éléments de la grille peuvent être aussi avoir des débits complètement hétérogènes. \\
Le caractéristique dynamique de la grille résulte de la relative facilité de changer de configuration. On peut ainsi tailler dynamiquement l'allocation des ressources de la grille aux utilisateurs selon les besoins de leur demande respective. Cet aspect a été élargi à "l'élasticité" de l'environnement dans le cadre du "cloud computing". \\
Enfin, la scalabilité de la grille de calcul découle de sa conception modulaire permettant d'ajouter d'autres composants selon les besoins. Pour augmenter par exemple la capacité de calcul de la grille, il suffit d'ajouter de nouveaux clusters pour une plus grande puissance globale de la grille. \\
Le milieu de la recherche dispose d'une grille de calcul dédié : le Grid'5000 [26, 27] est une grille répartie géographiquement dans différentes villes de France (Figure \figref{grid5000RG} ) mettant à disposition un "banc d'essai polyvalent à grande échelle" pour les expérimentations de la recherche en informatique particulièrement le calcul parallèle sur grille, sur le cloud, le calcul à haute performance mais aussi sur le Big Data. Grid'5000 permet aux utilisateurs l'accès à des ressources importantes de calcul dans un environnement complètement configurable et controllable. Il peut aussi fournir une trace détaillée ainsi que d'autres informations de mesure sur le comportement de l'application lors de l'exécution pour une étude ultérieure.
-\mfigure[h]{width=8cm, height=8cm}{"Grid5000 sites"} {Grid'5000 : Répartition géographique} {grid5000RG}
+\mfigure[h]{width=8cm}{"Grid5000 sites"} {Grid'5000 : Répartition géographique} {grid5000RG}
Grid'5000 est construit autour de plus de 1000 noeuds physiques de différents constructeurs composés de plus de 2000 processeurs (Intel Xeon et AMD Opteron) avec un total de plus de 10.000 coeurs. Plus de 650 différentes cartes d'interface réseau Ethernet, Infiniband et Myrinet sont interconnectés avec plus de 40 accélérateurs de type NVIDIA GPU et Intel Xeon Phi.
\subsection{Généralités sur la simulation}
La simulation est largement utilisée dans divers domaines de la recherche scientifique. Elle consiste au processus de la mise en oeuvre et "de la conduite d'expérimentations sur un modèle (une représentation simplifiée du réel) dans le but de comprendre le comportement du système modélisé sous des conditions sélectionnées ou de l'évaluation de diverses stratégies pour le fonctionnement du système sous la limite imposée par les critères de développement et d'exploitation" [29]. Particulièrement, la simulation de l'exécution d'une application parallèle distribuée étudie son comportement (résutats en sortie, temps de performance, scalabilité, ...) sur un environnement virtuel imitant au mieux le fonctionnement d'une plateforme physique réel ou d'un système en cours d'élaboration (banc d'essai) ou encore d'une hypothétique machine non encore réalisée. Ainsi, la simulation informatique se focalise sur le comportement dynamique du modèle à travers le temps. Plusieurs raisons motivent une telle simulation: à titre d'exemple, de réduire les coûts de la conception d'un système et d'éviter les erreurs, de produire dans un temps raisonnable des résultats en sortie d'un modèle ayant un temps d'exécution élevé, de répondre à des scénarions d'exécution avec des questions "what-if" (tests et évaluations), ou encore de créer des outils de simulation pour des formations ou des jeux. \\
-Dans le cadre d'une grille de calcul, les simulateurs ou les outils de simulation permettent à l'inverse des plateformes réelles l'évaluation de la performance des expérimentations "répétables et controllables" [25] sur des configurations flexibles et scalables. En effet, les environnements réels montrent leurs limites sur leur rigidité de passage à l'echelle mais aussi sur la flexibilité de disposer un environnement de calcul particulier répondant aux besoins précis de l'application à un moment donné. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'équipements de simulation par des personnes réelles. De façon générale, le simulateur utilise une échelle de temps "discret", c'est-à-dire le temps est découpé en intervalles qui peuvent être réguliers ou non. Dans le cas d'un système à temps discret régulier, le simulateur maintient et met à jour éventuellement un ensemble de "variables d'état" qui reflètent l'état du système physique à un instant t donné. Un "évenement" est associé à chaque instant donné à une "transition d'état". Pour des comparaisons futures, on distingue le "temps physique" comme étant le temps considéré au niveau du système physique, du "temps de simulation" et "le temps de l'horloge murale" désigne le temps de simulation du modèle. Toutefois, le "temps de simulation" est une notion abstraite utilisée par le simulateur pour évaluer le temps de simulation. Il est défini [30] comme étant "un ensemble de valeurs totalement ordonné E où chaque valeur représente un temps du système physique à modéliser et qui vérifie les conditions suivantes:" \\
+Dans le cadre d'une grille de calcul, les simulateurs ou les outils de simulation permettent à l'inverse des plateformes réelles l'évaluation de la performance des expérimentations "répétables et controllables" [25] sur des configurations flexibles et scalables. En effet, les environnements réels montrent leurs limites sur leur rigidité de passage à l'echelle mais aussi sur la flexibilité de disposer d'un environnement de calcul particulier répondant aux besoins précis de l'application à un moment donné. Selon la classification dans [30], la simulation d'applications sur une grille de calcul rejoint la classe de simulation "virtuelle" par l'utilisation d'équipements de simulation par des personnes réelles. De façon générale, le simulateur utilise une échelle de temps "discret", c'est-à-dire le temps est découpé en intervalles qui peuvent être réguliers ou non. Dans le cas d'un système à temps discret régulier, le simulateur maintient et met à jour éventuellement un ensemble de "variables d'état" qui reflètent l'état du système physique à un instant t donné. Un "évenement" est associé à chaque instant donné à une "transition d'état". Pour des comparaisons futures, on distingue le "temps physique" comme étant le temps considéré au niveau du système physique, du "temps de simulation" et "le temps de l'horloge murale" désigne le temps de simulation du modèle. Toutefois, le "temps de simulation" est une notion abstraite utilisée par le simulateur pour évaluer le temps de simulation. Il est défini [30] comme étant "un ensemble de valeurs totalement ordonné E où chaque valeur représente un temps du système physique à modéliser et qui vérifie les conditions suivantes:" \\
Soient E l'ensemble des temps discrets de simulation et P l'ensemble des temps du système physique.
\item[$\bullet$] La gestion de l'environnement MPI: Permet à l'utilisateur d'interagir avec l'environnement MPI créé lors du lancement du programme parallèle. Elle assure par abstraction la portabilité de l'application entre des plateformes matérielles et logicielles différentes.
-\item[$\bullet$] La gestion des processus: Définit la création des processus participant à l'exécution de l'application mais aussi détermine la topologie et la gestiobn des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul.
+\item[$\bullet$] La gestion des processus: Définit la création des processus participant à l'exécution de l'application mais aussi détermine la topologie et la gestion des groupes de processus en accord par exemple avec des architectures complexes comme les grilles de calcul.
\item[$\bullet$] Les types de données : Permettent de créer des structures de données complexes en mémoire à partir des types de données de base comme l'entier, le float, etc...
Le programme MPI s'exécute sur chaque processeur une fois que l'environnement logique est créé par la routine MPI\_Init. Ce dernier est constitué d'un groupe de processus, d'un contexte et d'un communicateur (par défaut MPI\_COMM\_WORLD), voir la figure \figref{MPI}-a. Chaque processus est identifié par son rang dans le groupe associé au communicateur (MPI\_Comm\_rank). Le nombre total de processus en jeu est donné par MPI\_Comm\_size. A la fin du code, MPI\_Finalize termine l'exécution en environnement MPI. De façon générale, une erreur arrête tous les processus en jeu. Toutefois, le programmeur peut gérer et personnaliser les erreurs au niveau de chaque processus ou globalement. Une routine MPI qui se termine avec succès retourne le code MPI\_SUCCESS. \\
-\mfigure[h]{width=8cm, height=8cm}{"MPI"} {Groupes et communicateur (a) - MPI - Opérations collectives (b)} {MPI}
+\mfigure[h]{width=8cm}{"MPI"} {Groupes et communicateur (a) - MPI - Opérations collectives (b)} {MPI}
-Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point à point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message à traiter sont passées à ces fonctions avec le type de données ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spécifiée par le rang du processus d'arrivée du message dans le communicateur considéré. Une variable de statut de l'opération permet de connaitre si l'opération a réussi ou a échoué. Cet échange peut se faire de manière synchrone ou asynchrone(resp. bloquant ou non bloquant). \\
-Contrairement à une communication point à point, une communication dite collective transfère un message à partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion où un processeur envoie le même message à destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les échanges entre les processus après l'appel à cette opération mais aussi d'autres types de communications collectives. Un processus avec MPI\_Scatter distribue une structure de données à d'autres processus participants tandis que MPI\_Gather rassemble des données de plusieurs processus participant en une seule structure. Enfin, les opérations de réduction appliquent une opération (somme, produit, maximum, minimum, etc ...)à un ensemble de processus et retourne le résultat vers le processus appellant.
+Au niveau de la communication, le transfert de message peut se faire d'un processus vers un autre (point à point). Pour cela, les routines MPI\_SEND et MPI\_RECV et leus variantes permettent respectivement d'envoyer et de recevoir un message. L'adresse du tampon contenant le message à traiter est passée à ces fonctions avec le type de données ainsi que le nombre d'objets. La destination dans le cas d'un envoi est spécifiée par le rang du processus d'arrivée du message dans le communicateur considéré. Une variable de statut de l'opération permet de connaitre si l'opération a réussi ou a échoué. Cet échange peut se faire de manière synchrone ou asynchrone(resp. bloquant ou non bloquant). \\
+Contrairement à une communication point à point, une communication dite collective transfère un message à partir d'un processeur vers un ensemble de processeurs. L'exemple le plus courant est le "broadcast" ou diffusion où un processeur envoie le même message à destination d'un ensemble de processeurs. La figure \figref{MPI}-b montre les échanges entre les processus après l'appel à cette opération mais aussi d'autres types de communications collectives. Un processus distribue avec MPI\_Scatter une structure de données à d'autres processus participants tandis que MPI\_Gather rassemble des données de plusieurs processus participant en une seule structure. Enfin, les opérations de réduction appliquent une opération (somme, produit, maximum, minimum, etc ...)à un ensemble de processus et retourne le résultat vers le processus appellant.
La synchronisation des processus peut être obtenue avec la routine MPI\_Barrier qui, une fois lancée par un processus, bloque ce dernier jusqu'à ce que tous les processus de son groupe atteigne cette barrière comme un point de rendez-vous.
\subsection{Simulateur SIMGRID - SMPI}
-SimGrid est utilisé pour la simulation et l'étude du comportement d'applications parallèles dans un contexte d'un environnement complexe, hétérogène, distribué et dynamique. Comme son nom l'indique, développé par la communauté des utilisateurs de grille de calcul, il est utilisé aussi largement sur dans les domaines des applications pair-à-pair,du calcul à haute performance et du cloud computing [5,9]. Le choix de Simgrid comme outil de simulation dans le cadre de ces travaux a été motivé par son efficacité pour la simulation d'applications parallèles à large échelle. En effet, Simgrid rassemble au mieux les caractéristiques requises pour un simulateur dans un environnement de grille de calcul telles que la robustesse, la scalabilité et la justesse des résultats accompagnées d'un temps de réponse correct et d'une tolérance aux pannes de l'exécution [34].
+SimGrid est utilisé pour la simulation et l'étude du comportement d'applications parallèles dans un contexte d'un environnement complexe, hétérogène, distribué et dynamique. Comme son nom l'indique, développé par la communauté des utilisateurs de grille de calcul, il est utilisé aussi largement dans les domaines des applications pair-à-pair, du calcul à haute performance et du cloud computing [5,9]. Le choix de Simgrid comme outil de simulation dans le cadre de ces travaux a été motivé par son efficacité pour la simulation d'applications parallèles à large échelle. En effet, Simgrid rassemble au mieux les caractéristiques requises pour un simulateur dans un environnement de grille de calcul telles que la robustesse, la scalabilité et la justesse des résultats accompagnées d'un temps de réponse correct et d'une tolérance aux pannes de l'exécution [34].
-Simgrid est conçu sur une simulation basée sur les évenements ("event driven")[26, 35] à un niveau d'abstraction et de fonctionnalités répondant aux applications et aux infrastructures. Cinq composants d'abstraction constitue le fonctionnement de Simgrid :
+Simgrid est conçu sur une simulation basée sur les évenements ("event driven") [26, 35] à un niveau d'abstraction et de fonctionnalités répondant aux applications et aux infrastructures. Cinq composants d'abstraction constituent le fonctionnement de Simgrid :
\begin{itemize}
\item[$\bullet$]Une "location" est une hôte de l'environnement de simulation sur laquelle l'agent s'exécute. Outre les données propres à la location, des boîtes aux lettres sont conçues pour permettre les échanges de données avec d'autres agents;
-\item[$\bullet$]Une "tâche" est une activité de l'application simulée. Elle se décline sous forme d'un calcul (temps de calcul nécessaire) ou d'un transfert de données (volume de données à échanger;
+\item[$\bullet$]Une "tâche" est une activité de l'application simulée. Elle se décline sous forme d'un calcul (temps de calcul nécessaire) ou d'un transfert de données (volume de données à échanger);
\item[$\bullet$]Un "chemin" décrit la liaison entre les locations. Il est utilisé par les agents lors d'un transfert de données à calculer le temps de transfert en tenant compte du routage à appliquer pour une telle liaison.
-\item[$\bullet$]La communication entre agents se fait à travers un "channel". Cette abstraction modélise la communication à travers un port entre des agents dans les locations.
+\item[$\bullet$]La communication entre agents se fait à travers un "canal". Cette abstraction modélise la communication à travers un port entre des agents dans les locations.
\end{itemize}
-Simgrid offre pour l'utilisateur plusieurs types d'interfaces de programmation [5,9]: MSG qui simule les "processes séquentiels conccurents", SimDAG qui est utilisé pour simuler des tâches parallèles modélisées en graphe acyclique direct et SMPI qui simule et exécute les applications écrites en MPI sans ou avec des modifications mineures. Outre le langage C natif, Simgrid accepte des applications écrites en C++, Java, Lua ou encore Ruby.
+Simgrid offre pour l'utilisateur plusieurs types d'interfaces de programmation [5,9]: MSG qui simule les "processus séquentiels conccurents", SimDAG qui est utilisé pour simuler des tâches parallèles modélisées en graphe acyclique direct et SMPI qui simule et exécute les applications écrites en MPI sans ou avec des modifications mineures. Outre le langage C natif, Simgrid accepte des applications écrites en C++, Java, Fortran, Lua ou encore Ruby.
De point de vue pratique, la figure \figref{simgrid1} présente la structure et les éléments de la plateforme de simulation Simgrid. Elle est composée des trois parties différentes suivantes :
\item[$\bullet$] Le scénario de la simulation qui constitue les "modèles de ressources" du système. Evidemment, il comprend le code de l'application à exécuter dans le simulateur avec ses différents paramètres d'entrée mais aussi son modèle de déploiement. Un autre composant important de ce scénario aussi est le fichier, généralement au format XML, modélisant les détails de la topologie et l'architecture de l'environnement d'exécution. Il détermine par exemple pour le cas d'une grille de calcul, le nombre et les caractéristiques des clusters contribuant à cet environnement. Pour chaque cluster, les spécifications des serveurs (nombre de cores ou de processeurs, puissance en Flops, taux de disponibilité, ...)sont définies ainsi que les propriétés des réseaux de liaison entre ces différents composants de la grille (topologie du réseau, débit et latence, table de routage, ...).
-\item[$\bullet$] Le simulateur proprement dit.
+\item[$\bullet$] Le simulateur proprement dit comprenant l'application à exécuter et le nouay du simulateur.
\item[$\bullet$] Les fichiers de sortie comprenant les résultats de la simulation de l'application ainsi que d'autres fichiers de monitoring de l'exécution comme un fichier de logging et de statistiques. Simgrid peut générer aussi des données pouvant être utilisées pour représenter visuellement le déroulement et la trace de la simulation dans le temps.
\end{itemize}
-\mfigure[h]{width=8cm, height=8cm}{"Simgrid - In a nutshell"} {SIMGRID : Les éléments de la plateforme de simulation} {simgrid1}
+\mfigure[h]{width=8cm}{"Simgrid - In a nutshell"} {SIMGRID : Les éléments de la plateforme de simulation} {simgrid1}
-Les applications sous-tendant les expérimentations effectuées dans le cadre de ces travaux ont été ecrites en C et utilise les librairies MPI. Simgrid dispose de l'interface SMPI (Simulated MPI) qui peut exécuter un code MPI parallèles sans aucune ou à la limite très peu de modifications. A titre d'exemple, les variables globales doivent être transférées dans un contexte local dans l'application SMPI. Simgrid/SMPI assure l'implémentation de plus de 80\% des routines de la librairie MPI 2.0. Le code est exécuté réellement dans le simulateur dans l'environnement virtuel spécifié sauf que les communications sont interceptées et le temps de transfert calculé en tenant compte du partage des ressources existantes (par exemple le partage de la bande passante entre processus concurrents sur les réseaux de liaison).La scalabilité de Simgrid peut être obtenu par appel à des routines SMPI qui utilisent des structures de données partagées entre les processus parallèles réduisant ainsi la quantité de mémoire utilisée et permettant une montée en charge non négligeable. Toutefois, dans ce cas, comme tous les processus utilisent la même structure de données, la véracité des résultats obtenus n'est pas importante.
+Les applications sous-tendant les expérimentations effectuées dans le cadre de ces travaux ont été ecrites en C et utilisent les librairies MPI. Simgrid dispose de l'interface SMPI (Simulated MPI) qui peut exécuter un code MPI parallèles sans aucune ou à la limite très peu de modifications. A titre d'exemple, les variables globales doivent être transférées dans un contexte local dans l'application SMPI. Simgrid/SMPI assure l'implémentation de plus de 80\% des routines de la librairie MPI 2.0. Le code est exécuté réellement dans le simulateur dans l'environnement virtuel spécifié sauf que les communications sont interceptées et le temps de transfert calculé en tenant compte du partage des ressources existantes (par exemple le partage de la bande passante entre processus concurrents sur les réseaux de liaison).La scalabilité de Simgrid peut être obtenue par appel à des routines SMPI qui utilisent des structures de données partagées entre les processus parallèles réduisant ainsi la quantité de mémoire utilisée et permettant une montée en charge non négligeable. Toutefois, dans ce cas, comme tous les processus utilisent la même structure de données, la véracité des résultats obtenus n'est pas importante.
\section{Conclusion partielle}
Pour un système parallèle « idéal », le speedup est égal à n et l'efficacité
à 1. Dans la pratique, le speedup est toujours inférieur à n avec
-une limite haute dûe à la loi de Amdahl et l'efficacité
+une limite haute dûe à la loi de Amdahl tandis que l'efficacité
a une valeur entre 0 et 1. On peut démontrer que l'efficacité
-est une fnction décroissante du nombre de processeurs n tandis qu'elle
+est une fonction décroissante du nombre de processeurs n tandis qu'elle
est une fonction croissante de la taille du problème.
Dans le cadre de nos travaux, nous avions introduit une métrique utilisée
A l'itération k, la convergence est atteinte quand
:
\begin{equation*}
-(\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)
+(\|X_l^k - X_l^{k+1}\|\leq\epsilon)
\end{equation*}
\subsection{Weak contre strong scaling}
la taille du problème en entrée reste constante même si on adjoint
une capacité plus grande aux unités de calcul.
-\mfigure[h]{width=8cm, height=8cm}{"Weak vs Strong scaling"} {Weak vs Strong scaling: Temps d'exécution et Speedup} {scaling}
+\mfigure[h]{width=10cm}{"Weak vs Strong scaling"} {Weak vs Strong scaling: Temps d'exécution et Speedup} {scaling}
La figure \figref{scaling} montre que le temps d'exécution décroit (resp. reste constant) quand le nombre de processeurs augmente en strong mode (resp. en weak mode). De même, le speedup croit avec le nombre de processeur en strong mode tandis qu'il reste constant en weak mode.
d'un programme en environnement parallèle ont tous
été confrontés à la même problématique de mise à disponibilité de
l'environnement d'exécution. En effet,
-la réservation des ressources nécessaires pour lancer le système n'est
+la réponse à une réservation des ressources nécessaires pour lancer le système n'est
pas toujours immédiate mais en plus, le coût peut ne pas être négligeable
dans un contexte de rareté des machines super puissantes pourtant
très sollicitées par différents acteurs {[}\dots {]}. Cette problématique
$(1)$ d'abord, les échanges internes au niveau d'un
élément d'un bloc (entre les coeurs d'un
processeur et entre les processeurs d'un même serveur
-physique), (2) ensuite, les échanges « intra-blocs » caractérisant
+physique), $(2)$ ensuite, les échanges « intra-blocs » caractérisant
le trafic entre les différents éléments d'un bloc et
-(3) enfin, les échanges « inter-blocs » définissant la communication
+$(3)$ enfin, les échanges « inter-blocs » définissant la communication
entre les blocs de la grille. Tant au niveau de leur topologie qu'en
termes d'efficacité, ces trois niveaux de communication
peuvent présenter des caractéristiques complètement différentes et
puce. La Figure~\ref{fig:4} donne un aperçu de l'architecture
d'un processeur multi-coeurs.
-\mfigure[h]{width=8cm, height=8cm}{"Architecture des CPU multi-coeurs"} {Architecture des CPU multicoeurs} {cpumulti}
+\mfigure[h]{width=8cm}{"Architecture des CPU multi-coeurs"} {Architecture des CPU multicoeurs} {cpumulti}
La performance d'une
telle entité de calcul repose sur la vitesse d'accès
Cette dernière classe regroupant les machines parallèles généralistes
actuelles se décline en trois sous-catégories :
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Distributed Memory"} {Modèle MIMD Distribué} {MIMDDM}
+\mfigure[h]{width=8cm}{"MIMD Distributed Memory"} {Modèle MIMD Mémoire Distribué} {MIMDDM}
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Shared memory - SMP"} {Modèle MIMD partagé} {MIMDSM}
+\mfigure[h]{width=8cm}{"MIMD Shared memory - SMP"} {Modèle MIMD Mémoire partagé} {MIMDSM}
-\mfigure[h]{width=8cm, height=8cm}{"MIMD Hybride"} {Modèle MIMD hybride} {MIMDHY}
+\mfigure[h]{width=8cm}{"MIMD Hybride"} {Modèle MIMD hybride} {MIMDHY}
\begin{itemize}
\item [$\bullet$] - Machine MIMD à mémoire partagée (Figure \figref{MIMDSM}) : Les unités de calcul
-accède à la mémoire partagée via un réseau d'interconnection
+accèdent à la mémoire partagée via un réseau d'interconnection
(généralement, de type GigabitEthernet (renvoi) ou Infiniband (renvoi)).
Il existe trois types d'implémentation : le crossbar,
le Omega-Network et le Central Databus.
\end{itemize}
-A titre d'exemple de machines parallèles, le site Top500.org
+A titre d'exemple de machines parallèles, le site Top5000.org
{[}14{]} classe suivant différents critères les plus performantes.
Ainsi, la figure \figref {power} montre l'évolution de la puissance
de calcul mondiale dont le top actuel développe un pic de performance
Center à Guangzhou en Chine {[}15{]}. A la tendance actuelle, l'atteinte
de l'exaflops n'est pas loin.
-\mfigure[h]{width=8cm, height=8cm}{"Evolution de la puissance de calcul mondiale"} {Evolution de la puissance de calcul mondiale} {power}
+\mfigure[h]{width=8cm}{"Evolution de la puissance de calcul mondiale"} {Evolution de la puissance de calcul mondiale} {power}
Pour arriver à de telles puissances, diverses architectures de processeurs
ont vu le jour ces dernières années. Outre l'Intel
les CPU accèdent une page mémoire physique de façon « uniforme »,
avec le même temps d'accès tolérant ainsi la mise à
l'échelle. Dans ce cas, les CPU sont tous connectés
-aux mémoires via un bus ((Figure \figref{UMA}). Un système d'adressage
+aux mémoires via un bus (Figure \figref{UMA}). Un système d'adressage
global est appliqué à l'ensemble des mémoires physiques.
(2) NUMA ou « Non Uniform Memory Access » où les groupes de CPU accèdent
à des mémoires locales à travers des buses et les groupes sont interconnectés
-par un réseau de communication ((Figure \figref{NUMA}). Dans ce cas, le temps
+par un réseau de communication (Figure \figref{NUMA}). Dans ce cas, le temps
d'accès des CPU aux pages mémoires varie selon que
ces dernières sont locales ou distantes. L'espace d'adressage
des mémoires se fait au niveau de chaque groupe de CPU. (3) L'architecture
COMA (« Cache Only Memory Access ») est un hybride avec un modèle
de programmation de mémoire partagée mais une implémentation physique
-de mémoire distribué ((Figure \figref{COMA}). Dans ce cas, chaque noeud détient
+de mémoire distribué (Figure \figref{COMA}). Dans ce cas, chaque noeud détient
une partie du système de l'espace d'adressage.
Le partitionnement des données étant dynamique, la structure COMA
n'associe pas la même adresse à une page physique de
la mémoire. Les mémoires locales dans ce cas de figure jouent finalement
un rôle de cache au processeur.
-\mfigure[h]{width=8cm, height=8cm}{"UMA architecture"} {Mémoire MIMD: Architecture UMA} {UMA}
+\mfigure[h]{width=8cm}{"UMA architecture"} {Mémoire MIMD: Architecture UMA} {UMA}
-\mfigure[h]{width=8cm, height=8cm}{"NUMA architecture"} {Mémoire MIMD: Architecture NUMA} {NUMA}
+\mfigure[h]{width=8cm}{"NUMA architecture"} {Mémoire MIMD: Architecture NUMA} {NUMA}
-\mfigure[h]{width=8cm, height=8cm}{"COMA architecture"} {Mémoire MIMD: Architecture COMA} {COMA}
+\mfigure[h]{width=7cm}{"COMA architecture"} {Mémoire MIMD: Architecture COMA} {COMA}
Malgré que dans le cadre de nos travaux, nous n'avions
pas eu une contrainte particulière en termes de système de stockage,
\end{itemize}
Les deux derniers points sont regroupés sous le nom générique de "profiling" ou de "tracing" selon le modèle adopté de l'acquistion des données. La figure \figref{anaperf} montre ces trois couches de l'analyse de performance et décrit les différentes techniques utilisées pour cette analyse. Les flèches tracées sur la figure montrent les combinaisons possibles entre les techniques présentées. D'ailleurs, dans la pratique, d'autres combinaisons peuvent être expérimentées pour atteindre les objectifs fixés.
-\mfigure[h]{width=8cm, height=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf}
+\mfigure[h]{width=8cm}{"Performance Analysis techniques"} {Classification des techniques d'analyse de la performance} {anaperf}
Cette approche à trois étapes commence par la collecte des données sur la performance du code qui consiste à deux techniques les plus utilisées à savoir le "sampling" (ou "l'échantillonage") et "l'instrumentation basée sur les évenements".
\begin{itemize}
-\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les données décrivant l'état du code lors de l'exécution du programme à chaque instant défini par la fréquence de l'echantillonage. IL est réalisé généralement avec la mise en place d'un timer qui déclenche la collecte des données selon une période définie. Ces dernières se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matériels [22]. Ainsi, il est d'usage de collecter le temps d'exécution d'un fonction ou combien de fois la fonction a été appellée ou encore de façon plus détaillée, combien de fois une ligne de code est exécutée. Evidemment, l'efficacité de la méthode dépend du taux d'échantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultérieure. Par contre, la surcharge engrendrée par la technique peut être contrôlée par l'utilisateur par un choix adéquet de la fréquence de l'echantillonage. \\
+\item [$\bullet$] Le "sampling" ou "l'echantillonage" capture les données décrivant l'état du code lors de l'exécution du programme à chaque instant défini par la fréquence de l'echantillonage. Il est réalisé généralement avec la mise en place d'un timer qui déclenche la collecte des données selon une période définie. Ces dernières se rapportent sur les statistiques relatives aux appels de fonctions ("call-path" des fonctions) mais aussi sur les compteurs matériels [22]. Ainsi, il est d'usage de collecter le temps d'exécution d'une fonction ou combien de fois la fonction a été appellée ou encore de façon plus détaillée, combien de fois une ligne de code est exécutée. Evidemment, l'efficacité de la méthode dépend du taux d'échantillonnage: les informations entre deux points de collecte ne sont pas disponibles pour l'analyse ultérieure. Par contre, la surcharge engrendrée par la technique peut être contrôlée par l'utilisateur par un choix adéquat de la fréquence de l'echantillonage. \\
L'alternative pour collecter les données de la performance d'une application parallèle se porte sur l'instrumentation basée sur les évenements. D'abord, de façon générale, l'instrumentation du code consiste à ajouter manuellement ou automatiquement des instructions supplémentaires à des endroits choisis afin de rapporter à chaque passage des informations spécifiques. A titre d'exemple, on peut positionner un timer au début d'une portion du code et d'arrêter ce timer à la sortie de cette région. On peut ainsi collecter le temps total d'execution consommé par l'application pour exécuter cette partie du programme. Cette technique est largement utilisée par exemple pour détermijner le temps de communication nécessaire lors d'un appel d'une instruction MPI de transfert ou collective (MPI\_send, MPI\_receive ou autre MPI\_Barrier). Cette modification directe qui nécessite une récompilation du code est aussi appellée "instrumentation au niveau de la source". D'autres techniques utilisant des outils existent telles que les "libraries wrapping" ou la "réécriture du code binaire" [22]. Ces dernières n'ont pas besoin d'une recompilation du code.
\item [$\bullet$] La deuxième étape du processus de la collecte des données en vue d'une future analyse consiste à enregister soit en mémoire soit sur un support de stockage externe les données obtenues lors de l'étape précédente. Deux techniques peuvent être exploitées à cette fin. D'abord, le "logging" ou le "tracing" permet d'ajouter le facteur temps sur les données collectées. Ainsi, avant le stockage, chaque entrée de données est estampillée d'une date de l'évenement (au format date - heure). Cette opération peut ajouter un temps de surcharge non négligeable lors de l'exécution.\\
Afin de réduire cette dernière mais aussi pour optimiser la taille du fichier de trace obtenu, la technique de "summarization" consiste à agréger les données après la collecte et de ne stocker que le minimum d'informations utiles. Ce dernier est généralement appellé le "profile" de l'application [21,22]. Certains détails peuvent être perdus avec cette méthode mais il s'agit ici de faire une balance entre la taille la granularité de l'information et la taille des données stockées.
-\item [$\bullet$] La troisième et dernière étape de l'analyse de la performance concerne la visualisation des données collectées en vue de l'analyse proporement dite et des décisions à prendre pour améliorer et optimiser l'exécution de l'application. Dans la même ligne de l'étape précédente, soient les données sont visualisées "au fil du temps" en suivant l'exécution du code sur les différentes machines de l'environnement parallèle, soient elles sont représentées par un groupement selon un facteur compréhensible par l'analyste (par fonction par exemple), on est en présence d'une technique générant un "timelines" ou un "profile" de l'application respectivement.
+\item [$\bullet$] La troisième et dernière étape de l'analyse de la performance concerne la visualisation des données collectées en vue de l'analyse proporement dite et des décisions à prendre pour améliorer et optimiser l'exécution de l'application. Dans la même ligne de l'étape précédente, soient les données sont visualisées "au fil du temps" en suivant l'exécution du code sur les différentes machines de l'environnement parallèle, soient elles sont représentées par un groupement selon un facteur compréhensible par l'analyste (par fonction par exemple), on est en présence d'une technique générant un "timeline" ou un "profile" de l'application respectivement.
\end{itemize}
\begin{itemize}
-\item [$\bullet$] IPM
+\item [$\bullet$] IPM (Integrated Performance Monitoring), comme tous les outils d'analyse de la performance particulièrement pour un code MPI, fournit d'une part les statistiques du profiling du code comprenant les indicateurs lors des appels de routines MPI mais aussi d'autre part, le tracing du code collectant les détails de l'historique et l'ordre des évènemments passés MPI lors de l'exécution du code [37, 38]. L'inventaire de ces évenements se fait par une "mesure directe". IPM se montre particulèrement efficace pour détecter les désequilibres de charge entre les processeurs pour une application parallèle. De plus, son utilisation entraîne une surcharge de calcul négligeable.
-\item [$\bullet$] TAU a été conçu à l'Université d'Oregon comme un outil open source d'évaluation de performance [24]. Il intègre le profiling et le tracing constituant une platerme complète couvrant les trois étapes de l'analyse d'une applicatio parallèle. L'instrumentation du code peut être effectuée d'une façon complètement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les régions et hotspots du code, l'utilisation mémoire, les boucles, les entrées/sorties,...Selon le paramètrage de lancement, TAU peut collecter des informations les plus fines telles que le temps passé à chaque instruction dans une boucle ou le temps passé dans les communications à une étape du programme particulièrement dans les instructions collectives MPI par exemple. Toutes ces données peuvent par la suite être visualisées sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance.
+\item [$\bullet$] TAU (Tuning and Analysis Utilities) a été conçu à l'Université d'Oregon comme un outil open source d'évaluation de performance [24, 42]. Il intègre de façon non intrusive le profiling et le tracing constituant une plateforme complète couvrant les trois étapes de l'analyse d'une application parallèle. L'instrumentation du code peut être effectuée d'une façon complètement automatique avec un package fourni ("PDT - Program Database Toolkit - for routines")collectant toutes les informations sur les régions et hotspots du code, l'utilisation mémoire, les boucles, les entrées/sorties,...Selon le paramètrage de lancement, TAU peut collecter des informations les plus fines telles que le temps passé à chaque instruction dans une boucle ou le temps passé dans les communications à une étape du programme particulièrement dans les instructions collectives MPI par exemple. Toutes ces données peuvent par la suite être visualisées sous forme graphique (Paraprof 3D browser) pour une analyse fine afin d'optimiser la performance.
-\item [$\bullet$] SCALA ou SCAlabity Analyzer est orienté particulèrement dans l'analyse de la performance des applications sur sa scalabilité lors de la montée en charge. Outre la prédiction de la performance, SCALA utilise les fonctionnalités avancées actuelles pour la mise au point (debugging) de la dite performance et d'une éventuelle restructuration du code parallèle d'une part mais aussi d'estimer l'impact des variations sur l'environnement matériel d'exécution.
+\item [$\bullet$] SCALA ou SCAlabity Analyzer est orienté particulèrement dans l'analyse de la performance des applications sur sa scalabilité lors de la montée en charge. Outre la prédiction de la performance (voir la section suivante), SCALA utilise les fonctionnalités avancées actuelles du compilateur pour la mise au point (debugging) de la dite performance et d'une éventuelle restructuration du code parallèle d'une part mais aussi d'estimer l'impact des variations sur l'environnement matériel d'exécution. L'outil permet de générer des suggestions de modifications du code pour une stratégie d'optimisation une fois l'analyse de la performance achevée.
\end{itemize}
\section{Méthodes de prédiction de la performance des applications parallèles}
+La prédiction de la performance des applications distribuées se présente comme une suite logique de l'analyse de la performance des dites applications. En effet, outre la compréhension du système ainsi que la collecte des détails sur l'exécution du système qui constituent fondamentalement l'analyse de la performance, la prédiction de cette performance du code est plus complexe parce que dans ce cas, on essaie, à partir des résultats des analyses sur une plateforme matérielle donnée, d'estimer les résultats et le comportement du système sur une plateforme cible globalement plus puissante mais aussi avec des paramètres d'entrées différents. Dans la classe d'applications considérée dans ces travaux, les résultats de prédiction les plus importants sont le temps d'exécution et le temps de communication estimés. Les objectifs de la prédiction sont axés sur la minimisation du coût de l'opération mais aussi et surtout son efficacité et sa justesse exprimées par le taux d'erreur de la prédiction.\\
+Plusieurs méthodes sont utilisées pour réaliser une prédiction de la performance des programmes parallèles distribués en particulier sur une grille de calcul. On peut les classer en trois catégories : les méthodes "analytiques", celles basées sur le profiling et enfin, les méthodes de prédiction utilisant la simulation. Des auteurs ont proposé des combinaisons dénommées "hybrides" de ces méthodes [39].
+\begin{itemize}
+
+\item [$\bullet$] La méthode analytique de prédiction de la performance consiste à la modélisation mathématique du comportement et l'exécution du code à analyser. Une fois le modèle construit, on peut calculer les temps d'exécution et de communication en fonction des paramètres passés comme la taille du problème, la puissance de calcul disponible, les paramètres du réseau. La méthode est réalisée en deux étapes [39, 40]:
+\begin{itemize}
+\item [$\bullet$] (1) la collecte des informations sur l'ensemble ou uniquement sur des régions choisies du code par instrumentation en utilisant des outils existant ou par l'ajout de pragmas et des lignes de capture d'informations dans le code. Cette opération peut être répétées plusieurs fois pour avoir une série de résultats éliminant ainsi des éventuels effets de bord. Les données collectées sont consignées dans un fichier au format convenu pour la prochaine étape.
+\item [$\bullet$] (2) la modélisation mathématique par la construction du modèle incluant la partie calcul mais aussi le volet réseau pour établir les formules reliant les paramètres en entrée de l'application avec les résultats obtenus. Cette étape peut être réalisée avec des techniques de statistiques d'analyse prédictive ou encore avec d'autres méthodes analytiques. La ou l'ensemble de fonctions décrivant le modèle peut être obtenue par itérations successives jusqu'à l'btention d'une erreur inférieure à un seuil préalablement établi.
+\end{itemize}
+
+PMaC ou "Performance Modelling and Characterization" de l'Université de San Diego [42] montre un exemple d'une méthode analytique de prédiction de la perfomance. Il consiste d'une part à déterminer la "signature" de l'application qui regroupe les résumés détaillés des différentes opérations fondamentales effectuées par l'application [41]. D'autre part, le "profile" de l'environnement d'exécution est aussi modélisé en donnant une "caractérisation" du matériel (CPU, mémoire, réseau, ...) par des métriques d'exécution des opérations fondamentales pour une application donnée. Dans une seconde étape, à partir de ces données collectées, un modèle mathématique est établi pour construire un mapping entre l'environnement d'exécution et la signature de l'applcation. Ce modèle sera utilisé pour une prédiction de la performance sur un autre environnement mais aussi éventuellement pour une autre taille du problème.
+
+\item [$\bullet$] Les méthodes de prédiction basées sur le profiling du code sont toujours accompagnées d'un tracing de l'exécution de l'application [40,41].Des outils de profiling et de tracing peuvent être utilisés afin de collecter les informations essentielles sur les différents blocs du code. Une fois ces informations disponibles, afin de déterminer la performance de l'application sur un autre environnement d'exécution, la prédiction de cette performance est obtenue en rejouant le fichier de trace sur cet environnement cible.
+TAU, un outil d'analyse de performance déjà mentionné plus haut, utilise cette méthode de prédiction. En effet, il incorpore des outils d'instrumentation, de mesures de performance matérielle et d'analyse.
-%Voir [23]
+\end{itemize}
\section{Conclusion partielle}
{[}36{]} Xian-He Sun, T. Fahringer, M. Pantano - SCALA: A perfformance system for scalable computing - \textit{Department Of Computer Science, Illinois Institute of Technology Chicago, Institute for software technology and parallel systems, University of Vienna Liechtenstein - The International Journal of High Performance Computing Applications,Volume 16, No. 4, Autumn 2002,}
+{[}37{]} IPM : Integrated Performance Monitoring - ipm-hpc.sourceforge.net
+
+{[}38{]} K. Fuerlinger, D. Skinner - Performance Analysis and Workload Workload Characterization with IPM -
+\textit{University of California Berkeley}
+
+{[}39{]} B. Florin Cornea et J. Bourgeois - Performance Prediction of Distributed Applications Using Block Benchmarking Methods - \textit{LIFC, University of Franche-Comté,Montbéliard, France}
+
+{[}40{]} D. R. Martinez, V. Blanco, M. Boullon, J. C. Cabaleiro, T. F. Pena - Analytical Performance Models of Parallel Programs in Clusters - \textit {University of Santiago de Compostela, Spain - La Laguna University, Spain}
+
+{[}41{]} R. Allan, A. Mills - Survey of HPC Performance Modelling and Prediction Tools - \textit {Computational Science and Engineering Department, Daresbury Laboratory, Warrington - High Performance Systems Group, Department of Computer Science, University of Warwick, Coventry}
+
+{[}42{]} PMaC : Performance Modeling and Characterization - http://www.sdsc.edu/pmac/
+
+{[}43{]} Haiwu He. Analyses avancées de la méthode hybride GMRES/LS-ARNOLDI asynchrone parallèle et distribuée pour les grilles de calcul et les supercalculateurs. \textit {Université des Sciences et Technologie de Lille, 2005}.
+
+{[}44{]} GMRES : Generalized minimal residual method. \textit {https://en.wikipedia.org/wiki/Generalized\_minimal\_residual\_method}.
+{[}45{]} G. Fasshauer - Numerical linear algebra - Illinois Institute of Technology - Department of Applied Mathematics - Chicago. 2006. Chapitre 14 - \textit {http://www.math.iit.edu/~fass/477577\_Chapter\_14.pdf}.
%%--------------------
%% List of figures and tables
\select@language {french}\r
\contentsline {part}{I\hspace {1em}PARTIE I: Contexte scientifique et revue de l'\IeC {\'e}tat de l'art}{3}{part.1}\r
-\contentsline {chapter}{\numberline {1}Cadre de travail et contexte scientifique}{5}{chapter.1}\r
-\contentsline {section}{\numberline {1.1}Classe des algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les \IeC {\`a} large \IeC {\'e}chelle dans une grille de calcul}{5}{section.1.1}\r
-\contentsline {subsection}{\numberline {1.1.1}Partitionnement du probl\IeC {\`e}me}{6}{subsection.1.1.1}\r
-\contentsline {subsection}{\numberline {1.1.2}Modes d'ex\IeC {\'e}cution synchrone et asynchrone}{7}{subsection.1.1.2}\r
-\contentsline {section}{\numberline {1.2}M\IeC {\'e}thodes de r\IeC {\'e}solution parall\IeC {\`e}les du probl\IeC {\`e}me de Poisson et de l'algorithme two-stage multisplitting de Krylov}{9}{section.1.2}\r
-\contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{9}{subsection.1.2.1}\r
-\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{10}{subsection.1.2.2}\r
-\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{11}{subsection.1.2.3}\r
-\contentsline {section}{\numberline {1.3}Simulateurs d'ex\IeC {\'e}cution d'algorithmes parall\IeC {\`e}les MPI dans une grille de calcul}{11}{section.1.3}\r
-\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{11}{subsection.1.3.1}\r
-\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{13}{subsection.1.3.2}\r
-\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{15}{subsection.1.3.3}\r
-\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{17}{subsection.1.3.4}\r
-\contentsline {section}{\numberline {1.4}Conclusion partielle}{19}{section.1.4}\r
-\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{21}{chapter.2}\r
-\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{21}{section.2.1}\r
-\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{21}{subsection.2.1.1}\r
-\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{23}{subsection.2.1.2}\r
-\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{23}{subsection.2.1.3}\r
-\contentsline {section}{\numberline {2.2}Probl\IeC {\'e}matique sur la pr\IeC {\'e}diction \IeC {\`a} large \IeC {\'e}chelle de la performance des applications}{24}{section.2.2}\r
-\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{25}{subsection.2.2.1}\r
-\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{26}{subsubsection.2.2.1.1}\r
-\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{28}{subsubsection.2.2.1.2}\r
-\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{32}{subsubsection.2.2.1.3}\r
-\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{32}{subsection.2.2.2}\r
-\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{33}{subsubsection.2.2.2.1}\r
-\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{33}{subsubsection.2.2.2.2}\r
-\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{36}{section.2.3}\r
-\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{36}{subsection.2.3.1}\r
-\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{36}{subsection.2.3.2}\r
-\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{38}{subsection.2.3.3}\r
-\contentsline {section}{\numberline {2.4}M\IeC {\'e}thodes de pr\IeC {\'e}diction de la performance des applications parall\IeC {\`e}les}{39}{section.2.4}\r
-\contentsline {section}{\numberline {2.5}Conclusion partielle}{39}{section.2.5}\r
-\contentsline {chapter}{\numberline {3}Motivations}{41}{chapter.3}\r
-\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{43}{part.2}\r
-\contentsline {chapter}{\numberline {4}Comparaison par simulation \IeC {\`a} large \IeC {\'e}chelle de la performance de deux algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les en mode asynchrone}{45}{chapter.4}\r
-\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{45}{section.4.1}\r
-\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{45}{section.4.2}\r
-\contentsline {section}{\numberline {4.3}Conclusion partielle}{45}{section.4.3}\r
-\contentsline {chapter}{\numberline {5}Simulation avec SIMGRID de l\textquoteright ex\IeC {\'e}cution des solveurs lin\IeC {\'e}aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\IeC {\'e}s}{47}{chapter.5}\r
-\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{47}{section.5.1}\r
-\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{47}{section.5.2}\r
-\contentsline {section}{\numberline {5.3}Conclusion partielle}{47}{section.5.3}\r
-\contentsline {chapter}{\numberline {6}Mod\IeC {\`e}le de pr\IeC {\'e}diction de la performance \IeC {\`a} large \IeC {\'e}chelle d'un algorithme it\IeC {\'e}ratif parall\IeC {\`e}le}{49}{chapter.6}\r
-\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{49}{section.6.1}\r
-\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{49}{section.6.2}\r
-\contentsline {section}{\numberline {6.3}Conclusion partielle}{49}{section.6.3}\r
-\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{51}{chapter.7}\r
-\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{51}{section.7.1}\r
-\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{51}{section.7.2}\r
-\contentsline {part}{III\hspace {1em}Annexes}{65}{part.3}\r
-\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{67}{appendix.A}\r
-\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{69}{appendix.B}\r
+\contentsline {chapter}{\numberline {1}Cadre de travail et contexte scientifique}{7}{chapter.1}\r
+\contentsline {section}{\numberline {1.1}Classe des algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les \IeC {\`a} large \IeC {\'e}chelle dans une grille de calcul}{7}{section.1.1}\r
+\contentsline {subsection}{\numberline {1.1.1}Partitionnement du probl\IeC {\`e}me}{8}{subsection.1.1.1}\r
+\contentsline {subsection}{\numberline {1.1.2}Modes d'ex\IeC {\'e}cution synchrone et asynchrone}{9}{subsection.1.1.2}\r
+\contentsline {section}{\numberline {1.2}M\IeC {\'e}thodes de r\IeC {\'e}solution parall\IeC {\`e}les du probl\IeC {\`e}me de Poisson et de l'algorithme two-stage multisplitting de Krylov}{10}{section.1.2}\r
+\contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{10}{subsection.1.2.1}\r
+\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{11}{subsection.1.2.2}\r
+\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{14}{subsection.1.2.3}\r
+\contentsline {section}{\numberline {1.3}Simulateurs d'ex\IeC {\'e}cution d'algorithmes parall\IeC {\`e}les dans une grille de calcul}{15}{section.1.3}\r
+\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille de calcul}{15}{subsection.1.3.1}\r
+\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{17}{subsection.1.3.2}\r
+\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{19}{subsection.1.3.3}\r
+\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{21}{subsection.1.3.4}\r
+\contentsline {section}{\numberline {1.4}Conclusion partielle}{23}{section.1.4}\r
+\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{25}{chapter.2}\r
+\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{25}{section.2.1}\r
+\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{25}{subsection.2.1.1}\r
+\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{27}{subsection.2.1.2}\r
+\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{27}{subsection.2.1.3}\r
+\contentsline {section}{\numberline {2.2}Probl\IeC {\'e}matique sur la pr\IeC {\'e}diction \IeC {\`a} large \IeC {\'e}chelle de la performance des applications}{28}{section.2.2}\r
+\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{29}{subsection.2.2.1}\r
+\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{30}{subsubsection.2.2.1.1}\r
+\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{32}{subsubsection.2.2.1.2}\r
+\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{35}{subsubsection.2.2.1.3}\r
+\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{35}{subsection.2.2.2}\r
+\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{35}{subsubsection.2.2.2.1}\r
+\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{36}{subsubsection.2.2.2.2}\r
+\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{38}{section.2.3}\r
+\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{38}{subsection.2.3.1}\r
+\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{39}{subsection.2.3.2}\r
+\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{41}{subsection.2.3.3}\r
+\contentsline {section}{\numberline {2.4}M\IeC {\'e}thodes de pr\IeC {\'e}diction de la performance des applications parall\IeC {\`e}les}{41}{section.2.4}\r
+\contentsline {section}{\numberline {2.5}Conclusion partielle}{43}{section.2.5}\r
+\contentsline {chapter}{\numberline {3}Motivations}{45}{chapter.3}\r
+\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{47}{part.2}\r
+\contentsline {chapter}{\numberline {4}Comparaison par simulation \IeC {\`a} large \IeC {\'e}chelle de la performance de deux algorithmes it\IeC {\'e}ratifs parall\IeC {\`e}les en mode asynchrone}{49}{chapter.4}\r
+\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{49}{section.4.1}\r
+\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{49}{section.4.2}\r
+\contentsline {section}{\numberline {4.3}Conclusion partielle}{49}{section.4.3}\r
+\contentsline {chapter}{\numberline {5}Simulation avec SIMGRID de l\textquoteright ex\IeC {\'e}cution des solveurs lin\IeC {\'e}aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\IeC {\'e}s}{51}{chapter.5}\r
+\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{51}{section.5.1}\r
+\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{51}{section.5.2}\r
+\contentsline {section}{\numberline {5.3}Conclusion partielle}{51}{section.5.3}\r
+\contentsline {chapter}{\numberline {6}Mod\IeC {\`e}le de pr\IeC {\'e}diction de la performance \IeC {\`a} large \IeC {\'e}chelle d'un algorithme it\IeC {\'e}ratif parall\IeC {\`e}le}{53}{chapter.6}\r
+\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{53}{section.6.1}\r
+\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{53}{section.6.2}\r
+\contentsline {section}{\numberline {6.3}Conclusion partielle}{53}{section.6.3}\r
+\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{55}{chapter.7}\r
+\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{55}{section.7.1}\r
+\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{55}{section.7.2}\r
+\contentsline {part}{III\hspace {1em}Annexes}{69}{part.3}\r
+\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{71}{appendix.A}\r
+\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{73}{appendix.B}\r
