X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/1bdc5bd76352d829a51e2d6407ad331af7164113..e81bd9912542bc52e4b0fd1206e0b6f9b93a5fda:/THESE/Chapters/chapter5/chapter5.tex?ds=inline

diff --git a/THESE/Chapters/chapter5/chapter5.tex b/THESE/Chapters/chapter5/chapter5.tex
index 22f6d63..be63700 100644
--- a/THESE/Chapters/chapter5/chapter5.tex
+++ b/THESE/Chapters/chapter5/chapter5.tex
@@ -1,17 +1,17 @@
 \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}
 
-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.
+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.
 
-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. 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}{}{:}
@@ -19,7 +19,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 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}\;
@@ -28,9 +28,9 @@ Cet emploi de mÃ©moire non paginÃ©e apporte un gain de temps important dans les
 \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}
@@ -53,84 +53,94 @@ 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}}  
-\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}
 
-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 pas 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}
-\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}
 
-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}
 
 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}
-\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}
 
-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$$
 
-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
-   \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}
 
-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 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}
 
-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.
+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.  
 
-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.  
+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$$
 
-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$$ 
+% 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
-   \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}
 
-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} 
 
@@ -144,7 +154,7 @@ L'ensemble des choix que nous venons de dÃ©crire et qui ont prÃ©sidÃ© Ã  l'Ã©lab
    \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. 
 
@@ -156,42 +166,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
-\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
-\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
-\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
-\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}}  
-\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}
 
 
-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
@@ -220,17 +215,34 @@ Les valeurs du tableau \ref{tab-median-chronos} dÃ©taillent les dÃ©bits de pixel
 \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}
 
-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
