From: RCE Date: Sat, 9 Jan 2016 21:26:19 +0000 (+0100) Subject: RCE : Update du 9/1/2016 X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/commitdiff_plain/c9389c5838efd5d6872ab508eaa000e3a769ed18 RCE : Update du 9/1/2016 --- diff --git a/Grid architecture.PNG b/Grid architecture.PNG new file mode 100644 index 0000000..1077bc6 Binary files /dev/null and b/Grid architecture.PNG differ diff --git a/Grid5000 sites.PNG b/Grid5000 sites.PNG new file mode 100644 index 0000000..665b7b2 Binary files /dev/null and b/Grid5000 sites.PNG differ diff --git a/MPI.pdf b/MPI.pdf new file mode 100644 index 0000000..55bc4e4 Binary files /dev/null and b/MPI.pdf differ diff --git a/Performance Analysis techniques.pdf b/Performance Analysis techniques.pdf new file mode 100644 index 0000000..c975c4f Binary files /dev/null and b/Performance Analysis techniques.pdf differ diff --git a/Simgrid - In a nutshell.pdf b/Simgrid - In a nutshell.pdf new file mode 100644 index 0000000..ed5e75b Binary files /dev/null and b/Simgrid - In a nutshell.pdf differ diff --git a/These_RCE.aux b/These_RCE.aux index 63a4a5b..c0a8fff 100644 --- a/These_RCE.aux +++ b/These_RCE.aux @@ -40,104 +40,112 @@ \newlabel{fig:async}{{1.4}{9}{Modèle de communication asynchrone}{figure.1.4}{}} \@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}} \@writefile{toc}{\contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{9}{subsection.1.2.1}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{9}{subsection.1.2.2}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{9}{subsection.1.2.3}} -\@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}{9}{section.1.3}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{9}{subsection.1.3.1}} -\@writefile{lof}{\contentsline {figure}{\numberline {1.5}{\ignorespaces Architecture d'une grille de calcul}}{10}{figure.1.5}} -\newlabel{fig:gridA}{{1.5}{10}{Architecture d'une grille de calcul}{figure.1.5}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {1.6}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{11}{figure.1.6}} -\newlabel{fig:grid5000RG}{{1.6}{11}{Grid'5000 : Répartition géographique}{figure.1.6}{}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{11}{subsection.1.3.2}} -\newlabel{eqsim}{{1.8}{12}{Généralités sur la simulation}{equation.1.3.8}{}} -\@writefile{lot}{\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{13}{table.1.1}} -\newlabel{table1}{{1.1}{13}{Quelques outils de simulation pour une grille de calcul}{table.1.1}{}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{13}{subsection.1.3.3}} -\@writefile{lof}{\contentsline {figure}{\numberline {1.7}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{14}{figure.1.7}} -\newlabel{fig:MPI}{{1.7}{14}{Groupes et communicateur (a) - MPI - Opérations collectives (b)}{figure.1.7}{}} -\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{15}{subsection.1.3.4}} -\@writefile{toc}{\contentsline {section}{\numberline {1.4}Motivations}{15}{section.1.4}} -\@writefile{toc}{\contentsline {section}{\numberline {1.5}Conclusion partielle}{15}{section.1.5}} -\@writefile{toc}{\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{17}{chapter.2}} +\newlabel{eq:2}{{1.8}{9}{Algorithme de Jacobi}{equation.1.2.8}{}} +\newlabel{eq:3}{{1.9}{10}{Algorithme de Jacobi}{equation.1.2.9}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{10}{subsection.1.2.2}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{11}{figure.1.5}} +\newlabel{algo:01}{{1.5}{11}{Algorithme itératif de Jacobi}{figure.1.5}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{11}{subsection.1.2.3}} +\@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}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{11}{subsection.1.3.1}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.6}{\ignorespaces Architecture d'une grille de calcul}}{12}{figure.1.6}} +\newlabel{fig:gridA}{{1.6}{12}{Architecture d'une grille de calcul}{figure.1.6}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.7}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{13}{figure.1.7}} +\newlabel{fig:grid5000RG}{{1.7}{13}{Grid'5000 : Répartition géographique}{figure.1.7}{}} +\@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}} +\newlabel{eqsim}{{1.11}{14}{Généralités sur la simulation}{equation.1.3.11}{}} +\@writefile{lot}{\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{15}{table.1.1}} +\newlabel{table1}{{1.1}{15}{Quelques outils de simulation pour une grille de calcul}{table.1.1}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{15}{subsection.1.3.3}} +\@writefile{lof}{\contentsline {figure}{\numberline {1.8}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{16}{figure.1.8}} +\newlabel{fig:MPI}{{1.8}{16}{Groupes et communicateur (a) - MPI - Opérations collectives (b)}{figure.1.8}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{17}{subsection.1.3.4}} +\@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}} +\newlabel{fig:simgrid1}{{1.9}{18}{SIMGRID : Les éléments de la plateforme de simulation}{figure.1.9}{}} +\@writefile{toc}{\contentsline {section}{\numberline {1.4}Conclusion partielle}{19}{section.1.4}} +\@writefile{toc}{\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{21}{chapter.2}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{17}{section.2.1}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{17}{subsection.2.1.1}} -\newlabel{eq:5}{{2.1}{17}{Performance de l'application parallèle et scalabilité}{equation.2.1.1}{}} -\newlabel{eq:6}{{2.2}{18}{Performance de l'application parallèle et scalabilité}{equation.2.1.2}{}} -\newlabel{eq:7}{{2.3}{18}{Performance de l'application parallèle et scalabilité}{equation.2.1.3}{}} -\newlabel{eq:8}{{2.4}{18}{Performance de l'application parallèle et scalabilité}{equation.2.1.4}{}} -\newlabel{eq:9}{{2.5}{19}{Performance de l'application parallèle et scalabilité}{equation.2.1.5}{}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{19}{subsection.2.1.2}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{19}{subsection.2.1.3}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{20}{figure.2.1}} -\newlabel{fig:scaling}{{2.1}{20}{Weak vs Strong scaling: Temps d'exécution et Speedup}{figure.2.1}{}} -\@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}{20}{section.2.2}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{21}{subsection.2.2.1}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{22}{subsubsection.2.2.1.1}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{23}{figure.2.2}} -\newlabel{fig:cpumulti}{{2.2}{23}{Architecture des CPU multicoeurs}{figure.2.2}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{24}{figure.2.3}} -\newlabel{fig:MIMDDM}{{2.3}{24}{Modèle MIMD Distribué}{figure.2.3}{}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{24}{subsubsection.2.2.1.2}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{25}{figure.2.4}} -\newlabel{fig:MIMDSM}{{2.4}{25}{Modèle MIMD partagé}{figure.2.4}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{26}{figure.2.5}} -\newlabel{fig:MIMDHY}{{2.5}{26}{Modèle MIMD hybride}{figure.2.5}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{27}{figure.2.6}} -\newlabel{fig:power}{{2.6}{27}{Evolution de la puissance de calcul mondiale}{figure.2.6}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{28}{figure.2.7}} -\newlabel{fig:UMA}{{2.7}{28}{Mémoire MIMD: Architecture UMA}{figure.2.7}{}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{28}{subsubsection.2.2.1.3}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{28}{subsection.2.2.2}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{29}{figure.2.8}} -\newlabel{fig:NUMA}{{2.8}{29}{Mémoire MIMD: Architecture NUMA}{figure.2.8}{}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{29}{subsubsection.2.2.2.1}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{29}{subsubsection.2.2.2.2}} -\newlabel{eq:10}{{2.6}{29}{Performance de la parallélisation}{equation.2.2.6}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{30}{figure.2.9}} -\newlabel{fig:COMA}{{2.9}{30}{Mémoire MIMD: Architecture COMA}{figure.2.9}{}} -\newlabel{eq:11}{{2.7}{30}{Performance de la parallélisation}{equation.2.2.7}{}} -\newlabel{eq:12}{{2.8}{30}{Performance de la parallélisation}{equation.2.2.8}{}} -\newlabel{eq:12}{{2.9}{31}{Performance de la parallélisation}{equation.2.2.9}{}} -\@writefile{toc}{\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{32}{section.2.3}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{32}{subsection.2.3.1}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{32}{subsection.2.3.2}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{33}{figure.2.10}} -\newlabel{fig:anaperf}{{2.10}{33}{Classification des techniques d'analyse de la performance}{figure.2.10}{}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{34}{subsection.2.3.3}} -\@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}{35}{section.2.4}} -\@writefile{toc}{\contentsline {section}{\numberline {2.5}Conclusion partielle}{35}{section.2.5}} -\@writefile{toc}{\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{37}{part.2}} -\@writefile{toc}{\contentsline {chapter}{\numberline {3}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}{39}{chapter.3}} +\@writefile{toc}{\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{21}{section.2.1}} +\@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}} +\newlabel{eq:5}{{2.1}{21}{Performance de l'application parallèle et scalabilité}{equation.2.1.1}{}} +\newlabel{eq:6}{{2.2}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.2}{}} +\newlabel{eq:7}{{2.3}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.3}{}} +\newlabel{eq:8}{{2.4}{22}{Performance de l'application parallèle et scalabilité}{equation.2.1.4}{}} +\newlabel{eq:9}{{2.5}{23}{Performance de l'application parallèle et scalabilité}{equation.2.1.5}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{23}{subsection.2.1.2}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{23}{subsection.2.1.3}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{24}{figure.2.1}} +\newlabel{fig:scaling}{{2.1}{24}{Weak vs Strong scaling: Temps d'exécution et Speedup}{figure.2.1}{}} +\@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}} +\@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}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{26}{subsubsection.2.2.1.1}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{27}{figure.2.2}} +\newlabel{fig:cpumulti}{{2.2}{27}{Architecture des CPU multicoeurs}{figure.2.2}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{28}{figure.2.3}} +\newlabel{fig:MIMDDM}{{2.3}{28}{Modèle MIMD Distribué}{figure.2.3}{}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{28}{subsubsection.2.2.1.2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{29}{figure.2.4}} +\newlabel{fig:MIMDSM}{{2.4}{29}{Modèle MIMD partagé}{figure.2.4}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{30}{figure.2.5}} +\newlabel{fig:MIMDHY}{{2.5}{30}{Modèle MIMD hybride}{figure.2.5}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{31}{figure.2.6}} +\newlabel{fig:power}{{2.6}{31}{Evolution de la puissance de calcul mondiale}{figure.2.6}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{32}{figure.2.7}} +\newlabel{fig:UMA}{{2.7}{32}{Mémoire MIMD: Architecture UMA}{figure.2.7}{}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{32}{subsubsection.2.2.1.3}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{32}{subsection.2.2.2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{33}{figure.2.8}} +\newlabel{fig:NUMA}{{2.8}{33}{Mémoire MIMD: Architecture NUMA}{figure.2.8}{}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{33}{subsubsection.2.2.2.1}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{33}{subsubsection.2.2.2.2}} +\newlabel{eq:10}{{2.6}{33}{Performance de la parallélisation}{equation.2.2.6}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{34}{figure.2.9}} +\newlabel{fig:COMA}{{2.9}{34}{Mémoire MIMD: Architecture COMA}{figure.2.9}{}} +\newlabel{eq:11}{{2.7}{34}{Performance de la parallélisation}{equation.2.2.7}{}} +\newlabel{eq:12}{{2.8}{34}{Performance de la parallélisation}{equation.2.2.8}{}} +\newlabel{eq:12}{{2.9}{35}{Performance de la parallélisation}{equation.2.2.9}{}} +\@writefile{toc}{\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{36}{section.2.3}} +\@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}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{36}{subsection.2.3.2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{37}{figure.2.10}} +\newlabel{fig:anaperf}{{2.10}{37}{Classification des techniques d'analyse de la performance}{figure.2.10}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{38}{subsection.2.3.3}} +\@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}} +\@writefile{toc}{\contentsline {section}{\numberline {2.5}Conclusion partielle}{39}{section.2.5}} +\@writefile{toc}{\contentsline {chapter}{\numberline {3}Motivations}{41}{chapter.3}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {3.1}Protocoles et exp\IeC {\'e}rimentations}{39}{section.3.1}} -\@writefile{toc}{\contentsline {section}{\numberline {3.2}R\IeC {\'e}sultats}{39}{section.3.2}} -\@writefile{toc}{\contentsline {section}{\numberline {3.3}Conclusion partielle}{39}{section.3.3}} -\@writefile{toc}{\contentsline {chapter}{\numberline {4}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}{41}{chapter.4}} +\@writefile{toc}{\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{43}{part.2}} +\@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}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{41}{section.4.1}} -\@writefile{toc}{\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{41}{section.4.2}} -\@writefile{toc}{\contentsline {section}{\numberline {4.3}Conclusion partielle}{41}{section.4.3}} -\@writefile{toc}{\contentsline {chapter}{\numberline {5}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}{43}{chapter.5}} +\@writefile{toc}{\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{45}{section.4.1}} +\@writefile{toc}{\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{45}{section.4.2}} +\@writefile{toc}{\contentsline {section}{\numberline {4.3}Conclusion partielle}{45}{section.4.3}} +\@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}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {5.1}Approche et m\IeC {\'e}thodologie}{43}{section.5.1}} -\@writefile{toc}{\contentsline {section}{\numberline {5.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{43}{section.5.2}} -\@writefile{toc}{\contentsline {section}{\numberline {5.3}Conclusion partielle}{43}{section.5.3}} -\@writefile{toc}{\contentsline {chapter}{\numberline {6}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{45}{chapter.6}} +\@writefile{toc}{\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{47}{section.5.1}} +\@writefile{toc}{\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{47}{section.5.2}} +\@writefile{toc}{\contentsline {section}{\numberline {5.3}Conclusion partielle}{47}{section.5.3}} +\@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}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {6.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{45}{section.6.1}} -\@writefile{toc}{\contentsline {section}{\numberline {6.2}Travaux futurs et perspectives}{45}{section.6.2}} +\@writefile{toc}{\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{49}{section.6.1}} +\@writefile{toc}{\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{49}{section.6.2}} +\@writefile{toc}{\contentsline {section}{\numberline {6.3}Conclusion partielle}{49}{section.6.3}} +\@writefile{toc}{\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{51}{chapter.7}} +\@writefile{lof}{\addvspace {10\p@ }} +\@writefile{lot}{\addvspace {10\p@ }} +\@writefile{toc}{\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{51}{section.7.1}} +\@writefile{toc}{\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{51}{section.7.2}} \bibstyle{phdthesisapa} \bibdata{biblio.bib} -\@writefile{toc}{\contentsline {part}{III\hspace {1em}Annexes}{57}{part.3}} -\@writefile{toc}{\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{59}{appendix.A}} +\@writefile{toc}{\contentsline {part}{III\hspace {1em}Annexes}{65}{part.3}} +\@writefile{toc}{\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{67}{appendix.A}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{61}{appendix.B}} +\@writefile{toc}{\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{69}{appendix.B}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} diff --git a/These_RCE.dvi b/These_RCE.dvi new file mode 100644 index 0000000..e1219bc Binary files /dev/null and b/These_RCE.dvi differ diff --git a/These_RCE.lof b/These_RCE.lof index 9cea16f..8b6954b 100644 --- a/These_RCE.lof +++ b/These_RCE.lof @@ -4,20 +4,23 @@ \contentsline {figure}{\numberline {1.2}{\ignorespaces D\IeC {\'e}composition en domaines 1D, 2D et 3D}}{6}{figure.1.2} \contentsline {figure}{\numberline {1.3}{\ignorespaces Mod\IeC {\`e}le de communication synchrone}}{8}{figure.1.3} \contentsline {figure}{\numberline {1.4}{\ignorespaces Mod\IeC {\`e}le de communication asynchrone}}{9}{figure.1.4} -\contentsline {figure}{\numberline {1.5}{\ignorespaces Architecture d'une grille de calcul}}{10}{figure.1.5} -\contentsline {figure}{\numberline {1.6}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{11}{figure.1.6} -\contentsline {figure}{\numberline {1.7}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{14}{figure.1.7} -\addvspace {10\p@ } -\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{20}{figure.2.1} -\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{23}{figure.2.2} -\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{24}{figure.2.3} -\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{25}{figure.2.4} -\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{26}{figure.2.5} -\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{27}{figure.2.6} -\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{28}{figure.2.7} -\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{29}{figure.2.8} -\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{30}{figure.2.9} -\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{33}{figure.2.10} +\contentsline {figure}{\numberline {1.5}{\ignorespaces Algorithme it\IeC {\'e}ratif de Jacobi}}{11}{figure.1.5} +\contentsline {figure}{\numberline {1.6}{\ignorespaces Architecture d'une grille de calcul}}{12}{figure.1.6} +\contentsline {figure}{\numberline {1.7}{\ignorespaces Grid'5000 : R\IeC {\'e}partition g\IeC {\'e}ographique}}{13}{figure.1.7} +\contentsline {figure}{\numberline {1.8}{\ignorespaces Groupes et communicateur (a) - MPI - Op\IeC {\'e}rations collectives (b)}}{16}{figure.1.8} +\contentsline {figure}{\numberline {1.9}{\ignorespaces SIMGRID : Les \IeC {\'e}l\IeC {\'e}ments de la plateforme de simulation}}{18}{figure.1.9} +\addvspace {10\p@ } +\contentsline {figure}{\numberline {2.1}{\ignorespaces Weak vs Strong scaling: Temps d'ex\IeC {\'e}cution et Speedup}}{24}{figure.2.1} +\contentsline {figure}{\numberline {2.2}{\ignorespaces Architecture des CPU multicoeurs}}{27}{figure.2.2} +\contentsline {figure}{\numberline {2.3}{\ignorespaces Mod\IeC {\`e}le MIMD Distribu\IeC {\'e}}}{28}{figure.2.3} +\contentsline {figure}{\numberline {2.4}{\ignorespaces Mod\IeC {\`e}le MIMD partag\IeC {\'e}}}{29}{figure.2.4} +\contentsline {figure}{\numberline {2.5}{\ignorespaces Mod\IeC {\`e}le MIMD hybride}}{30}{figure.2.5} +\contentsline {figure}{\numberline {2.6}{\ignorespaces Evolution de la puissance de calcul mondiale}}{31}{figure.2.6} +\contentsline {figure}{\numberline {2.7}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture UMA}}{32}{figure.2.7} +\contentsline {figure}{\numberline {2.8}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture NUMA}}{33}{figure.2.8} +\contentsline {figure}{\numberline {2.9}{\ignorespaces M\IeC {\'e}moire MIMD: Architecture COMA}}{34}{figure.2.9} +\contentsline {figure}{\numberline {2.10}{\ignorespaces Classification des techniques d'analyse de la performance}}{37}{figure.2.10} +\addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } diff --git a/These_RCE.log b/These_RCE.log index 9eed2cc..0e4191b 100644 --- a/These_RCE.log +++ b/These_RCE.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.14159265-2.6-1.40.16 (MiKTeX 2.9) (preloaded format=pdflatex 2015.11.9) 12 DEC 2015 10:00 +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 entering extended mode **These_RCE.tex (These_RCE.tex @@ -988,54 +988,75 @@ Now handling font encoding PD1 ... defining Unicode char U+2122 (decimal 8482) defining Unicode char U+2423 (decimal 9251) )) -("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\multirow\multirow.sty" +(C:\Users\rmj2666\AppData\Roaming\MiKTeX\2.9\tex\latex\algorithmicx\algpseudoco +de.sty +Package: algpseudocode + +(C:\Users\rmj2666\AppData\Roaming\MiKTeX\2.9\tex\latex\algorithmicx\algorithmic +x.sty +Package: algorithmicx 2005/04/27 v1.2 Algorithmicx + +Document Style algorithmicx 1.2 - a greatly improved `algorithmic' style +\c@ALG@line=\count159 +\c@ALG@rem=\count160 +\c@ALG@nested=\count161 +\ALG@tlm=\skip72 +\ALG@thistlm=\skip73 +\c@ALG@Lnr=\count162 +\c@ALG@blocknr=\count163 +\c@ALG@storecount=\count164 +\c@ALG@tmpcounter=\count165 +\ALG@tmplength=\skip74 +) +Document Style - pseudocode environments for use with the `algorithmicx' style +) ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\multirow\multirow.sty" \bigstrutjot=\dimen175 ) *** define extension value defensedate **** -\c@upmmytheorem=\count159 +\c@upmmytheorem=\count166 (These_RCE.aux LaTeX Warning: Label `eq:12' multiply defined. ) -LaTeX Font Info: Checking defaults for OML/txmi/m/it on input line 191. -LaTeX Font Info: Try loading font information for OML+txmi on input line 191 +LaTeX Font Info: Checking defaults for OML/txmi/m/it on input line 197. +LaTeX Font Info: Try loading font information for OML+txmi on input line 197 . ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\omltxmi.fd" File: omltxmi.fd 2000/12/15 v3.1 ) -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 191. -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 191. -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for OMS/txsy/m/n on input line 191. -LaTeX Font Info: Try loading font information for OMS+txsy on input line 191 +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 197. +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 197. +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for OMS/txsy/m/n on input line 197. +LaTeX Font Info: Try loading font information for OMS+txsy on input line 197 . ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\omstxsy.fd" File: omstxsy.fd 2000/12/15 v3.1 ) -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for OMX/txex/m/n on input line 191. -LaTeX Font Info: Try loading font information for OMX+txex on input line 191 +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for OMX/txex/m/n on input line 197. +LaTeX Font Info: Try loading font information for OMX+txex on input line 197 . ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\omxtxex.fd" File: omxtxex.fd 2000/12/15 v3.1 ) -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for U/txexa/m/n on input line 191. -LaTeX Font Info: Try loading font information for U+txexa on input line 191. +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for U/txexa/m/n on input line 197. +LaTeX Font Info: Try loading font information for U+txexa on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\utxexa.fd" File: utxexa.fd 2000/12/15 v3.1 ) -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 191. -LaTeX Font Info: ... okay on input line 191. -LaTeX Font Info: Try loading font information for OT1+phv on input line 191. +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 197. +LaTeX Font Info: ... okay on input line 197. +LaTeX Font Info: Try loading font information for OT1+phv on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\psnfss\ot1phv.fd" @@ -1043,26 +1064,26 @@ File: ot1phv.fd 2001/06/04 scalable font definitions for OT1/phv. ) ("C:\Program Files (x86)\MiKTeX 2.9\tex\context\base\supp-pdf.mkii" [Loading MPS to PDF converter (version 2006.09.02).] -\scratchcounter=\count160 +\scratchcounter=\count167 \scratchdimen=\dimen176 \scratchbox=\box75 -\nofMPsegments=\count161 -\nofMParguments=\count162 +\nofMPsegments=\count168 +\nofMParguments=\count169 \everyMPshowfont=\toks42 -\MPscratchCnt=\count163 +\MPscratchCnt=\count170 \MPscratchDim=\dimen177 -\MPnumerator=\count164 -\makeMPintoPDFobject=\count165 +\MPnumerator=\count171 +\makeMPintoPDFobject=\count172 \everyMPtoPDFconversion=\toks43 ) -LaTeX Info: Redefining \degres on input line 191. -LaTeX Info: Redefining \dots on input line 191. -LaTeX Info: Redefining \up on input line 191. +LaTeX Info: Redefining \degres on input line 197. +LaTeX Info: Redefining \dots on input line 197. +LaTeX Info: Redefining \up on input line 197. Package frenchb.ldf Warning: OT1 encoding should not be used for French. (frenchb.ldf) Add \usepackage[T1]{fontenc} to the preamble -(frenchb.ldf) of your document, on input line 191. +(frenchb.ldf) of your document, on input line 197. *** Overriding the 'enumerate' environment. Pass option 'standardlists' for avo @@ -1070,7 +1091,7 @@ iding this override. *** Overriding the 'description' environment. Pass option 'standardlists' for a voiding this override. \AtBeginShipoutBox=\box76 -Package hyperref Info: Link coloring OFF on input line 191. +Package hyperref Info: Link coloring OFF on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\hyperref\nameref.sty" Package: nameref 2012/10/27 v2.43 Cross-referencing by name of section @@ -1078,22 +1099,22 @@ Package: nameref 2012/10/27 v2.43 Cross-referencing by name of section ("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\oberdiek\gettitlestring.sty" Package: gettitlestring 2010/12/03 v1.4 Cleanup title references (HO) ) -\c@section@level=\count166 +\c@section@level=\count173 LaTeX Info: Redefining \Ref on input line 513. ) -LaTeX Info: Redefining \ref on input line 191. -LaTeX Info: Redefining \pageref on input line 191. -LaTeX Info: Redefining \nameref on input line 191. +LaTeX Info: Redefining \ref on input line 197. +LaTeX Info: Redefining \pageref on input line 197. +LaTeX Info: Redefining \nameref on input line 197. (These_RCE.out) (These_RCE.out) \@outlinefile=\write3 -LaTeX Info: Redefining \Ref on input line 191. +LaTeX Info: Redefining \Ref on input line 197. ************ USE CUSTOM FRONT COVER File: spimufcphdthesis-frontpage.pdf Graphic file (type pdf) -Package pdftex.def Info: spimufcphdthesis-frontpage.pdf used on input line 191. +Package pdftex.def Info: spimufcphdthesis-frontpage.pdf used on input line 197. (pdftex.def) Requested size: 600.00493pt x 855.03816pt. [1 @@ -1107,35 +1128,35 @@ phdthesis-frontpage.pdf>] [2 File: spimufcphdthesis-p3-head.pdf Graphic file (type pdf) -Package pdftex.def Info: spimufcphdthesis-p3-head.pdf used on input line 191. +Package pdftex.def Info: spimufcphdthesis-p3-head.pdf used on input line 197. (pdftex.def) Requested size: 600.0pt x 285.92554pt. LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <10.95> not available -(Font) Font shape `OT1/phv/b/n' tried instead on input line 191. -LaTeX Font Info: Try loading font information for OT1+txr on input line 191. +(Font) Font shape `OT1/phv/b/n' tried instead on input line 197. +LaTeX Font Info: Try loading font information for OT1+txr on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\ot1txr.fd" File: ot1txr.fd 2000/12/15 v3.1 ) -LaTeX Font Info: Try loading font information for U+txmia on input line 191. +LaTeX Font Info: Try loading font information for U+txmia on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\utxmia.fd" File: utxmia.fd 2000/12/15 v3.1 ) -LaTeX Font Info: Try loading font information for U+txsya on input line 191. +LaTeX Font Info: Try loading font information for U+txsya on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\utxsya.fd" File: utxsya.fd 2000/12/15 v3.1 ) -LaTeX Font Info: Try loading font information for U+txsyb on input line 191. +LaTeX Font Info: Try loading font information for U+txsyb on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\utxsyb.fd" File: utxsyb.fd 2000/12/15 v3.1 ) -LaTeX Font Info: Try loading font information for U+txsyc on input line 191. +LaTeX Font Info: Try loading font information for U+txsyc on input line 197. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\utxsyc.fd" @@ -1165,7 +1186,7 @@ Underfull \vbox (badness 10000) has occurred while \output is active [] ] [4] Chapitre 1. -LaTeX Warning: Reference `fig:decoupage' on page 5 undefined on input line 277. +LaTeX Warning: Reference `fig:decoupage' on page 5 undefined on input line 283. [5 @@ -1176,7 +1197,7 @@ File: "3D data partitionning btw 2 clusters".pdf Graphic file (type pdf) Package pdftex.def Info: "3D data partitionning btw 2 clusters".pdf used on inp -ut line 284. +ut line 290. (pdftex.def) Requested size: 156.49014pt x 104.12645pt. <"1D-2D-3D Domain decomposition".pdf, id=422, 229.85875pt x 520.94624pt> @@ -1184,7 +1205,7 @@ File: "1D-2D-3D Domain decomposition".pdf Graphic file (type pdf) Package pdftex.def Info: "1D-2D-3D Domain decomposition".pdf used on input line - 289. + 295. (pdftex.def) Requested size: 156.49014pt x 354.6839pt. Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -1192,14 +1213,14 @@ Underfull \vbox (badness 10000) has occurred while \output is active [] [6 <./3D data partitionning btw 2 clusters.pdf> <./1D-2D-3D Domain decompositi on.pdf>] -LaTeX Warning: Reference `fig:Decompo' on page 7 undefined on input line 356. +LaTeX Warning: Reference `fig:Decompo' on page 7 undefined on input line 362. <"Synchronous iterations model".pdf, id=432, 597.51233pt x 845.0471pt> File: "Synchronous iterations model".pdf Graphic file (type pdf) Package pdftex.def Info: "Synchronous iterations model".pdf used on input line -376. +382. (pdftex.def) Requested size: 227.62231pt x 227.6242pt. @@ -1210,7 +1231,7 @@ File: "Asynchronous iterations model".pdf Graphic file (type pdf) Package pdftex.def Info: "Asynchronous iterations model".pdf used on input line - 378. + 384. (pdftex.def) Requested size: 227.61887pt x 227.63321pt. @@ -1226,127 +1247,155 @@ ARGE []ECHELLE DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 7 Underfull \vbox (badness 10000) has occurred while \output is active [] [8 <./Synchronous iterations model.pdf>] -Underfull \hbox (badness 10000) in paragraph at lines 465--466 - - [] - - Overfull \hbox (312.32625pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 1.2. M[]ETHODES DE R[]ESOLUTION PARALL[]ELES DU PROBL[]EME DE POISSON ET DE L'ALGORITHME TWO-STAGE MULTISPLITTING DE KRYLOV \OT1/phv/m/n/ 10.95 9 [] -[9 <./Asynchronous iterations model.pdf>] -<"Grid architecture".png, id=472, 449.42906pt x 176.15813pt> +[9 <./Asynchronous iterations model.pdf>] [10] +Underfull \hbox (badness 10000) in paragraph at lines 584--585 + + [] + +<"Grid architecture".png, id=484, 449.42906pt x 176.15813pt> File: "Grid architecture".png Graphic file (type png) -Package pdftex.def Info: "Grid architecture".png used on input line 467. +Package pdftex.def Info: "Grid architecture".png used on input line 586. (pdftex.def) Requested size: 227.62164pt x 227.62123pt. -Underfull \hbox (badness 10000) in paragraph at lines 469--472 + +LaTeX Warning: `h' float specifier changed to `ht'. + + +Underfull \hbox (badness 10000) in paragraph at lines 588--591 [] -[10 <./Grid architecture.png>] -<"Grid5000 sites".png, id=482, 292.09125pt x 231.86626pt> + +Overfull \hbox (107.96115pt too wide) has occurred while \output is active +\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES +MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 11 + [] + +[11] <"Grid5000 sites".png, id=493, 292.09125pt x 231.86626pt> File: "Grid5000 sites".png Graphic file (type png) -Package pdftex.def Info: "Grid5000 sites".png used on input line 475. +Package pdftex.def Info: "Grid5000 sites".png used on input line 594. (pdftex.def) Requested size: 227.62967pt x 227.62715pt. -Underfull \hbox (badness 10000) in paragraph at lines 483--485 + +LaTeX Warning: `h' float specifier changed to `ht'. + + +Underfull \vbox (badness 10000) has occurred while \output is active [] + + [12 <./Grid architecture.png>] +Underfull \hbox (badness 10000) in paragraph at lines 602--604 [] Overfull \hbox (107.96115pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES -MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 11 +MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 13 [] -[11 <./Grid5000 sites.png>] -LaTeX Font Info: Try loading font information for OT1+txtt on input line 493 +[13 <./Grid5000 sites.png>] +LaTeX Font Info: Try loading font information for OT1+txtt on input line 612 . ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\txfonts\ot1txtt.fd" File: ot1txtt.fd 2000/12/15 v3.1 ) -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Font Info: Try loading font information for OML+phv on input line 493. +LaTeX Font Info: Try loading font information for OML+phv on input line 612. ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\psnfss\omlphv.fd" File: omlphv.fd ) LaTeX Font Info: Font shape `OML/phv/m/n' in size <10.95> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 493. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -LaTeX Warning: Command \textless invalid in math mode on input line 493. +LaTeX Warning: Command \textless invalid in math mode on input line 612. -Underfull \hbox (badness 10000) in paragraph at lines 496--499 +Underfull \hbox (badness 10000) in paragraph at lines 615--618 [] -[12] LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <8> not available -(Font) Font shape `OT1/phv/b/n' tried instead on input line 515. +(Font) Font shape `OT1/phv/b/n' tried instead on input line 634. -Overfull \hbox (41.8198pt too wide) in paragraph at lines 512--540 +Overfull \hbox (41.8198pt too wide) in paragraph at lines 631--659 [][] [] - +[14] Overfull \hbox (107.96115pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES -MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 13 +MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 15 [] -[13] -Underfull \hbox (badness 10000) in paragraph at lines 563--564 +[15] +Underfull \hbox (badness 10000) in paragraph at lines 682--683 [] -<"MPI".pdf, id=502, 614.295pt x 794.97pt> +<"MPI".pdf, id=520, 614.295pt x 794.97pt> File: "MPI".pdf Graphic file (type pdf) -Package pdftex.def Info: "MPI".pdf used on input line 565. +Package pdftex.def Info: "MPI".pdf used on input line 684. (pdftex.def) Requested size: 227.62303pt x 227.62413pt. + [16 <./MPI.pdf>] +Overfull \hbox (107.96115pt too wide) has occurred while \output is active +\OT1/phv/m/sl/10.95 1.3. SIMULATEURS D'EX[]ECUTION D'ALGORITHMES PARALL[]ELES +MPI DANS UNE GRILLE DE CALCUL \OT1/phv/m/n/10.95 17 + [] -Underfull \vbox (badness 10000) has occurred while \output is active [] +[17] - [14 <./MPI.pdf>] [15] [16 +pdfTeX warning: pdflatex (file ./Simgrid - In a nutshell.pdf): PDF inclusion: f +ound PDF version <1.7>, but at most version <1.5> allowed +<"Simgrid - In a nutshell".pdf, id=543, 298.2091pt x 132.36852pt> +File: "Simgrid - In a nutshell".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "Simgrid - In a nutshell".pdf used on input line 723. +(pdftex.def) Requested size: 227.62411pt x 227.63707pt. + [18 <./Simgrid - In a nutshell.pdf>] +[19] [20 ] Chapitre 2. -[17] [18] <"Weak vs Strong scaling".pdf, id=541, 617.30624pt x 188.705pt> +[21] [22] <"Weak vs Strong scaling".pdf, id=573, 617.30624pt x 188.705pt> File: "Weak vs Strong scaling".pdf Graphic file (type pdf) -Package pdftex.def Info: "Weak vs Strong scaling".pdf used on input line 750. +Package pdftex.def Info: "Weak vs Strong scaling".pdf used on input line 902. (pdftex.def) Requested size: 227.61792pt x 227.62253pt. @@ -1355,54 +1404,55 @@ LaTeX Warning: `h' float specifier changed to `ht'. Underfull \vbox (badness 6859) has occurred while \output is active [] - [19] + [23] Underfull \vbox (badness 1655) has occurred while \output is active [] - [20 <./Weak vs Strong scaling.pdf>] + [24 <./Weak vs Strong scaling.pdf>] Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 21 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 25 [] -[21] +[25] -LaTeX Warning: Reference `fig:4' on page 22 undefined on input line 932. +LaTeX Warning: Reference `fig:4' on page 26 undefined on input line 1084. -[22] -<"Architecture des CPU multi-coeurs".pdf, id=565, 275.0275pt x 173.64874pt> +[26] +<"Architecture des CPU multi-coeurs".pdf, id=596, 275.0275pt x 173.64874pt> File: "Architecture des CPU multi-coeurs".pdf Graphic file (type pdf) Package pdftex.def Info: "Architecture des CPU multi-coeurs".pdf used on input -line 935. +line 1087. (pdftex.def) Requested size: 227.63069pt x 227.6299pt. -<"MIMD Distributed Memory".pdf, id=566, 928.46875pt x 474.77374pt> +<"MIMD Distributed Memory".pdf, id=597, 928.46875pt x 474.77374pt> File: "MIMD Distributed Memory".pdf Graphic file (type pdf) -Package pdftex.def Info: "MIMD Distributed Memory".pdf used on input line 948. +Package pdftex.def Info: "MIMD Distributed Memory".pdf used on input line 1100. + (pdftex.def) Requested size: 227.61142pt x 227.62076pt. LaTeX Warning: `h' float specifier changed to `ht'. -<"MIMD Shared memory - SMP".pdf, id=567, 624.3325pt x 483.8075pt> +<"MIMD Shared memory - SMP".pdf, id=598, 624.3325pt x 483.8075pt> File: "MIMD Shared memory - SMP".pdf Graphic file (type pdf) -Package pdftex.def Info: "MIMD Shared memory - SMP".pdf used on input line 950. - +Package pdftex.def Info: "MIMD Shared memory - SMP".pdf used on input line 1102 +. (pdftex.def) Requested size: 227.6175pt x 227.6258pt. LaTeX Warning: `h' float specifier changed to `ht'. -<"MIMD Hybride".pdf, id=568, 564.1075pt x 358.33875pt> +<"MIMD Hybride".pdf, id=599, 564.1075pt x 358.33875pt> File: "MIMD Hybride".pdf Graphic file (type pdf) -Package pdftex.def Info: "MIMD Hybride".pdf used on input line 952. +Package pdftex.def Info: "MIMD Hybride".pdf used on input line 1104. (pdftex.def) Requested size: 227.61873pt x 227.62459pt. @@ -1414,54 +1464,54 @@ Underfull \vbox (badness 4291) has occurred while \output is active [] Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 23 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 27 [] -[23 <./Architecture des CPU multi-coeurs.pdf>] -<"Evolution de la puissance de calcul mondiale".pdf, id=581, 702.625pt x 489.83 +[27 <./Architecture des CPU multi-coeurs.pdf>] +<"Evolution de la puissance de calcul mondiale".pdf, id=613, 702.625pt x 489.83 pt> File: "Evolution de la puissance de calcul mondiale".pdf Graphic file (type pdf ) Package pdftex.def Info: "Evolution de la puissance de calcul mondiale".pdf use -d on input line 986. +d on input line 1138. (pdftex.def) Requested size: 227.62137pt x 227.61911pt. LaTeX Warning: `h' float specifier changed to `ht'. -[24 <./MIMD Distributed Memory.pdf>] -<"UMA architecture".pdf, id=591, 400.49625pt x 172.645pt> +[28 <./MIMD Distributed Memory.pdf>] +<"UMA architecture".pdf, id=623, 400.49625pt x 172.645pt> File: "UMA architecture".pdf Graphic file (type pdf) -Package pdftex.def Info: "UMA architecture".pdf used on input line 1053. +Package pdftex.def Info: "UMA architecture".pdf used on input line 1205. (pdftex.def) Requested size: 227.62523pt x 227.626pt. Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 25 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 29 [] -[25 <./MIMD Shared memory - SMP.pdf>] +[29 <./MIMD Shared memory - SMP.pdf>] LaTeX Warning: `h' float specifier changed to `ht'. -<"NUMA architecture".pdf, id=600, 429.605pt x 223.83624pt> +<"NUMA architecture".pdf, id=632, 429.605pt x 223.83624pt> File: "NUMA architecture".pdf Graphic file (type pdf) -Package pdftex.def Info: "NUMA architecture".pdf used on input line 1055. +Package pdftex.def Info: "NUMA architecture".pdf used on input line 1207. (pdftex.def) Requested size: 227.62401pt x 227.62685pt. LaTeX Warning: `h' float specifier changed to `ht'. -<"COMA architecture".pdf, id=601, 333.245pt x 278.03876pt> +<"COMA architecture".pdf, id=633, 333.245pt x 278.03876pt> File: "COMA architecture".pdf Graphic file (type pdf) -Package pdftex.def Info: "COMA architecture".pdf used on input line 1057. +Package pdftex.def Info: "COMA architecture".pdf used on input line 1209. (pdftex.def) Requested size: 227.62566pt x 227.62415pt. @@ -1470,144 +1520,152 @@ LaTeX Warning: `h' float specifier changed to `ht'. Underfull \vbox (badness 10000) has occurred while \output is active [] - [26 <./MIMD Hybride.pdf>] + [30 <./MIMD Hybride.pdf>] Underfull \vbox (badness 10000) has occurred while \output is active [] Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 27 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 31 [] -[27 <./Evolution de la puissance de calcul mondiale.pdf>] [28 <./UMA architectu +[31 <./Evolution de la puissance de calcul mondiale.pdf>] [32 <./UMA architectu re.pdf>] Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 29 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 33 [] -[29 <./NUMA architecture.pdf>] [30 <./COMA architecture.pdf>] +[33 <./NUMA architecture.pdf>] [34 <./COMA architecture.pdf>] Underfull \vbox (badness 10000) has occurred while \output is active [] Overfull \hbox (138.89304pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.2. PROBL[]EMATIQUE SUR LA PR[]EDICTION []A LARGE []ECHEL -LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 31 +LE DE LA PERFORMANCE DES APPLICATIONS \OT1/phv/m/n/10.95 35 [] -[31] <"Performance Analysis techniques".pdf, id=638, 505.89pt x 287.0725pt> +[35] <"Performance Analysis techniques".pdf, id=669, 505.89pt x 287.0725pt> File: "Performance Analysis techniques".pdf Graphic file (type pdf) Package pdftex.def Info: "Performance Analysis techniques".pdf used on input li -ne 1321. +ne 1473. (pdftex.def) Requested size: 227.62523pt x 227.62581pt. LaTeX Warning: `h' float specifier changed to `ht'. -[32] +[36] Underfull \vbox (badness 6268) has occurred while \output is active [] Overfull \hbox (22.54312pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.3. TECHNIQUES D'ANALYSE DE PERFORMANCE DES APPLICATIONS -PARALL[]ELES \OT1/phv/m/n/10.95 33 +PARALL[]ELES \OT1/phv/m/n/10.95 37 [] -[33 <./Performance Analysis techniques.pdf>] -Underfull \vbox (badness 10000) has occurred while \output is active [] - - [34] +[37 <./Performance Analysis techniques.pdf>] [38] Overfull \hbox (54.373pt too wide) has occurred while \output is active \OT1/phv/m/sl/10.95 2.4. M[]ETHODES DE PR[]EDICTION DE LA PERFORMANCE DES APPL -ICATIONS PARALL[]ELES \OT1/phv/m/n/10.95 35 +ICATIONS PARALL[]ELES \OT1/phv/m/n/10.95 39 [] -[35] [36 +[39] [40 -] [37] [38] +] Chapitre 3. -[39 -] [40 +Underfull \vbox (badness 10000) has occurred while \output is active [] -] + [41] +[42] [43 + +] [44] Chapitre 4. -[41] [42 +[45 + +] [46 ] Chapitre 5. -[43] [44 +[47] [48 ] Chapitre 6. -[45] [46 +[49] [50 + +] +Chapitre 7. +[51] [52 ] No file These_RCE.bbl. -[47 +[53 -] [48] +] [54] LaTeX Font Info: Font shape `OT1/phv/m/it' in size <10.95> not available -(Font) Font shape `OT1/phv/m/sl' tried instead on input line 1434. +(Font) Font shape `OT1/phv/m/sl' tried instead on input line 1608. -Underfull \hbox (badness 10000) in paragraph at lines 1448--1450 +Underfull \hbox (badness 10000) in paragraph at lines 1628--1630 []\OT1/phv/m/n/10.95 [12] M. Du-bois and X. Vi-gou-roux. Un-leash your HPC per- for-mance with [] -Underfull \hbox (badness 10000) in paragraph at lines 1448--1450 +Underfull \hbox (badness 10000) in paragraph at lines 1628--1630 \OT1/phv/m/n/10.95 Bull. \OT1/phv/m/sl/10.95 Maxi-mi-zing com-pu-ting per-for-m ance while re-du-cing po-wer consump-tion\OT1/phv/m/n/10.95 . [] -Underfull \hbox (badness 1286) in paragraph at lines 1453--1454 +Underfull \hbox (badness 1286) in paragraph at lines 1633--1634 []\OT1/phv/m/n/10.95 [15] C. Har-ris et al. HPC Tech-no-logy Up-date. \OT1/phv/ m/sl/10.95 Paw-set Su-per-com-pu-ting Cen-ter - [] -Underfull \hbox (badness 10000) in paragraph at lines 1455--1457 +Underfull \hbox (badness 10000) in paragraph at lines 1635--1637 []\OT1/phv/m/n/10.95 [16] A. J. van der Steen, J. J. Don-garra. Over-view of Re cent Su-per- [] -Underfull \hbox (badness 10000) in paragraph at lines 1455--1457 +Underfull \hbox (badness 10000) in paragraph at lines 1635--1637 \OT1/phv/m/n/10.95 com-pu-ters. \OT1/phv/m/sl/10.95 Aca-de-mic Com-pu-ting Cent re Utrecht, the Ne-ther-lands, De-part- [] -Underfull \hbox (badness 10000) in paragraph at lines 1455--1457 +Underfull \hbox (badness 10000) in paragraph at lines 1635--1637 \OT1/phv/m/sl/10.95 ment of Com-pu-ter Science, Uni-ver-sity of Ten-nes-see, Kn ox-ville, Ma-the-ma-ti- [] -Underfull \hbox (badness 2460) in paragraph at lines 1455--1457 +Underfull \hbox (badness 2460) in paragraph at lines 1635--1637 \OT1/phv/m/sl/10.95 cal Sciences Sec-tion, Oak Ridge, Na-tio-nal La-bo-ra-tory, Oak Ridge\OT1/phv/m/n/10.95 . http ://ci-te- [] -Underfull \hbox (badness 3078) in paragraph at lines 1464--1466 +Underfull \hbox (badness 3078) in paragraph at lines 1644--1646 []\OT1/phv/m/n/10.95 [19] M. Ewan. Ex-plo-ring Clus-te-red Pa-ral-lel File Sys- tems and Ob-ject Sto-rage. [] -Underfull \hbox (badness 2680) in paragraph at lines 1469--1471 +Underfull \vbox (badness 10000) has occurred while \output is active [] + + [55] +Underfull \hbox (badness 2680) in paragraph at lines 1649--1651 []\OT1/phv/m/n/10.95 [21] G. Bal-lard et Al. Com-mu-ni-ca-tion Op-ti-mal Pa-ral -lel Mul-ti-pli-ca-tion of Sparse [] -Underfull \hbox (badness 1960) in paragraph at lines 1469--1471 +Underfull \hbox (badness 1960) in paragraph at lines 1649--1651 \OT1/phv/m/n/10.95 Ran-dom Ma-trices". \OT1/phv/m/sl/10.95 UC Ber-ke-ley, IN-RI A Pa-ris Roc-quen-court, Tel-Aviv Uni-ver-sity\OT1/phv/m/n/10.95 . [] @@ -1615,55 +1673,55 @@ A Pa-ris Roc-quen-court, Tel-Aviv Uni-ver-sity\OT1/phv/m/n/10.95 . Underfull \vbox (badness 10000) has occurred while \output is active [] - [49] -[50] (These_RCE.lof) -\tf@lof=\write5 - [51 + [56] +[57] [58 -] [52 +] (These_RCE.lof) +\tf@lof=\write5 + [59] [60 ] (These_RCE.lot) \tf@lot=\write6 showing upmdefinition -[53] [54 +[61] [62 -] (These_RCE.loe) [55] [56 +] (These_RCE.loe) [63] [64 -] [57] [58] +] [65] [66] Annexe A. -[59 +[67 -] [60 +] [68 ] Annexe B. -[61] [62 +[69] [70 -] [63] +] [71] pdfTeX warning: pdflatex (file ./spimufcphdthesis-backpage.pdf): PDF inclusion: found PDF version <1.6>, but at most version <1.5> allowed - + File: spimufcphdthesis-backpage.pdf Graphic file (type pdf) -Package pdftex.def Info: spimufcphdthesis-backpage.pdf used on input line 1521. +Package pdftex.def Info: spimufcphdthesis-backpage.pdf used on input line 1709. (pdftex.def) Requested size: 600.04684pt x 900.02122pt. \tf@loe=\write7 -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 1521. - [64 +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 1709. + [72 <./spimufcphdthesis-backpage.pdf>] -Package atveryend Info: Empty hook `AfterLastShipout' on input line 1521. +Package atveryend Info: Empty hook `AfterLastShipout' on input line 1709. (These_RCE.aux) -Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 1521. -Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 1521. +Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 1709. +Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 1709. Package rerunfilecheck Info: File `These_RCE.out' has not changed. -(rerunfilecheck) Checksum: C8B94E96FC102A52D2451E376B4745DC;5235. +(rerunfilecheck) Checksum: D21A0DE433E48EB3AE5D5C0B7498F849;5228. LaTeX Warning: There were undefined references. @@ -1671,13 +1729,13 @@ LaTeX Warning: There were undefined references. LaTeX Warning: There were multiply-defined labels. -Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 1521. +Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 1709. ) Here is how much of TeX's memory you used: - 11500 strings out of 493673 - 172609 string characters out of 3141524 - 290746 words of memory out of 3000000 - 14310 multiletter control sequences out of 15000+200000 + 12008 strings out of 493673 + 180096 string characters out of 3141524 + 301797 words of memory out of 3000000 + 14797 multiletter control sequences out of 15000+200000 67017 words of font info for 119 fonts, out of 3000000 for 9000 1025 hyphenation exceptions out of 8191 65i,17n,41p,1782b,642s stack positions out of 5000i,500n,10000p,200000b,50000s @@ -1688,14 +1746,15 @@ iKTeX 2.9/fonts/type1/public/txfonts/txex.pfb> - -Output written on These_RCE.pdf (74 pages, 5050903 bytes). +xfonts/txsyc.pfb> +Output written on These_RCE.pdf (82 pages, 5103422 bytes). PDF statistics: - 888 PDF objects out of 1000 (max. 8388607) - 171 named destinations out of 1000 (max. 500000) - 533 words of extra memory for PDF output out of 10000 (max. 10000000) + 943 PDF objects out of 1000 (max. 8388607) + 184 named destinations out of 1000 (max. 500000) + 538 words of extra memory for PDF output out of 10000 (max. 10000000) diff --git a/These_RCE.lot b/These_RCE.lot index 0382dc0..ffd6d8a 100644 --- a/These_RCE.lot +++ b/These_RCE.lot @@ -1,6 +1,7 @@ \select@language {french} \addvspace {10\p@ } -\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{13}{table.1.1} +\contentsline {table}{\numberline {1.1}{\ignorespaces Quelques outils de simulation pour une grille de calcul}}{15}{table.1.1} +\addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } diff --git a/These_RCE.out b/These_RCE.out index db9ddd7..361ed2e 100644 --- a/These_RCE.out +++ b/These_RCE.out @@ -12,43 +12,43 @@ \BOOKMARK [2][]{subsection.1.3.2}{1.3.2 G\351n\351ralit\351s sur la simulation}{section.1.3}% 12 \BOOKMARK [2][]{subsection.1.3.3}{1.3.3 MPI - Message Passing Interface}{section.1.3}% 13 \BOOKMARK [2][]{subsection.1.3.4}{1.3.4 Simulateur SIMGRID - SMPI}{section.1.3}% 14 -\BOOKMARK [1][]{section.1.4}{1.4 Motivations}{chapter.1}% 15 -\BOOKMARK [1][]{section.1.5}{1.5 Conclusion partielle}{chapter.1}% 16 -\BOOKMARK [0][]{chapter.2}{2 Etat de l'art et travaux de recherche associ\351s}{part.1}% 17 -\BOOKMARK [1][]{section.2.1}{2.1 Concepts et d\351finitions}{chapter.2}% 18 -\BOOKMARK [2][]{subsection.2.1.1}{2.1.1 Performance de l'application parall\350le et scalabilit\351}{section.2.1}% 19 -\BOOKMARK [2][]{subsection.2.1.2}{2.1.2 Taux d'erreur lors de la pr\351diction}{section.2.1}% 20 -\BOOKMARK [2][]{subsection.2.1.3}{2.1.3 Weak contre strong scaling}{section.2.1}% 21 -\BOOKMARK [1][]{section.2.2}{2.2 Probl\351matique sur la pr\351diction \340 large \351chelle de la performance des applications}{chapter.2}% 22 -\BOOKMARK [2][]{subsection.2.2.1}{2.2.1 Facteurs li\351s \340 l'\351cosyst\350me}{section.2.2}% 23 -\BOOKMARK [3][]{subsubsection.2.2.1.1}{2.2.1.1 Facteur architecture des processeurs}{subsection.2.2.1}% 24 -\BOOKMARK [3][]{subsubsection.2.2.1.2}{2.2.1.2 Facteur : M\351moire et stockage}{subsection.2.2.1}% 25 -\BOOKMARK [3][]{subsubsection.2.2.1.3}{2.2.1.3 Facteur : R\351seaux de communication}{subsection.2.2.1}% 26 -\BOOKMARK [2][]{subsection.2.2.2}{2.2.2 Facteurs li\351s au code de l'application}{section.2.2}% 27 -\BOOKMARK [3][]{subsubsection.2.2.2.1}{2.2.2.1 Facteur : Taille du probl\350me}{subsection.2.2.2}% 28 -\BOOKMARK [3][]{subsubsection.2.2.2.2}{2.2.2.2 Performance de la parall\351lisation}{subsection.2.2.2}% 29 -\BOOKMARK [1][]{section.2.3}{2.3 Techniques d'analyse de performance des applications parall\350les}{chapter.2}% 30 -\BOOKMARK [2][]{subsection.2.3.1}{2.3.1 G\351n\351ralit\351s et objectifs}{section.2.3}% 31 -\BOOKMARK [2][]{subsection.2.3.2}{2.3.2 Approches et m\351thodologie}{section.2.3}% 32 -\BOOKMARK [2][]{subsection.2.3.3}{2.3.3 Quelques outils d'analyse de performance}{section.2.3}% 33 -\BOOKMARK [1][]{section.2.4}{2.4 M\351thodes de pr\351diction de la performance des applications parall\350les}{chapter.2}% 34 -\BOOKMARK [1][]{section.2.5}{2.5 Conclusion partielle}{chapter.2}% 35 +\BOOKMARK [1][]{section.1.4}{1.4 Conclusion partielle}{chapter.1}% 15 +\BOOKMARK [0][]{chapter.2}{2 Etat de l'art et travaux de recherche associ\351s}{part.1}% 16 +\BOOKMARK [1][]{section.2.1}{2.1 Concepts et d\351finitions}{chapter.2}% 17 +\BOOKMARK [2][]{subsection.2.1.1}{2.1.1 Performance de l'application parall\350le et scalabilit\351}{section.2.1}% 18 +\BOOKMARK [2][]{subsection.2.1.2}{2.1.2 Taux d'erreur lors de la pr\351diction}{section.2.1}% 19 +\BOOKMARK [2][]{subsection.2.1.3}{2.1.3 Weak contre strong scaling}{section.2.1}% 20 +\BOOKMARK [1][]{section.2.2}{2.2 Probl\351matique sur la pr\351diction \340 large \351chelle de la performance des applications}{chapter.2}% 21 +\BOOKMARK [2][]{subsection.2.2.1}{2.2.1 Facteurs li\351s \340 l'\351cosyst\350me}{section.2.2}% 22 +\BOOKMARK [3][]{subsubsection.2.2.1.1}{2.2.1.1 Facteur architecture des processeurs}{subsection.2.2.1}% 23 +\BOOKMARK [3][]{subsubsection.2.2.1.2}{2.2.1.2 Facteur : M\351moire et stockage}{subsection.2.2.1}% 24 +\BOOKMARK [3][]{subsubsection.2.2.1.3}{2.2.1.3 Facteur : R\351seaux de communication}{subsection.2.2.1}% 25 +\BOOKMARK [2][]{subsection.2.2.2}{2.2.2 Facteurs li\351s au code de l'application}{section.2.2}% 26 +\BOOKMARK [3][]{subsubsection.2.2.2.1}{2.2.2.1 Facteur : Taille du probl\350me}{subsection.2.2.2}% 27 +\BOOKMARK [3][]{subsubsection.2.2.2.2}{2.2.2.2 Performance de la parall\351lisation}{subsection.2.2.2}% 28 +\BOOKMARK [1][]{section.2.3}{2.3 Techniques d'analyse de performance des applications parall\350les}{chapter.2}% 29 +\BOOKMARK [2][]{subsection.2.3.1}{2.3.1 G\351n\351ralit\351s et objectifs}{section.2.3}% 30 +\BOOKMARK [2][]{subsection.2.3.2}{2.3.2 Approches et m\351thodologie}{section.2.3}% 31 +\BOOKMARK [2][]{subsection.2.3.3}{2.3.3 Quelques outils d'analyse de performance}{section.2.3}% 32 +\BOOKMARK [1][]{section.2.4}{2.4 M\351thodes de pr\351diction de la performance des applications parall\350les}{chapter.2}% 33 +\BOOKMARK [1][]{section.2.5}{2.5 Conclusion partielle}{chapter.2}% 34 +\BOOKMARK [0][]{chapter.3}{3 Motivations}{part.1}% 35 \BOOKMARK [-1][]{part.2}{II PARTIE II - Travaux de contributions, r\351sultats et perspectives}{}% 36 -\BOOKMARK [0][]{chapter.3}{3 Comparaison par simulation \340 large \351chelle de la performance de deux algorithmes it\351ratifs parall\350les en mode asynchrone}{part.2}% 37 -\BOOKMARK [1][]{section.3.1}{3.1 Protocoles et exp\351rimentations}{chapter.3}% 38 -\BOOKMARK [1][]{section.3.2}{3.2 R\351sultats}{chapter.3}% 39 -\BOOKMARK [1][]{section.3.3}{3.3 Conclusion partielle}{chapter.3}% 40 -\BOOKMARK [0][]{chapter.4}{4 Simulation avec SIMGRID de l\220ex\351cution des solveurs lin\351aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\351s}{part.2}% 41 -\BOOKMARK [1][]{section.4.1}{4.1 Protocoles et exp\351rimentations}{chapter.4}% 42 -\BOOKMARK [1][]{section.4.2}{4.2 R\351sultats}{chapter.4}% 43 -\BOOKMARK [1][]{section.4.3}{4.3 Conclusion partielle}{chapter.4}% 44 -\BOOKMARK [0][]{chapter.5}{5 Mod\350le de pr\351diction de la performance \340 large \351chelle d'un algorithme it\351ratif parall\350le}{part.2}% 45 -\BOOKMARK [1][]{section.5.1}{5.1 Approche et m\351thodologie}{chapter.5}% 46 -\BOOKMARK [1][]{section.5.2}{5.2 Exp\351rimentations et r\351sultats}{chapter.5}% 47 -\BOOKMARK [1][]{section.5.3}{5.3 Conclusion partielle}{chapter.5}% 48 -\BOOKMARK [0][]{chapter.6}{6 Conclusion g\351n\351rale et perspectives}{part.2}% 49 -\BOOKMARK [1][]{section.6.1}{6.1 Conclusion g\351n\351rale}{chapter.6}% 50 -\BOOKMARK [1][]{section.6.2}{6.2 Travaux futurs et perspectives}{chapter.6}% 51 +\BOOKMARK [0][]{chapter.4}{4 Comparaison par simulation \340 large \351chelle de la performance de deux algorithmes it\351ratifs parall\350les en mode asynchrone}{part.2}% 37 +\BOOKMARK [1][]{section.4.1}{4.1 Protocoles et exp\351rimentations}{chapter.4}% 38 +\BOOKMARK [1][]{section.4.2}{4.2 R\351sultats}{chapter.4}% 39 +\BOOKMARK [1][]{section.4.3}{4.3 Conclusion partielle}{chapter.4}% 40 +\BOOKMARK [0][]{chapter.5}{5 Simulation avec SIMGRID de l\220ex\351cution des solveurs lin\351aires en mode synchrone et asynchrone sur un environnement multi-coeurs simul\351s}{part.2}% 41 +\BOOKMARK [1][]{section.5.1}{5.1 Protocoles et exp\351rimentations}{chapter.5}% 42 +\BOOKMARK [1][]{section.5.2}{5.2 R\351sultats}{chapter.5}% 43 +\BOOKMARK [1][]{section.5.3}{5.3 Conclusion partielle}{chapter.5}% 44 +\BOOKMARK [0][]{chapter.6}{6 Mod\350le de pr\351diction de la performance \340 large \351chelle d'un algorithme it\351ratif parall\350le}{part.2}% 45 +\BOOKMARK [1][]{section.6.1}{6.1 Approche et m\351thodologie}{chapter.6}% 46 +\BOOKMARK [1][]{section.6.2}{6.2 Exp\351rimentations et r\351sultats}{chapter.6}% 47 +\BOOKMARK [1][]{section.6.3}{6.3 Conclusion partielle}{chapter.6}% 48 +\BOOKMARK [0][]{chapter.7}{7 Conclusion g\351n\351rale et perspectives}{part.2}% 49 +\BOOKMARK [1][]{section.7.1}{7.1 Conclusion g\351n\351rale}{chapter.7}% 50 +\BOOKMARK [1][]{section.7.2}{7.2 Travaux futurs et perspectives}{chapter.7}% 51 \BOOKMARK [-1][]{part.3}{III Annexes}{}% 52 \BOOKMARK [0][]{appendix.A}{A Premier chapitre des annexes}{part.3}% 53 \BOOKMARK [0][]{appendix.B}{B Second chapitre des annexes}{part.3}% 54 diff --git a/These_RCE.pdf b/These_RCE.pdf deleted file mode 100644 index 9f4868c..0000000 Binary files a/These_RCE.pdf and /dev/null differ diff --git a/These_RCE.synctex.gz b/These_RCE.synctex.gz index 22b789a..e528f6d 100644 Binary files a/These_RCE.synctex.gz and b/These_RCE.synctex.gz differ diff --git a/These_RCE.tex b/These_RCE.tex index 2e58d63..ae7e4d8 100644 --- a/These_RCE.tex +++ b/These_RCE.tex @@ -67,6 +67,12 @@ %\usepackage{subcaption} \usepackage{graphicx} +\usepackage{algpseudocode} +\algnewcommand\algorithmicinput{\textbf{Input:}} +\algnewcommand\Input{\item[\algorithmicinput]} +\algnewcommand\algorithmicoutput{\textbf{Output:}} +\algnewcommand\Output{\item[\algorithmicoutput]} + \usepackage{multirow} %%-------------------- @@ -445,7 +451,120 @@ si un mécanisme de reprise sur panne est mis en place. \section{Méthodes de résolution parallèles du problème de Poisson et de 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. + \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]. + +Soit le système d'équations linéaires suivant : + +\begin{equation} +\label{eq:2} +Ax = b +\end{equation} +où : + +\begin{tabbing} +\hspace{2cm}\=\kill + \> A est une matrice carrée réelle creuse inversible de taille n, \\ + \> x le vecteur inconnu de taille n, \\ + \> et b un vecteur constant.\\ +\end{tabbing} + +Ainsi, \eqref{eq:2} peut s'écrire : + +\begin{equation*} + \left(\begin{array}{ccc} + a_{1,1} & \cdots & a_{1,n} \\ + \vdots & \ddots & \vdots\\ + a_{n,1} & \cdots & a_{n,n} + \end{array} \right) + \times + \left(\begin{array}{c} + x_1 \\ + \vdots\\ + x_n + \end{array} \right) + = + \left(\begin{array}{c} + b_1 \\ + \vdots\\ + b_n + \end{array} \right) +\end{equation*} + +Notons : \\ +D la matrice carrée de taille n formée par la diagonale de A. On suppose qu'aucun élément $a_{i,i}$ n'est égal à 0. \\ +L (resp. U) la matrice carrée de taille n formée par les éléments du bas (resp. haut) de A.\\ +On a donc : + +\begin{equation*} +D=\left( \begin{array}{ccc} +a_{1,1} & \cdots & 0 \\ +\vdots & \ddots & \vdots \\ +0 & \cdots & a_{n,n} +\end{array}\right) +\space +, \hspace{0,1cm}L=\left( \begin{array}{ccc} +0 & \cdots & 0 \\ +\vdots & \ddots & \vdots \\ +a_{n,1} & \cdots & 0 +\end{array}\right) +\space +et \hspace{0,2cm}U=\left( \begin{array}{ccc} +0 & \cdots & a_{1,n} \\ +\vdots & \ddots & \vdots \\ +0 & \cdots & 0 +\end{array}\right) +\end{equation*} + +Comme A = D + (L + U) et si $D^{-1}$ est l'inverse de la matrice diagonale D, on peut écrire : + +\begin{equation*} +Ax = b \Leftrightarrow ( D + L + U )x = b +\end{equation*} + +\begin{equation*} +\Leftrightarrow Dx = -(L+U)x + b +\end{equation*} + +\begin{equation} +\label{eq:3} +\Leftrightarrow ( x = D^{-1} \times [-(L+U)] x + D^{-1} b) +\end{equation} +Cette dernière égalité est l'equation $du point fixe$. L'algorithme itératif de Jacobi Figure~\ref{algo:01} (version séquentielle) et ses variantes découle de cette équation [4]. Si $x^{(k)}$ est la valeur approchée du vecteur inconnu à l'itération $k$, on a d'après \eqref{eq:3} avec un $x^{0}$ initial donné : + +\begin{equation} +x^{(k+1)} = D^{-1} \times [-(L+U)] x^{(k)} + D^{-1} b +\end{equation} + +\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, $xOld_{i}$ (vecteur solution à l'itération précédente) +\Output $x_{i}$ (Vecteur solution)\medskip + +\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} +\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 $x_{i} \leftarrow x_{i} + A_{ij} \times xOld_{j}$ +\EndFor +\For {$i=0,1,2,\ldots (n-1)$} +\State $xOld_{i} \leftarrow ( b_{i} - x_{i} ) \quad {/} \quad A_{ii}$ +\EndFor +\EndFor +\State \textbf{end repeat} + +\Statex +\end{algorithmic} +\caption{Algorithme itératif de Jacobi} +\label{algo:01} +\end{figure} + +La condition de convergence est déterminée au début du traitement. La méthode permet de passer à large échelle en distribuant l'exécutuion de l'algorithme sur un environnement de grille de calcul. \subsection{Méthode de résolution GMRES} @@ -569,9 +688,42 @@ Contrairement à une communication point à point, une communication dite collec 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. Il est conçu sur une simulation basée sur les évenements ("event driven") à un niveau d'abstraction et de fonctionnalités répondant aux applications et aux infrastructures [26]. +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 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 : + +\begin{itemize} + +\item[$\bullet$]Un "agent" est une entité qui assure l'ordonnancement de l'application et exécute le code sur une "location"; -\section{Motivations} +\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$]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. + +\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. + +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 : + +\begin{itemize} + +\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$] 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} + +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. + \section{Conclusion partielle} @@ -1337,13 +1489,17 @@ Plusieurs outils d'analyse de la performance parallèle utilisant une ou des com \subsection{Quelques outils d'analyse de performance} +Quelques outils d'analyse de performance sont passés en revue dans cette section. Ils mettent en exergue les différentes approches pour aborder ce problème crucial de performance pour les applications parallèles et distribuées. + +\begin{itemize} - - IPM +\item [$\bullet$] IPM -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 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. - - SCALASCA +\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. +\end{itemize} \section{Méthodes de prédiction de la performance des applications parallèles} @@ -1351,6 +1507,23 @@ TAU a été conçu à l'Université d'Oregon comme un outil open source d'évalu \section{Conclusion partielle} + +\chapter{Motivations} + +Malgré les grandes avancées dues aux performances des nouveaux processeurs, mémoires mais aussi des réseaux de communication, le milieu académique comme le domaine industriel sont toujours confrontés à des défis et challenges de plus en plus ambitieux. Ce fait est surtout accentué par des besoins de plus en plus variés et importants de calcul scientifique nécessitant de plus en plus de moyens mais aussi de méthodes plus efficientes et performantes. Ces besoins requièrent le traitement de données de plus en plus volumineuses mais aussi l'écriture d'algorithmes donnant des résultats probants dans un laps de temps correct. Le défi actuel serait donc l'exploitation de la puissance de calcul des matériels actuels dans un environnement de calcul optimisé pour traiter un volume de données de plus en plus important. \\ +Dans le cadre de nos travaux, l'objectif final est d'aider les utilisateurs finals (scientifiques, chercheurs, industriels, étudiants, ...) en calcul à haute performance à rentabiliser au maximum l'accès aux infrastructures de calcul physiques existantes, étant donné le côut et la difficulté (même des fois l'impossibilité) d'accès à ces dernières. En effet, la demande d'utilisation de ces infrastructures dépasse largement l'offre établie, entraînant des longues listes d'attente avant de pouvoir y accéder pour une durée très limitées. \\ +Pour atteindre ces objectifs, nous proposons d'utiliser des outils de simulation pour exécuter les applications pour étudier leurs comportements à large échelle mais aussi pour pouvoir déterminer les conditions optimales pour obtenir des résultats optimaux. Le simulateur permet d'étudier le comportement des algorithmes sous différentes conditions et sur des plateformes variées et paramétrables. Plusieurs modes d'exécution peuvent être essayés lors de l'expérimentation. De plus, la flexibilité de l'outil permet l'estimation de la performance des algorithmes lors du passage à l'échelle.\\ +Les questionnements suivants résument les motivations des travaux consignés dans cette thèse. +\begin{itemize} +\item [$\bullet$] a. Quelles solutions pratiques peut-on apporter pour réduire le coût de l’exécution d’applications parallèles et distribuées dans un environnement de grille de calcul durant tout son cycle de vie de développement ? +\item [$\bullet$] b. Quel est le comportement de l’algorithme distribué à large échelle dans cette architecture de grille de clusters en particulier lors de son exécution en mode asynchrone ? +\item [$\bullet$] c. Dans ce contexte, quels sont les facteurs importants identifiés permettant d’avoir un gain de temps d’exécution en mode asynchrone comparativement au mode synchrone ? A quel niveau peut-on estimer le gain obtenu en comparant l'exécution en mode asynchrone par rapport au mode classique synchrone. +\item [$\bullet$] d. Quel est le taux d'erreur de validation obtenue en comparant les résultats du lancement de l'application entre une exécution simulée et une execution sur un environnement réél équivalent. +\end{itemize} + +La partie suivante va exposer la méthodologie adoptée et les travaux de contributions pour apporter des réponses à ces questions. + + \part{PARTIE II - Travaux de contributions, résultats et perspectives} \chapter{Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone} @@ -1431,6 +1604,13 @@ TAU a été conçu à l'Université d'Oregon comme un outil open source d'évalu \part*{BIBLIOGRAPHIE ET REFERENCES} + +{[}3{]} J. M. Bahi, S. Contassot-Vivier, R. Couturier - Parallel Iterative Algorithms: from Sequential to Grid Computing - \textit{CRC PRESS - Boca Raton London New York Washington, D.C.} + +{[}4{]} R. Couturier - Résolution de systèmes linéaires à très large échelle : méthodes classiques versus méthodes à large échelle - \textit{2014 - FEMTO-ST, Université de Franche-Comté} + +{[}5{]} C. E. Ramamonjisoa, L. Z. Khodjav, D. Laiymani, A. Giersch and R. Couturier. - Grid-enabled simulation of large-scale linear iterative solvers - \textit{2014 Femto-ST Institute - DISC Department - Université de Franche-Comté, IUT de Belfort-Montbéliard} + {[}6{]} J.M. Bahi, S. Contassot-Vivier, R. Couturier. Interest of the asynchronism in parallel iterative algorithms on meta-clusters. \textit{LIFC - Université de Belford-Montbéliard}. {[}7{]} T.P. Collignon and M.B. van Gijzen. Fast iterative solution of large sparse linear systems on geographically separated clusters. \textit{The International Journal of High Performance Computing Applications} 25(4) 440\textendash 450. @@ -1492,6 +1672,14 @@ of Sparse Random Matrices". \textit{UC Berkeley, INRIA Paris Rocquencourt, Tel-A {[}32{]} MPICH : www.mpich.org {[}33{]} OpenMPI : www.openmpi.org + +{[}34{]} M. Quinson et Al. - Experimenting HPC Systems with Simulation - \textit{Nancy University, France, Caen, HPCS/IWCMC 2010.} + +{[}35{]} A. Legrand, L. Marchal, H. Casanova - Scheduling Distributed Applications: the SimGrid Simulation Framework - \textit{Laboratoire de l’Informatique du Parallèlisme - Ecole Normale Supérieure de Lyon, Dept. of Computer Science and Engineering San Diego Supercomputer Center - University of California at San Diego} + +{[}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,} + + %%-------------------- %% List of figures and tables diff --git a/These_RCE.toc b/These_RCE.toc index 7e75c89..cd65dbe 100644 --- a/These_RCE.toc +++ b/These_RCE.toc @@ -6,50 +6,50 @@ \contentsline {subsection}{\numberline {1.1.2}Modes d'ex\IeC {\'e}cution synchrone et asynchrone}{7}{subsection.1.1.2} \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} \contentsline {subsection}{\numberline {1.2.1}Algorithme de Jacobi}{9}{subsection.1.2.1} -\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{9}{subsection.1.2.2} -\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{9}{subsection.1.2.3} -\contentsline {section}{\numberline {1.3}Simulateurs d'ex\IeC {\'e}cution d'algorithmes parall\IeC {\`e}les MPI dans une grille de calcul}{9}{section.1.3} -\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{9}{subsection.1.3.1} -\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{11}{subsection.1.3.2} -\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{13}{subsection.1.3.3} -\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{15}{subsection.1.3.4} -\contentsline {section}{\numberline {1.4}Motivations}{15}{section.1.4} -\contentsline {section}{\numberline {1.5}Conclusion partielle}{15}{section.1.5} -\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{17}{chapter.2} -\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{17}{section.2.1} -\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{17}{subsection.2.1.1} -\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{19}{subsection.2.1.2} -\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{19}{subsection.2.1.3} -\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}{20}{section.2.2} -\contentsline {subsection}{\numberline {2.2.1}Facteurs li\IeC {\'e}s \IeC {\`a} l'\IeC {\'e}cosyst\IeC {\`e}me}{21}{subsection.2.2.1} -\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{22}{subsubsection.2.2.1.1} -\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{24}{subsubsection.2.2.1.2} -\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{28}{subsubsection.2.2.1.3} -\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{28}{subsection.2.2.2} -\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{29}{subsubsection.2.2.2.1} -\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{29}{subsubsection.2.2.2.2} -\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{32}{section.2.3} -\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{32}{subsection.2.3.1} -\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{32}{subsection.2.3.2} -\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{34}{subsection.2.3.3} -\contentsline {section}{\numberline {2.4}M\IeC {\'e}thodes de pr\IeC {\'e}diction de la performance des applications parall\IeC {\`e}les}{35}{section.2.4} -\contentsline {section}{\numberline {2.5}Conclusion partielle}{35}{section.2.5} -\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{37}{part.2} -\contentsline {chapter}{\numberline {3}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}{39}{chapter.3} -\contentsline {section}{\numberline {3.1}Protocoles et exp\IeC {\'e}rimentations}{39}{section.3.1} -\contentsline {section}{\numberline {3.2}R\IeC {\'e}sultats}{39}{section.3.2} -\contentsline {section}{\numberline {3.3}Conclusion partielle}{39}{section.3.3} -\contentsline {chapter}{\numberline {4}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}{41}{chapter.4} -\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{41}{section.4.1} -\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{41}{section.4.2} -\contentsline {section}{\numberline {4.3}Conclusion partielle}{41}{section.4.3} -\contentsline {chapter}{\numberline {5}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}{43}{chapter.5} -\contentsline {section}{\numberline {5.1}Approche et m\IeC {\'e}thodologie}{43}{section.5.1} -\contentsline {section}{\numberline {5.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{43}{section.5.2} -\contentsline {section}{\numberline {5.3}Conclusion partielle}{43}{section.5.3} -\contentsline {chapter}{\numberline {6}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{45}{chapter.6} -\contentsline {section}{\numberline {6.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{45}{section.6.1} -\contentsline {section}{\numberline {6.2}Travaux futurs et perspectives}{45}{section.6.2} -\contentsline {part}{III\hspace {1em}Annexes}{57}{part.3} -\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{59}{appendix.A} -\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{61}{appendix.B} +\contentsline {subsection}{\numberline {1.2.2}M\IeC {\'e}thode de r\IeC {\'e}solution GMRES}{10}{subsection.1.2.2} +\contentsline {subsection}{\numberline {1.2.3}Solveur multisplitting}{11}{subsection.1.2.3} +\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} +\contentsline {subsection}{\numberline {1.3.1}Calcul sur grille}{11}{subsection.1.3.1} +\contentsline {subsection}{\numberline {1.3.2}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s sur la simulation}{13}{subsection.1.3.2} +\contentsline {subsection}{\numberline {1.3.3}MPI - Message Passing Interface}{15}{subsection.1.3.3} +\contentsline {subsection}{\numberline {1.3.4}Simulateur SIMGRID - SMPI}{17}{subsection.1.3.4} +\contentsline {section}{\numberline {1.4}Conclusion partielle}{19}{section.1.4} +\contentsline {chapter}{\numberline {2}Etat de l'art et travaux de recherche associ\IeC {\'e}s}{21}{chapter.2} +\contentsline {section}{\numberline {2.1}Concepts et d\IeC {\'e}finitions}{21}{section.2.1} +\contentsline {subsection}{\numberline {2.1.1}Performance de l'application parall\IeC {\`e}le et scalabilit\IeC {\'e}}{21}{subsection.2.1.1} +\contentsline {subsection}{\numberline {2.1.2}Taux d'erreur lors de la pr\IeC {\'e}diction}{23}{subsection.2.1.2} +\contentsline {subsection}{\numberline {2.1.3}Weak contre strong scaling}{23}{subsection.2.1.3} +\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} +\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} +\contentsline {subsubsection}{\numberline {2.2.1.1}Facteur architecture des processeurs}{26}{subsubsection.2.2.1.1} +\contentsline {subsubsection}{\numberline {2.2.1.2}Facteur : M\IeC {\'e}moire et stockage}{28}{subsubsection.2.2.1.2} +\contentsline {subsubsection}{\numberline {2.2.1.3}Facteur : R\IeC {\'e}seaux de communication}{32}{subsubsection.2.2.1.3} +\contentsline {subsection}{\numberline {2.2.2}Facteurs li\IeC {\'e}s au code de l'application}{32}{subsection.2.2.2} +\contentsline {subsubsection}{\numberline {2.2.2.1}Facteur : Taille du probl\IeC {\`e}me}{33}{subsubsection.2.2.2.1} +\contentsline {subsubsection}{\numberline {2.2.2.2}Performance de la parall\IeC {\'e}lisation}{33}{subsubsection.2.2.2.2} +\contentsline {section}{\numberline {2.3}Techniques d'analyse de performance des applications parall\IeC {\`e}les}{36}{section.2.3} +\contentsline {subsection}{\numberline {2.3.1}G\IeC {\'e}n\IeC {\'e}ralit\IeC {\'e}s et objectifs}{36}{subsection.2.3.1} +\contentsline {subsection}{\numberline {2.3.2}Approches et m\IeC {\'e}thodologie}{36}{subsection.2.3.2} +\contentsline {subsection}{\numberline {2.3.3}Quelques outils d'analyse de performance}{38}{subsection.2.3.3} +\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} +\contentsline {section}{\numberline {2.5}Conclusion partielle}{39}{section.2.5} +\contentsline {chapter}{\numberline {3}Motivations}{41}{chapter.3} +\contentsline {part}{II\hspace {1em}PARTIE II - Travaux de contributions, r\IeC {\'e}sultats et perspectives}{43}{part.2} +\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} +\contentsline {section}{\numberline {4.1}Protocoles et exp\IeC {\'e}rimentations}{45}{section.4.1} +\contentsline {section}{\numberline {4.2}R\IeC {\'e}sultats}{45}{section.4.2} +\contentsline {section}{\numberline {4.3}Conclusion partielle}{45}{section.4.3} +\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} +\contentsline {section}{\numberline {5.1}Protocoles et exp\IeC {\'e}rimentations}{47}{section.5.1} +\contentsline {section}{\numberline {5.2}R\IeC {\'e}sultats}{47}{section.5.2} +\contentsline {section}{\numberline {5.3}Conclusion partielle}{47}{section.5.3} +\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} +\contentsline {section}{\numberline {6.1}Approche et m\IeC {\'e}thodologie}{49}{section.6.1} +\contentsline {section}{\numberline {6.2}Exp\IeC {\'e}rimentations et r\IeC {\'e}sultats}{49}{section.6.2} +\contentsline {section}{\numberline {6.3}Conclusion partielle}{49}{section.6.3} +\contentsline {chapter}{\numberline {7}Conclusion g\IeC {\'e}n\IeC {\'e}rale et perspectives}{51}{chapter.7} +\contentsline {section}{\numberline {7.1}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{51}{section.7.1} +\contentsline {section}{\numberline {7.2}Travaux futurs et perspectives}{51}{section.7.2} +\contentsline {part}{III\hspace {1em}Annexes}{65}{part.3} +\contentsline {chapter}{\numberline {A}Premier chapitre des annexes}{67}{appendix.A} +\contentsline {chapter}{\numberline {B}Second chapitre des annexes}{69}{appendix.B}