X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/72441aeeda78a2607a1fe941b9a3580e74b4951c..0b60f2b9f649af92fb00ae9fb88d77fe1cbb5c85:/THESE/Chapters/chapter5/chapter5.tex

diff --git a/THESE/Chapters/chapter5/chapter5.tex b/THESE/Chapters/chapter5/chapter5.tex
index 2ec0d10..88ec0cb 100644
--- a/THESE/Chapters/chapter5/chapter5.tex
+++ b/THESE/Chapters/chapter5/chapter5.tex
@@ -1,17 +1,16 @@
 \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}
-
-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.
 
-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}{}{:}
@@ -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.
  
-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}
@@ -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}}  
-\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 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 :
@@ -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}
 
-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.
 
@@ -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}
-
 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}
-\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 \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$$
 
-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
-   \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}
 
 
@@ -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.
 
-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
@@ -125,11 +132,11 @@ $$  n-\sqrt{n} \ge \lceil\frac{n}{2}\rceil +1$$
    \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}.
 
@@ -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. 
  
-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}
@@ -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
-\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}}  
@@ -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. 
 
-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
@@ -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}
 
+\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}
 
-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. 
 
