\chapter{État de l'art des algorithmes d'ordonnancement}

%\def\baselinestretch{1.66}

La conception d'applications parallèles nécessite l'utilisation de plusieurs modèles : Un modèle pour présenter le programme parallèle, un modèle pour représenter la machine et un modèle pour représenter l'exécution. Une fois ces modèles définis, nous pouvons simuler l'exécution de ces algorithmes. Ainsi, nous pouvons étudier l'exécution des algorithmes d'ordonnancement.
L'objectif de ce chapitre est de faire un tour d'horizon sur les différents modèles pour le parallélisme et et de présenter les algorithmes d'ordonnancement.

\smallskip
\goodbreak

\section{Introduction}

L'étude de l'ordonnancement des tâches d'un programme sur une machine parallèle réelle étant très complexe, l'introduction de modèle s'impose. La mise prise en compte de toutes les caractéristiques de la machine s'avère assez difficile. En outre, le degré d'influence pour certaines caractéristiques est plus important que pour des autres. Les modèles considèrent quelques unes d'entre elles, sans prendre en compte d'autre caractéristiques qui influencent moins les performances. Ils servent à estimer le comportement de la machine lors d'une véritable exécution. Malheureusement, il n'existe pas de modèle universel pour les machines parallèles similaire au modèle d'architecture de VON Neumann pour les ordinateurs séquentiels.

\medskip

Un bon modèle doit avoir deux qualités: être simple et réaliste. Le réalisme est un modèle antagoniste de simplicité. Plus un modèle est simple, donc abstrait, moins il est proche du comportement d'une machine réelle. A l'opposé, un modèle réaliste s'avère souvent trop complexe à utiliser. Nous allons classer les modèles utilisés selon trois catégories:
\begin{itemize}
\item {\bf Les modèles d'application:} ils servent à présenter le parallélisme potentiel d'un algorithme.
\item {\bf Les modèles de machine:} ils décrivent les principales caractéristiques de la machine parallèle comme les flots d'instruction et de communication entre les processeurs.
\item {\bf Les modèles d'exécution:} ils détaillent les formes de programmation ainsi que ses paradigmes.
\end{itemize}
Le développement d'une application parallèle sur une machine cible peut être vue comme la succession des étapes suivantes:
\begin{enumerate}
\item Trouver un modèle de machine qui représente la machine cible
\item Représenter le parallélisme potentiel de l'algorithme et choisir un modèle l'exécution cohérent avec le modèle de la machine,
\item Rechercher un ordonnancement.
\end{enumerate}
Les étapes 2 et 3 sont les principales. Dans la deuxième étape, le choix du modèle dépend fortement de la machine cible et du parallélisme présent dans l'algorithme. De même, le choix du niveau de parallélisme relève du modèle d'exécution. Après le choix des modèles, la recherche d'un ordonnancement convenable peut commencer.
Dans ce chapitre, nous présentons les différentes représentations d'une application, puis les modèles de machines parallèles et les modèles d'exécution. Nous clôturons ce chapitre par une description détaillé de l'ordonnancement en présentant quelques résultats standards qui vont nous être utile plutard dans notre travail.

\smallskip
\goodbreak

\section{modèles de programmes parallèles}

dans cette section nous allons présenter les différents modèles de graphes utilisé dans le monde du parallélisme. Nous commençons par définir  la terminologie utilisé pour les graphes. Nous passons ensuite à présenter les différents modèles de graphes utilisé dans le monde du parallélisme. Enfin, nous présentons les relations qui existent entre ces modèles.

\subsection{Terminologie}

Un  graphe est une paire $(V,E)$ où $V$ est un ensemble  fini de
noeuds (ou tâches ou sommets) et $E$  un ensemble de fini
d'arcs\cite{TH}. Un élément $e = (u,v)$ de  $E$ dénote arc entre les
noeuds $u$ et $v$ appartenant à $V$. Un graphe peut être orienté ou
non orienté. Dans les graphes orientés, un  élément $e$ appartenant
à $E$, quitte le noeud $u$ et entre dans le noeud $v$. Par contre
dans les graphes non orientés un arc relit simplement deux sommets
(le sens n'a pas d'importance dans le tels graphes). Dans un graphe
orienté l'arc $(u,v)$ dénote un arc allant de $u$ vers $v$ , et
donc, $(u,v) \ne(v,u)$ avec $u \ne v$. les arcs qui relient un noeud
à lui même sont permis dans les graphes orientés. Si $(u,v)$ est un
arc dans un graphe orienté nous disons que $(u,v)$ quitte le noeud
$u$ et entre dans le noeud $v$.

\medskip

Un chemin d'un noeud $V_{0}$ à $V_{k}$  est une séquence $(v_{0},..,v_{k})$ de noeuds avec $(v_{i-1},v_{i})$ appartenant à $E$ pour $i \in 1..k$. Un chemin dans lequel $v_{0}=v_{k}$ forme un cycle. Dans un graphe non orienté un chemin $(v_{0},..v_{k})$ forme un cycle si $v_{0}=v_{k}$ et $v_{0},v_{1},..v_{k}$ sont distincts. Un graphe sans cycle est dit acyclique. Un poids peut être associé à un noeud, il est alors noté $c(v)$. De même un poids peut être associé à un arc
$(u,v)$ et il est alors noté $w(u,v)$. Ces poids peuvent être définis par les fonctions $w :E \longrightarrow \Real$ et  $c : V \longrightarrow \Real$. Un graphe
(weighted) est un graphe dans lequel chaque arc a un poids. Un graphe peut être représenté graphiquement par des cercles  et des flèches ou des lignes. Les cercles représentent les noeuds. Les flèches représentent les arcs d'un graphe orienté, alors que les lignes désignent les arcs d'un graphe non orienté.

\subsection{Modèle théorique des graphes qui représentent un programme parallèle}

D'un point de vue théorique, un programme ou algorithmes parallèles
fait deux activités calcul est communication. Le calcul est associé
aux sommets du graphe et les communications à ses arcs. Nous
appelons donc le sommet noeud et le calcul qui lui est associé tâches.
Une tâche peut être simplement une instruction atomique (i.e
une instruction qui ne peut pas être divisée en de plus  petites
unité) ou des blocs instructions, des boucles etc. Dans un noeud,
les instructions sont exécutés dans un ordre séquentiel
c'est à dire il n'y a pas de parallélisme au sein d'une tâche. A
chaque instant, un noeud est soit entrain de faire un calcul, soit
entrain de faire une communication\footnote{Dans la pratique, le langage MPI
permet l'envoi et la réception non bloquant des données}. Les noeuds
doivent respecter leurs interfaces (i.e leurs entrées/sorties).
Ainsi, un noeud ne peut pas commencer l'exécution de son code
séquentiel avant d'avoir reçu toutes les données figurant dans ses
entrées. De même aucune donnée ne sera disponible en sortie que si
le calcul est achevé.  Dans ce modèle, le branchement n'est pas
autorisé, c'est-à-dire un noeud ne peut pas décider si un ou
plusieurs de ces successeurs participent ou non dans le calcul. Les
segments de contrôles (appelée aussi segments de contrôle de
dépendance \cite{RAT}) doivent être modelé au sein d'une tâche.
D'autre part, le contrôle de dépendance peut être transformé en
dépendance de donnée qui est aussi une communication entre tâches
\cite{UB}. Un noeud $n_{j}$ dépend d'un noeud $n_{i}$ si et seulement si il
existe un arc orienté$(n_{i},n_{j})$. Cette dépendance signifie que le
noeud $n_{j}$ ne peut pas commencer l'exécution de son code séquentiel
avant que $n_{i}$ ait terminé la sienne. Un poids associé à un noeud
représente le coût de calcul de la tâche. Le sens du poids associé
l'arc varie selon le modèle.

\subsection{Modèle de graphes utilisés pour représenter  un programme parallèle}

Plusieurs modèles  de graphes ont été proposé pour représenter un programme parallèle \cite{OS} . chaque modèle est adapté à un type donné de problèmes. Ces modèles peuvent être classifier selon plusieurs critères. Les critères retenus sont: le calcul parallèle qui peut être représenté, l'architecture supporté par le modèle et les algorithmes proposés pour traiter ces modèles.

\subsubsection{calcul parallèle}

Cette propriété classifie les modèles de graphes selon les calculs
qu'ils peuvent représenter. En se basant sur les modèles existants,
les propriétés suivantes ont pu être extraites :
\begin{enumerate}
\item \textbf{Granularité:} La granularité d'un programme parallèle
est définie comme étant la moyenne des poids des tâches (ou unité) de calcul séquentiel\cite{VS}. La granularité d'un modèle de graphe quand à elle est définie comme étant la moyenne des tâches associées aux noeuds de calcul. Concrètement, la granularité reflète le rapport entre la travail total et la somme des communications. Nous distinguons trois types de granularité: granularité fine (un nombre  réduit d'instructions), granularité moyenne (blocs basiques d'instructions.) et granularité grande (boucles, fonctions ....).
\item \textbf{Calcul itératif:} Une partie itérative d'un programme est
une séquence d'opérations exécutées d'une façon répétitive c'est à dire
des boucles ou des appels récursifs. Un modèle peut ainsi représenter les
différents types de dépendance (i.e des communications) au sein d'une itération
(dépendance intra-itéation) et des dépendance entre les itérations (dépendance inter-itération).

\item \textbf{Régularité:} Un programme peut incorporer différentes formes de
régularité. Si un modèle est capable de les représenter explicitement, alors le
programme parallèle peut être représenté d'une façon plus exacte et plus compacte
et par la suite les algorithmes basés sur ce modèle peuvent produire de meilleurs
résultats. Trois types de régularités sont considérés: régularité spatiale,régularité
temporelle et uniformité des coûts des communications et/ou calculs.
\end{enumerate}

\subsubsection{Architectures parallèles:} Pour utiliser d'une façon efficace un modèle de graphe en prenant en compte l'architecture parallèle sur laquelle l'application va s'exécuter, ce modèle doit refléter les caractéristiques de cette architecture. \footnote{le Paragraphe ... est dédié pour l'étude des  modèles des machine parallèles.}

\subsubsection{Algorithmes Proposés}
Dans le contexte des outils de parallélisation , l'utilité
d'un modèle de graphe dépend des algorithmes qui existent pour
ce modèle. Les types suivants d'algorithmes sont considérés pour classifier
les différents modèles de graphes.
\begin{enumerate}
\item \textbf{Analyse de dépendance et exploitation du parallélisme:}
L'analyse des dépendances entre les tâches détermine le
parallélisme intrinsèque qui peut exister dans un calcul. Par la
suite, les algorithmes qui analysent cette dépendance et qui
exploitent le parallélisme sont fondamentaux pour une exécution
efficace du programme parallèle sur un système multiprocesseurs.
\item \textbf{Algorithmes d'allocations des tâches aux processeurs:}
Pour exécuter un programme parallèle sur une architecture parallèle,
les tâches doivent être allouées aux processeurs adéquats. Les algorithmes d'allocations allouent les tâches d'un graphe statiquement aux processeurs d'un système parallèle.

\item \textbf{Algorithmes d'ordonnancement:}
Les algorithmes d'allocations alloues les tâches aux processeurs, mais, ils ne définissent pas les dates des débuts d'exécution des tâches allouées aux mêmes processeurs. Les algorithmes d'ordonnancement  ordonnancent d'une façon statique un
programme parallèle représenté par un modèle de graphe sur des processeurs parallèles. De tels algorithmes affectent les tâches aux processeurs et définissent pour chaque tâche le temps de début d'exécution.
\end{enumerate}
\subsubsection{Les modèles de graphes}
Dans ce paragraphe, nous présentons trois modèles graphes. Nous
commençons par présenter les caractéristiques de chaque graphe, puis,
nous allons les classifier selon les critères cités ci-dessus. Un
résumé sera illustré dans le table *****.
\subsubsection{Graphe  orienté acyclique \label{DAG}}
Les graphes orientés acycliques peuvent être considérés comme une classe de graphe théorique pour le calcul parallèle \cite{OS}. Leurs désignations reflète
leurs natures théorique qui est acyclique et orienté. Nous pouvons
raffiner cette classification en introduisant le concept du poids
associé à la tâche ou/et à l'arc. Ce type de graphes contient des
arcs orientés entre les noeuds. Ils constituent le flot  des données
entre les noeuds, et par la suite, la relation de dépendance entre
les noeuds. La nature acyclique de ces graphes impose des
restrictions sur la façon avec laquelle le calcul parallèle peut
être représenté. Ainsi, les calculs itératifs qui construisent un
cycle, doivent être modelés d'une certaine façon. Une approche à
granularité grande consiste à projeter la partie itérative d'un
calcul itératif dans un noeud. Par contre, avec une approche à
granularité fine,  seuls les instructions d'une seule itération sont
représentés au sein d'une tâche. Pour une représentation complète
d'un calcul itératif avec l'approche à granularité fine, ceux ci
sont représentés dans des sous graphes (un sous graphe pour chaque
calcul itératif). Ces sous graphes sont ensuite reliés entre eux
selon les dépendances inter-itérations qu'ils présentent. Avec une
telle approche, la taille du graphe crois linéairement avec le
nombre d'itérations. Dans la pratique, ce modèle est généralement
utilisé pour un nombre réduit d'itérations. De plus, ce nombre
doit être connu au moment  de la compilation , et par
conséquent, les calculs dont le nombre d'itérations n'est pas connu
au moment de la compilation ne peuvent pas être représenté avec ce
modèle.

\medskip

Les graphes orientés acycliques peuvent être étendues en
attribuant des poids aux noeuds et/ou arcs. Le modèle va alors
représenter des calculs où les tâches n'ont pas le même temps
d'exécutions et où les communications entre ces tâches n'ont pas la
même durée. Ce modèle s'adapte bien avec les programmes parallèles à
grande granularité. Les graphes orienté acycliques sont souvent
utilisés pour l'allocation et l'ordonnancement des programmes
parallèles distribués. Pour les systèmes à mémoire centralisée et
partagée, l'information portant sur la communication n'est pas
indispensable pour les algorithmes d'ordonnancement. Un modèle où
seuls les noeuds ont un poids peut suffire pour de tels
architectures. Les graphes dont les noeuds et les arcs possèdent un
poids sont utiles pour des structures MIMD. Un grand nombre
d'algorithmes d'ordonnancements a été proposé et qui sont basés  sur
les graphes orienté acycliques dont les noeuds et/ou les arcs
possèdent un poids. C'est la nature orienté et acyclique de ces
graphes qui permet  l'obtention d'algorithmes efficaces. Le coût de
communication est définit comme étant le temps nécessaire pour un
échange de données entre deux processeurs. Par le suite, ce temps
sera considéré comme étant nul pour deux tâches affectées au même
processeurs. La communication entre les processeurs se fait par
passage de message. Un grand nombre de travaux a été dédié  à l'étude
et à l'évaluation des algorithmes d'ordonnancement agissant sur ce
type de graphes.

\subsubsection{Graphes de tâches itératifs}

Les graphes de tâches itératifs \cite{TY} appartiennent au groupes de
graphes de flot de données, qui modélisent le flot des données dans
un calcul. Ces graphes sont des graphes orientés et contrairement
aux graphes orientés acycliques, le flot  de données dans ces
graphes peut  constituer un cycle, par conséquent, permet une
représentation plus compacte et plus réduite du calcul parallèle.
Pour que ces graphes représentent les calculs d'une
façon valide, au moins un [delay] soit être ajouté à un cycle. Ce
[delay] est représenté par un poids associé à un arc. Il peut être
exprimé par un multiple d'une unité de temps (souvent appelée D) où
le nombre d'itérations qui vont se dérouler entre les deux noeuds
(ou tâches). Du point de vue  implémentation, le [delay] correspond
à une file FIFO associée aux arcs. Ces [delay] coupent les
contraintes de précédente entre les noeuds d'un cycle et par la suite
, il permettent de donner une représentation calculable d'un calcul
itératif. Ces [delay] peuvent être associés à tous les arcs et ne
sont pas restreints aux arcs d'un cycle. Grâce à ces [delays ] les
graphes de tâches itératifs peuvent représenter les dépendances
entre les itérations [inter-iteration] celles au sein de la même
itération [intra-iteration]. Une représentation efficace d'un
programme parallèle avec les graphes de tâches itératifs permet la
réduction du nombre de noeuds ainsi que la représentation d'un nombre
non déterminé d'itération car ceux-ci sont représentés d'une façon
plus intuitive et plus structurés. Avec ce modèle, les détails des
itérations peuvent être représentés. Donc, ce type de graphes
s'adapte aux problèmes de granularité fines et moyennes. Le flux de
données peut être [data driven ] ou [control driven] \cite{SYK}. Dans le
premier cas, l'exécution de la tâche est initié par l'arrivée de
toutes les données figurants en entrée de la tâche. Pour le deuxième
cas, une horloge globale temporise le début d'exécution des tâches.
Des poids peuvent être associés aux noeuds et/ou arcs. Ils
reflètent, respectivement,  les coûts de calculs et des
communications. Le graphe de tâches itératifs est un modèle
[data-driven] qui inclut des coûts des calculs et des
communications (figure \ref{itg}). Il est principalement utilisé pour
exploiter le parallélisme, les algorithmes d'allocations et
d'ordonnancement.

\begin{figure}
   \begin{center}
      \includegraphics{ITG.eps}
   \end{center}
   \caption{un graphe de tâche itératif. \label{itg}}
\end{figure}

\subsubsection{Graphe Temporel de Communication}
Le graphe temporel de communication \cite{VML} est basé sur le diagramme
espace/temps introduit par lamport\cite{RAT}. Un diagramme espace/temps
proposé pour représenter un calcul distribué consiste en un ensemble
de processus séquentiels communicant par l'envoi des messages.
Chaque processus exécute séquentiellement un ensemble d'activités
qui se résument en trois états: changer d'état, envoyer ou recevoir
un message. Graphiquement, une ligne horizontale est associée à
chaque processus et toutes les lignes sont parallèles entre elles
(figure \ref{tcg}).  Les noeuds   sur les lignes décrivent les activités
des processus et les flèches entre ces noeuds décrivent les messages.
L'envoie d'un message est représenté par le noeud de départ d'une
flèche alors que la réception est représentée par les noeuds
d'arrivée d'une flèche. Les noeuds d'un même processus sont connectés
via des arcs orientés. Comme les processus sont définis à être
strictement séquentiels, ces arcs représentent les relations de
dépendance intra-processus. Notons que la réception et l'émission
d'un message ne sont jamais associés aux mêmes noeuds. Le graphe
ainsi construit est un graphe orienté acyclique et il possède toutes
les propriété citées dans le paragraphe \ref{DAG}.

\medskip

Les noeuds de ce modèle décrivent des calculs aux quels nous pouvons associer un
poids qui représente le coût (durée) de ce calcul. De même, un poids
peut être associé aux arcs et qui représente alors le coût de
communication. Un graphe temporel de communication peut ainsi être
considéré comme étant un graphe orienté acyclique où les noeuds et
les arcs possèdent un poids et que ce dernier est nul pour les arcs
reliant les noeuds d'un même processus. La figure \ref{tcg} illustre un
graphe temporel de communication composé de plusieurs processus
séquentiels. D'une part, cette orientation limite la flexibilité du
modèle (limites héritées par le fait que ce type de graphe est
considéré comme un graphe orienté acyclique). D'autre part, ce
modèle tient sa puissance de ce schéma. En effet, dans \cite{VML}, Lo a
montré que de nombreux calculs consistent en deux phases : calculs
et communication. Ces phases peuvent exploiter des régularités
spatiales et temporelles. Le schéma présenté par ce modèle de graphe
est une vue intuitive aux programmeurs pour la description des
différentes phases d'un calcul. Ce modèle a été utilisé par plusieurs
outils dont l'outil OREGAMI \cite{SG} qui utilise ces graphes pour
l'allocation et l'ordonnancement des tâches au processeurs. Comme
pour les graphes orientés acycliques, ce modèle est bien adapté aux
problèmes à granularité moyennes et grandes.  De plus, grâce aux
poids associés aux arcs et qui représentent les coûts de
communications, ce modèle s'adapte bien aux architecture MIMD.
\begin{figure}
   \begin{center}
      \includegraphics{TCG.eps}
   \end{center}
   \caption{un graphe temporel de communication. \label{tcg}}
\end{figure}

\subsubsection{relations entre modèles de graphes}

Beaucoup de relations existent entre les modèles étudiés précédemment. La transition d'un modèle à l'autre peut être faite. Elle permettra alors , une représentation plus simple du graphe. La figure \ref{relations} illustre les relations qui existent entre ces modèles. Les transformations suivantes peuvent être définies entre les
modèles : réduction, projection et dépliage.

\medskip

Par réduction, un modèle complexe de graphe peut être transformé en un graphe plus
simple dont les propriétés forment un sous ensemble des propriétés du modèle initial.  Ainsi, un graphe de tâches itératif peut être transformé en un graphe orienté acyclique en éliminant les arcs contenant des [delays] non nuls.  De même, l'élimination des poids des arcs dans un graphe orienté acyclique peut nous ramener à un graphe plus simple dont les arcs n'ont pas de poids associé.

\medskip

Par projection, un modèle de graphe peut être transformé en un autre
modèle avec une représentation plus compacte du calcul parallèle. En
effet, il est possible d'obtenir un graphe de tâches itératifs en
projetant les noeuds d'un graphe itératifs de tâches en sous graphes
d'un graphe orienté acyclique.

\medskip

Par dépliage, un graphe orienté acyclique peut être transformé en un
graphe de tâche itératif en dépliant les noeuds contenants des
calculs itératifs, et permet donc,  le passage d'une représentation
à granularité grande à une représentation à granularité moyenne.

\medskip

En dehors des transformations,  un graphe de tâches de communication,
peut être considéré comme un graphe acyclique orienté dont les
arcs et les noeuds possèdent un poids (figure \ref{relations}).
\begin{figure}
   \begin{center}
      \includegraphics{relations.eps}
   \end{center}
   \caption{un graphe de tâche itératif. \label{relations}}
\end{figure}

\smallskip
\goodbreak


\section{Modélisation de machines parallèles}
Les modèles sont employés pour classer les machines elles mêmes, ainsi que pour fournir un support pour la programmation. Ces modèles sont dénommés respectivement modèles de machine et modèles d'exécution. Les modèles de machine caractérisent l'architecture du matériel, alors que le modèle d'exécution sert à expliciter le comportement de la machine et à préciser des caractéristiques telles que la gestion des communications.
\subsection{Description des caractéristiques des machines}
Pendant longtemps la classification la plus utilisée des ordinateurs parallèles a  été celle proposé par Flynn \cite{FL}. Les machines peuvent être classées selon deux critères : le  flot d'instructions et le  flot de données. Quand les  flots d'instructions et de données sont uniques, la machine est dite SISD (single instruction single data), ce qui correspond aux machines séquentielles. Les deux autres types de machines courantes sont les machines SIMD (single instruction multiple data) qui ont un  flot d'instructions unique, et plusieurs  flots de données, et les machines MIMD (multiple instruction multiple data) où les  flots d'instructions et les  flots de données sont multiples. Aujourd'hui la plupart des machines est MIMD, donc la classification de Flynn devient obsolète au profit d'autres caractéristiques. Il est courant de diviser la classe MIMD en deux groupes : les multiordinateurs et les multiprocesseurs \cite{AST}. Il est à noter que les latences pour l'échange des données sont plus importantes dans les multiordinateurs que dans les multiprocesseurs. Un autre point qui différencie les architectures d'ordinateurs parallèles est l'architecture physique de la mémoire. il existent deux grand types d'architecture:

\begin{itemize}
\item {\bf \it UMA } (de l'anglais Uniform Memory Access) il existe un espace d'adressage commun accessible à tous les processeurs. Le temps accès  a cette mémoire est le même pour tous les processeurs.
\item {\bf \it NUMA }: (de l'anglais Non-Uniform Memory Access) chaque processeur possède sa propre mémoire locale. Dans ce cas, la machine et son système d'exploitation fournissent des primitives de communication entre les processeurs. Pour un processeur, il existe plusieurs formes accès  a la mémoire d'un autre processeur : soit par un espace d'adressage unique comme dans le CRAY T3E, soit par l'échange de messages comme dans le IBM SP2.
\end{itemize}

Dans une machine à mémoire NUMA le coût d'un accès à une mémoire non locale est beaucoup plus important que le coût d'un accès local. Dans ce cas la notion de localité des données devient primordiale. Le fait d'avoir une mémoire avec accès uniforme simplifie le travail de parallélisation. Cependant, les contraintes technologiques font que le nombre de processeurs dans les machines UMA est limité (de l'ordre d'une cinquantaine). Pour disposer de beaucoup plus de processeurs, les architectures NUMA s'imposent. Dans le modèle de machines NUMA les processeurs sont reliés par un réseaux d'interconnexion, la manière que cette interconnexion est réalisée définit la topologie du réseau. Le modèle SIMD présuppose un fonctionnement synchrone des processeurs (généralement, il existe une unité centrale de contrôle responsable pour le  flot d'instructions), chaque processeur exécute des cycles composés de calculs et de communications entre processeurs voisins. À chaque cycle, les processeurs exécutent les mêmes instructions, mais avec des données différentes. Dans le modèle MIMD les processeurs peuvent fonctionner de façon asynchrone, il n'y a pas de restriction sur le programme exécuté par chaque processeur. Les modèles de machines servent  a classer les machines existantes, mais ils ne sont pas satisfaisants lors du développement d'une application. Si nous voulons connaître le traitement des conflits lors de accès à une donnée partagée, ou les formes de communication entre les processeurs, nous avons besoin des modèles d'exécution.

\smallskip
\goodbreak

\section{Description des modèles d'exécution}

Il est clair que le modèle d'exécution doit être adapté au modèle de machine. Un modèle d'exécution qui ne prend pas en compte le temps accès à une donnée distante s'avérer peu pratique pour une machine MIMD de type NUMA. Nous allons diviser la présentation des modèles selon leurs origines. D'abord nous présentons les modèles théoriques, c'est-à-dire, ceux qui n'ont pas  été inspirés de machines existantes. Ensuite les modèles basés sur les caractéristiques de machines réelles sont présentés. Dans ce chapitre nous allons  étudier de manière assez brève plusieurs de ces modèles afin de fournir la connaissance de base du sujet.

\medskip

Les modèles d'exécution servent de base à la programmation d'une machine parallèle. Ils donnent la sémantique d'exécution. Un des principaux buts des modèles d'exécution est de servir à la prédiction du temps d'exécution d'un programme parallèle. De la même façon que dans le cas de machines SIMD, le temps d'exécution peut être mesuré en cycles (calcul plus communication). Nous nous intéresserons plutôt aux modèles pour les machines MIMD. Nous allons restreindre notre étude à des modèles où tous les processeurs sont identiques, c'est-à-dire qu'ils ont la même vitesse et peuvent exécuter le même ensemble d'instructions.
\subsection{Un modèle pour la complexité: PRAM}
Le modèle {\it \bf PRAM} (de l'anglais Parallel Random Access Machine) est le premier modèle à avoir  été proposé pour l'informatique parallèle\cite{SF}. Encore aujourd'hui il sert de référence. Il est très populaire pour l'évaluation et la comparaison d'algorithmes parallèles \cite{RMK}. Dans ce modèle les processeurs identiques fonctionnent en cadence par cycle d'une instruction, et ont accès  a une mémoire globale commune. Le nombre de processeurs ainsi que la taille de la mémoire sont illimités. Ce modèle se révèle irréaliste en pratique, car le coût de maintien d'une mémoire globale dépend du nombre de processeurs. Un modèle plus restreint, la p-PRAM, où le nombre de processeurs est égal à $p$, a aussi été proposé dans la littérature. Ce modèle sert à approcher le comportement des ordinateurs SMP (de l'anglais Symmetric MultiProcessing), lesquels partagent les ressources mémoire et entrée/sortie. Les ordinateurs multi processeurs du type PC de dernière génération, où les cartes mères peuvent accueillir jusqu'à huit processeurs qui accèdent la mémoire de façon uniforme, sont des machines SMP. Dans le but de définir les règles d'accès à la mémoire dans le modèle PRAM, plusieurs versions ont été proposées. Les types sont : le EREW (Exclusive Read Exclusive Write), où chaque cellule est accédée par au plus un processeur à chaque cycle, le CREW (Concurrent Read Exclusive Write) et le CRCW (Concurrent Read Concurrent Write) où l'accès aux cellules peut se faire par plusieurs processeurs pour la lecture, et pour la lecture et  écriture, respectivement. Dans le dernier cas, des règles de résolution de conflits sont définies. Les plus courantes, en ordre croissant de complexité sont : arbitraire, prioritaire et combinaison de valeurs (par un maximum, une somme, etc).
\subsection{modèles avec délai de communication}
Dans les modèles avec délai de communication il existe un support pour la communication entre les processeurs. Ce support consiste en l'envoi et la réception de messages. Dorénavant nous dénotons par modèles délai, les modèles que considèrent uniquement la taille des tâches et le délai de communication entre tâches successives allouées à des processeurs différents, lequel peut être aussi considéré comme étant zéro. Les modèles délai et des techniques d'ordonnancement associées ont été proposés simultanément. Un ordonnancement d'un graphe sur une machine consiste à attribuer à chaque tâche du graphe un processeur et une date de début d'exécution\footnode{la section suivante est consacrée à l'étude des algorithmes d'ordonnancement}. Lors de la transmission ou de la réception d'un message dans une machine réelle le processeur est occupé pendant une période de temps (avec des copies mémoire, allocation de tampons, etc). Les modèles de cette section ne prennent pas en compte cette période sur le temps d'exécution des processeurs. Le recouvrement total des communications par du calcul est autorisé, c'est-à-dire que les processeurs peuvent calculer pendant les communications. Les modèles délai ne prennent également pas en compte la congestion du réseaux. Le surcoût de communication sur le temps de calcul et la congestion ont été considérés dans le modèle LogP (voir plus loin dans la section \ref{logp}). Nous présentons d'abord le modèle avec bande passante illimitée, c'est-à-dire, sans surcoût de communication. Ensuite nous présentons les modèles avec bande passante limitée, ce qui introduit des délais de communication. Une des façons d'alléger ce surcoût peut se faire  à travers la duplication des tâches. Dans ce cas, nous pouvons au lieu de communiquer à partir des prédécesseurs, dupliquer quelques-uns d'entre eux. Les paramètres que nous utiliserons pour les modèles suivants sont le nombre de processeurs et la possibilité de dupliquer des tâches. Nous présentons des exemples d'exécutions d'un graphe G de la figure \ref{graphg} (page \pageref{graphg}) sous différents modèles d'exécution. La représentation utilisée est le diagramme de Gantt (diagramme espace temps classique, où l'espace correspond à l'occupation des processeurs), où les tâches, les communications et les temps d'attente sont placés selon leurs dates, processeurs et durées d'exécution. Le poids des sommets du graphe G sont identiques, le poids de ses arcs sera explicité pour chaque modèle. Nous allons présenter des schémas d'exécution sur trois processeurs identiques.

\medskip

\subsubsection{modèle UET}

L'approche théorique de base est simplement d'ignorer le temps de communication entre processeurs. La bande passante est considérée illimitée. Le modèle UET ({\it unit exécution time}) a été proposé par Papadimitriou et Ullman \cite{CHP}. Le temps d'exécution des tâches est unitaire, les attentes dues aux communications ne sont pas considérées. Il est clair que dans ce cas la duplication de tâches avérer inutile. Ce modèle est similaire au modèle PRAM. Dans le diagramme de la  figure \ref{uet} nous présentons un schéma d'exécution optimal.

Les zones rayées correspondent au temps d'inactivité, cette notation sera utilisée dorénavant.
\subsubsection{modèle UET-UCT}
L'extension naturelle du modèle UET considère de manière simplifiée les communications. Lorsque les temps d'exécution des tâches ainsi que les temps de communication sont unitaires, nous avons le modèle UET-UCT (unit execution time - unit communication time). Ce modèle a été proposé par Rayward-Smith \cite{VJR}. Les schémas d'exécution avec et sans duplication sont représentés dans la  figure \ref{uet-uct}

\begin{figure}
   \centering
   \includegraphics[scale=1]{uetuct.eps}
   \caption{Exécutions dans le modèle UET-UCT sans et avec duplication}
   \label{uet-uct}
\end{figure}
Dans l'exemple de la  figure \cite{uet-uct}, en permettant la duplication, le temps d'exécution a été diminué d'une unité. Dans la  figure \cite{uet-uct} et dorénavant, lorsqu'une tâche est exécutée plusieurs fois, une de ses allocations est dénommé par l'index de la tâche. Les autres exécutions d'une tâche $v_i$ sont désignées par $v_i^0$.
\subsubsection{modèle UET-LCT}
Le modèle proposé par Papadimitriou et Yannakakis \cite{CHP} considère toujours des tâches de durée unitaire, mais le coût de communication est donné par \gamme > 1. Ce modèle est dénommé UET-LCT (Unit Execution Time - Large Communication Time). Ce modèle convient aux réseaux d'ordinateurs où les processeurs sont rapides et le réseau représente le point d'étranglement du système. Dans la  figure \ref{uet-lct}, le temps de communication entre tâches exécutées sur processeurs distincts est  $\gamme=2,5$, c'est-à-dire deux fois et demi le temps d'exécution d'une tâche. Jusqu'ici, les coûts des tâches ainsi que les coûts des communications ont été constants. Il existe aussi la possibilité d'avoir des coûts variables.
\subsubsection{modèle SCT}
Il existe d'autres approches tel que le modèle SCT (Small Communication Time) proposé par Colin et Chrétienne \cite{JYC}. Dans ce cas, les temps d'exécution sont plus grands que les temps de communication. La  figure \cite{sct} montre des schémas d'exécution du graphe G, avec et sans duplication. Le temps de communication est la moitié de la durée d'une tâche.
\begin{figure}
   \centering
   \includegraphics[scale=1]{sct.eps}
   \caption{Exécutions dans le modèle SCT sans et avec duplication}
   \label{sct}
\end{figure}

L'intérêt de l'introduction de plusieurs restrictions sur les modèles délai réside dans la possibilité de pouvoir donner des garanties de performances plus fines pour les problèmes d'ordonnancement.
\subsubsection{modèles plus généraux}
Un modèle général où les durées d'exécution des tâches dépendent de leur poids et le coût de communication du poids des arcs a été proposé par Hwang et al\cite{JJH}. Ils ont considéré également la topologie de la machine. Les auteurs ont proposé une fonction élémentaire \Gamma qui associe à chaque paire de processeurs le coût de communication d'un mot. Il perd en simplicité ce qu'il gagne en réalisme.
Dans les autres modèles avec délai de communication le réseau d'interconnexion n'est pas considéré. La position d'un processeur dans le réseau n'affecte pas le coût de communication.

\medskip
\subsection{modèle LogP \label{logp}}
Le modèle LogP \cite{DEC} a le mérite d'avoir été  conçu conjointement par des spécialistes en architectures, en environnements d'exécution et en algorithmique. Ce modèle suppose un nombre fini $P$ de processeurs à mémoire locale. La topologie du réseau n'est pas prise en compte. Les synchronisations sont faites par échange de messages. Le temps de communication considère le coût d'échanges de message pour chaque processeur. Dans le modèle LogP les coûts de communication sont déterminés à travers les paramètres L, o et g. Lors de l'envoi d'un message le processeur expéditeur ne peut pas calculer pendant un période de temps, ce surcoût est dénoté par o (de l'anglais overhead). La réception d'un message coûte aussi un temps de calcul o du processeur récepteur. Il existe aussi un intervalle de temps minimal entre l'envoi de deux messages par le même processeur, cet intervalle est dénoté par g (de l'anglais gap). Cet intervalle de temps doit aussi être respecté lors de la réception des messages. La latence L est le maximum entre le temps d'envoi d'un message (achèvement de l'opération d'envoi) et le temps de réception de ce message (début de l'opération de réception), sur des conditions de communication normales. Pour éviter la congestion du réseau, au plus $[\frac{L}{D}]$  messages peuvent transiter simultanément. Dans la  figure \ref{logp} nous illustrons les paramètres du modèle LogP, les tâches noires" sont dues aux surcoûts de transmission et de réception. Un carré gris représente la latence. Entre deux communications consécutives il existe un intervalle de taille au moins g.\\
La définition première de LogP a été donnée pour de petits messages. Avec de gros messages, la latence peut devenir négative, le premier mot du message peut arriver avant le départ de son dernier mot. Quelques variations plus générales du modèle LogP ont été proposées \cite{AA,JE}. Les modèles avec délai de communication peuvent être vus comme un cas particulier du modèle LogP avec o = g = 0.
\medskip
\subsection{modèles plus précis}
Une approche consiste à considérer la topologie du réseau ainsi que les contraintes de communication d'une machine réelle. Une bonne approximation du temps de communication entre processeurs voisins est fournie par le modèle linéaire (approximation linéaire du premier ordre). La transmission d'un message dans un réseau sans congestion nécessite une phase d'initialisation (en anglais start-up) correspondant au temps d'initialisation des registres mémoires plus le temps nécessaire aux protocoles (empaquetage des données). Ensuite la bande passante est considérée. Dans ce modèle le coût de transmission d'un message de taille S est $t_c = \beta + S\lamda $, où \beta est le temps d'initialisation, et \gamme est l'inverse de la bande passante \cite{JDR}. d'autres résultats concernant ce modèle peuvent être trouvé dans \cite{JDR,AG}.

\subsection{modèle BSP}
Plus qu'un modèle d'exécution, BSP \cite{JMD,LGV} (Bulk Synchronous Parallel) est un modèle de programmation. Son objectif est de fournir un cadre permettant de concevoir facilement des algorithmes portables et efficaces. Le modèle BSP n'est pas basé sur des modèles de machines existantes, mais il convient aux machines MIMD.\\
L'idée principale du modèle BSP est la séparation du calcul de la communication. Ses concepts de base sont la super-étape (de l'anglais super-step) et la synchronisation. L'application est divisée en super-étapes. Tous les processeurs commencent une super-étape au même instant. Entre deux super-étapes, il existe une étape de synchronisation. Les données communiquées lors d'une super-étape seront disponibles aux processeurs destinataires au début de la super-étape suivante. Les trois paramètres utilisés afin de décrire le modèle sont p, l et g.
\begin{itemize}
\item  {\it p} le nombre de processeurs de la machine
\ipem  {\it l} le coût d'une synchronisation globale
\item  {\it g} le temps de transport d'un mot par le réseau. Autrement dit, $\frac{1}{g} $ est la bande passante.
\end{itemize}
Le modèle original proposé par Valiant \cite{LGV} introduit un paramètre qui représente la périodicité d'une synchronisation. Dans son modèle, une vérification globale est effectué après chaque période de L unités de temps. Elle sert à déterminer si la super-étape a été achevée sur tous les processeurs. Dans la version du modèle présentée par McColl \cite{WMF} il n'y a pas de référence à la périodicité. Cette approche a été probablement choisie parce que dans les machines courantes la périodicité peut être aussi petite que le coût de synchronisation.

\subsection{tâches malléables}
Les tâches malléables \cite{JT} (de l'anglais malleable tasks) est un modèle où les tâches du graphe de précédente peuvent elles mêmes s'exécuter en parallèle. Pour considérer le surcoût d'exécution d'une tâche sur plusieurs processeurs une fonction d'inefficacité $\mu (p,N)$ est introduite, où p est le nombre de processeurs utilisés lors de l'exécution parallèle d'une tâche et N est le nombre d'instructions de la tâche. Généralement, cette fonction augmente avec le nombre de processeurs et diminue avec la taille de la tâche.\\
La  figure \ref{mt} illustre un exemple d'allocation de tâches malléables. À gauche les cinq tâches malléables sont alloués une par processeur. À droite est présentée une allocation où l'inefficacité est visible, pour chaque tâche exécutée sur plus d'un processeur un surcoût est ajouté. Par exemple la tâche alloué à gauche sur P6 est exécutée en 5 unités de temps sur 4 processeurs à droite, et donc l'inefficacité est  $\mu (4,18)=20-18= 20$
\begin{figure}
   \centering
   \includegraphics[scale=1]{mt.eps}
   \caption{Schéma d'exécution des tâches malléables}
   \label{mt}
\end{figure}
