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

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

\TDnumber{6}
\TDtitle{Communicateurs et produit matriciel en \MPI}
\TDabstract{Dans ce TD, nous allons mettre en {\oe}uvre un produit de matrice
  en \MPI basé l'algorithme de double diffusion. Les diffusions se
  faisant sur certain processeurs uniquement, nous allons créer de
  nouveaux groupes de processus pour pouvoir utiliser la fonction
  \code{MPI\_Bcast}.}
\TDauthor{A.\textsc{Legrand} \and Y.\textsc{Robert}}

\title{Communicateurs et produit matriciel en \MPI}
\author{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}

\TDmaketitle
\maketitle
\begin{abstract}
    Dans ce TD, nous allons mettre en {\oe}uvre un produit de matrice
    en \MPI basé l'algorithme de double diffusion. Les diffusions se
    faisant sur certain processeurs uniquement, nous allons créer de
    nouveaux groupes de processus pour pouvoir utiliser la fonction
    \code{MPI\_Bcast}.
\end{abstract}

\section{Communicateurs \MPI}
Nous avons déjà utilisé le communicateur \code{MPI\_COMM\_WORLD} qui
regroupe l'intégralité des processus lancés. Il est possible de créer
d'autres communicateurs, c'est à dire d'autres groupes de processus,
notamment en utilisant la fonction \code{MPI\_Comm\_split}.
\begin{verbatim}
      int MPI_Comm_split ( MPI_Comm comm, int color, int key, MPI_Comm *newcomm )
\end{verbatim}
\begin{itemize}
\item \code{comm} est le communicateur que l'on souhaite scinder
\item \code{color} est un entier positif qui détermine à quel ensemble
  on appartiendra, le nouveau communicateur regroupant les processus
  de même couleur.
\item \code{key} est un entier qui permet de déterminer le rang du
  processus au sein du nouveau communicateur. Deux processeurs de même
  couleur seront donc dans le même communicateur et leur rang sera
  déterminé en fonction de leur valeur respectives de \code{key}
\item \code{newcomm} est le nouveau communicateur.
\end{itemize}

\section{Produit de matrice parallèle}
\subsection{Rappel sur l'algorithme par double diffusion}
On souhaite effectuer le calcul $C_{ij}=(A.B)_{ij}=\sum_{k=1}^{n}
A_{ik} B_{kj}$ pour tout $i,j$ dans $\llbracket 1,n\rrbracket$.
L'Algorithme~\ref{algo.MMM1} décrit une façon naturelle d'effectuer ce
calcul mais pas forcément adaptée à une parallélisation directe.
\begin{algorithm}[htbp]
  \begin{algo}{6.4cm}
    \FUNC{MatMult($A,B,C$)}
    \NSTATE \FOR $i=1$ \TO $n$ \DO \label{algo.MMM1.i}
    \NSTATE    \FOR $j=1$ \TO $n$ \DO \label{algo.MMM1.j}
    \NSTATE       \FOR $k=1$ \TO $n$ \DO \label{algo.MMM1.k}
    \NSTATE          $C_{ij}\leftarrow C_{ij}+A_{ik} B_{kj}$
                  \ENDFOR
               \ENDFOR
            \ENDFOR
  \end{algo}
  \caption{Algorithme général séquentiel du produit de matrice}
  \label{algo.MMM1}
\end{algorithm}

Les boucles~\ref{algo.MMM1.i} et~\ref{algo.MMM1.j} de cet
algorithme sont parallèles. La boucle de la ligne~\ref{algo.MMM1.k}
correspond à une opération de réduction (qui peut s'effectuer par
exemple à l'aide d'un arbre) et réduit le parallélisme. On
séquentialise généralement une partie de ces boucles afin d'ordonner
et de régulariser les calculs (éviter des migrations de données
excessives et désordonnées), de simplifier le contrôle et surtout
d'adapter la granularité de la machine cible.
\begin{algorithm}[htbp]
  \begin{algo}{6.4cm}
    \FUNC{MatMult($A,B,C$)}
    \NSTATE \FOR $k=1$ \TO $n$ \DO \label{algo.MMM2.k}
    \NSTATE    \FORALL $i$ \DO \INPARALLEL\label{algo.MMM2.i}
    \NSTATE       \FORALL $j$ \DO \INPARALLEL\label{algo.MMM2.j}
    \NSTATE          $C_{ij}\leftarrow C_{ij}+A_{ik} B_{kj}$
                  \ENDFOR
               \ENDFOR
            \ENDFOR
  \end{algo}
  \caption{Algorithme parallèle du produit de matrice}
  \label{algo.MMM2}
\end{algorithm}

Il est donc préférable de permuter les boucles pour arriver à
l'Algorithme~\ref{algo.MMM2} et d'effectuer alors la boucle externe
(ligne~\ref{algo.MMM2.k}) séquentiellement et les boucles internes
(lignes~\ref{algo.MMM2.i} et \ref{algo.MMM2.j}) en parallèle. Si
chaque $C_{ij}$ est alloué à une unité de calcul fixe, alors les
$A_{ik}$ et les $B_{kj}$ doivent circuler entre chaque étape de
calcul, mais cela ne nuit pas au parallélisme et permet un
recouvrement potentiel du calcul et des communications (même si le
premier TD a démontré la difficulté de ce recouvrement avec \MPI).

\begin{figure}[htbp]
  \begin{center}
    \begin{makeimage}
      \includegraphics[width=.5\linewidth]{MM_Homo_Grid_4x4.fig}
    \end{makeimage} 
\caption{Distribution homogène contiguë pour une grille $4\times 4$}
    \label{fig:2DHomo}
  \end{center}
\end{figure}

Dans le cas où l'on dispose de $p.q$ processeurs identiques
interconnectés en grille (voir Figure~\ref{fig:2DHomo})~: chaque
processeur est responsable de sous-matrices de taille $\frac{n}{p}
\times \frac{n}{q}$ de $A$, $B$ et $C$.
% $A_{[r_{i-1}+1,r_{i}] \times [c_{j-1}+1,c_{j}]}$, $B_{[\dots]}$,
% $C_{[\dots]}$ avec $r_i=in/p$ et $c_j=jn/q$
L'Algorithme~\ref{algo.MMM2} se déroule donc en $n$ étapes et à
l'étape $k$, la $k^{\grave{e}me}$ colonne de $A$ et la
$k^{\grave{e}me}$ ligne de $B$ sont diffusées horizontalement (pour la
colonne) et verticalement (pour la ligne).  Chaque processeur reçoit
donc un fragment de colonne de $A$ et un fragment de ligne de $B$ de
tailles respectivement $n/p$ et $n/q$ et met à jour la partie de $C$
dont il est responsable (voir Figure~\ref{fig:2DHomo}).

\subsection{Mise en {\oe}uvre en \MPI de l'algorithme par double
  diffusion}
Vous trouverez dans \url{http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar/MPI/src/} un
canevas pour le programme de produit matriciel
(\texttt{matmult\_template.c}). Comme d'habitude, le programme est
commenté et il n'y a qu'à remplir les trous. Une fois que le programme
fonctionne, augmentez la granularité des communications. Comment faire
pour évitez des copies inutiles lors des envois des fragment de lignes
et de colonnes ?

Une solution est disponible à la même adresse dans \texttt{matmult.c}.
\end{document}
