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 2ec0d1027fb3d8063de1d80bcb3a2f968ec2b25e..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é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}).
+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 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 intuitivement semblé que ces débits étaient très en deçà 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 GPU, 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.
+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.
 
 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.
 

-Les images de sortie filtrées 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 même s'il peut aussi s'avérer limitant lorsqu'il s'agit de traiter de très grands volumes de données. 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.
+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}{}{:}


@@ -30,7 +29,7 @@ Cet emploi de mémoire non paginée apporte un gain de temps important dans les
 
 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.
  
 
 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 en 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 constatés de 15\% à 75\%.
+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,14 +52,14 @@ 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 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 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 :
 
 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 :


@@ -69,8 +68,8 @@ Le cadre général des traitements sur GPU présenté au paragraphe \ref{sec-bil
 \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}
 
 \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}
 

-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 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 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 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.
 
 
 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.
 


@@ -80,30 +79,28 @@ De ce point de vue, l'architecture Fermi, et en particulier le modèle C2070, ne
 
 
 \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.

-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 permet de ne pas avoir recours à cette cardinalité de un registre pour un pixel de la fenêtre (\cite{medianggems5}).
+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 \textit{extrema} dépend des valeurs dans chaque liste. Cette variabilité, n'étant pas conjointe à des branches d'exécution divergentes, elle 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 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 
+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écessaires à 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.png}}
-   \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 (Instruction Level Parallelism) 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}
 
 
 \end{figure}
 
 


@@ -111,12 +108,22 @@ Cette valeur de $R_n$ représente donc aussi le nombre minimum de registres néc
 
 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.
 
 
 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 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 à 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.
+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.
+
+\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}

 
 

-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 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.  
+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. 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$$ 
+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


@@ -125,11 +132,11 @@ $$  n-\sqrt{n} \ge \lceil\frac{n}{2}\rceil +1$$
    \label{fig-median-overlap}
 \end{figure}
 
    \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$), 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 donc 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 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.
+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, 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}.
 
 
 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}.
 


@@ -147,7 +154,7 @@ L'ensemble des choix que nous venons de décrire et qui ont présidé à l'élab
 
 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. 
  
 
 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}


@@ -157,16 +164,16 @@ 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}}  


@@ -177,24 +184,7 @@ La première analyse que nous pouvons en faire est la pertinence des choix faits
 
 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. 
 
 
 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. 
 

-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 grandes 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 200 millions de pixels par seconde permis par les implémentations de référence. 
-
-\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


@@ -223,15 +213,32 @@ La valeur de ce débit maximum est obtenue en exécutant un kernel ``identité''
 \label{tab-median-chronos}
 \end{table}
 
 \label{tab-median-chronos}
 \end{table}
 

+\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é 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}
 
 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é 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}
 

-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 qu'elle permet 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, qui sont aussi 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ê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. 
 
 
 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.