\documentclass[a4paper,twoside]{article}
\usepackage{styles/tdstyle}
\usepackage{relsize,fancyvrb}

% La gestion des figures
\usepackage{texgraphicx}
\graphicspath{{fig/}}

\TDnumber{4}
\TDtitle{Diffusion avec \MPI}
\TDabstract{Dans ce TD, nous allons nous familiariser avec les
  fonctions de communications de \MPI et essayer d'écrire nous-même la
  fonction de diffusion à partir d'envois et de receptions
  simples. Nous allons également nous rendre compte de la difficulté
  de l'écriture d'une opération de diffusion non bloquante avec \MPI
  et ainsi souligner bon nombre de limitations de \MPI.}
\TDauthor{A.\textsc{Legrand} \and Y.\textsc{Robert}}


\def\code#1{\texttt{#1}}
\def\MPI{\textsf{MPI}\xspace}
\def\MPICH{\textsf{MPICH}\xspace}

\begin{document}
\title{Diffusion avec \MPI}
\author{A.\textsc{Legrand} \and Y.\textsc{Robert}}
\maketitle
\begin{abstract}
  Dans ce TD, nous allons nous familiariser avec les fonctions de
  communications de \MPI et essayer d'écrire nous-même la fonction de
  diffusion à partir d'envois et de receptions simples. Nous allons
  également nous rendre compte de la difficulté de l'écriture d'une
  opération de diffusion non bloquante avec \MPI et ainsi souligner
  bon nombre de limitations de \MPI.
\end{abstract}

\TDmaketitle

\begin{ExercisePart}
\section{Un mot d'histoire}
Tout d'abord, il convient de rappeler quelques généralités sur ce
qu'est \MPI et sur ce que ce n'est pas. \MPI n'est pas une bibliothèque de
communication développée par une université ou une entreprise: c'est
un standard qui est né au début des années 90 pour répondre à un
besoin de clarification. En effet, à cette époque, la seule façon de
faire du calcul parallèle efficace consistait à acheter une grosse
machine parallèle propriétaire. Ces dernières étaient généralement
livrées avec leur propre bibliothèque de communication qui n'était que
rarement compatible avec celle de la machine précédente et jamais avec
celle des concurrents. Il était donc très difficile de maintenir
un programme à jour et un gros travail était nécessaire à chaque fois
que l'on souhaitait changer de machine. Le standard \MPI est donc né de
la collaboration entre des universitaires et des industriels de tous
domaines scientifiques. Cependant, si ce standard a permit de résoudre
la majorité des problèmes que l'on pouvait avoir au moment de sa
création, il souffre désormais d'un bon nombre de limitations et d'une
inadéquation aux plateformes de calcul actuelles. 

En effet, la mode actuelle en matière de calcul distribué et parallèle
est à l'interconnection, via des liens à très haut débit, de grands
centres de calculs disséminés à l'échelle d'un pays, d'un continent
voire du monde. C'est ce que l'on appelle le \emph{meta-computing}. Personne
ne sait si on pourra un jour exploiter correctement de telle
plateformes mais, dixit Al.~Geist (responsable du projet PVM) il y a
quelques jours\footnote{Et oui, on voit du beau monde dans les
  confs\dots}: "Il y a de toutes façons tellement d'argent investi 
dans ce domaine que cela aboutira forcément à quelque chose". 

Mais revenons à \MPI. Un des gros problème auquel on se heurte dès que
l'on essaie d'utiliser un programme \MPI sur une plateforme de
\emph{meta-computing} est que les bibliothèques \MPI d'un centre de calcul
à l'autre ne sont pas forcément identiques et rien dans le standard
n'oblige une bibliothèque à perdre en performance pour être compatible
avec une bibliothèque concurrente. À cela s'ajoutent la difficulté de
déploiement d'un tel programme, la nécessité de prendre en compte (
autant au niveau algorithmique qu'au niveau système) l'hétérogénéité
des processeurs et des réseaux, le coût énorme des synchronisations et
donc des opérations bloquantes, la non-tolérance aux pannes,\dots Même
s'il serait plaisant de pouvoir programmer et utiliser ces plateformes
comme une simple station de travail, nous en somme très loin
actuellement et leur complexité semble rendre cette entreprise un peu
utopique.

Ce portrait de \MPI et du calcul parallèle actuel peut sembler un peu
pessimiste mais tous ces projets ont aussi donné naissance à de très
bonnes choses. Même si \MPI n'est plus adapté aux plateformes de calcul
telle qu'elles sont envisagées actuellement, l'aventure \MPI est quand même un
succès étant donné qu'elle a permis à bon nombre de personnes non
informaticiennes de développer des programmes efficaces pour les
plateformes de calcul parallèle classiques et de collaborer grâce à des codes
portables. L'émulation créée par ces projets ambitieux de
\emph{global-computing} permet à bon nombre de scientifiques non
informaticiens de résoudre des problèmes qu'ils n'auraient jamais pu
espérer résoudre il y a de cela quelques années. Enfin, même si tous
ces projets semblent un peu fous et extrêmement ambitieux, il est
indéniable que la communauté scientifique a un besoin toujours
croissant de puissance de calcul et de communication et que nous ne
sommes actuellement pas en mesure de répondre à leurs besoins.

Un nouveau standard \MPI-2 a été mis en place il y a quelques années et
résout certains des problèmes précédemment évoqués. Il existe
cependant encore très peu de bibliothèques mettant en {\oe}uvre
l'intégralité du standard \MPI-2.

\section{Introduction à l'utilisation de \MPI}
\subsection{Initialisation et terminaison du programme}
Un programme \MPI commence en général par un appel de la fonction
\code{MPI\_Init} dont le prototypage est le suivant:
\begin{verbatim}
   int MPI_Init(int *argc, char ***argv)
\end{verbatim}
Cette fonction initialise les connections \MPI en fonction des
arguments passés à votre programme. C'est pourquoi avant de lire les
arguments de votre programme, il convient de faire un appel à cette
fonction.

Un programme \MPI se termine généralement par l'appel de la fonction
\code{MPI\_Finalize}. Tous les processus doivent appeler ce
programme avant leur terminaison. Cette opération est bloquante ne
termine que lorsque toutes les opérations de communications en cours
ou en attente sont terminées.

Il peut être utile de savoir combien de processus participent au
calcul et quel numéro on a. Les fonctions \code{MPI\_Comm\_size} et
\code{MPI\_Comm\_rank} dont le prototype est le suivant. Un
\code{MPI\_Comm} est un groupe de processus \MPI. Pour l'instant,
nous n'utiliserons que le groupe prédéfini \code{MPI\_COMM\_WORLD}
qui regroupe l'intégralité des processus \MPI participant au calcul.
\begin{verbatim}
   int MPI_Comm_size ( MPI_Comm comm, int *size )
   int MPI_Comm_rank ( MPI_Comm comm, int *rank )
\end{verbatim}

\subsection{Communications bloquantes}
Les envois et les réceptions bloquantes se font grâce aux fonctions
\code{MPI\_Send} et \code{MPI\_Recv} dont le prototype est le suivant:

\begin{verbatim}
   int MPI_Send( void *buf, int count, MPI_Datatype datatype, int dest,
                 int tag, MPI_Comm comm )
   int MPI_Recv( void *buf, int count, MPI_Datatype datatype, int source,
                 int tag, MPI_Comm comm, MPI_Status *status )
\end{verbatim}

Quelques explications :
\begin{itemize}
\item \code{buf} représente l'adresse du buffer d'émission (pour
  \code{MPI\_Send}) ou du buffer de réception (pour
  \code{MPI\_Recv}).
\item \code{count} est le nombre d'éléments à envoyer ou à recevoir.
\item \code{datatype} est le type des éléments que l'on va envoyer
  (ou recevoir). On doit préciser le type des éléments car \MPI peut
  effectuer des conversions de type si les architectures cibles ne
  représentent pas les objets de la même manière (\emph{big
    indian}/\emph{little indian}\dots). Il est possible de créer des
  types \MPI de façon à faciliter la programmation mais nous
  n'utiliserons pour l'instant que le type \code{MPI\_INT}.
\item \code{dest} et \code{source} sont respectivement les indices
  des processeurs destinataires et sources mais vous l'aviez
  probablement deviné tout seul.
\item \code{tag} est un nombre qui sert généralement à identifier un
  type de message. Choisissez-en un et essayez de vous y tenir\dots
\item \code{comm} est le groupe de processus impliqués dans la
  communication. Comme cela a été signalé précédemment, nous nous
  contenterons de \code{MPI\_COMM\_WORLD}.
\item \code{status} est un objet permettant de récupérer des
  informations sur la communication et ne nous servira pas pour
  l'instant.
\end{itemize}

Enfin une autre fonction qui s'avère souvent utile : la barrière de
synchronisation.
\begin{verbatim}
   int MPI_Barrier ( MPI_Comm comm )
\end{verbatim}

Nous allons essayer de simuler la fonction \code{MPI\_Bcast} dont le
prototype est le suivant.
\begin{verbatim}
   int MPI_Bcast ( void *buffer, int count, MPI_Datatype datatype, int root,
                   MPI_Comm comm )
\end{verbatim}
Cette fonction est bloquante. Lorsqu'un programme alterne des phases
de calcul et des phases de communications, il y a donc intérêt à ce
que l'équilibrage de charge soit parfait\dots

\subsection{Communications non bloquantes}
Les fonctions d'envoi et de réception non bloquantes
\code{MPI\_Isend} et \code{MPI\_Irecv} ont le prototype suivant:
\begin{verbatim}
   int MPI_Isend( void *buf, int count, MPI_Datatype datatype, int dest, int tag,
                  MPI_Comm comm, MPI_Request *request )
   int MPI_Irecv( void *buf, int count, MPI_Datatype datatype, int source,
                  int tag, MPI_Comm comm, MPI_Request *request )
\end{verbatim}
\code{request} est un \emph{"numéro"} de communication. Cela permet
de savoir si une communication est terminée ou pas, notamment grâce à la
fonction \code{MPI\_Test} ou à la fonction \code{MPI\_Wait}.
\begin{verbatim}
   int MPI_Test ( MPI_Request *request, int *flag, MPI_Status *status)
   int MPI_Wait ( MPI_Request *request, MPI_Status *status)
\end{verbatim}
\code{flag} reçoit la valeur vrai si la communication est
effectivement terminée.

\subsection{Lancement du programme}
Un programme \MPI minimal (\texttt{simple.c}) ainsi qu'un makefile
permettant de compiler (en tapant \texttt{make}\dots) et de lancer des
programmes \MPI (en tapant \texttt{make run}) sont disponibles dans
\url{http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar/MPI/src/}. Théoriquement, si vos clés
ssh ont été posées, le lancement des applications ne devrait pas poser
de problème. La bibliothèque \MPI que nous allons utiliser s'appelle
\MPICH et est disponible sur une grande variété de plateformes.

\section{Diffusion en \MPI}
\definecolor{violet}{rgb}{.5,0,.7}
\definecolor{bleu}{rgb}{0,0,.7}
\definecolor{rouge}{rgb}{.7,0,0}
\def\DiffInput#1#2#3{~\\
  \begin{figure}[htbp]
    \centering
    \resizebox{\linewidth}{!}{\parbox{15.2cm}{
        \VerbatimInput[frame=single, fontsize=\relsize{-4},
        label=\fbox{\emph{#1}}, numbers=left, 
        defineactive=\def£{\color{violet}|}\defµ{\color{blue}>}\def¢{\color{rouge}<},
        firstline=6]{#3} 
      }}    
    \caption{#1}
    \label{fig:#2}
  \end{figure}
}
\begin{Question}
  Écrivez un programme où le processeur $0$ diffuse aux autres
  processeurs un tableau d'entiers à l'aide de la fonction
  \code{MPI\_Bcast}. Rajoutez un appel à la fonction
  \code{long\_computation} juste après la diffusion et mesurez le
  temps nécessaire à ces opérations grâce à la fonction
  \code{ms\_time}\footnote{ces deux fonctions sont disponibles dans
  le programme \MPI minimal évoqué précédemment}.
\begin{Reponse}
  La Figure~\ref{fig:mpiBcast} représente les modifications à
  apporter au programme \texttt{simple.c} pour effectuer une diffusion
  utilisant la fonction \texttt{MPI\_Bcast}
  \DiffInput{Utilisation de la fonction
    \code{MPI\_Bcast}}{mpiBcast}{src/diff1.txt}
\end{Reponse}
\end{Question}

\begin{Question}
  Recommencez en écrivant vous même la diffusion (en anneau) à l'aide
  d'opérations bloquantes. Que pensez-vous des performances, notamment quand
  vous faites varier le nombre de processus ?
\begin{Reponse}
  La Figure~\ref{fig:mpiSend} représente les modifications à apporter
  au programme précédent pour simuler l'appel à \code{MPI\_Bcast} par
  communications bloquantes. Au fur et a mesure que le nombre de
  processeur augmente, les performances se dégradent. Ceci est du au
  fait que la bibliothèque \MPICH utilise un arbre de diffusion pour
  mettre en {\oe}uvre la fonction \code{MPI\_Bcast}.
  \DiffInput{Utilisation des fonctions de communications bloquantes}{mpiSend}{src/diff2.txt}
\end{Reponse}
\end{Question}

\begin{Question}
  Remplacez maintenant vos émissions bloquantes par des émissions non
  bloquantes. Que pensez-vous des performances ?
\begin{Reponse}
  Les performances sont, contrairement à ce que l'on pourrait croire,
  complètement lamentables. La question suivante devrait éclaircir les
  choses.
  \DiffInput{Utilisation des fonctions de communications asynchrones}{mpiISend}{src/diff3.txt}
\end{Reponse}
\end{Question}

\begin{Question}
  Rajoutez une barrière de synchronisation juste avant l'appel à
  \code{long\_computation}. Que pensez-vous des performances ?
  Avez-vous une explication à proposer ?
\begin{Reponse}
  Encore une fois, les performances sont contraires à l'intuition.
  Ces problèmes sont dus au fait que cette bibliothèque \MPI n'est pas
  \emph{multi-threadée}. Les communications ne sont traitées que
  lorsque l'on rentre dans une fonction \MPI. L'appel à la fonction
  \code{MPI\_ISend} ne fait que préparer la communication à venir.
  Pour que la communication puisse se faire effectivement, il faut que
  les deux parties soient prêtes et il suffit donc en général de faire
  un appel à une fonction \MPI quelconque pour déclancher la
  communication.
\end{Reponse}
\end{Question}

\begin{Question}
  Essayer de remédier au problème en utilisant autre chose qu'une
  barrière de synchronisation.
\begin{Reponse} 
  On peut également résoudre le problème en truffant les fonctions de
  calcul d'appels à la fonction \code{MPI\_Test} (voir
  Figure~\ref{fig:mpiTest}). Imaginez maintenant que vous souhaitiez
  remplacer la réception bloquante par une réception asynchrone et
  vous aurez alors une idée des problèmes auxquels ont du faire face
  les développeurs de bibliothèques reposant sur \MPI.
  \DiffInput{Truffer les calculs de \code{MPI\_Test}}{mpiTest}{src/diff4.txt}
\end{Reponse}
\end{Question}

L'objectif de ce TD était de mettre en valeur un certain nombre de
limitations de \MPI. Il ne faut quand même pas oublier que ces
bibliothèques sont quand même très efficaces sur des plateformes
homogènes, qu'elles offrent une quantité d'opérations globales
impressionnantes ainsi qu'un haut niveau d'abstraction, ce qui permet
de développer très rapidement un programme parallèle.

Les fichiers \textsf{C} solutions au problème sont disponibles
dans \url{http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar/MPI/src/}
(\texttt{broadcast1.c}, \texttt{broadcast2.c}, \texttt{broadcast3.c},
\texttt{broadcast4.c}, \texttt{broadcast5.c}).
\end{ExercisePart}
\end{document}
