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

\TDnumber{5}
\TDtitle{Structures de données et tri avec \MPI}
\TDabstract{Dans ce TD, nous mettrons en {\oe}uvre un tri en parallèle
  en \MPI basé sur le réseau de tri pair/impair vu en cours. Le tri se
  fera sur une structure de données complexe, ce qui permettra de
  manipuler un peu les types \MPI.}
\TDauthor{A.\textsc{Legrand} \and Y.\textsc{Robert}}

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

\begin{document}
\title{Structures de données et tri avec \MPI}
\author{A.\textsc{Legrand} \and Y.\textsc{Robert}}
\maketitle
\begin{abstract}
  Dans ce TD, nous mettrons en {\oe}uvre un tri en parallèle en \MPI
  basé sur le réseau de tri pair/impair vu en cours. Le tri se fera
  sur une structure de données complexe, ce qui permettra de manipuler
  un peu les types \MPI.
\end{abstract}

\TDmaketitle

\section{Quelques nouvelles fonctions \MPI}
Il est possible de créer des types \MPI afin de faciliter la
manipulation de structures complexes et de s'affranchir de conversions
explicites de données lorsque la plateforme de calcul est hétérogène.
Nous allons utiliser pour cela les fonctions suivantes:
\begin{itemize}
\item[$\triangleright$] \code{MPI\_Address} Sur certain systèmes, la valeur renvoyée
  par cette fonction sera la même que celle que vous auriez récupérée
  en utilisant l'opérateur \code{\&} du C mais cela n'est pas obligatoire. Il
  vaut donc mieux utiliser les adresses renvoyées par cette fonction
  pour calculer les offset des différents champs d'une structure.
\begin{verbatim}
   int MPI_Address( void *location, MPI_Aint *address)
\end{verbatim}
\item[$\triangleright$] \code{MPI\_Type\_struct} Cette fonction permet de construire un
  type \MPI structuré. Le prototypage est le suivant:
\begin{verbatim}
   int MPI_Type_struct(
        int count, int blocklens[],
        MPI_Aint indices[], MPI_Datatype old_types[],
        MPI_Datatype *newtype )
\end{verbatim}
  \begin{itemize}
  \item \code{count} représente le nombre de champs de la structure
    (c'est aussi le nombre d'éléments des différents tableaux passés
    en arguments)
  \item \code{blocklens[i]} représente le nombre d'éléments dans le
    champs \code{i}.
  \item \code{indices[i]} représente l'offset du champs \code{i} dans
    la structure \C.
  \item \code{old\_types[i]} représente le type des éléments du champs
    \code{i}.
  \item \code{newtype} est le type structuré créé par l'appel à
    \code{MPI\_Type\_struct}. 
  \end{itemize}
\item[$\triangleright$] \code{MPI\_Type\_commit} permet de rendre public un type \MPI et
  doit être appelé avant toute utilisation du nouveau type.
\end{itemize}

Enfin, voici deux autres fonctions qui nous seront utiles pour
distribuer et récupérer les données : 
\begin{itemize}
\item[$\triangleright$] \code{MPI\_Scatter} Cette fonction permet de distribuer des
  données à un groupe de processeurs.
\begin{verbatim}
   int MPI_Scatter (
        void *sendbuf, int sendcnt, MPI_Datatype sendtype,
        void *recvbuf, int recvcnt, MPI_Datatype recvtype,
        int root, MPI_Comm comm )
\end{verbatim}
  \begin{itemize}
  \item\code{root} est l'indice du processeur qui va effectuer les émissions.
  \item\code{sendbuf} est l'adresse du buffer d'émission (pertinent
    uniquement sur le processeur \code{root}).
  \item\code{sendcnt} est le nombre d'éléments qui va être envoyé à
    chaque processeur (pertinent uniquement sur le processeur
    \code{root}).
  \item\code{sendtype} est le type \MPI des objets du buffer
    (pertinent uniquement sur le processeur \code{root}).
  \item\code{recvbuf} est l'adresse du buffer de réception.
  \item\code{recvcnt} est le nombre d'éléments qui va être reçu par
    chaque processeur.
  \item\code{recvtype} est le type \MPI des objets que les processeurs
    vont recevoir.
  \end{itemize}
\item[$\triangleright$] \code{MPI\_Gather} Cette fonction permet de rassembler vers un
  processeur donné des données distribuées sur un groupe de
  processeurs.
\begin{verbatim}
   int MPI_Gather (
        void *sendbuf, int sendcnt, MPI_Datatype sendtype,
        void *recvbuf, int recvcnt, MPI_Datatype recvtype,
        int root, MPI_Comm comm )
\end{verbatim}
  \begin{itemize}
  \item\code{root} est l'indice du processeur qui va récupérer les
    données.
  \item\code{sendbuf} est l'adresse du buffer d'émission.
  \item\code{sendcnt} est le nombre d'éléments qui va être envoyé à
    chaque processeur.
  \item\code{sendtype} est le type \MPI des objets du buffer .
  \item\code{recvbuf} est l'adresse du buffer de réception (pertinent
    uniquement sur le processeur \code{root}).
  \item\code{recvcnt} est le nombre d'éléments qui va être reçu de la
    part de chacun des processeurs (pertinent uniquement sur le
    processeur \code{root}).
  \item\code{recvtype} est le type \MPI des objets que le processeur
    \code{root} va recevoir (pertinent uniquement sur le processeur
    \code{root}).
  \end{itemize}
\end{itemize}

Au cas où ces explications ne suffiraient pas, je vous invite à aller
voir les sites suivants :
\begin{itemize}
\item \url{http://www-unix.mcs.anl.gov/mpi/tutorial/gropp/talk.html}
\item \url{http://www.netlib.org/utk/papers/mpi-book/mpi-book.html}
\end{itemize}
Vous pouvez également aller lire les pages de man qui sont disponibles
à peu près n'importe où.

\section{Tri en parallèle}
Vous trouverez dans \url{http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar/MPI/src/} un
canevas pour le programme de tri (\texttt{parsort\_init.c}) ainsi
qu'un fichier contenant des informations (désormait totalement
obsolètes) sur les utilisateurs du réseau de l'école
(\texttt{liste.txt}). Dans sa version initiale, ce programme lit ce
fichier et stocke les valeurs dans un grand tableau sur le processeur
$0$. Il vous appartient donc de le modifier afin de distribuer ce
tableau sur les différents processeurs, de faire un tri pair/impair
puis de rassembler les résultats sur le processeur $0$.

Une solution possible est disponible à la même adresse dans le fichier
\texttt{parsort.c}.
\end{document}
