modif finale lnivs + keywords

[these_gilles.git] / THESE / Chapters / chapter5 / chapter5.tex

diff --git a/THESE/Chapters/chapter5/chapter5.tex b/THESE/Chapters/chapter5/chapter5.tex
index 22f6d635ff632288f107dee4c5c2c628976e7329..88ec0cbd84c0d0da94e7b08a5a55566579f1b735 100644 (file)
--- a/THESE/Chapters/chapter5/chapter5.tex
+++ b/THESE/Chapters/chapter5/chapter5.tex
@@ -1,17 +1,16 @@
 \section{Introduction}
 \section{Introduction}

-Au cours de nos expérimentations, en particulier concernant le débruitage par lignes de niveaux décrit dans la chapitre précédent, nous avons cherché à comparer les performances d'un certain nombre d'algorithmes de filtrage portés sur GPU. Comme nous l'avons dit dans le chapitre décrivant les diverses solutions proposées, il s'est avére que le filtre médian n'avait pas fait l'objet de beaucoup de publications. On recensait tout de même quelques  implémentations intéressantes des algorithmes BVM et PCMF, ainsi que l'existence d'une solution commerciale libJacket/Arrayfire (se reporter au paragraphe \ref{sec-median}).
+Au cours de nos expérimentations, en particulier concernant le débruitage par lignes de niveaux décrit dans le chapitre précédent, nous avons cherché à comparer les performances d'un certain nombre d'algorithmes de filtrage portés sur GPU. Comme nous l'avons dit dans le chapitre \ref{ch-filtrage}, il s'est avéré que le filtre médian n'avait pas fait l'objet de beaucoup de publications. On a tout de même recensé quelques  implémentations intéressantes des algorithmes BVM et PCMF, ainsi que l'existence d'une solution commerciale libJacket/Arrayfire (se reporter au paragraphe \ref{sec-median}).

 
 

-Les performances annoncées pour des fenêtres de petite taille comme le médian 3$\times$3 pouvaient atteindre jusqu'à 180 millions de pixels traités à la seconde dans le cas de Arrayfire. En regard du petit nombre d'opérations à effectuer pour sélectionner la valeur médiane dans une fenêtre 3$\times$3, il nous a intuitivement semblé que ces débits étaient très en deça des possibilités des GPU employés.
+Les performances annoncées pour des fenêtres de petite taille comme 3$\times$3 pouvent atteindre jusqu'à 180 millions de pixels traités à la seconde dans le cas d'Arrayfire. En regard du petit nombre d'opérations à effectuer pour sélectionner la valeur médiane dans une fenêtre 3$\times$3, il nous a semblé que ces débits étaient très en deçà des possibilités des GPUs employés.

 
 Un rapide prototypage a conforté cette idée et nous a conduit à chercher plus avant une technique d'implémentation du filtre médian qui exploite pleinement les capacités de nos GPU.
 
 \section{Les transferts de données}
 
 Un rapide prototypage a conforté cette idée et nous a conduit à chercher plus avant une technique d'implémentation du filtre médian qui exploite pleinement les capacités de nos GPU.
 
 \section{Les transferts de données}

+Le chapitre \ref{ch-GPU}, présentant l'architecture et les caractéristiques principales des GPUs, donne également la liste et les spécificités des types de mémoire accessibles par un kernel. Lorsqu'il s'agit de stocker des volumes importants de données, comme les images d'entrée et de sortie, les alternatives sont assez limitées. En effet, le seul espace mémoire suffisamment important est celui la mémoire dite globale, malheureusement la plus lente. On dispose cependant de plusieurs modes pour y accéder, comme la déclaration de textures, qui offre un mécanisme de cache 2D permettant d'augmenter assez nettement les débits en lecture dans le cas d'accès au voisinage d'une donnée.
+Dans le cadre de nos travaux, cette mémorisation sous forme de texture s'est montrée la plus performante pour les images d'entrée.

 
 

-Le chapitre \ref{ch-GPU}, présentant l'architecture et les caractéristiques principales des GPU, donne également la liste et les spécificités des types de mémoire accessibles par un kernel parallèle. Lorsqu'il s'agit de stocker des volumes importants de données, comme les images d'entrée et de sortie, les alternatives sont assez limitées. En effet, la seule mémoire suffisamment importante est la mémoire externe, malheureusement la plus lente également. On dispose cependant de plusieurs modes d'accès, comme la déclaration de textures, qui offre un mécanisme de cache 2D permettant d'augmenter assez nettement les débits en lecture.
-Dans le cadre de nos travaux, cette mémorisation sous forme de texture s'est montré la plus performante pour les images d'entrée.
-
-Les images de sortie sont produites en mémoire globale standard, hors texture, puis copiées vers une zone de mémoire non paginée de l'hôte CPU. L'algorithme \ref{algo-median-memcpy} synthétise ces pratiques en introduisant aussi les notations pour la suite. 
-Cet emploi de mémoire non paginée apporte un gain de temps important dans les transferts ; il peut s'avérer limitant dans des situations requérant de très grands volumes de données. Les quantités de mémoire vive dont disposent les ordinateurs modernes (plusieurs Go) permettent cependant de traiter sans restriction des images de plusieurs centaines de millions de pixels. Nos essais ont été conduits avec des images d'au maximum 100MP.
+Les images de sortie filtrées sont produites en mémoire globale standard, hors texture, puis copiées vers une zone de mémoire de l'hôte (CPU) dont les pages sont réservées à l'avances et verrouillées, ce qui évite les pertes de performances liées aux défauts de page. L'algorithme \ref{algo-median-memcpy} synthétise ces pratiques en introduisant aussi les notations pour la suite. 
+Cet emploi de mémoire que l'on qualifiera dorénavant de \og non paginée \fg{}, apporte un gain de temps important dans les transferts même s'il peut aussi s'avérer limitant lorsqu'il s'agit de traiter de très grands volumes de données, puisqu'il empêche d'accéder à l'ensemble de la mémoire vive de l'hôte CPU. Les quantités de mémoire vive dont disposent les ordinateurs modernes permettent cependant de traiter sans restriction des images de plusieurs centaines de millions de pixels. Nos essais ont été conduits avec des images d'au maximum 100~MP.

 
 \begin{algorithm}
 %\SetNlSty{textbf}{}{:}
 
 \begin{algorithm}
 %\SetNlSty{textbf}{}{:}


@@ -19,7 +18,7 @@ Cet emploi de mémoire non paginée apporte un gain de temps important dans les
  allocation et affectation en mémoire CPU \textbf{h\_img\_in}\;
  allocation de mémoire CPU non-paginée \textbf{h\_img\_out}\;
  allocation de mémoire globale GPU  \textbf{d\_img\_out}\;
  allocation et affectation en mémoire CPU \textbf{h\_img\_in}\;
  allocation de mémoire CPU non-paginée \textbf{h\_img\_out}\;
  allocation de mémoire globale GPU  \textbf{d\_img\_out}\;

- allocation de mémoir texture GPU \textbf{tex\_img\_in}\;
+ allocation de mémoire texture GPU \textbf{tex\_img\_in}\;

  copie image de \textbf{h\_img\_in} vers \textbf{tex\_img\_in}\; 
  kernel\kl gridDim,blockDim\kr\tcc*[f]{sortie dans d\_img\_out}\;
  copie image de sortie de \textbf{d\_img\_out} vers \textbf{h\_img\_out}\;
  copie image de \textbf{h\_img\_in} vers \textbf{tex\_img\_in}\; 
  kernel\kl gridDim,blockDim\kr\tcc*[f]{sortie dans d\_img\_out}\;
  copie image de sortie de \textbf{d\_img\_out} vers \textbf{h\_img\_out}\;


@@ -28,9 +27,9 @@ Cet emploi de mémoire non paginée apporte un gain de temps important dans les
 \end{algorithm}
 
 
 \end{algorithm}
 
 

-Ces choix concernant les types de mémoire employés sont un facteur déterminant de la performance globale de l'implémentation. Cela sera confirmé par les mesures présentées à la fin de ce chapitre sur le filtre médian, mais une première expérience permet de s'en convaincre : le kernel médian 3$\times$3 d'Arrayfire, aimablement mis à disposition par l'un des développeurs, voit son débit global pratiquement doublé lorsqu'on adapte ses accès mémoire pour la combinaison texture/non-paginée que l'on vient de presenter.
+Ces choix concernant les types de mémoire employés sont un facteur déterminant de la performance globale de l'implémentation. Cela sera confirmé par les mesures présentées à la fin de ce chapitre, mais une première expérience permet de s'en convaincre : le kernel médian 3$\times$3 d'Arrayfire, aimablement mis à disposition par l'un des développeurs, voit son débit global pratiquement doublé lorsqu'on remplace ses accès mémoire par la combinaison texture/non-paginée que l'on vient de présenter.

  
  

-Le tableau \ref{tab-median-memcpy} donne le détail des temps de transferts pour quelques tailles usuelles d'images de niveaux de gris, codés en 8 ou 16 bits, et compare les temps globaux avec ceux mesurés lorsque la simple mémoire globale est employée. L'impact du choix de la configuration mémoire y est rendu évident, avec des gains de 15\% à 75\% constatés.
+Le tableau \ref{tab-median-memcpy} donne le détail des temps de transfert pour quelques tailles usuelles d'images en niveaux de gris, codés en 8 ou 16 bits, et compare les temps globaux avec ceux mesurés lorsque l'on utilise uniquement la mémoire globale. L'impact du choix de la configuration mémoire est évident, avec des gains constatés de 15\% à 75\%.

 
 \begin{table}[ht]
 \renewcommand{\arraystretch}{1.5}
 
 \begin{table}[ht]
 \renewcommand{\arraystretch}{1.5}


@@ -53,84 +52,93 @@ Le tableau \ref{tab-median-memcpy} donne le détail des temps de transferts pour
                                & 16 &6.21 &5.21 &\textbf{11.42}&13.16 \\
 \bottomrule
 \end{tabular}}  
                                & 16 &6.21 &5.21 &\textbf{11.42}&13.16 \\
 \bottomrule
 \end{tabular}}  

-\caption{Temps de transfert vers et depuis le GPU, en fonction de la dimension de l'image et de la profondeur de niveaux de gris. La colonne ``Mémoire globale'' donne les temps mesurés lorsque cette seule mémoire est employée.}
+\caption{Temps de transfert vers et depuis le GPU, en fonction de la dimension de l'image et de la profondeur des niveaux de gris. La colonne ``Mémoire globale'' donne les temps mesurés lorsque cette seule mémoire est employée.}

 \label{tab-median-memcpy}
 \end{table}
 
 
 \section{Utilisation des registres}
 
 \label{tab-median-memcpy}
 \end{table}
 
 
 \section{Utilisation des registres}
 

-En traitement d'image, les filtres médians sont beaucoup employés avec des tailles de fenêtres modestes pour du prétraitement, événtuellement itératif, ou bien avec de grandes fenêtres pour de l'estimation d'intensité d'arrière plan. Les taille intérmédiaires, disons de quelques dizaines de pixels, ne sont à notre connaissance pas employées.
+En traitement d'image, les filtres médians sont beaucoup employés avec des tailles de fenêtres modestes comme pré-traitement, éventuellement itératif, ou bien avec de grandes tailles de fenêtres pour de l'estimation d'intensité d'arrière plan. Les taille intermédiaires, de l'ordre de quelques dizaines de pixels, ne sont à notre connaissance que rarement employées.

 
 Un filtre médian de petite taille ne réalise que peu d'opérations, sans complexité de surcroît, et doit donc atteindre des niveaux de performances élevés.
 Le cadre général des traitements sur GPU présenté au paragraphe \ref{sec-bilateral} n'est alors plus pertinent, pour deux raisons :
 \begin{enumerate}
 
 Un filtre médian de petite taille ne réalise que peu d'opérations, sans complexité de surcroît, et doit donc atteindre des niveaux de performances élevés.
 Le cadre général des traitements sur GPU présenté au paragraphe \ref{sec-bilateral} n'est alors plus pertinent, pour deux raisons :
 \begin{enumerate}

-\item La phase de préchargement des données nécessaires en mémoire partagée prend du temps et la lecture se faisant depuis la mémoire globale/texture, elle est soumise aux latences qui lui sont attachées.
-\item l'utilisation en lecture/écriture des données en mémoire partagée, outre le fait qu'elle puisse être contraignante en terme de motif d'accès, n'atteint pas les débits permis par les registres individuels à la disposition des threads.
+\item La phase de pré-chargement des données nécessaires en mémoire partagée prend du temps et la lecture se faisant depuis la mémoire texture, elle est soumise aux latences qui lui sont attachées.
+\item l'utilisation en lecture/écriture des données en mémoire partagée, outre le fait qu'elle puisse être contraignante en terme de motifs d'accès, n'atteint pas les débits permis par les registres individuels à la disposition des threads.

 \end{enumerate}
 
 \end{enumerate}
 

-Il est ainsi clair que la chaîne de traitement la plus performante consiste à ne faire qu'une lecture en texture par pixel puis  d'effectuer les calcul en registres. Les limites d'intérêt de ce schéma général sont le nombre de registres disponibles, par thread et par bloc. Si on dépasse ces limites, le compilateur déporte les variables en mémoire locale, très peu performante. 
-Sans aller au delà de la limite, l'utilisation de trop nombreux registres va mécaniquement limiter le nombre de thread effectivement exécutés en parallèle par le GPU et bien souvent grêver la performance du kernel. Un compromis est à définir entre la recherche de vitesse par l'emploi des registres et le ralentissement que provoque l'usage d'un trop grand nombre de registres.
+Il est ainsi clair que la chaîne de traitement la plus performante consiste à ne faire qu'une lecture en texture par pixel puis  d'effectuer les calculs en registres. Les limites  de ce schéma général sont le nombre de registres disponibles, par thread et par bloc. Si on dépasse ces limites, le compilateur déporte les variables en mémoire locale très peu performante. 
+Sans aller au delà de la limite, l'utilisation de trop nombreux registres va mécaniquement limiter le nombre de threads effectivement exécutés en parallèle par le GPU et bien souvent grever la performance du kernel. Un compromis est donc à définir entre la recherche de vitesse par l'emploi des registres et le ralentissement que provoque l'usage d'un trop grand nombre de ces derniers.

 
 

-Prenons l'exemple d'un kernel qui ferait usage d'un total de 20 registres et que l'on exécuterait par blocs de 128 threads. La limite des 63 threads par blocs n'est évidemment pas atteinte, ni celle des 32K par bloc avec seulement $128 \times 20 = 2560$ registres. Dans ce cas, le GPU pourra exécuter en parallèle $32K/2560 = 12$ blocs, soit 1536 threads, ce qui représente le maximum possible.
-En revanche si le même kernel utilise maintenant 24 registres, le GPU ne pourra plus exécuter en parallèle que 1280 threads sur les 1536 physiquement possibles. Une perte de performance est alors à craindre.  
+Prenons l'exemple d'un kernel qui ferait usage d'un total de 20 registres par thread et que l'on exécuterait par blocs de 128 threads. La limite des 63 registres par thread n'est évidemment pas atteinte, ni celle des 32K par bloc avec seulement $128 \times 20 = 2560$ registres par bloc de 128 threads. Dans ce cas, le GPU pourra exécuter en parallèle $32K/2560 = 12$ blocs, soit 1536 threads, ce qui représente le maximum possible et permet d'envisager un bon niveau de performance.

 
 

-De ce point de vue, l'architecture Fermi qui propose 63 registres par thread et dont le modèle C2070 est un représentant, représente une régression par rapport à la génération précédente avec par exemple le GPU C1060 et ses 128 registres par thread. 
+En revanche, si le même kernel utilise maintenant 24 registres, le GPU ne pourra plus exécuter en parallèle que 1280 threads sur les 1536 techniquement possibles. Une perte de performance est alors à craindre.  

 
 

+De ce point de vue, l'architecture Fermi, et en particulier le modèle C2070, ne proposant que 63 registres par thread, représente une régression par rapport à la génération précédente avec par exemple le GPU C1060 et ses 128 registres par thread. 

 
 

-\subsection{La sélection de la valeur médiane}

 
 

+\subsection{La sélection de la valeur médiane}

 Dans le cas des filtres médians à petite fenêtre, on peut envisager d'attribuer un registre par valeur à trier. Dans ce cas, un médian 3$\times$3 emploiera 9 registres par thread, et cette méthode pourra théoriquement s'appliquer jusqu'au médian 7$\times$7 sur C2070 et 11$\times$11 sur C1060.
 Dans le cas des filtres médians à petite fenêtre, on peut envisager d'attribuer un registre par valeur à trier. Dans ce cas, un médian 3$\times$3 emploiera 9 registres par thread, et cette méthode pourra théoriquement s'appliquer jusqu'au médian 7$\times$7 sur C2070 et 11$\times$11 sur C1060.

-Toutefois, la recherche de performance impose de rationnaliser l'utilisation des registres et nous nous sommes orientés vers une méthode de sélection qui permet de ne pas avoir recours à cette cardinalité de un registre pour un pixel de la fenêtre, l'algorithme dit \textit{forgetful selection} ou sélection par oubli.
+Comme la recherche de performance impose de rationaliser l'utilisation des registres, nous nous sommes orientés vers l'algorithme dit \textit{forgetful selection} (sélection par oubli) qui évite d'avoir recours à cette cardinalité de \og un registre pour un pixel\fg{} de la fenêtre (\cite{medianggems5}).

 
 

-Le principe de la sélection par oubli est illustré en figure \ref{fig-median-ffs3-a} par l'exemple de la sélection de la médiane parmi 9 valeurs. Plus généralement, il s'agit de 
+Cette méthode  de  \og sélection par oubli\fg{} est illustrée en figure \ref{fig-median-ffs3-a} par l'exemple de la sélection de la médiane parmi 9 valeurs. Plus généralement, il s'agit de 

 \begin{enumerate}
 \begin{enumerate}

-\item former une liste initiale de $R_n$ valeurs prises parmi les $n=k\times k$ valeurs de la fenêtre du filtre.
-\item identifier, puis éliminer de la liste la plus petite et la plus grande valeur. 
-\item insérer dans la liste une nouvelle valeur parmi celles non encore intégrées.
+\item former une liste initiale de $R_n$ valeurs prises parmi les $n=k\times k$ valeurs de la fenêtre du filtre,
+\item identifier, puis éliminer de la liste la plus petite et la plus grande valeur,
+\item insérer dans la liste une nouvelle valeur parmi celles non encore intégrées,

 \item reprendre au point 2, et ce jusqu'à ce qu'il ne reste plus de valeur non utilisée. La médiane est alors la valeur restant dans la liste.
 \end{enumerate}
 
 \item reprendre au point 2, et ce jusqu'à ce qu'il ne reste plus de valeur non utilisée. La médiane est alors la valeur restant dans la liste.
 \end{enumerate}
 

-Cet algorithme nécessite un nombre constant d'étapes égal à $\left(n - \lceil\frac{n}{2}\rceil\right)$, ce qui assure une charge quasi équivalente pour tous les threads, même si le nombre d'opérations requis par l'identification des extrema dépend des valeurs dans chaque liste. Cette variabilité n'est pas conjointe à des branches d'exécution divergentes et n'induit pas de perte de performances.    
+Cet algorithme nécessite un nombre constant d'étapes, égal à $n - \lceil\frac{n}{2}\rceil$, ce qui devrait assurer une charge équivalente pour tous les threads. Cependant, il existe un léger déséquilibre dû au nombre d'opérations requis par l'identification des \textit{extrema} qui dépend des valeurs dans chaque liste. Cette variabilité, n'implique pas de branches d'exécution divergentes, et n'induit pas de perte de performances.    

 
 

-Nous avons par ailleurs choisi de fixer le nombre $R_n$ de valeurs figurant initialement dans la liste, comme le plus petit permettant de réaliser la sélection de la médiane. On obtient ce nombre limite en considérant qu'à chaque phase d'élimination des extrema, il faut garantir que la  médiane globale n'est pas élimnée. Or, la définition de la médiane indique que dans la liste triée complète, on trouve autant de valeurs dont l'indice est supérieur à celui de la médiane que de valeurs dont l'indice est inférieur. Sachant que les fenêtres des filtres comportent toujours un nombre impair de valeurs, la condition suffisante pour garantir la sélection est donc que le nombre de valeurs non intégrées dans la liste initiale soit inférieur au nombre de valeurs d'indice supérieur (ou inférieur) à la médiane dans la liste complète triée, soit 
+Nous avons par ailleurs choisi de fixer le nombre $R_n$ de valeurs figurant initialement dans la liste, comme le plus petit nombre permettant de réaliser la sélection de la médiane. On obtient cette valeur limite en considérant qu'à chaque phase d'élimination des extrema, il faut garantir que la  médiane globale n'est pas éliminée. Or, la définition de la médiane indique que dans la liste triée complète, on trouve autant de valeurs dont l'indice est supérieur à celui de la médiane que de valeurs dont l'indice lui est inférieur. Sachant que les fenêtres des filtres comportent toujours un nombre impair de valeurs, la condition suffisante pour garantir la sélection est donc que le nombre de valeurs non-intégrées dans la liste initiale soit inférieur au nombre de valeurs d'indice supérieur (ou inférieur) à la médiane dans la liste complète triée, soit 

 $$R_{n}=\lceil \frac{n}{2}\rceil+1$$
 
 $$R_{n}=\lceil \frac{n}{2}\rceil+1$$
 

-Cette valeur de $R_n$ représente donc aussi le nombre minimum de registres nécessaire à la sélection par oubli et sa minimisation permet de reculer la limite de taille admissible pour le filtre médian avec 9$\times$9 pour le GPU C2070.
+Cette valeur de $R_n$ représente donc aussi le nombre minimum de registres nécessaires à la sélection par oubli, ce qui permet de reculer la limite de taille admissible pour le filtre médian avec 9$\times$9 pour le GPU C2070.

 \begin{figure}
    \centering
 \begin{figure}
    \centering

-   \subfigure[Étapes de la sélection par oubli pour un filtre 3$\times$3.]{\label{fig-median-ffs3-a}\includegraphics[height=7cm]{Chapters/chapter5/img/forgetful_selectionb.jpg}\qquad}
-   \subfigure[Première étape d'identification des extrema pour un filtre 5$\times$5.]{\label{fig-median-ffs3-b}\includegraphics[height=5cm]{Chapters/chapter5/img/bitonic.jpg}}
-   \caption{Application de la sélection de médiane par oubli. a) à une fenêtre de  $3\times 3$ pixels. b) Maximisation de l'ILP pour l'identification des extrema. }
-   \label{fig-median-ffs3}
+   \includegraphics[height=7cm]{Chapters/chapter5/img/forgetful_selectionb.jpg}
+   \caption{Application de la sélection de médiane par oubli à une fenêtre de  $3\times 3$ pixels. }
+   \label{fig-median-ffs3-a}

 \end{figure}
 
 
 \subsection{Masquage des latences}
 
 \end{figure}
 
 
 \subsection{Masquage des latences}
 

-Les lectures en textures ainsi que les écritures en mémoire globale sont soumises à des latences que nous avons déjà détaillées au chapitre \ref{ch-GPU}. La mémoire texture bénéficie d'un cache permettant d'optimiser les lectures dans un voisinage à deux dimensions. Cela permet de réduire nettement les latences apparentes lors de l'accès aux éléments de la fenêtre du filtre. L'algorithme que nous proposons ne requiert qu'une lecture par élément de la fenêtre, dont la taille est assez petite pour que tous les éléments soient mis en cache. Aucune latence supeflue n'est donc générée à la lecture.
+Les lectures en texture ainsi que les écritures en mémoire globale sont soumises à des latences que nous avons déjà détaillées au chapitre \ref{ch-GPU}. La mémoire texture bénéficie d'un cache permettant d'optimiser les lectures dans un voisinage à deux dimensions. Cela permet de réduire nettement les latences apparentes lors de l'accès aux éléments de la fenêtre du filtre. L'algorithme que nous proposons ne requiert qu'une lecture par élément de la fenêtre, dont la taille est assez petite pour que tous les éléments soient mis en cache. Aucune latence superflue n'est donc générée à la lecture.

 
 

-Un autre moyen de réduire la latence moyenne constatée d'une séquence d'instructions est d'augmenter le niveau d'ILP (Instruction Level Parallelism ou parralélisme d'instructions). On cherche pour cela à réduire autant que possible la dépendance entre instructions successives au sein d'un kernel, de sorte à ne pas forcer le vidage des pipelines. Nous avons appliqué ce principe à la phase d'identification des extrema de la liste en arrangeant les instructions élémentaires de permutation de sorte à éloigner au maximum les instructions inter-dépendantes.  Dans l'exemple de la figure \ref{fig-median-ffs3-b}, on montre la séquence des permutations conditionnelles permettant l'identification des extrema lors de la première étape de sélection d'un filtre médian 5$\times$5. On retrouve donc les $R_n=14$ éléments de la liste initiale en haut de la figure, et la même liste au bas avec la valeur minimale à gauche et la valeur maximale à droite. Les séquences d'instructions indépendantes sont séparées par les lignes pointillées horizontales.
+Un autre moyen de réduire la latence moyenne constatée d'une séquence d'instructions est d'augmenter le niveau d'ILP (Instruction Level Parallelism ou parallélisme d'instructions). On cherche pour cela à réduire autant que possible la dépendance entre instructions successives au sein d'un kernel, de sorte à ne pas forcer les pipelines d'instructions des SMs à se vider. Nous avons appliqué ce principe à la phase d'identification des extrema de la liste en arrangeant les instructions élémentaires de permutation de sorte à éloigner au maximum les instructions inter-dépendantes.  L'exemple de la figure \ref{fig-median-ffs3-b} montre la séquence des permutations conditionnelles permettant l'identification des extrema lors de la première étape de sélection d'un filtre médian 5$\times$5. On retrouve les $R_n=14$ éléments de la liste initiale en haut de la figure, et la même liste au bas avec la valeur minimale à gauche et la valeur maximale à droite. Les séquences d'instructions indépendantes étant séparées par les lignes pointillées horizontales.

 
 

-Enfin, il est possible de réduire aussi la latence moyenne d'accès à la mémoire globale en faisant en sorte que chaque thread produise non pas la valeur de sortie d'un seul, mais de plusieurs pixels et ce, par autant d'écritures immédiatement consécutives, seule la première de la série générant une latence. Pour que l'application de ce principe produise l'effet attendu, il faut tout de même garantir la contiguïté des accès par demi-warp, ce qui est le cas ici si les valeurs multiples issues  par chaque thread sont également à des adresses consécutives en mémoire globale.  
+\begin{figure}
+   \centering
+   \includegraphics[height=5cm]{Chapters/chapter5/img/bitonic.png}
+   \caption{Première étape d'identification des extrema pour un filtre 5$\times$5, avec maximisation de l'ILP (Instruction Level Parallelism) pour l'identification des extrema.}
+   \label{fig-median-ffs3-b}
+\end{figure}

 
 

-Nous faisons l'hypothèse que chaque thread traite deux pixels voisins et cela impose de gérer la superposition partielle des fenêtres du filtre. La méthode de sélection que nous avons choisie nous interdit en effet d'employer les techniques habituelles, comme la mise à jour incrémentale de l'histogramme des niveaux de gris. Au contraire, les sélections doivent être menées conjointement et cela est rendu possible par le fait que la liste initiale ne comporte que $R_n$ éléments, ce qui est toujours inférieur ou égal au nombre de valeurs partagées par les fenêtres associées à deux pixels voisins (sous-entendu : horizontalement). Deux fenêtres voisines partagent $S_n = n-k = n-\sqrt{n}$ éléments  et, pour  $n\ge 9$ :  
-$$  n-\sqrt{n} \ge \lceil\frac{n}{2}\rceil +1$$ 
+Enfin, il est également possible de réduire la latence moyenne d'accès à la mémoire globale en faisant en sorte que chaque thread produise, non pas la valeur de sortie d'un seul pixel, mais de plusieurs, et ce par autant d'écritures immédiatement consécutives, seule la première de la série générant une latence. Pour que l'application de ce principe produise l'effet attendu, il faut tout de même garantir la contiguïté des accès par demi warp, ce qui est le cas ici si les valeurs multiples issues  par chaque thread se trouvent également à des adresses consécutives en mémoire globale.  
+
+Nous faisons l'hypothèse que chaque thread traite deux pixels voisins et cela impose de gérer la superposition partielle des fenêtres du filtre. La méthode de sélection que nous avons choisie nous interdit en effet d'employer les techniques habituelles, comme la mise à jour incrémentale de l'histogramme des niveaux de gris. Cependant, une partie des traitements est commune aux 2 processus de sélection. En effet, les fenêtres associées aux deux  pixels partagent un certain nombre de données, égal à $S_n = n-k = n-\sqrt{n}$. Or, pour $n\ge 9$ :
+$$  n-\sqrt{n} \ge \lceil\frac{n}{2}\rceil +1$$
+
+% Au contraire, les sélections doivent être menées conjointement et cela est rendu possible par le fait que la liste initiale ne comporte que $R_n$ éléments, ce qui est toujours inférieur ou égal au nombre de valeurs partagées par les fenêtres associées à deux pixels voisins (sous-entendu : horizontalement). Deux fenêtres voisines partagent $S_n = n-k = n-\sqrt{n}$ éléments  et, pour  $n\ge 9$ :  
+% $$  n-\sqrt{n} \ge \lceil\frac{n}{2}\rceil +1$$ 

 
 \begin{figure}
    \centering
 
 \begin{figure}
    \centering

-   \includegraphics[width=6cm]{Chapters/chapter5/img/median5_overlap.jpg}
+   \includegraphics[width=6cm]{Chapters/chapter5/img/median5_overlap.png}

    \caption{Gestion des éléments communs aux fenêtres de deux pixels centraux voisins dans un filtre médian 5$\times$5. La liste initiale comprend les 14 premiers éléments communs, puis les 7 premières étapes de sélection sont conduites en commun avant que les 5 dernières le soient en parallèle, mais de manière disjointe.}
    \label{fig-median-overlap}
 \end{figure}
 
    \caption{Gestion des éléments communs aux fenêtres de deux pixels centraux voisins dans un filtre médian 5$\times$5. La liste initiale comprend les 14 premiers éléments communs, puis les 7 premières étapes de sélection sont conduites en commun avant que les 5 dernières le soient en parallèle, mais de manière disjointe.}
    \label{fig-median-overlap}
 \end{figure}
 

-Nous pouvons donc initialiser la liste de sélection  avec $R_n$  valeurs choisies parmi les $S_n$ valeurs communes,  puis mener les $\left(S_n-R_n+1\right)$ premières étapes de sélection permettant d'intégrer progressivement l'ensemble des valeurs communes à la liste. Il ne reste alors que les $k$ éléments propres à chaque fenêtre à intégrer dans deux séquences de sélection rendues distinctes mais réalisées en parallèle. Cette répartition des éléments pour un filtre médian 5$\times$5 est représentée à la figure \ref{fig-median-overlap}. Comme on le voit sur la figure, les $R_n$ premières valeurs sont simplement prises au début de la liste des valeurs communes, sans que cela ne génère des défauts de cache pour les fenêtres de taille supérieure (le cache de texture 2D contient environ 5Ko).
+Nous pouvons donc initialiser la liste de sélection  avec $R_n$  valeurs choisies parmi les $S_n$ valeurs communes en étant sur que le processus de sélection n'écartera pas les deux médianes. Ensuite, on mène les $\left(S_n-R_n+1\right)$ premières étapes de sélection permettant d'intégrer progressivement l'ensemble des valeurs communes à la liste. Il ne reste alors que les $k$ éléments propres à chaque fenêtre à intégrer dans deux séquences de sélection rendues distinctes mais réalisées en alternance par le même thread. Cette répartition des éléments pour un filtre médian 5$\times$5 est représentée à la figure \ref{fig-median-overlap}. Comme on le voit sur la figure, les $R_n$ premières valeurs sont simplement prises au début de la liste des valeurs communes, sans que cela ne génère des défauts de cache pour les fenêtres de taille supérieure (le cache de texture 2D contient environ 5Ko).

 
 

-Chaque thread utilise plus de registres ($R_n+2k$) pour traiter deux pixels que pour un seul ($R_n$). Notons que cela ne modifie pas les capacités  théoriques de traitement avec toujours une taille maximale de 9$\times$9 pour C2070. Il suffit alors de réduire le nombre de threads par bloc pour retrouver le niveau de parallélisme souhaité. Mais globalement, traiter deux pixels par threads permet d'utiliser $k+1$ registres de moins par paire de pixels par rapport au traitement par threads distincts. Cela nous permet donc finalement aussi un gain de parallélisme au niveau de chaque bloc.
+Chaque thread utilise plus de registres ($R_n+2k$) pour traiter deux pixels que pour un seul ($R_n$), mais cela ne modifie pas les capacités  théoriques de traitement, avec toujours une taille maximale de 9$\times$9 sur C2070. Il suffit alors de réduire le nombre de threads par bloc pour retrouver le niveau de parallélisme souhaité. Mais globalement, traiter deux pixels par threads permet d'utiliser $k+1$ registres de moins par paire de pixels par rapport au traitement par threads distincts, ce qui représente  un gain de parallélisme au niveau de chaque bloc.

 
 

-Nous avons fait ici l'hypothèse d'un traitement de deux pixels par thread. Le passage à quatre pixels par thread signifie ne plus disposer que de $n-3k$ éléments communs aux quatre fenêtres, ce qui est inférieur à $R_n$ pour les tailles 3$\times$3 et 5$\times$5, et ne permet que deux étapes de sélection communes pour le 7$\times$7, ce qui ne permet pas de compenser le coût des copies nécessaires au dédoublement. Le cas du 9$\times$9 pourrait sembler plus pertinent, mais là encore les coûts inhérents aux sélections disjointes ne parviennent pas à être compensées par une séquence suffisamment importante de sélections communes aux quatre pixels. La solution deux pixels par thread s'avère la plus performante.
+Nous avons fait jusqu'ici l'hypothèse d'un traitement de deux pixels par thread. Le passage à quatre pixels par thread implique $n-3k$ éléments communs aux quatre fenêtres, ce qui est inférieur à $R_n$ pour les tailles 3$\times$3 et 5$\times$5, et ne permet que deux étapes de sélections communes pour le 7$\times$7. cela ne compense pas le coût des copies nécessaires au dédoublement. Le cas du 9$\times$9 pourrait sembler plus pertinent, mais là encore, les sélections communes aux quatre pixels ne sont pas suffisamment nombreuses pour compenser les coûts inhérents aux sélections disjointes. La solution deux pixels par thread s'avère la plus performante.

 
 

-L'ensemble des choix que nous venons de décrire et qui ont présidé à l'élaboration de notre filtre médian GPU conduisent à adopter un style de codage assez inhabituel. En effet, les registres dont nous faisons un usage intensif ne sont en particulier pas indexables. Le code du filtre médian 3$\times$3 est reproduit au listing \ref{lst-median3} pour en illustrer ces implications pratiques.
+L'ensemble des choix que nous venons de décrire et qui ont présidé à l'élaboration de notre filtre médian GPU conduisent à adopter un style de codage assez inhabituel, du fait de l'usage intensif des registres dont une des caractéristiques est de ne pas être indexables. Le code du filtre médian 3$\times$3 est reproduit au listing \ref{lst-median3}.

 
 \lstinputlisting[label={lst-median3},caption=Kernel réalisant un filtre médian 3$\times$3 en registres.]{Chapters/chapter5/code/median3-2pix.cu} 
 
 
 \lstinputlisting[label={lst-median3},caption=Kernel réalisant un filtre médian 3$\times$3 en registres.]{Chapters/chapter5/code/median3-2pix.cu} 
 


@@ -144,9 +152,9 @@ L'ensemble des choix que nous venons de décrire et qui ont présidé à l'élab
    \label{fig-median-comp}
 \end{figure}
 
    \label{fig-median-comp}
 \end{figure}
 

-Les valeurs présentées dans les tableaux  \ref{tab-median-coutcpy}, \ref{tab-median-chronos} et la figure \ref{fig-median-comp} sont obtenues par moyennage du chronométrage de 1000 exécutions du même kernel, développé en variantes 8 et 16 bits de profondeur de niveau de gris. 
+Les valeurs présentées dans les tableaux  \ref{tab-median-coutcpy}, \ref{tab-median-chronos} et la figure \ref{fig-median-comp} sont obtenues par moyennage du chronométrage de 1000 exécutions du même kernel, développé en variantes 8 et 16 bits de profondeurs de niveau de gris. 

  
  

-La première analyse que nous pouvons en faire est la pertinence des choix faits quant aux transferts de données, qui représentent entre 13\% et 82\% du temps total d'exécution des configurations testées. 
+L'analyse que nous pouvons tirer du tableau \ref{tab-median-coutcpy} est la pertinence des choix relatifs aux transferts de données, qui représentent entre 13\% et 82\% du temps total d'exécution des configurations testées. 

 
 \begin{table}[ht]
 \renewcommand{\arraystretch}{1.5}
 
 \begin{table}[ht]
 \renewcommand{\arraystretch}{1.5}


@@ -156,42 +164,27 @@ La première analyse que nous pouvons en faire est la pertinence des choix faits
 \toprule
 {\bf Taille d'image}& {\bf Profondeur}& \textbf{3$\times$3} & \textbf{5$\times$5} & \textbf{7$\times$7} \\
 \midrule
 \toprule
 {\bf Taille d'image}& {\bf Profondeur}& \textbf{3$\times$3} & \textbf{5$\times$5} & \textbf{7$\times$7} \\
 \midrule

-\multirow{2}{*}{512$^2$} &8 bits&73\% &44\% &20\% \\
+\multirow{2}{*}{512$\times$512} &8 bits&73\% &44\% &20\% \\

                                          &16 bits&82\% &57\% &29\% \\
 \midrule
                                          &16 bits&82\% &57\% &29\% \\
 \midrule

-\multirow{2}{*}{1024$^2$}&8 bits&68\% &37\% &15\% \\
+\multirow{2}{*}{1024$\times$1024}&8 bits&68\% &37\% &15\% \\

                                          &16 bits&80\% &53\% &25\% \\
 \midrule
                                          &16 bits&80\% &53\% &25\% \\
 \midrule

-\multirow{2}{*}{2048$^2$}&8 bits&66\% &34\% &14\% \\
+\multirow{2}{*}{2048$\times$2048}&8 bits&66\% &34\% &14\% \\

                                          &16 bits&79\% &59\% &23\% \\
 \midrule
                                          &16 bits&79\% &59\% &23\% \\
 \midrule

-\multirow{2}{*}{4096$^2$}&8 bits&65\% &33\% &13\% \\
+\multirow{2}{*}{4096$\times$4096}&8 bits&65\% &33\% &13\% \\

                                          &16 bits&78\% &50\% &23\% \\
 \bottomrule
 \end{tabular}}  
                                          &16 bits&78\% &50\% &23\% \\
 \bottomrule
 \end{tabular}}  

-\caption{Pourcentage du temps d'exécution pris par les transferts de données en fonction de la taille de fenêtre du filtre, pour les profondeurs  8 and 16 bit sur GPU C2070.}
+\caption{Pourcentage du temps d'exécution pris par les transferts de données en fonction de la taille de fenêtre du filtre, pour les profondeurs  8 et 16 bits sur GPU C2070.}

 \label{tab-median-coutcpy}
 \end{table}
 
 
 \label{tab-median-coutcpy}
 \end{table}
 
 

-Les valeurs du tableau \ref{tab-median-chronos} détaillent les débits de pixels réalisés par les différents kernels. Ils prennent en compte le temps d'exécution ainsi que les temps de transfert. Par ailleurs, afin d'évaluer le niveau de performance absolue de notre méthode, nous avons également mesuré le débit maximum effectif permis par le couple GPU/CPU. Ce débit maximum  nous permet d'évaluer la pertinence d'éventuelles recherches postérieures qui chercheraient à améliorer encore les débits. La valeur de ce débit maximum est obtenue en exécutant un kernel ``identité'' qui n'effectue aucune opération mais se contente de faire les lectures et écritures en mémoire. Les débits ainsi mesurés sont regroupés dans le tableau  \ref{tab-median-debitmax} où l'on constate en particulier que plus l'image est de grande dimensions, plus on peut espérer un débit élevé. On vérifie aussi notre intuition initiale avec des valeurs d'environ 2 milliards de pixels par seconde, à comparer aux moins de 2 millions de pixels par seconde permis par les implémentations de référence. 
+Les valeurs du tableau \ref{tab-median-chronos} détaillent les débits de pixels réalisés par les différents kernels. Ils prennent en compte le temps d'exécution ainsi que les temps de transfert. Par ailleurs, afin d'évaluer le niveau de performance absolue de notre méthode, nous avons également mesuré le débit maximum effectif permis par le couple GPU/CPU, ce qui  nous permet d'évaluer la pertinence d'éventuelles recherches postérieures visant à améliorer encore les débits. 

 
 

-\begin{table}[h]
-\centering
-{
-\begin{tabular}{ccc}
-\toprule
-{\bf Taille d'image}& {$\mathbf{ T_8}$} & {$\mathbf{T_{16}}$} \\
-\midrule
-512$\times$512   &1598 &975 \\
-1024$\times$1024 &2101 &1200 \\
-2048$\times$2048 &2359 &1308 \\
-4096$\times$4096 &2444 &1335 \\
-\bottomrule
-\end{tabular} }
-\caption{Débits maximum effectifs $T_8$ and $T_{16}$ (en MP/s), respectivement pour les variantes 8 et 16 bits sur C2070.}
-\label{tab-median-debitmax}
-\end{table}
+La valeur de ce débit maximum est obtenue en exécutant un kernel \og identité\fg{} qui n'effectue aucune opération mais se contente de faire les lectures et écritures en mémoire. Les débits ainsi mesurés sont regroupés dans le tableau  \ref{tab-median-debitmax} où l'on constate en particulier que plus l'image est de grande dimension, plus on peut espérer un débit élevé. On vérifie aussi notre intuition initiale avec des valeurs d'environ 2000~MP/s, à comparer aux moins de 200~MP/s permis par les implémentations de référence. 

 
 \begin{table}[ht]
 \centering
 
 \begin{table}[ht]
 \centering


@@ -220,17 +213,34 @@ Les valeurs du tableau \ref{tab-median-chronos} détaillent les débits de pixel
 \label{tab-median-chronos}
 \end{table}
 
 \label{tab-median-chronos}
 \end{table}
 

-Les performances des kernels en variante 16 bits ne différent pas de celles en variante 8 bits, les seuls temps de transfert des données sont à l'origine des différences de performance globale. 
+\begin{table}[h]
+\centering
+{
+\begin{tabular}{ccc}
+\toprule
+{\bf Taille d'image}& {$\mathbf{ T_8}$} & {$\mathbf{T_{16}}$} \\
+\midrule
+512$\times$512   &1598 &975 \\
+1024$\times$1024 &2101 &1200 \\
+2048$\times$2048 &2359 &1308 \\
+4096$\times$4096 &2444 &1335 \\
+\bottomrule
+\end{tabular} }
+\caption{Débits maximum effectifs $T_8$ and $T_{16}$ (en MP/s), respectivement pour les variantes 8 et 16 bits sur C2070.}
+\label{tab-median-debitmax}
+\end{table}
+
+Les performances des kernels en variante 16 bits ne différent pas de celles en variante 8 bits, seuls les temps de transfert des données sont à l'origine des variations du débit global. 

 
 

-Enfin, considérant que l'algorithme implémenté est proche de celui d'Arrayfire, nous avons mesuré les débits atteints par leurs kernels, modifiés pour adopter notre gestion mémoire. Cette manipulation permet au kernel Arrayfire 3$\times$3 de traiter 670~MP/s, soit 3,7 fois plus que la version commerciale. L'écart restant avec notre implémentation ($\times$2,7) étant à mettre au crédit de notre implémentation du kernel.
-$\times$
+Enfin, considérant que l'algorithme implémenté dans les kernels d'Arrayfire est proche du notre, nous avons mesuré les débits d'une version modifiée de leur kernel appliquant nos techniques de gestion mémoire, avec pour résultat un filtre médian 3$\times$3 capable de traiter 670~MP/s, soit 3,7 fois plus que la version commerciale. L'écart restant ($\times$2,7) étant à mettre au crédit de notre implémentation du kernel.

 
 \section{Conclusion}
 
 
 \section{Conclusion}
 

-L'implémentation GPU du filtre médian que nous avons décrite permet de traiter environ jusqu'à 1854 millions de pixels à la seconde, soit aussi 900 images haute définition (1080p), et surclasse les solutions jusqu'alors proposées dans la littérature dont la plus performante ne débitait que 180 millions de pixels par seconde (voir \cite{sanchezICASSP12}). Cet important gain de vitesse est la conséquence de l'attention toute particulière que nous avons apportée à la gestion de la mémoire, tant du coté GPU que CPU, et qui nous a conduit à concevoir des kernels utilisant exclusivement des registres pour effectuer les opérations de sélection. 
+L'implémentation GPU du filtre médian que nous avons décrite permet de traiter jusqu'à 1854 millions de pixels à la seconde, soit aussi 900 images haute définition (1080p), et surclasse les solutions jusqu'alors proposées dans la littérature, dont la plus performante ne débitait que 180 millions de pixels par seconde (voir \cite{sanchezICASSP12}). Elle a fait l'objet d'un article dans la revue \textit{Journal of Signal Processing Systems} (voir \cite{perrot2013fine}). L'important gain de vitesse est la conséquence de l'attention toute particulière que nous avons apportée à la gestion de la mémoire, tant du côté GPU que CPU, et qui nous a conduit à concevoir des kernels utilisant exclusivement des registres pour effectuer les opérations de sélection. 

 
 

-Le débit de pixels constaté approche cette fois le débit maximal effectif de la plateforme (2444~MP/s), ce qui ne laisse pas envisager la possibilité d'obtenir de nouveau un gain de cet ordre par d'autres techniques. Toutefois, notre algorithme appartient à la classe des solutions de filtrage médian par tri (incomplet)  des valeurs et à ce titre, ses temps d'exécution sont fortement dépendants de la taille de la fenêtre de filtrage, comme le montrent les diagrammes de la figure \ref{fig-median-comp}. Il n'est donc pertinent que pour les petites tailles de fenêtre, les plus communément employées en traitement d'image.
+Le débit de pixels constaté approche cette fois le débit maximal effectif de la plateforme (2444~MP/s), ce qui limite le gain que pourraient apporter des implémentations futures. Toutefois, notre algorithme appartient à la classe des solutions de filtrage médian par tri (incomplet) des valeurs et à ce titre, ses temps d'exécution sont fortement dépendants de la taille de la fenêtre de filtrage, comme le montrent les diagrammes de la figure \ref{fig-median-comp}. Il n'est donc pertinent que pour les petites tailles de fenêtre, qui sont aussi les plus communément employées en traitement d'image.

 
 

-Dans les grandes tailles de fenêtres, la plupart des solutions adoptent des méthodes approchées de détermination de la médiane. Les principes que nos avons appliqués peuvent alors apporter des gains de performance, ainsi qu'à beaucoup d'autres méthodes de calcul comme les filtres de convolution abordés dans le chapitre suivant. 
+Dans les grandes tailles de fenêtre, la plupart des solutions adoptent des méthodes approchées de détermination de la médiane. Les principes que nos avons appliqués peuvent alors apporter des gains de performance comme nous l'avons montré dans \cite{perrotbookgpu}, ainsi qu'à beaucoup d'autres méthodes de calcul comme les filtres de convolution abordés dans le chapitre suivant. 

 
 

-Enfin la conclusion du prochain chapitre présentera l'outil en ligne que nous proposons et qui permet de générer les codes des kernels médians et de convolution.
\ No newline at end of file
+Enfin nous renvoyons le lecteur à la conclusion du prochain chapitre qui présentera l'outil en ligne que nous proposons et qui permet de générer les codes des kernels médians et de convolution.
+% LocalWords:  cardinalité warp incrémentale indexables