X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/1bdc5bd76352d829a51e2d6407ad331af7164113..10d54068846e7aee58e98dc76fa92f6f3a5c957a:/THESE/Chapters/chapter6/chapter6.tex

diff --git a/THESE/Chapters/chapter6/chapter6.tex b/THESE/Chapters/chapter6/chapter6.tex
index c650ee4..12badec 100644
--- a/THESE/Chapters/chapter6/chapter6.tex
+++ b/THESE/Chapters/chapter6/chapter6.tex
@@ -1,17 +1,21 @@
 \section{Introduction}
-AprÃ¨s avoir conÃ§u des  filtres mÃ©dians aux peformances Ã©levÃ©es, nous avons cherchÃ© Ã  en appliquer les principes Ã  d'autres types d'algorithmes de filtrage.
+AprÃ¨s avoir conÃ§u des  filtres mÃ©dians aux performances Ã©levÃ©es, nous avons cherchÃ© Ã  en appliquer les principes Ã  d'autres types d'algorithmes de filtrage.
 Les filtres de convolution, par la diversitÃ© des traitements qu'ils permettent de rÃ©aliser et leur universalitÃ©, nous ont semblÃ© Ãªtre un objectif particuliÃ¨rement intÃ©ressant.
 
-Les principes et formulation de la convolution sont prÃ©sentÃ©s au chapitre \ref{sec-op-base} et nous nous attacherons uniquement dans les paragraphes qui suivent Ã  dÃ©tailler les solutions et expÃ©rimentations qui permettent de concevoir des filtres de convolution performants sur GPU. Nous faisons l'hypothÃ¨se que les fonctions de convolution sont Ã  support carrÃ© de taille impaire, permettant ainsi de considÃ©rer un \textit{pixel central}. Cette hypothÃ¨se ne constitue pas une restriction en termes de traitement car tout support non carrÃ© peut Ãªtre Ã©tendu Ã  un support carrÃ© mÃªme si dans ce cas de figure, l'exÃ©cution impliquera plus d'opÃ©rations que nÃ©cessaire et ne sera ainsi plus optimale. 
+Le principe et la formulation de la convolution sont prÃ©sentÃ©s au chapitre \ref{sec-op-base} aussi nous attacherons nous uniquement dans les paragraphes qui suivent Ã  dÃ©tailler les solutions et expÃ©rimentations permettant de concevoir des filtres rapides sur GPU. 
 
-L'Ã©tude la plus complÃ¨te et qui montre les performances les plus Ã©levÃ©es Ã©mane du constructeur Nvidia lui-mÃªme dans \cite{convolutionsoup}. Nous l'avons prÃ©sentÃ©e dans le chapitre \ref{} et nous rappellons simplement ici qu'elle a utilisÃ© des modÃ¨les Ã  architecture GT200 (GTX280) dont nous disposons Ã©galement et qu'elle a choisi comme traitement de rÃ©fÃ©rence une convolution non-sÃ©parable de masque 5$\times$5 sur une image en profondeur 8 bits de 2048$\times$2048 pixels.
-Leur implÃ©mentation la plus rapide effectue cette opÃ©ration en 1.4~ms et permet un dÃ©bit global (incluant les temps de transfert des donnÃ©es) de 945 millions de pixels Ã  la seconde (MP/s). Elle est prise comme rÃ©fÃ©rence pour nos implÃ©mentations. 
+Nous faisons l'hypothÃ¨se que les fonctions de convolution sont Ã  support carrÃ©, de taille de cÃ´tÃ©s impaire, permettant ainsi de considÃ©rer un \textit{pixel central}. Cette hypothÃ¨se ne constitue pas une restriction en termes de traitement car tout support non carrÃ© peut Ãªtre Ã©tendu Ã  un support carrÃ© mÃªme si, dans ce cas de figure, l'exÃ©cution impliquera plus d'opÃ©rations que nÃ©cessaire et ne sera ainsi plus optimale. 
 
-\section{ImplÃ©mentation gÃ©nÃ©rique de la convolution non sÃ©parable}
+L'Ã©tude la plus complÃ¨te et qui montre les performances les plus Ã©levÃ©es Ã©mane du constructeur Nvidia lui-mÃªme dans \cite{convolutionsoup}. Nous l'avons prÃ©sentÃ©e au paragraphe \ref{sec-filtresgpu} et nous rappellerons simplement ici qu'elle a utilisÃ© des modÃ¨les Ã  architecture GT200 (GTX280) et choisi comme traitement de rÃ©fÃ©rence une convolution non-sÃ©parable de masque 5$\times$5 sur une image en profondeur 8 bits de 2048$\times$2048 pixels.
+Leur implÃ©mentation la plus rapide effectue cette opÃ©ration en 1,4~ms et permet un dÃ©bit global (incluant les temps de transfert des donnÃ©es) de 945 millions de pixels Ã  la seconde (MP/s). Elle servira de rÃ©fÃ©rence pour nos expÃ©rimentations. 
+
+\section{ImplÃ©mentation gÃ©nÃ©rique de la convolution non sÃ©parable sur GPU}
 
 L'implÃ©mentation GPU de la  convolution non-sÃ©parable d'une fonction image $I$ par une fonction masque $h$ dÃ©finie sur un support $\Omega$ peut-Ãªtre dÃ©crite comme dans l'algorithme \ref{algo-convo-gene}. Pour le cas oÃ¹ la somme $S_h$ des valeurs du masque est diffÃ©rente de 1, l'image rÃ©sultante $I'$ est obtenue aprÃ¨s une normalisation nÃ©cessaire pour ne pas modifier l'intensitÃ© moyenne de l'image. Par exemple, pour une profondeur de 8 bits :
+Si $S_h > 0$ alors $I' = I_{\Omega}/S_h$
+
+Selon la valeur de la somme $S_h$, il peut Ãªtre nÃ©cessaire de \og recaler\fg{} globalement les niveaux de gris de l'image. Ainsi : 
 \begin{enumerate}
-\item Si $S_h > 0$ alors $I' = I_{\Omega}/S_h$
 \item Si $S_h = 0$ alors $I' = I_{\Omega} + 128$
 \item Si $S_h < 0$ alors $I' = I_{\Omega} + 255$
 \end{enumerate}
@@ -28,13 +32,13 @@ L'implÃ©mentation GPU de la  convolution non-sÃ©parable d'une fonction image $I$
   }
 \end{algorithm}
 
-Il est tout Ã  fait possible d'envisager ici l'application brute des principes mis en \oe uvre pour les filtres mÃ©dians. Cela conduit au code du listing \ref{lst-convo-gene3reg8} oÃ¹ les coefficients du masque (moyenneur 3$\times$3) sont fixÃ©s et mÃ©morisÃ©s chacun dans un registre, le calcul de la somme s'effectuant Ã©galement dans un registre. Pour Ã©viter des opÃ©rations coÃ»teuses comme la division, on remarque que la normalisation est Ã©vitÃ©e et prÃ©-effectuÃ©e au niveau des coefficients du masque dont la somme est ainsi Ã©gale Ã  1.
+Il est tout Ã  fait possible d'envisager ici l'application brute des principes mis en \oe uvre pour les filtres mÃ©dians. Cela conduit au code du listing \ref{lst-convo-gene3reg8} oÃ¹ chaque coefficient du masque (moyenneur 3$\times$3) est fixÃ© et mÃ©morisÃ© dans un registre, le calcul de la somme s'effectuant Ã©galement dans un registre. Pour Ã©viter des opÃ©rations coÃ»teuses comme la division, on remarque que la normalisation est Ã©vitÃ©e et prÃ©-effectuÃ©e au niveau des coefficients du masque dont la somme est ainsi toujours Ã©gale Ã  1.
 Par ailleurs, pour des raisons de lisibilitÃ© de ce premier code, chaque thread ne traite ici qu'un seul pixel.
 
 \lstinputlisting[label={lst-convo-gene3reg8},caption={Kernel rÃ©alisant la convolution par un masque moyenneur 3$\times$3 dont les coefficients normalisÃ©s sont codÃ©s \textit{en dur}, dans les registres du GPU.}]{Chapters/chapter6/code/convoGene3Reg8.cu}
 
-Les performances de cette implÃ©mentation directe ont Ã©tÃ© regroupÃ©es dans les tableaux \ref{tab-convo-gene3reg8-480} et \ref{tab-convo-gene3reg8-2070} oÃ¹ l'on peut immÃ©diatement constater que la solution optimale Nvidia demeure plus rapide. 
-L'analyse plus dÃ©taillÃ©e nous apprend aussi que le modÃ¨le GTX280 exÃ©cute le kernel plus vite que le plus rÃ©cent C2070, en raison d'un plus grand nombre de registres disponibles. MalgrÃ© tout, lorsqu'on prend en compte les temps de transfert des donnÃ©es, l'avantage va au C2070 qui rÃ©alise ce traitement Ã  875~MP/s.
+Les performances de cette implÃ©mentation directe ont Ã©tÃ© regroupÃ©es dans les tableaux \ref{tab-convo-gene3reg8-2070} et \ref{tab-convo-gene3reg8-480} oÃ¹ l'on peut immÃ©diatement constater que la solution optimale Nvidia demeure plus rapide. 
+L'analyse plus dÃ©taillÃ©e nous apprend aussi que le modÃ¨le GTX280 exÃ©cute le kernel plus vite que le rÃ©cent C2070, en raison d'un plus grand nombre de registres disponibles. MalgrÃ© tout, lorsqu'on prend en compte les temps de transfert des donnÃ©es, l'avantage va au C2070 qui rÃ©alise ce traitement Ã  875~MP/s.
 
 \begin{table}
 \centering
@@ -82,19 +86,17 @@ Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times
 \label{tab-convo-gene3reg8-480}
 \end{table}
 
-\section{ImplÃ©mentation optimisÃ©e de la convolution non sÃ©parable}
+\section{ImplÃ©mentation optimisÃ©e de la convolution non sÃ©parable sur GPU}
 
-Les coefficients du masque de convolution sont indÃ©pendants et il est donc impossible, sauf cas particulier, de rÃ©duire le nombre de registres nÃ©cessaire. Pour cette mÃªme raison, multiplier le nombre de pixels traitÃ©s par chaque thread ne permet pas d'Ã©conomiser des registres au niveau bloc comme il a Ã©tÃ© possible de la faire pour les mÃ©dians. 
+Les coefficients du masque de convolution sont indÃ©pendants et il est donc impossible, sauf cas particulier, de rÃ©duire le nombre de registres nÃ©cessaires. Pour cette mÃªme raison, multiplier le nombre de pixels traitÃ©s par chaque thread, ne permet pas d'Ã©conomiser des registres au niveau bloc comme il a Ã©tÃ© possible de la faire pour les mÃ©dians. 
 
 De surcroÃ®t, autant il Ã©tait envisageable de concevoir un kernel par taille de masque lorsqu'il s'agissait de filtres mÃ©dians car ils ne comportent qu'un seul paramÃ¨tre, autant cela devient inconcevable pour les filtres de convolution et l'immense variÃ©tÃ© de paramÃ©trage qu'ils recouvrent. La contrainte de dÃ©finir les valeurs des coefficients du masque de maniÃ¨re littÃ©rale Ã  l'intÃ©rieur du kernel doit donc Ãªtre levÃ©e pour permettre de rendre toute leur souplesse aux opÃ©rations de convolution.
 
-Parmi les types de mÃ©moire disponibles, nous avons optÃ© pour le stockage des coefficients du masque en mÃ©moire constante (\textit{symbol memory}) en raison de ses performances et du petit volume requis. L'abandon des registres permet aussi d'adopter un style de codage beaucoup plus conventionnel utilisant des structures de contrÃ´le classiques (itÃ©rations et tableaux). 
-
-L'augmentation du nombre de pixels traitÃ©s par chaque thread est alors de nouveau envisageable, puisque l'utilisation de la mÃ©moire constante pour les coefficients libÃ¨re autant de registres. Il faut cependant organiser les calculs de maniÃ¨re Ã  rÃ©duire autant que possible les accÃ¨s en lecture aux valeurs de l'image en texture ; en d'autres termes, on cherche Ã  exploiter le recouvrement entre positions voisines du masque de convolution et n'effectuer qu'une seule lecture par pixel de l'image pour en distribuer la valeur sur l'ensemble des calculs de convolutions en cours dans le thread. Cela complique quelque peu les expressions des sommes partielles mais rÃ©alise l'objectif opÃ©rationnel de la mÃ©moire partagÃ©e sans en subir le coÃ»t ni les contraintes d'accÃ¨s et permet ainsi d'envisager de meilleures performances.
+Parmi les types de mÃ©moires disponibles, nous avons optÃ© pour le stockage des coefficients du masque en mÃ©moire constante (\textit{symbol memory}) en raison de ses performances et du petit volume des donnÃ©es. L'abandon des registres permet aussi d'adopter un style de codage beaucoup plus conventionnel utilisant des structures de contrÃ´le classiques (itÃ©rations et tableaux). 
 
-Multiplier les pixels traitÃ©s par un mÃªme thread impose Ã©galement de faire un choix sur la forme de ce que l'on appellera un \textit{paquet} de pixels (centraux, par opposition aux pixels des voisinages, mÃªme si un pixel a successivement l'un et l'autre des statuts). La contrainte de contiguitÃ© des accÃ¨s en mÃ©moire globale pour la mÃ©morisation des valeurs de sortie font que seule l'organisation \textit{en ligne} des paquets de pixels est bÃ©nÃ©fique, bien que n'Ã©tant pas celle qui prÃ©sente systÃ©matiquement les recouvrements les plus importants. 
+L'augmentation du nombre de pixels traitÃ©s par chaque thread est alors de nouveau envisageable, puisque l'utilisation de la mÃ©moire constante pour les coefficients libÃ¨re autant de registres. Il faut cependant organiser les calculs de maniÃ¨re Ã  rÃ©duire autant que possible les accÃ¨s aux valeurs des pixels de l'image; en d'autres termes, on cherche Ã  exploiter le recouvrement entre positions voisines du masque de convolution et n'effectuer qu'une seule lecture par pixel de l'image pour en distribuer la valeur sur l'ensemble des calculs de convolutions en cours dans le thread. Cela complique quelque peu les expressions des sommes partielles mais rÃ©alise l'objectif opÃ©rationnel de la mÃ©moire partagÃ©e sans en subir le coÃ»t ni les contraintes d'accÃ¨s, et permet ainsi d'envisager de meilleures performances.
 
-Multiplier les pixels traitÃ©s par un mÃªme thread impose Ã©galement de faire un choix sur la forme de ce que l'on appellera un \textit{paquet} de pixels (centraux, par opposition aux pixels des voisinages, mÃªme si un pixel adopte successivement l'un et l'autre des statuts.
+Multiplier les pixels traitÃ©s par un mÃªme thread impose Ã©galement de faire un choix sur la forme de ce que l'on appellera un \textit{paquet} de pixels (centraux, par opposition aux pixels des voisinages, mÃªme si un pixel a successivement l'un et l'autre des statuts). La contrainte de contiguÃ¯tÃ© des accÃ¨s en mÃ©moire globale pour la mÃ©morisation des valeurs de sortie fait que seule l'organisation \og en ligne\fg{} des paquets de pixels est bÃ©nÃ©fique, bien que n'Ã©tant pas celle qui prÃ©sente systÃ©matiquement les recouvrements les plus importants. Par exemple, un paquet carrÃ© ou rectangulaire prÃ©sente plus de recouvrements qu'un paquet \og en ligne\fg{}. 
 
 \begin{figure}[ht]
   \centering
@@ -104,7 +106,7 @@ Multiplier les pixels traitÃ©s par un mÃªme thread impose Ã©galement de faire un
 \label{fig-convo-overlap}
 \end{figure}
 
-Une valeur de 8 pixels comme taille des paquets, dÃ©terminÃ©e expÃ©rimentalement, s'est avÃ©rÃ©e optimale sur les deux types d'architecture GPU et pour toutes les tailles de masques soumis au mesures. Cela signifie que chaque thread conduit simultanÃ©ment les calculs de convolution attachÃ©s Ã  chacun des  8 pixels du paquet qu'il traite. La somme partielle de chaque convolution est mÃ©morisÃ©e dans un registre. Sur cette base, on a schÃ©matisÃ© Ã  la figure \ref{fig-convo-overlap}, l'implication de chaque pixel de la zone d'intÃ©ret d'un thread dÃ©coulant du recouvrement des 8 positions du masque. Pour chaque pixel, cette implication est figurÃ©e par une valeur de \textit{multiplicitÃ©} reprÃ©sentant le nombre de convolutions diffÃ©rentes dans lesquelles il est impliquÃ© au sein d'un mÃªme thread. Tous les pixels d'une colonne partagent la mÃªme multiplicitÃ© et chaque pixel Ã©tant au moins impliquÃ© dans un des 8 calculs, les valeurs de cette multiplicitÃ© varient de 1 Ã  k, si k est le \textit{rayon} du masque tel que $n=2k+1$.
+La valeur de 8 pixels comme taille de paquet, dÃ©terminÃ©e expÃ©rimentalement, s'est avÃ©rÃ©e optimale sur les deux types d'architecture GPU et pour toutes les tailles de masques soumis aux mesures. Cela signifie que chaque thread conduit simultanÃ©ment les calculs de convolution attachÃ©s Ã  chacun des  8 pixels du paquet qu'il traite. La somme partielle de chaque convolution est mÃ©morisÃ©e dans un registre. Sur cette base, on a schÃ©matisÃ© Ã  la figure \ref{fig-convo-overlap}, l'implication de chaque pixel de la zone d'intÃ©rÃªt d'un thread, dÃ©coulant du recouvrement des 8 positions du masque. Pour chaque pixel, cette implication est figurÃ©e par une valeur de \textit{multiplicitÃ©} reprÃ©sentant le nombre de convolutions diffÃ©rentes dans lesquelles il est impliquÃ© au sein d'un mÃªme thread. Tous les pixels d'une colonne partagent la mÃªme multiplicitÃ© et chaque pixel Ã©tant au moins impliquÃ© dans l'un des 8 calculs, les valeurs de cette multiplicitÃ© varient de 1 Ã  k, si k est le \textit{rayon} du masque tel que $n=2k+1$.
 
 On peut dÃ©nombrer globalement les multiplicitÃ©s comme suit :
 \begin{itemize}
@@ -113,8 +115,11 @@ On peut dÃ©nombrer globalement les multiplicitÃ©s comme suit :
 \item Les deux colonnes extÃ©rieures ont ainsi leurs pixels impliquÃ©s chacun dans un seul calcul de convolution.   
 \end{itemize}
 
-Le listing \ref{lst-convo-8x8pL3} prÃ©sente pour exemple, le code implÃ©mentant ces solutions pour les masques de taille 3$\times$3 et l'ensemble des mesures de performance associÃ©es, sur C2070,  est regroupÃ© dans le tableau \ref{tab-convo-8x8p}. Cette implÃ©mentation atteint des dÃ©bits supÃ©rieurs aux prÃ©cÃ©dentes, mais aussi et surtout surpasse la solution Nvidia avec une exÃ©cution du traitement de rÃ©fÃ©rence en 1.21~ms sur GTX280, soit une accÃ©lÃ©ration de plus de 14\%. Le gain au niveau du dÃ©bit reste modeste car les transferts reprÃ©sentent Ã  eux seuls plus de 72\% du temps total. Le modÃ¨le GTX280 traite ainsi 962~MP Ã  la seconde, soit un gain de seulement 1.7\% par rapport Ã  la solution de rÃ©fÃ©rence. 
-Sur C2070, grÃ¢ce Ã  une bande passante mÃ©moire supÃ©rieure, les dÃ©bits mesurÃ©s peuvent dÃ©passer les 2100~MP/s, pour une convolution 3$\times$3 sur une image de 4096$^2$ pixels. Le traitement de rÃ©fÃ©rence quant Ã  lui est effectuÃ© en 0.987~ms pour un dÃ©bit de 1666~MP/s. 
+Le listing \ref{lst-convo-8x8pL3} prÃ©sente, pour exemple, le code implÃ©mentant ces solutions pour les masques de taille 3$\times$3.
+On remarque qu'il n'y a que 30 accÃ¨s Ã  la texture, au lieu des $9\times 8=72$ sans optimisation, et que la sortie opÃ¨re sur 8 pixels consÃ©cutifs en mÃ©moire globale. On obtient ainsi une utilisation optimale de la mÃ©moire.
+L'ensemble des mesures de performance associÃ©es, sur C2070,  est regroupÃ© dans le tableau \ref{tab-convo-8x8p}. On observe que, grÃ¢ce Ã  une bande passante mÃ©moire supÃ©rieure, les dÃ©bits mesurÃ©s peuvent dÃ©passer les 2100~MP/s, pour une convolution 3$\times$3 sur une image de 4096$\times$4096 pixels. Le traitement de rÃ©fÃ©rence quant Ã  lui est effectuÃ© en 0.987~ms pour un dÃ©bit de 1666~MP/s. 
+
+Sur GTX280, cette implÃ©mentation atteint Ã©galement des dÃ©bits supÃ©rieurs aux prÃ©cÃ©dents, mais surtout, dÃ©trÃ´ne la solution Nvidia avec une exÃ©cution du traitement de rÃ©fÃ©rence en 1,21~ms, soit une accÃ©lÃ©ration de plus de 14\%. Le gain au niveau du dÃ©bit reste modeste car les transferts reprÃ©sentent Ã  eux seuls plus de 72\% du temps total. Le modÃ¨le GTX280 traite ainsi 962~MP Ã  la seconde, soit un gain de seulement 1.7\% par rapport Ã  la solution de rÃ©fÃ©rence.
 
 \begin{table}
 \centering
@@ -135,15 +140,16 @@ Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times
 \bottomrule
 \end{tabular}
 }  
-\caption{Performances des kernels effectuant la convolution non-sÃ©parable sur le modÃ¨le du listing \ref{lst-convo-8x8pL3}, sur GPU C2070. Le temps d'exÃ©cution correspond Ã  la seule exÃ©cution du kernel. Le dÃ©bit global intÃ¨gre les temps de transfert. Les valeurs en gras correspondent au traitement de rÃ©fÃ©rence }
+\caption{Performances des kernels effectuant la convolution non-sÃ©parable sur le modÃ¨le du listing \ref{lst-convo-8x8pL3}, sur GPU C2070. Le temps d'exÃ©cution correspond Ã  la seule exÃ©cution du kernel. Le dÃ©bit global intÃ¨gre les temps de transfert. Les valeurs en gras correspondent au traitement de rÃ©fÃ©rence. }
 \label{tab-convo-8x8p}
 \end{table}
 
+\pagebreak
 \lstinputlisting[label={lst-convo-8x8pL3},caption={Kernel rÃ©alisant la convolution par un masque 3$\times$3 dont les coefficients normalisÃ©s sont en mÃ©moire constante.}]{Chapters/chapter6/code/convoGene8x8pL3.cu}
 
 \section{Cas de la convolution sÃ©parable}
 
-Dans la pratique, les traitements appliquÃ©s aux images par des opÃ©rations de convolution Ã  deux dimensions reposent souvent sur des masques prÃ©sentant une ou plusieurs symÃ©tries. Lorsqu'un tel masque $h$ peut s'Ã©crire comme le produit de 2 vecteurs $h_v$ et $h_h$, comme dans l'exemple ci-dessous, alors on dit que la convolution 2D est sÃ©parable et peut donc Ãªtre effectuÃ©e en deux opÃ©rations de convolution 1D de masques respectifs $h_v$ et $h_h$.
+Dans la pratique, les traitements appliquÃ©s aux images par des opÃ©rations de convolution Ã  deux dimensions reposent souvent sur des masques prÃ©sentant une ou plusieurs symÃ©tries. On rappelle que lorsqu'un tel masque $h$ peut s'Ã©crire comme le produit de 2 vecteurs $h_v$ et $h_h$, comme dans l'exemple ci-dessous, alors on dit que la convolution 2D est sÃ©parable et peut donc Ãªtre effectuÃ©e en deux opÃ©rations de convolution 1D de masques respectifs $h_v$ et $h_h$.
 
 $$h = h_v \times h_h = \begin{bmatrix}1\\2\\1\end{bmatrix} \times \begin{bmatrix}-1&2&-1\end{bmatrix} = \begin{bmatrix}
 -1&2&-1\\
@@ -153,73 +159,154 @@ $$h = h_v \times h_h = \begin{bmatrix}1\\2\\1\end{bmatrix} \times \begin{bmatrix
 
 Une convolution sÃ©parable $n\times n$ est donc moins coÃ»teuse en nombre d'opÃ©rations arithmÃ©tiques, avec seulement $2n$ paires addition/multiplication par pixel contre $n^2$ pour une convolution non sÃ©parable. Cela reprÃ©sente un gain de 60\% du nombre d'opÃ©rations pour un masque 5$\times$5 et nous laisse entrevoir des performances supÃ©rieures Ã  celles de la convolution non sÃ©parable.
 
-Il faut cependant considÃ©rer qu'effectuer un traitement en 2 exÃ©cutions de kernel(s) consÃ©cutives implique de multiplier aussi les Ã©critures en mÃ©moire globale, ce qui a un coÃ»t. La plupart des implÃ©mentations sÃ©quentielles de la convolution sÃ©parable utilisent la mÃªme fonction pour rÃ©aliser les 2 passes, horizontale et verticale, la premiÃ¨re mÃ©morisant la transposÃ©e de l'image de sortie pour qu'elle soit traitÃ©e directement par la seconde passe. Sur GPU, cette solution se heurte aux contraintes de contiguÃ¯tÃ© dans les accÃ¨s Ã  la mÃ©moire globale, il faut donc prÃ©fÃ©rer deux kernels distincts : un pour la convolution verticale, l'autre par l'horizontale. La mÃ©morisation de l'image intermÃ©diaire est effectuÃ©e en mÃ©moire globale, qui est ensuite recopiÃ©e en texture. Nos mesures (tableau \ref{tab-convo-memcpy}) montrent que le coÃ»t de la copie en texture est largement compensÃ© par le gain apportÃ© par le cache 2D de la texture pour les lectures des valeurs des pixels.
+Il faut cependant considÃ©rer qu'effectuer un traitement en 2 kernels consÃ©cutifs implique de multiplier aussi les Ã©critures en mÃ©moire globale, ce qui a un coÃ»t. La plupart des implÃ©mentations sÃ©quentielles de la convolution sÃ©parable utilisent la mÃªme fonction pour rÃ©aliser les 2 passes horizontale et verticale, la premiÃ¨re mÃ©morisant la transposÃ©e de l'image de sortie pour qu'elle soit traitÃ©e directement par la seconde passe. Sur GPU, cette solution se heurte aux contraintes de contiguÃ¯tÃ© dans les accÃ¨s Ã  la mÃ©moire globale, il faut donc prÃ©fÃ©rer deux kernels distincts : un pour la convolution verticale, l'autre pour l'horizontale.
+ 
+Dans une convolution 1D verticale de masque $h_v$, il n'y a pas de recouvrement entre les diffÃ©rentes positions du masque associÃ©es aux pixels d'un paquet tel que nous le dÃ©finissons. Aucune optimisation de la distribution des donnÃ©es n'est donc possible de ce cÃ´tÃ© et il s'avÃ¨re mÃªme que l'utilisation de la mÃ©moire partagÃ©e est ici la solution la plus performante. La zone d'intÃ©rÃªt d'un bloc de threads ne s'Ã©tendant que vers le haut et le bas, on peut appliquer une version simplifiÃ©e du cadre gÃ©nÃ©ral d'emploi de la mÃ©moire partagÃ©e prÃ©sentÃ© au paragraphe \ref{sec-bilateral}. Remarquons Ã  ce sujet que tous les threads ne \og chargent\fg{} pas systÃ©matiquement le mÃªme nombre de pixels en mÃ©moire partagÃ©e, ce qui implique que certains threads doivent attendre avant de pouvoir entamer le calcul principal. Ceci impose l'emploi d'une barriÃ¨re de synchronisation entre ces deux phases. Le listing \ref{lst-convo-1Dv} dÃ©taille la mise en \oe uvre complÃ¨te de ce kernel, pour des paquets de 8 pixels, qui demeure la taille optimale dans le cas sÃ©parable. 
+Notons que ce type de kernel permet de travailler avec une taille de masque quelconque, passÃ©e en paramÃ¨tre. 
+ 
+\lstinputlisting[label={lst-convo-1Dv},caption={Kernel rÃ©alisant la convolution verticale k$\times$1 avec utilisation de la mÃ©moire partagÃ©e.}]{Chapters/chapter6/code/convoSepShV.cu}
+\lstinputlisting[label={lst-convo-1Dh},caption={Kernel rÃ©alisant la convolution horizontale 1$\times$k avec utilisation de la mÃ©moire partagÃ©e.}]{Chapters/chapter6/code/convoSepShH.cu}
 
-\begin{table}
+
+\begin{table}[h]
 \centering
-{\normalsize
-\begin{tabular}{cr}
+{\scriptsize
+\begin{tabular}{clrrrr}
 \toprule
-\textbf{Image}& Temps (ms)\\
+&&\multicolumn{4}{c}{Taille d'image}\\
+Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
+\midrule
+\multirow{2}*{3$\times$3}& temps exÃ©c. (ms)   & 0.056 & 0.192 & 0.719 & 2.796 \\
+                         & dÃ©bit calcul (MP/s)& 4681  & 5461  & 5834  & 6000  \\
+\midrule
+\multirow{2}*{5$\times$5}& temps exÃ©c. (ms)   & 0.060 & 0.213 & 0.794 & 3.073\\ 
+                         & dÃ©bit calcul (MP/s)& 4369  & 4923  & 5282  & 5460  \\
 \midrule
-$\mathbf{512\times 512}$  & 0.029\\
-$\mathbf{1024\times 1024}$& 0.101\\
-$\mathbf{2048\times 2048}$& 0.387\\
-$\mathbf{4096\times 4096}$& 1.533\\
+\multirow{2}*{7$\times$7}& temps exÃ©c. (ms)   & 0.064 & 0.225 & 0.886 & 3.490\\ 
+                         & dÃ©bit calcul (MP/s)& 4096  & 4660  & 4734  & 4807\\
 \bottomrule
 \end{tabular}
 }  
-\caption{CoÃ»t, en ms, de la copie effectuÃ©e entre les deux phases de convolution 1D, sur C2070.}
-\label{tab-convo-memcpy}
+\caption{Performances des kernels effectuant la convolution sÃ©parable sur le modÃ¨le des listings \ref{lst-convo-1Dv} et \ref{lst-convo-1Dh}, sur GPU C2070. Le temps d'exÃ©cution correspond Ã  l'exÃ©cution des 2 kernels. Cette variante prÃ©sente des performances voisines de la solution Nvidia.}
+\label{tab-convons-nv}
 \end{table}
 
-En revanche, les latences d'accÃ¨s aux textures ne sont plus compensÃ©es par les distributions des valeurs sur plusieurs des calculs menÃ©s par un thread pour un paquet de pixels. En effet, dans une convolution sÃ©parable, il n'y a pas de recouvrement entre les diffÃ©rentes positions du masque associÃ©es aux pixels d'un paquet. Aucun gain n'est donc possible de ce cÃ´tÃ© et il s'avÃ¨re mÃªme que l'utilisation de la mÃ©moire partagÃ©e est ici la solution la plus performante.
+Le cas de la convolution 1D horizontale est diffÃ©rent : il existe toujours des recouvrements entre les diffÃ©rentes positions du masque au sein d'un paquet de pixels. Il serait alors naturel de penser Ã  appliquer la technique que nous avons proposÃ©e pour la convolution non-sÃ©parable et qui consiste Ã  lire chaque donnÃ©e d'entrÃ©e une seule fois, puis de la distribuer Ã  tous les calculs auxquels elle participe. 
+Il faut cependant considÃ©rer que lire l'image intermÃ©diaire depuis la mÃ©moire texture impose de l'y copier prÃ©alablement, entre les deux opÃ©rations de convolution 1D, ce qui reprÃ©sente un coÃ»t en fonction de la taille d'image, dont le dÃ©tail est donnÃ© par la table \ref{tab-convons-memcpy}.
+
+La solution retenue pour maximiser les performances de cette passe horizontale est alors de lire les donnÃ©es d'entrÃ©e directement depuis la mÃ©moire globale, bÃ©nÃ©ficiant ainsi de son  cache 1D (sur C2070) tout en Ã©conomisant l'opÃ©ration de copie en texture. 
+L'exploitation des recouvrements intra-paquet peut Ãªtre faite de la mÃªme maniÃ¨re que pour la convolution non-sÃ©parable et cela conduit, pour la convolution horizontale 1$\times$3 au kernel du listing \ref{lst-convons-optim}.
+
+\lstinputlisting[label={lst-convons-optim},caption={Kernel rÃ©alisant la convolution horizontale optimisÃ©e 1$\times$3 sans utilisation de la mÃ©moire partagÃ©e.}]{Chapters/chapter6/code/convoSepoptimH.cu}
 
-Pour chacune des convolutions 1D, la zone d'intÃ©rÃªt d'un bloc de threads ne s'Ã©tend que dans une direction et l'on peut donc appliquer une version simplifiÃ©e du cadre gÃ©nÃ©ral d'emploi de la mÃ©moire partagÃ©e prÃ©sentÃ© au paragraphe \ref{sec-bilateral}. Les listings \ref{lst-convo-1Dv} et \ref{lst-convo-1Dh} dÃ©taillent la mise en \oe uvre complÃ¨te des kernels de convolutions verticale et horizontale, pour des paquets de 8 pixels, qui demeure la taille optimale dans le cas sÃ©parable. 
+Les performances globales de cette solution sont particuliÃ¨rement Ã©levÃ©es et surpassent assez nettement celles de la solution proposÃ©e par le constructeur qui met en \oe uvre deux kernels complÃ©mentaires semblables et faisant usage de la mÃ©moire partagÃ©e. Le premier ressemble Ã  celui du listing \ref{lst-convo-1Dv}, pour la convolution 1D verticale et le second Ã  celui du listing \ref{lst-convo-1Dh} pour la convolution 1D horizontale. Cette paire de kernels fournit une solution souple oÃ¹ la taille du masque est un paramÃ¨tre d'entrÃ©e, mais ses performances sont voisines de celles des kernels Nvidia dont on trouve le dÃ©tail dans la table \ref{tab-convons-nv}, qui prÃ©sente les temps d'exÃ©cution ainsi que les dÃ©bits correspondants (hors transferts).  La plus grande efficacitÃ© de la convolution sÃ©parable par rapport Ã  la non-sÃ©parable y est globalement confirmÃ©e par des temps d'exÃ©cution infÃ©rieurs , Ã  l'exception de la taille de masque 3$\times$3 oÃ¹ les coÃ»ts de l'Ã©criture intermÃ©diaire en mÃ©moire globale ne parviennent pas Ã  Ãªtre compensÃ©s par le plus petit nombre d'opÃ©rations arithmÃ©tiques. 
+Les dÃ©bits globaux de la table \ref{tab-convons-tpg} sont obtenus aprÃ¨s intÃ©gration des temps de transfert des donnÃ©es, dÃ©taillÃ©s dans la table \ref{tab-median-memcpy} et rappelÃ©s dans la table \ref{tab-convo-memcpy} pour des images 8 bits.
+
+Notre solution, dont les rÃ©sultats dÃ©taillÃ©s sont donnÃ©s en table \ref{tab-convons-optim}, prÃ©sente un dÃ©bit de calcul pouvant dÃ©passer les 7000~MP/s alors que ceux de Nvidia ne dÃ©passent jamais les 6000~MP/s, soit des accÃ©lerations de 17\% Ã  33\%. Ã cause de la prÃ©pondÃ©rance des transferts de donnÃ©es, les dÃ©bits globaux ne varient que trÃ¨s peu, avec des maxima de 2026~MP/s pour nos kernels et 1933~MP/s pour ceux de Nvidia. 
+
+\begin{table}[h]
+\renewcommand{\arraystretch}{1.5}
+\centering
+{\scriptsize
+\begin{tabular}{cc}
+\toprule
+ Image & \textbf{Total} (ms) \\
+\midrule
+{512$\times$512}  &{0.14} \\
+\midrule
+{1024$\times$1024}&{0.43} \\
+\midrule
+{2048$\times$2048}&{1.53} \\
+\midrule
+{4096$\times$4096}&{5.88} \\
+\bottomrule
+\end{tabular}}  
+\caption{Temps de transfert total depuis et vers le GPU, en fonction de la dimension de l'image. Extrait de la table \ref{tab-median-memcpy}.}
+\label{tab-convo-memcpy}
+\end{table}
+
+ \begin{table}[h]
+ \centering
+ {
+\scriptsize
+ \begin{tabular}{cr}
+ \toprule
+ Image&Temps (ms)\\
+ \midrule
+ 512$\times$512  &0.029\\
+ \midrule
+ 1024$\times$1024& 0.101\\
+ \midrule
+ 1024$\times$1024&0.387\\
+ \midrule
+ 1024$\times$1024& 1.533\\
+ \bottomrule
+ \end{tabular}
+ }  
+ \caption{DurÃ©e de la copie depuis la mÃ©moire globale vers la mÃ©moire texture, en fonction de la taille de l'image.}
+ \label{tab-convons-memcpy}
+ \end{table}  
  
-\lstinputlisting[label={lst-convo-1Dv},caption={Kernel rÃ©alisant la convolution verticale 3$\times$1.}]{Chapters/chapter6/code/convoSepShV.cu}
-\lstinputlisting[label={lst-convo-1Dh},caption={Kernel rÃ©alisant la convolution horizontale 1$\times$3.}]{Chapters/chapter6/code/convoSepShH.cu}
 
-Les temps d'exÃ©cution et dÃ©bits effectifs globaux de cette implÃ©mentation sont dÃ©taillÃ©s dans le tableau \ref{tab-convo-sep} jusqu'Ã  la taille 13$\times$13. Les temps d'excÃ©cution des deux kernels Ã©tant trÃ¨s voisins, le tableau prÃ©sente la somme des temps des deux et de la copie mÃ©moire afin de disposer d'une base de comparaison claire avec la convolution non sÃ©parable. 
-L'analyse des valeurs nous confirme que la complexitÃ© rÃ©duite de la convolution sÃ©parable permet une moindre dÃ©pendance Ã  la taille du masque. Elle confirme Ã©galement que le coÃ»t de la copie intÃ©rmÃ©diaire n'est pas amorti pour les petites tailles de masque et l'implÃ©mentation optimisÃ©e de la convolution non sÃ©parable demeure plus rapide que la sÃ©parable pour le tailles 3$\times$3 et 5$\times$5.
 
-\begin{table}
+
+\begin{table}[h]
 \centering
-{\normalsize
+{\scriptsize
 \begin{tabular}{clrrrr}
 \toprule
 &&\multicolumn{4}{c}{Taille d'image}\\
 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 \midrule
-\multirow{2}*{3$\times$3}& temps exÃ©c. (ms)   & 0.080 & 0.306 & 1.094 & 4.262 \\
-                         & dÃ©bit global (MP/s)& 1150  & 1415  & 1598  & 1654  \\
+\multirow{2}*{3$\times$3}& temps exÃ©c. (ms)   & 0.042 & 0.142 & 0.550 & 2.390 \\
+                         & dÃ©bit calcul (MP/s)& 6242  & 7384  & 7626  & 7020  \\
 \midrule
-\multirow{2}*{5$\times$5}& temps exÃ©c. (ms)   & 0.087 & 0.333 & 1.191 & 4.631\\ 
-                         & dÃ©bit global (MP/s)& 1116  & 1365  & 1541  & 1596  \\
+\multirow{2}*{5$\times$5}& temps exÃ©c. (ms)   & 0.046 & 0.160 & 0.604 & 2.578\\ 
+                         & dÃ©bit calcul (MP/s)& 5699  & 6554  & 6944  & 6508  \\
 \midrule
-\multirow{2}*{7$\times$7}& temps exÃ©c. (ms)   & 0.095 & 0.333 & 1.260 & 5.000\\ 
-                         & dÃ©bit global (MP/s)& 1079  & 1365  & 1503  & 1542\\
+\multirow{2}*{7$\times$7}& temps exÃ©c. (ms)   & 0.054 & 0.192 & 0.731 & 2.987\\ 
+                         & dÃ©bit calcul (MP/s)& 4855  & 5461  & 5738  & 5617\\
+\bottomrule
+\end{tabular}
+}  
+\caption{Performances des kernels effectuant la convolution sÃ©parable optimisÃ©e sur le modÃ¨le des listings \ref{lst-convo-1Dv} et \ref{lst-convons-optim}, sur GPU C2070. Le temps d'exÃ©cution correspond Ã  l'exÃ©cution des 2 kernels.}
+\label{tab-convons-optim}
+\end{table}
+
+\begin{table}[h]
+\centering
+{\scriptsize
+\begin{tabular}{crrrr}
+\toprule
+&\multicolumn{4}{c}{Taille d'image}\\
+Masque&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 \midrule
-\multirow{2}*{9$\times$9}& temps exÃ©c. (ms)   & 0.108 & 0.378 & 1.444 & 5.676\\ 
-                         & dÃ©bit global (MP/s)& 1024  & 1290  & 1410  & 1452\\
+{3$\times$3}& 1380  & 1817  & 2016  & 2028  \\
 \midrule
-\multirow{2}*{11$\times$11}& temps exÃ©c. (ms)   & 0.115 & 0.404 & 1.545 & 6.105\\ 
-                         & dÃ©bit global (MP/s)  & 997  & 1250  & 1364  & 1400\\
+{5$\times$5}& 1351  & 1762  & 1965  & 1983 \\ 
 \midrule
-\multirow{2}*{13$\times$13}& temps exÃ©c. (ms)   & 0.126 & 0.468 & 1.722 & 6.736\\ 
-                         & dÃ©bit global (MP/s)  & 957  & 1169  & 1290  & 1330\\
+{7$\times$7}& 1298  & 1672  & 1855  & 1892 \\ 
 \bottomrule
 \end{tabular}
 }  
-\caption{Performances des kernels effectuant la convolution sÃ©parable sur le modÃ¨le des listings \ref{lst-convo-1Dv} et \ref{lst-convo-1Dh}, sur GPU C2070. Le temps d'exÃ©cution correspond Ã  l'exÃ©cution des 2 kernels et de la copie intÃ©rmÃ©diaire. Le dÃ©bit global intÃ¨gre les temps de transfert.}
-\label{tab-convo-sep}
+\caption{DÃ©bit global en ms (incluant les transferts) des kernels effectuant la convolution sÃ©parable sur le modÃ¨le des listings \ref{lst-convo-1Dv} et \ref{lst-convons-optim}, sur GPU C2070.}
+\label{tab-convons-tpg}
 \end{table}
 
 \section{Conclusion}
 
-L'architecture des GPU et le modÃ¨le de programmation CUDA permettent d'implÃ©menter efficacement les opÃ©rations de convolution, sÃ©parable ou non sÃ©parable. 
-Nous avons transposÃ© les principes appliquÃ©s aux filtres mÃ©dians et montrÃ© qu'ils n'Ã©taient pas tous pertinents dans le cas de la convolution. Nous avons cependant proposÃ© des solutions adaptÃ©es qui ont permis d'atteindre des performances encore inÃ©galÃ©es sur GPU Nvidia avec jusqu'Ã  2138 millions de pixels traitÃ©s Ã  la seconde, transferts inclus.
-Les expÃ©rimentations conduites sur les kernels de convolution tendent Ã©galement Ã  confirmer dans un cadre plus large ce que les travaux sur les filtres mÃ©dians avaient fait apparaÃ®tre : l'usage de la mÃ©moire partagÃ©e ne reprÃ©sente souvent pas la solution apportant les meilleure performances. Cela peut cependant Ãªtre les cas, en particulier lorsque les voisinages des pixels d'un mÃªme paquet ne se recouvrent pas, rendant sans objet toute optimisation liÃ©e Ã  ces recouvrements, comme la distribution des valeurs sur les calculs multiples.
+L'architecture des GPUs et le modÃ¨le de programmation CUDA permettent d'implÃ©menter efficacement les opÃ©rations de convolution, sÃ©parable ou non. 
+Nous avons transposÃ© les principes appliquÃ©s aux filtres mÃ©dians et montrÃ© qu'ils n'Ã©taient pas tous pertinents dans le cas de la convolution. Nous avons malgrÃ© cela proposÃ© des solutions adaptÃ©es qui ont permis d'atteindre des performances encore inÃ©galÃ©es sur GPU Nvidia avec jusqu'Ã  2138 millions de pixels traitÃ©s Ã  la seconde, transferts inclus.
+Les expÃ©rimentations conduites sur les kernels de convolution tendent Ã©galement Ã  confirmer, dans un cadre plus large, ce que les travaux sur les filtres mÃ©dians avaient fait apparaÃ®tre : l'usage de la mÃ©moire partagÃ©e ne reprÃ©sente pas forcÃ©ment la solution apportant les meilleures performances. Cela peut cependant Ãªtre le cas, en particulier lorsque les voisinages des pixels d'un mÃªme paquet ne se recouvrent pas, rendant sans objet toute optimisation liÃ©e Ã  ces recouvrements.
+
+Conscients du manque de souplesse dÃ©coulant de l'optimisation de ces kernels et pour que cela ne soit pas un frein Ã  l'utilisation de ces solutions, nous avons enfin proposÃ© une application en ligne qui gÃ©nÃ¨re, Ã  la demande, les codes des kernels mÃ©dians et de convolution d'aprÃ¨s les critÃ¨res indiquÃ©s par l'utilisateur. Ce dernier peut alors tÃ©lÃ©charger un ensemble suffisant et immÃ©diatement fonctionnel comprenant un fichier kernel GPU, un fichier main.c, un Makefile et une image de test. Il est accessible Ã  l'adresse http://info.iut-bm.univ-fcomte.fr/staff/perrot/convomed et ses pages d'accueil et de tÃ©lÃ©chargement sont reproduites Ã  la figure \ref{fig-convomed-copie}.
+\begin{figure}[h]
+\centering
+  \subfigure[SÃ©lection des paramÃ¨tres.]{\includegraphics[width=10cm]{Chapters/chapter6/img/convomed1.png}}\\
+  \subfigure[TÃ©lÃ©chargement des fichiers.]{\includegraphics[width=10cm]{Chapters/chapter6/img/convomed2.png}}
+  \caption{GÃ©nÃ©rateur de codes sources pour les filtres GPU rapides.}
+ \label{fig-convomed-copie}
+\end{figure}
+
 
-Conscients du manque de souplesse dÃ©coulant de l'optimisation de ces kernels et pour que cela ne soit pas un frein Ã  l'utilisation de ces solutions, nous avons enfin proposÃ© une application en ligne qui gÃ©nÃ¨re Ã  la demande les codes des kernels mÃ©dians et de convolution d'aprÃ¨s les critÃ¨res indiquÃ©s par l'utilisateur, qui peut alors tÃ©lÃ©charger un ensemble suffisant et immÃ©diatement fonctionnel comprenant un fichier kernel GPU, un fichier main.c, un Makefile et une image de test. Il est accessible Ã  l'adresse http://info.iut-bm.univ-fcomte.fr/staff/perrot/convomed.
  
\ No newline at end of file
