7 avril pour jury

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

diff --git a/THESE/Chapters/chapter6/chapter6.tex b/THESE/Chapters/chapter6/chapter6.tex
index 2f9790ff4c1f368663797dd8ff604d7de1fff1fb..12badec3c7f35a34207229004c47e483088b794f 100644 (file)
--- a/THESE/Chapters/chapter6/chapter6.tex
+++ b/THESE/Chapters/chapter6/chapter6.tex
@@ -2,18 +2,20 @@
 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.
 
 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 principe et 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. 
+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. 

 
 

-Nous faisons l'hypothèse que les fonctions de convolution sont à support carré de taille de coté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. 
+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. 

 
 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.
 
 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. 
+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 :
 
 \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}
 \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}
 \item Si $S_h = 0$ alors $I' = I_{\Omega} + 128$
 \item Si $S_h < 0$ alors $I' = I_{\Omega} + 255$
 \end{enumerate}


@@ -35,7 +37,7 @@ Par ailleurs, pour des raisons de lisibilité de ce premier code, chaque thread
 
 \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}
 
 
 \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. 
+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}
 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}


@@ -94,7 +96,7 @@ Parmi les types de mémoires disponibles, nous avons opté pour le stockage des
 
 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.
 
 
 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 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 \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. 
+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
 
 \begin{figure}[ht]
   \centering


@@ -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}
 
 \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
 
 \begin{table}
 \centering


@@ -139,6 +144,7 @@ Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times
 \label{tab-convo-8x8p}
 \end{table}
 
 \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}
 \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}


@@ -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.
 
 
 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 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 par l'horizontale. L'image intermédiaire est mémorisée en mémoire globale, puis 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
 \centering

-{\normalsize
-\begin{tabular}{cr}
+{\scriptsize
+\begin{tabular}{clrrrr}

 \toprule
 \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
 \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}*{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
+\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}
 }  
 \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}
 
 \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}
+
+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.

 
 

-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. 
+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'exécution des deux kernels étant très voisins, le tableau présente la somme des temps d'exécution des deux kernels ajouté au temps de la copie mémoire : on dispose ainsi 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 que l'implémentation optimisée de la convolution non séparable demeure plus rapide que la séparable pour les tailles 3$\times$3 et 5$\times$5.

 
 

-\begin{table}
+
+\begin{table}[h]

 \centering
 \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
 \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
 \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
 \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
 \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
 \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
 \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}
 }  
 \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 intermé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}
 
 \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. 
+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.
 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 souvent pas 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.
+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
  
\ No newline at end of file