\documentclass[11pt]{article}

\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{texgraphicx}
\usepackage{amsfonts,amsmath,amssymb,stmaryrd}
\usepackage{xspace}
\usepackage{pifont} % pour les dinglist
\usepackage{relsize}
\usepackage{enumerate}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}

\usepackage{fancybox} % les boites avec une ombre
\usepackage{fancyheadings} % pour definit facilement les têtes et les
                           % pieds de page
\usepackage{multicol} % comme son nom l'indique
\usepackage{xspace}
\usepackage{url} \urlstyle{sf}

\usepackage{bibtopic}
\usepackage{frbib}

% Compteur pour la partie 'références'
\newcounter{mybibcnt}
\setcounter{mybibcnt}{1}

%\newcommand{\mybibitem}[1]{%
%  \bibitem[{\texttt{\Alph{mybibcnt}}}]{#1}\stepcounter{mybibcnt}%
%}
\newcommand{\mybibitem}[1]{%
  \bibitem[{\texttt{\arabic{mybibcnt}}}]{#1}\stepcounter{mybibcnt}%
}


\usepackage[francais]{babel}
%\usepackage{palatino}

%*********************************************************************
%% lettrine 

\def\lettrine#1#2{\begingroup\def\par{\endgraf\endgroup\lineskiplimit=0pt}
    \setbox2=\hbox{\uppercase{#2} }\newdimen\tmpht \tmpht \ht2
    \advance\tmpht by \baselineskip\font\hhuge=cmr10 at \tmpht
    \setbox1=\hbox{{\hhuge #1}}
    \count7=\tmpht \count8=\ht1\divide\count8 by 1000 \divide\count7 by\count8
    \tmpht=.001\tmpht\multiply\tmpht by \count7\font\hhuge=cmr10 at \tmpht
    \setbox1=\hbox{{\hhuge #1}} \noindent \hangindent1.05\wd1
    \hangafter=-2 {\hskip-\hangindent \lower1\ht1\hbox{\raise1.0\ht2\copy1}%
    \kern-0\wd1}\copy2\lineskiplimit=-1000pt}

%*********************************************************************
% changement de page

\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}

%*********************************************************************
% redefinition des marques des itemizes

\newenvironment{myitemize}{%
\renewcommand{\labelitemi}{$\bullet$}%
\renewcommand{\labelitemii}{$\Box$}%
\renewcommand{\labelitemiii}{$\ast$}%
\begin{itemize}%
\setlength{\itemsep}{0.1cm}%
\setlength{\parsep}{0.0cm}%
}{\end{itemize}}

%*********************************************************************
% ajustement des différentes tailles

%\renewcommand{\baselinestretch}{1.2}

%*********************************************************************

%*********************************************************************
\newlength{\rubriquetableauparindent} % indentation au début d'une
% ligne de droite dans un «rubriquetableau». Cette longueur peut
% être négative, auquel cas l'alignement dans le tableau se fait
% compte tenu du retrait de la première ligne : celle-ci ne «bavera»
% pas sur l'espace réservé pour la colonne de gauche, au lieu de cela,
% l'ensemble de la colonne de droite est décalé de l'espace correspondant.

\setlength{\rubriquetableauparindent}{-16pt}

%\newlength{\@cvlenB}\newlength{\@cvlenC}

\newenvironment{rubriquetableau}[2][\linewidth]%% "rubriquetableau" 
%						% prend deux arguments
{\bgroup\rubrique{#2}%     % le second argument : titre
\setlength{\@cvlenB}{#1}%  % Le premier argument :indentation
\setlength{\@cvlenC}{\linewidth}%	       % Calculs...
\ifthenelse{\lengthtest{\rubriquetableauparindent<0pt}}
   {\addtolength{\@cvlenC}{\rubriquetableauparindent}}
   {}%
\addtolength{\@cvlenC}{-\@cvlenB}%
\addtolength{\@cvlenC}{-9pt}%
\begin{tabular}[t]{p{\@cvlenB}!{%
   \ifthenelse{\lengthtest{\rubriquetableauparindent<0pt}}
	      {\hspace*{\rubriquetableauparindent}}
	      {}%
    }>{\setlength{\parindent}{\rubriquetableauparindent}}p{\@cvlenC}}}
{\end{tabular}\egroup}
%*********************************************************************


\def\Section#1{\section*{\hfil#1}\addcontentsline{toc}{section}{#1}}

\def\Titre#1{\titre{#1}\addcontentsline{toc}{section}{#1}}

% Pour laisser de l'espace entre les lignes du tableau
\newcommand\espace{\vrule height 15pt width 0pt}

% Pour mes grands titres
\newcommand{\titre}[1]{%
	%\begin{center}
	%\rule{\textwidth}{1pt}
        \noindent
	%\par\vspace{0.1cm}
        \textbf{\Large #1} \\
	%\par
	\rule{\textwidth}{1pt}
	%\end{center}
	}

\setcounter{tocdepth}{1}




\begin{document}

%*********************************************************************

\pagestyle{plain}
%\thispagestyle{empty}
%*********************************************************************


%*********************************************************************
\newpage
\thispagestyle{empty}
%\setlength{\fboxrule}{2pt}\setlength{\fboxsep}{2mm}
%\par\framebox[1.5\width]{Dossier de candidature à la fonction
%d'ATER}\\
%\par\fbox{Dossier de candidature à la fonction d'ATER}\\
%{\Large \textit{\centerline{Dossier de candidature à la fonction d'ATER}}}\\
\vspace{0.3cm}

\noindent\setlength{\fboxrule}{2pt}\setlength{\fboxsep}{2mm}
%\hspace{-0.5cm}\par
\framebox[15.85cm][c]{\centerline{\huge{Dossier de soutenance de thèse}}}\\
\vspace{3.5cm}

{\LARGE  \textit{\centerline{Loris Marchal}}}\\
%{\Large \textit{\centerline{LIP ENS Lyon}}}\\

\vspace{3cm}

\begin{center}
{\huge \textbf{\textsc{Communications collectives \\
\rule{0pt}{3ex}
      et ordonnancement en régime permanent\\
\rule{0pt}{2.9ex}
      sur plates-formes hétérogènes}}}\\
\end{center}
\vspace{3cm}
\renewcommand{\contentsname}{Sommaire} 

\begin{center}
  \begin{minipage}{.7\linewidth}
    \tableofcontents
  \end{minipage}
\end{center}

\newpage
%\thispagestyle{empty}
%\centerline{{\bf\huge État civil}}

%\addcontentsline{toc}{section}{État civil}

%\vspace{0.6cm}


%\setlength{\unitlength}{1cm}
\thispagestyle{empty}
\begin{center}
\par\textbf{\LARGE{{Curriculum vit\ae}}}
\label{CV}
\end{center}
\addcontentsline{toc}{section}{Cirriculum vit\ae}

\titre{État civil}

\textbf{\Large{Loris Marchal}}
\begin{center}
  \begin{tabular}{@{}l@{\hspace{.8cm} } l@{  }}
    $\bullet$ Date de naissance : &22 février 1980\\
    $\bullet$ Lieu de naissance : &Lyon 6eme (69)\\
    $\bullet$ Nationalité : &française\\
    $\bullet$ Situation familiale : &célibataire\\
    $\bullet$ Adresse professionnelle :&
    LIP, ENS-Lyon, 46 allée d'Italie,\\
    & 69364 Lyon Cedex 07\\
    $\bullet$ Téléphone professionnel : &04 72 72 85 04\\
    $\bullet$ Adresse personnelle : &
	23 rue René Leynaud,\\
	& 69001 LYON.\\
    $\bullet$ Téléphone : &06 64 51 58 95\\
    $\bullet$ Adresse électronique : &Loris.Marchal@ens-lyon.fr\\
    $\bullet$ Page personnelle : &\url{http://perso.ens-lyon.fr/loris.marchal/}
  \end{tabular}
\end{center}

\vspace*{0.5cm}
\titre{Cursus}

\noindent
\begin{tabular}{l@{ :  }p{0.8\textwidth}}
\textbf{2003--2006} & \textbf{Thèse}
\end{tabular}

\noindent
\begin{tabular}{l@{\hspace{.3cm}}p{0.8\textwidth}}
\hspace{.5cm}Titre :& \textbf{Communications collectives et ordonnancement en
      régime permanent sur plates-formes hétérogènes}\\
\hspace{.5cm}Directeurs :& Olivier \textsc{Beaumont} et Yves \textsc{Robert} \\
\hspace{.5cm}Lieu :& École normale supérieure de Lyon\\
\hspace{.5cm}     & LIP, Laboratoire de l'informatique et du
parallélisme\\
\hspace{.5cm}Situation :& Moniteur allocataire de recherche
(allocation couplée)\\
\end{tabular}


\noindent
\begin{tabular}{l@{ :  }p{0.8\textwidth}}
\textbf{2000--2003} & \textbf{Magistère d'Informatique et Modélisation} de l'ENS Lyon
\\

\textbf{2002--2003} & \textbf{DEA d'informatique fondamentale} à l'ENS Lyon
\\

\espace
\textbf{2001--2002} & \textbf{Maîtrise d'Informatique} à l'ENS Lyon.\\

\espace
\textbf{1998--2000} & \textbf{Licence d'Informatique  } à l'ENS Lyon.\\

\espace
\textbf{1998--2000} & \textbf{Classes préparatoires} au lycée ``Aux
Lazaristes'' (Lyon 5eme).\\

\espace
\textbf{1997--1998} & \textbf{Baccalauréat} série \textbf{S} option mathématiques.\\
\end{tabular}
\vspace*{1cm}

\titre{Fonctions occupées}

\begin{tabular}{l@{ :  }p{0.8\textwidth}}
\textbf{2003--2006} & Allocataire de recherche au sein du projet Graal
du LIP, ENS Lyon. Moniteur à l'ENS Lyon.
\\
\textbf{2000--2003} & Élève normalien de l'ENS Lyon.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
% \clearpage
% \thispagestyle{empty}
% \section*{}


\Titre{Formation}


\subsection*{Stages de recherches}

\begin{tabular}{l@{ :  }p{0.8\textwidth}}
2003 & Stage de DEA de cinq mois au Laboratoire de l'Informatique du
Parallélisme de l'ENS Lyon, \textit{Sujet de stage: communications collectives pipelinées
    sur plate-forme hétérogène}, encadré pas Yves \textsc{Robert}.\\
2002 & Stage de dix semaines à l'université de Californie à San Diego:
\textit{A Network Model for Simulation of Grid Application}, encadré
par Henri \textsc{Casanova}.\\
2001  & Stage de six semaines au Laboratoire d'Informatique de
Marseille,  \textit{Automates cellulaires number-conserving :
  dynamique et décidabilité}, encadré par Bruno \textsc{Durand} et
Enrico \textsc{Formenti}.
\end{tabular}

\subsection*{Formation complémentaire}

\noindent Stages CIES: Évaluation d'un enseigné et d'un enseignement,
Initiation à la zététique : comment enseigner l'esprit critique ? \\

\noindent Atelier CIES:  Approche interdisciplinaire des mathématiques pour les
sciences de la vie.\\

\noindent Module d'insertion professionnelle: "Histoire et philosophie des sciences".\\
\noindent Participation à deux Workshops organisés dans le cadre le l'équipe
associé INRIA I-ARTUHR, en 28-30 septembre 2004 et 12-14 novembre 2005.\\
% http://graal.ens-lyon.fr/~desprez/I-ARTHUR/


\noindent Participation aux Journées de l'ACI PairAPair, 24-25 mars
2005.
% http://www.lri.fr/~pierre/PairAPair/


\noindent Participation à la réunion de l'ANR Alpage, 3 et 4 juin 2006.




\vspace{3cm}

\Titre{Enseignement}

\begin{tabular}{l@{ :  }p{0.8\textwidth}}
\textbf{2006--2007} & Moniteur ENS-Lyon: Architecture, Réseaux et Système
(Licence 3) et Algorithmique des Réseaux et des Télécoms (Master 1)
\\

\textbf{2005--2006} & Moniteur ENS-Lyon: Algorithmique Parallèle
(Master 1) et Algorithmique des Réseaux et des Télécoms (Master 1)
\\

\textbf{2004--2005} & Moniteur ENS-Lyon: Algorithmique Parallèle
(Master 1) et Bases de données et Algorithmique, à l'INSA (première
année de classe préparatoire)
\end{tabular}


%\vspace{3cm}
\newpage
\Titre{Doctorat}

\noindent
\begin{tabular}{p{.3\textwidth}p{0.66\textwidth}}
  \textbf{Titre} & Communications collectives et ordonnancement en
  régime permanent sur plates-formes hétérogènes\\
  \textbf{Directeurs} & Olivier \textsc{Beaumont} et Yves \textsc{Robert}\\
  \textbf{mots clés} & ordonnancement, régime permanent, communications
  collectives, optimisation
  combinatoire, programmation linéaire.\\
  \textbf{Date de soutenance prévue} & 16 octobre 2006
\end{tabular}

\vspace{3cm}
\thispagestyle{empty}
\Titre{Contributions et résumé de la thèse}


%L'objet de ce travail est d'étudier diverses techniques
%d'ordonnancement pour les plates-formes distribuées à grande échelle.


\subsection*{Contexte de la thèse}

L'objet de ce travail est d'étudier diverses techniques
d'ordonnancement pour les plates-formes distribuées à grande échelle.
Ce type de plates-formes, rassemblant des ressources de calculs
distribuées à l'échelle d'un pays, ou d'un continent, voit son intérêt
grandir, en particulier parce qu'il offre une alternative relativement
peu coûteuse aux super-calculateurs monolithiques comme les récents «BlueGene» ou
«Earth Simulator». De nombreux projets tentent de rassembler des
ressources distribuées afin de créer des «grilles de calcul», comme le
projet français Grid5000. La contrepartie du coût limité de ces
plates-formes par rapport à des super-calculateurs est leur
irrégularité et leur hétérogénéité, présente à tous les niveaux: 
\begin{itemize}
\item au niveau matériel, les processeurs sont différents, et le
  réseaux d'interconnexion très complexe,
\item au niveau logiciel, ces machines utilisent des systèmes
  d'exploitation, des librairies de calcul, et des intergiciels
  différents,
\item et même au niveau administratif l'accès aux différentes
  ressources n'est souvent pas centralisé.
\end{itemize}
Notre objectif est d'étudier comment utiliser efficacement de telles
plates-formes. Une première constatation s'impose: l'utilisation d'une
plate-forme distribuée, puissante mais complexe, n'est justifiée que pour
l'exécution d'une application nécessitant beaucoup de calculs. De plus,
vu l'hétérogénéité de la plate-forme, on ne peut espérer y exécuter un
code fortement couplé. Notre étude s'oriente donc vers des
applications nécessitant beaucoup de calculs, mais relativement
simples. On peut par exemple penser au modèle de tâches indépendantes,
pour lequel l'application consiste en un grand nombre de tâches
similaires et indépendantes. Ce modèle convient par exemple au projets
de grilles participatives, utilisant les ordinateurs de personnes
volontaires pendant leur absence; on peut par exemple citer le projet
BOINC, ou encore les très classiques SETI@home ou Einstein@home.


Nous voulons également étudier des applications qui ne sont pas aussi
simples que des tâches indépendantes, quoique présentant une certaine
régularité. Pour ceci, on s'intéresse aux communications impliquées
par l'exécution d'une application distribuée. Ces communications
peuvent souvent être rassemblées sous la forme de primitives de
communications collectives, comme par exemple la diffusion de données:
une des machines transmet à toutes les autres une copie d'une donnée
qu'elle possède. Pour qu'une application mérite d'être exécutée sur
une plate-forme à grande échelle, il est probable que le volume de
données à communiquer soit important, on peut par exemple imaginer
qu'une base de données de grande taille soit nécessaire à
l'application, et doive ainsi être diffusée à toutes les machines
avant le début du calcul. Pour effectuer ces transferts d'importants
volumes de données, nous les découpons en une série d'un grand nombre
de communications de taille plus modeste: la diffusion d'une donnée
de grande taille sera alors transformée en une série d'un grand nombre
de diffusion de messages de taille plus modeste, que l'on cherche à
effectuer de façon pipelinée.


\subsection*{Régime permanent}

Nous allons profiter de la régularité des applications pour
optimiser leur temps d'exécution. Nous supposons que ces applications
consistent en un grand nombre d'actions répétitives: soit une série de
tâches indépendantes, soit une série de communications collectives, 
soit même une série de graphes de tâches similaires. Plutôt que de
chercher à minimiser le temps total d'exécution de l'application, nous
tentons de maximiser le débit d'opérations effectuées pendant la phase
de régime permanent. Ceci a un triple avantage. D'abord, cette
approche \emph{simplifie} le problème d'optimisation: en négligeant
les phases d'initiation et de terminaison des calculs, nous nous
occupons uniquement des quantités moyennes de calcul et de
communication allouées à chaque machine. Ensuite, cette approche est
\emph{efficace}: nous construisons des solutions optimales pour le
régime permanent sous la forme d'ordonnancements périodiques, qui sont
décrits de façon compacte et peuvent ainsi être implantés
facilement. Enfin, cette approche a l'avantage de l'\emph{adaptation}
à la dynamicité naturelle des plates-formes à grande échelle: comme
nos solutions sont périodiques, on peut mesurer les caractéristiques de
la plate-forme pendant l'exécution d'une période et mettre à jour la
solution en conséquence pour la période suivante, ce qui permet de
réagir rapidement aux changements de la plate-forme.



\subsection*{Contributions}

\thispagestyle{empty}
\subsubsection*{Communications collectives}


Nous avons tout d'abord étudié l'optimisation du régime permanent
pour les communications collectives. Nous proposons un cadre
théorique d'étude de différentes primitives de communications
collectives, sous l'angle de la maximisation du débit. Pour certaines
d'entre elles, la diffusion, la distribution et la réduction de
données, nous proposons des algorithmes efficaces qui construisent des
ordonnancements périodiques de débit optimal. D'autres primitives de
communications se révèlent plus difficiles: nous montrons en
particulier que pour  la diffusion partielle et le calcul des
préfixes, la recherche du débit optimal est un problème NP-complet.
D'un point de vue expérimental, nous validons notre approche en la
comparant aux  méthodes existantes par simulation, et nous proposons
également des heuristiques pour résoudre les problèmes
d'optimisation difficiles. Nous proposons également, pour le problème
de la diffusion, une implantation réelle, testée sur la grille de
recherche française Grid5000. 

\subsubsection*{Applications multiples}

Dans un deuxième temps, nous étendons notre étude du régime permanent
à l'ordonnancement d'applications sur les grilles de calcul. Nous
prenons en compte le fait que plusieurs applications concurrentes se
partagent les ressources disponibles. Nous étudions en particulier
comment ordonnancer des applications consistant chacune en un grand
nombre de tâches indépendantes, sur une plate-forme hiérarchique, en
forme d'arbre. Nous montrons que des stratégies non coopératives
peuvent conduire à des situations de famine (une application est
complètement défavorisée par rapport aux autres), et nous évaluons des
stratégies décentralisées, en les comparant à une stratégie optimale
centralisée.

D'autre part, nous nous intéressons également à la modélisation fine
du réseau d'interconnexion des plates-formes distribuées. Dans ce
modèle, nous montrons que l'exécution équitable de débit optimal d'un
ensemble d'applications divisibles est un problème NP-complet, et nous
proposons des algorithmes heuristiques pour résoudre ce problème.  En
collaboration avec l'équipe RESO du LIP, nous nous intéressons
également à la réservation de ressources dans les réseaux
d'interconnexion des grilles de calcul, en particulier pour les
problèmes liés à la contention des connexions au niveau de points
d'entrée et de sortie du c\oe{}ur du réseau. Nous  montrons que le
problème d'optimisation associé est NP-complet, et nous proposons des
stratégies heuristiques pour le résoudre.


\subsubsection*{Autres problèmes d'ordonnancement}

Au cours de cette thèse, nous avons également été amenés à nous
intéresser à d'autres problèmes d'ordonnancement en marge du thème
principal de l'optimisation du régime permanent. Nous nous sommes
intéressés à l'ordonnancement de tâches indépendantes en présence de
mémoire limitée: dans les autres travaux, nous supposons avoir à notre
disposition sur chaque processeur une mémoire pouvant contenir une
nombre illimité de tâches à traiter. Nous montrons que si cette
hypothèse n'est pas vérifiée, alors un grand nombre de problèmes
d'ordonnancement que l'on savait résoudre, en particulier
l'optimisation du débit, deviennent NP-complets. Par contre, nous
présentons des résultats de simulation montrant que lorsqu'un seuil
dans la taille de la mémoire est franchi, alors on peut espérer
atteindre le débit optimal calculé sans contrainte de mémoire.
\thispagestyle{empty}
Nous avons également apporté une contribution à la théorie des tâches
divisibles, en étudiant l'ordonnancement de telles tâches avec
messages de retour.  En effet, on ne considère souvent que les données
en entrée des calculs, tout en négligeant les résultats. Nous montrons
que prendre en compte les messages de retour contenant les résultats
rend les problèmes d'ordonnancement significativement plus difficiles.
En particulier, nous exhibons le premier cas (à notre connaissance)
d'ordonnancement optimal sous un modèle sans latence où tous les
processeurs ne prennent pas part au calcul.



%\subsection*{Perspectives}




\newpage
\thispagestyle{empty}

\Titre{Publications de Loris \textsc{MARCHAL}}



\selectlanguage{francais}

\bibliographystyle{fgasbib2}




\begin{btSect}{loris.j}
\subsection*{Revues internationales avec comité de lecture}
\btPrintAll
\end{btSect}

\begin{btSect}{loris.a}
\subsection*{Conférences internationales avec comité de lecture}
\btPrintAll
\end{btSect}
\thispagestyle{empty}
\begin{btSect}{loris.a.fr}
\subsection*{Conférences nationales avec comité de lecture}
\btPrintAll
\end{btSect}


%\newpage

%\Titre{Avis motivé du directeur scientifique, \\proposition et justification de jury de thèse}


\end{document}


%%% Local Variables:
%%% ispell-local-dictionary: "francais"
%%% End:
