\documentclass[11pt,a4paper]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}


\usepackage{epsfig}
\usepackage{a4}
\usepackage{fullpage}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{D}

%% POUR METTRE OU ENLEVER LES CORRECTIONS
%%\input{/home/jlroch/TeX/STYLES/style-corrige}
\newcommand{\question}[1]{\textrm{#1}}  % pour l'enonce
%\newcommand{\reponse}[1]{}            % pour supprimer le corrige
%\newcommand{\placereponse}[1]{$~$ \\ \\ {\bf R\'{e}ponse\,: }\\ \vspace*{#1} }

%\newcommand{\question}[1]{}  % pour supprimer l'enonce
\newcommand{\reponse}[1]{ {\bf Corrig\'e $~$ } \textit{#1}} % pour le corrige
\newcommand{\placereponse}[1]{}


%\newenvironment{corrige}[1]{\begin{description} \item[Correction:] \em   #1 }{\end{description}}
%\newenvironment{corrige}[1]{}{}

\newcommand{\nomprenom}{}
\newcommand{\newpagenom}{}

%\newcommand{\nomprenom}{
%    \noindent{\bf NOM\,:  $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ 
%                         Pr\'{e}nom\,:  
%                         \hfill Place\,:  $~$ } \\ \hrule
%}
%\newcommand{\newpagenom}{
%   \newpage
%   \vspace*{-0.5cm}
%    \nomprenom
%}

%% Pour gagner de la place...
\textwidth 17cm
\oddsidemargin -0.6cm
\evensidemargin -0.6cm
\textheight 25cm
%\topmargin -1.5cm

%\parskip -0.2cm

\begin{document}
\question{\nomprenom}

\vspace*{2cm}
{\sc{M2R Parallel Systems }
\hfill Training exercises        
}

\begin{center}
{\large \bf \reponse{ \, } Exercises: Parallel merge and application to sort} \\
Jean-Louis Roch 
\end{center}   

% \noindent \paragraph{Important:}
 % \bf


\question{ \paragraph{NB} {\em \bf Ce problème est constitué de cinq parties indépendantes. } 
}

\question{
Dans tout le problème, on considère une machine parallèle de type CREW: les processeurs peuvent 
accéder en lecture à n'importe quelle donnée; mais les écritures sur une m\^eme case mémoire sont en
exclusion mutuelle. \\
On s'intéresse dans la suite à des algorithmes parallèles de fusion et de tri de tableaux basés sur des comparaisons entre les éléments. 
Les coûts sont évalués uniquement en {\em nombre de comparaisons entre éléments} (NB les comparaisons entre deux indices de tableaux ne sont pas prises en compte).
Pour un algorithme parallèle et une instance de taille $n$, on
note:
\begin{itemize}
\item  $W_1(n)$\,: le nombre maximal de comparaisons effectuées;
i.e. le temps de son exécution séquentielle, noté aussi parfois $T_1(n)$;
\item  $\D(n)$ sa profondeur, i.e.  le nombre maximal de comparaisons entre éléments sur un chemin critique dans le graphe de précédence; i.e. le temps de l'exécution parallèle  sur un nombre infini de processeurs identiques, noté aussi $T_\infty(n)$).
\end{itemize}
Dans toute la suite, on considère le
problème MERGE suivant:
\begin{itemize}
\item Entrée : deux tableaux {\bf triés} 
 $A=[a_0, \ldots, a_{n-1}]$ et $B=[b_0, \ldots, b_{m-1}]$ (par ordre croissant). \\ 
On suppose de plus tous les éléments $a_i$ et $b_j$  {\bf distincts}\,:
  $a_i \neq b_j$ pour tout  $0\leq i < n$ et  $0 \leq j < m$. \\
On a donc   $a_0 < a_1 <  \ldots <  a_{n-1}$
et        $b_0 < b_1 <  \ldots <  b_{m-1}$.
\item Sortie : un tableau $X=[x_0, \ldots, x_{n+m-1}]$ trié 
(i.e. $x_0 < x_1 < \ldots <  x_{n+m-1}$) contenant les éléments de $A$ et $B$.
\end{itemize}
}

\subsection*{I. Complexité de MERGE et algorithme séquentiel }

\question{
On étudie ici un minorant de la complexité séquentielle de MERGE en nombre de comparaisons.}

\paragraph{1.} 
\question{
Justifier que pour deux tableaux quelconques $A$ ($n$ éléments) et $B$
($m$ éléments), il y a $C_{n+m}^n=\frac{(n+m)!}{n!.m!}$ configurations possibles pour le tableau $X$ résultat de la fusion de $A$ et $B$.
}
\reponse{
On fixe, dans $X$, $n$ positions arbitraires: il y
a $C_{n+m}^n$ possibilités.
Une fois les positions fixées, on y
place les $n$ éléments (distincts) de $A$ dans l'ordre.
Et dans les espaces restants, tous les éléments étant distincts, 
il y a une seule possibilité pour placer les éléments de $B$ dans l'ordre.
}
\placereponse{2cm}

\paragraph{2.} 
\question{En déduire un minorant de la complexité de MERGE
 (on ne demande pas ici d'équivalent).
 }
\reponse{
A chaque opération de comparaison, on peut au mieux partitionner l'ensemble des sorties possibles en 2.
Donc, un minorant de complexité est $\log_2{C_{n+m}^n}$.
}
\placereponse{1cm}

\question{\newpagenom}
\paragraph{3.} 
\question{
On rappelle la formule de Stirling\,:
$n! \simeq \sqrt{2\pi n} {\left(\frac{n}{e}\right)}^n$.
En déduire un minorant de complexité dans le cas où $n=m$.
}
\reponse{
On a 
$\log_2 n! \simeq n \log_2 n - n \log_2 e + \frac{1}{2}\log_2 n +O(1)$
d'où le minorant:
$2n \log_2 2n - 2n \log_2 e -2n \log_2 n +2n \log_2 e - \log_2 n + \frac{1}{2}\log_2 n + O(1) \simeq 
2n -frac{1}{2}\log_2 n + O(1) \simeq 2n$.
}
\placereponse{1.5cm}

\question{
\paragraph{4.} 
On considère dans cette question
l'algorithme suivant de fusion séquentielle (classique): \\
\hspace*{1cm}{ %\centerline{
\parbox{10cm}{ \tt \footnotesize
for (k=0, ptA=0, ptB=0 ; (ptA $\neq$ n) \&\& (ptB $\neq$ m); k += 1) 
\{ \\
$~~~$ if (B[ptB] $<$ A[ptA] ) \{ X[k] = B[ptB] ; ptB += 1 ; \}  \\
$~~~$ else  \{ X[k] = A[ptA] ; ptA += 1 ; \}  \\
\} \\ % $~$
while (ptA $\neq$ n)  \{ X[k] = A[ptA] ; ptA += 1 ; k += 1 ; \} ;  \\
while (ptB $\neq$ m)  \{ X[k] = B[ptB] ; ptB += 1 ; k += 1 ; \} ; \\
\\ $~$
}
} 
}

\paragraph{4.a.}
\question{Justifier que cet algorithme effectue 
$W_1(n,m) \leq n+m-1$ comparaisons; expliciter un pire cas.
}
\reponse{
Dans la première boucle (la seule comportant des comparaisons), à chaque comparaison, on range 1 élement.
Comme cette boucle range au plus $n+m-1$ éléments, il y a au plus 
$n+m-1$ comparaisons.\\
De plus,  pour l'instance
 $a_0 < \ldots < a_{n-2} < b_0 < \ldots < b_{m-1} < a_{n-1}$: 
les $n-1$ premiers éléments de $A$ sont comparés à $b_0$
et les $m$ éléments de $B$ sont comparés à $a_{n-1}$.
Le majorant $n+m-1$ est atteint.
}
\placereponse{3cm}

\paragraph{4.b.}
\question{
Quelle est en pire cas sa profondeur 
$\D$ en nombre de comparaisons (i.e. temps parallèle sur un nombre infini de processeurs)  ? 
}
\reponse{
Toutes les comparaisons de la première boucle for sont en dépendance séquentielle.
Dans le cas général, on a $\D(n,m) \geq \min(n,m)$.  
Dans l'instance précédente, toutes les comparaisons sont en dépendances. Donc $\D(n,m)=n+m-1$ en pire cas. 
}
\placereponse{1cm}

\question{\newpagenom}
\subsection*{II. Un algorithme parallèle D\&C pour MERGE }
\question{
\paragraph{5.}
%Dans cette question,
On considère l'algorithme parallèle {\em MergePar} de type "Diviser pour Régner" suivant\,:
% (qui résout correctement le problème MERGE,
%et dont {\em on ne demande pas la justification})\,:
\begin{enumerate}
\item On se ramène au cas $n \geq m >0$ (sinon on appelle MergePar$(B,A,X)$ et si $m=0$ on a fini). % recopie $A$ dans $X$). 
\item 
On partitionne le tableau $A$ en deux sous-tableaux 
$A_1 = [a_0,  \ldots, a_{n/2-1}]$ et 
$A_2 = [a_{n/2},  \ldots, a_{n-1}]$.
\item Soit $\alpha =a_{n/2}$; on sépare $B$ en deux sous-tableaux $B_1$ et $B_2$\,: 
$B_1 = [b_0,  \ldots, b_{j-1}]$ 
contient les éléments de $B$ plus petits que $\alpha$
et  
$B_2 = [b_{j},  \ldots, b_{m-1}]$ les éléments de $B$ plus grands que $\alpha$; i.e.
%\begin{itemize}
\\ $~~\bullet$ % \item 
      si $b_0>\alpha$ alors $B_1$ est vide et $B_2=B$;
\\ $~~\bullet$ % \item 
      sinon si $b_{m-1}<\alpha$ alors $B_1=B$ et $B_2$ est vide;
\\ $~~\bullet$ % \item 
      sinon: $j$ est l'unique indice tel que $b_{j-1} < \alpha < b_j$.
% \end{itemize}
\item On fusionne récursivement $A_1$ et $B_1$ dans $X[0, \ldots, n/2+j-1]$ ; \\
et, en parallèle,
on fusionne récursivement
$A_2$ et $B_2$ dans $X[n/2+j, \ldots, n+m-1]$.
\end{enumerate}
}

\paragraph{5.a.} 
\question{
Justifier brièvement que l'algorithme MergePar fusionne correctement
les tableaux triés $A$ et $B$ (tous les éléments étant supposés distincts).
}
\reponse{
Comme $A$ et $B$ sont triés, $A_1$, $A_2$, $B_1$ et $B_2$ le sont aussi. 
Tous les éléments de $A_1$ et $B_1$ sont inférieurs à $\alpha$,
donc à tous les éléments de $A_2$ et $B_2$. 
On peut donc fusionner indépendamment les $n/2+j$ éléments de $A_1$ et $B_1$  
aux $n/2+j$ premières positions de $X$;
et les éléments de $A_2$ et $B_2$ 
aux $n+m-n/2-j$ dernières positions de $X$.
On obtient bien ainsi un tableau trié.
\\ 
NB: si $A$ ou $B$ sont vides,
il suffit de recopier -en parallèle- les éléments de l'autre tableau dans $X$.
}
\placereponse{1.5cm}

\paragraph{5.b. } 
\question{
Expliquer comment calculer -en séquentiel- l'indice $j$ utilisé pour partitionner $B$ en faisant $O(\log_2 m)$ comparaisons:  on ne demande pas l'algorithme, juste le principe.
}
\reponse{ On fait une recherche dichotomique dans $B$\,:
elle nécessite $\lceil \log_2 m\rceil$ comparaisons.
}
\placereponse{0.5cm}
 
\paragraph{5.c } 
\question{Justifier brièvement la récurrence\,: 
 $\left\{
 \begin{array}{ll}
 \D(m, n) = \D(n,m) & \mbox{si~} n < m \\ 
 \D(n, m) \leq \D(n/2,m) + O(\log m) & \mbox{si~} n \geq m \\
 \D(n, 0) = O(1)
 \end{array}\right.
$ \\
En déduire que le temps parallèle  de cet algorithme est 
$\D(n,m) = O(\log^2(n+m) )$.
}
\reponse{
La récurrence s'écrit directement; en pire cas, $m$ est maximum
($n=m$) et le tableau
$B$ est toujours d'un seul côté d'où
$D(n,n) \leq D(n/2,n) + \log n \leq D(n/2,n/2) + 2 \log n -1 
=O(\log^2 n) = O(\log^2 n+m)$
}
\placereponse{0.5cm}

% \paragraph{2.c.} Montrer que le nombre d'opérations de cet algorithme parallèle de fusion est 
% $W_1(n,m) = O( n+m )$.
%\begin{corrige}{ 
%On a $\left\{
% \begin{array}{ll}
% W_1(n, m) < W_1(n/2,m_1) + W_1(n/2, m_2) + O(\log n) & \mbox{si~} n \geq m \\
% W_1(n, 0) = O(n)
% \end{array}\right.
%$
%d'où $W_1 = \Theta(n+m)$ par théorème magique.
%}\end{corrige}
%\placereponse{1.5cm}

\paragraph{5.d. } 
 \question{
 On admet que  le nombre d'opérations effectuées
 par l'algorithme MergePar est $W(n,m)= n+m + o(n+m)$ (on ne demande pas de
 le justifier). Majorer le temps d'exécution sur $p$ processeurs identiques en utilisant un algorithme d'ordonnancement glouton
 (par vol de travail). 
 }
\reponse{ $T_p < \frac{n+m}{p} + o(n+m) + O(\log^2 n+m).$ }
\placereponse{0.1cm}

\question{\newpagenom}
\subsection*{III. Un algorithme très parallèle pour MERGE }


\question{ 
\paragraph{6.}
Le but de cette partie est de construire un 
algorithme parallèle MergeParFast  de temps parallèle (profondeur) constante, mais qui effectue un grand nombre de comparaisons. \\
Pour simplifier, on pose  $a_{-1} = b_{-1} = -\infty$ et $a_n=b_m=+\infty$.
\\
Soit $i \in \{0, \ldots, n-1\}$ un indice arbitraire dans $A$; 
soit alors $k\in \{0, \ldots, m\}$ l'indice dans $B$ tel que $b_{k-1} < a_i$ et
$b_k > a_i$.
}

\paragraph{6.a.} 
\question{
 Justifier  que $x_{i+k} = a_i$.
}
\reponse{
Le nombre d'éléments de $X$ inférieurs à $a_i$ est $i$ dans $A$ et $k$ dans $B$,
donc $i+k$.
}
\placereponse{2cm}

\paragraph{6.b.} 
\question{
Expliquer  comment calculer l'indice $k$ associé à $a_i$ en temps parallèle $O(1)$
avec $m$ comparaisons.
}
\reponse{
En parallèle pour tout $k$: calcul du  booléen 
$t_{i,k}:= (b_{k-1} < a_i) \vee  (b_k > a_i)$. \\
Comme les éléments sont distincts, il est vrai pour un seul $k$. \\
Le calcul se 
fait en profondeur  O(1) avec au total $m$ comparaisons.
}
\placereponse{3cm}

\paragraph{6.c.} 
\question{
En déduire un algorithme de fusion de temps parallèle $O(1)$; préciser
le nombre de comparaisons nécessaires. 
{\bf Indication\,:}{\em ranger 
en parallèle tous les éléments de $A$ et de $B$ dans $X$.}
}
\reponse{
On applique l'algorithme de la question 6.b à tous les éléments de $A$ pour trouver leur
position dans le tableau $X$ en temps $O(1)$ avec $n.m$ comparaisons.
D'où l'algorithme\,:
\\
%\begin{itemize}
$\bullet$ En parallèle pour $i=0..n-1$ doSEQ : \\
$~~~1.~$ En parallèle pour $k=0..m-1$  calcul du  booléen $t_{i,k}:= (b_{k-1} < a_i) \vee (b_k > a_i)$. \\
$~~~2.~$ En parallèle pour $k=0..m-1$: si $t_{i,k} == vrai$ alors
$x_{i+k} := a_i$. \\
$\bullet$ On procède de même pour les éléments de $B$.
\\
On a ainsi fusionné les
deux tableaux en temps $O(1)$ avec $2nm$ comparaisons.
} 
\placereponse{4cm}

\question{\newpagenom}
\subsection*{IV. Un algorithme en cascade efficace pour MERGE }

\question{ 
\paragraph{7.}
Le but de cette partie est d'améliorer  l'algorithme précédent pour construire un
algorithme de fusion parallèle très rapide mais qui effectue seulement 
$W_1(n,m) = O(n+m)$ comparaisons.
}

\question{ 
Pour  $i=0, \ldots, \lfloor \sqrt{n} \rfloor$, on pose $ \alpha_i = a_{i \sqrt{n}}$.
De même, pour $j=0, \ldots, \lfloor \sqrt{m} \rfloor$, on pose $ \beta_j = b_{j \sqrt{m}}$.
On pose 
$\alpha_{-1}= \beta{-1} = -\infty$ et 
$\alpha_{\lfloor \sqrt{n} \rfloor+1}= 
\beta_{\lfloor \sqrt{m} \rfloor+1}=  +\infty$. \\
Enfin, pour $i=0, \ldots, \lfloor \sqrt{n} \rfloor$, on définit l'indice $\mu_i \in \{0, \ldots, \lfloor \sqrt{m} \rfloor +1 \}$
tel que: $\beta_{\mu_i-1} < \alpha_i < \beta_{\mu_i}$. 
\\
et pour $j=0, \ldots, \lfloor \sqrt{m} \rfloor$, on définit l'indice $\nu_j \in \{0, \ldots, \lfloor \sqrt{n} \rfloor+1\}$
tel que: $\alpha_{\nu_j-1} < \beta_j < \alpha_{\nu_j}$. 
}

\paragraph{7.a.} 
\question{
En utilisant la question 6, montrer que tous les indices $\mu_i$ et $\nu_j$ peuvent être calculés en $O(1)$ avec $O(n+m)$ comparaisons.
}
\reponse{
Chaque $\mu_i$ peut être interclassé comme en 6.a en temps 1 avec  $O(\sqrt{m})$ opérations.
Donc tous les $\mu_i$ sont calculés ainsi en temps $1$ avec $O(\sqrt{n}.\sqrt{m})=O(n+m)$ opérations.
} 
\placereponse{2cm}

\paragraph{7.b.} 
\question{
En déduire un algorithme parallèle pour MERGE de temps parallèle $O(\log \log n)$;
et qui effectue $O(n \log\log n)$ comparaisons.
}
\reponse{
Une fois calculés le $\mu_i$ et $\mu_j$ on a une partition de $A$ (resp. $B$) en $\sqrt{n}+\sqrt{m}$ 
blocs, définis pour $A$ par les $\alpha_i$ et $\nu_j$   (resp. par les $\beta_j$ et $\mu_i$.
On obtient ici en $O(1)$ une séquence de $\sqrt{n}+\sqrt{m}$ couples de blocs (un pour $A$, l'autre pour $B$); chaque couple contient un bloc de $A$ avec moins de $\sqrt{n}$ à fusionner
récursivement avec un bloc de $B$ ayant moins de $\sqrt{m}$ éléments. \\ 
On a $\D(n) = \D(\sqrt{n})+O(1) = O( \log \log n)$ et 
 $W_1(n) \leq \sqrt{n}.W_1(\sqrt{n})+O(n) = O( n.\log \log n)$.
}
\placereponse{4cm}

\paragraph{7.c.}  
\question{
Construire un algorithme qui résout MERGE en temps parallèle $\D(n,m) =
O(\log \log n )$ et qui effectue $O(n+m)$ comparaisons seulement.
%{\bf Indication: }{\em utiliser l'algorithme de la question 6 sur deux tableaux de taille $O(n/\log\log n)$
%et $O(m/\log\log m)$ et utiliser l'algorithme de la question 1 par exemple pour terminer les fusions.
}
\reponse{
Il suffit de découper le tableau $A$ (resp $B$) en $O(n/\log\log n)$ (resp. $O(m/\log\log m)$) 
blocs, et de prendre le premier élément de chaque bloc pour former le tableau $\alpha$
(resp. $\beta$). \\
Ensuite on fusionne $\alpha$ et $\beta$ en temps $O(\log\log n)$ avec $O(n)$ opérations.
\\
Enfin, on a maintenant la liste des couples à fusionner; dans chaque couple il y  a au plus
$\log\log n$ éléments pour $A$ et au plus $\log\log m$ éléments pour $B$. On fait
une fusion séquentielle de ces blocs. L'algorithme est en $O(\log\log n)$ et chacune des 3 phases
fait $O(n)$ opérations.
} 
\placereponse{4cm}

\question{\newpagenom}
\subsection*{V. Application à un tri par fusion parallèle }

\question{
Cette partie, indépendante des précédentes, utilise un algorithme
de fusion (qui peut être vu comme un oracle) pour 
réaliser le tri.
L'algorithme récursif de tri par partition-fusion (MERGE-SORT)
est le suivant: \\
\hspace*{2cm}{%\centerline{
\parbox{10cm}{ \tt \footnotesize
Algorithme TRI ( T [0 .. n-1] ) \{ \\
$~~~$ if (n == 1) return T ; \\
$~~~$ else \{  \\ 
$~~~$$~~~$  A[0.. n/2 - 1] = TRI( T[0 .. n/2-1] ) ; \\
$~~~$$~~~$  B[0.. n- n/2 - 1] = TRI( T[n/2 .. n-1] ) ; \\
$~~~$$~~~$  return MERGE(A, B ) ; \\
$~~~$ \}  \\
\} \\$~$
}
} 
}

\paragraph{8.}
\question{
On note $\D^{(M)}(n)$ (resp. $W_1^{(M)}(n)$) le temps parallèle (resp. nombre d'opérations)
de l'algorithme MERGE utilisé. 
%\\ Sans prendre en compte les coûts de communication, 
Donner le temps parallèle $\D(n)$ et le nombre d'opérations $W_1(n)$ de cet algorithme TRI lorsque MERGE est réalisé par\,;
 \begin{itemize}
\item[9.a] l'algorithme séquentiel  de la question 4;
\item[9.b] l'algorithme parallèle de la question 5 pour lequel 
$\D^{(M)}(n) = \log^2 n$  et $W_1^{(M)}(n) = O(n)$; 
\item[9.c]  l'algorithme parallèle de la question 8 pour lequel 
$\D^{(M)}(n) = \log\log n$  et $W_1^{(M)}(n) = O(n)$.
\end{itemize}
}
\reponse{ On a $W_1(n) = 2 W_1(N/2) + W_1^{(M)}(n)$ et
$D(n) = D(N/2) + \D^{(M)}(n)$. D'où par résolution de la récurrence dans les 3 cas: 
\\{\bf 9.a.}  $\D(n) = O(n)$  et $W_1^(n) = O(n \log n)$; 
\\{\bf 9.b.} $\D(n) = O(\log^3 n)$  et $W_1^(n) = O(n \log n)$; 
\\{\bf 9.c.} $\D(n) = O(\log n . \log\log n)$  et $W_1^(n) = O(n \log n)$; 
}
\placereponse{2cm}

\end{document}



