modif finale lnivs + keywords

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

diff --git a/THESE/Chapters/chapter6/chapter6.tex b/THESE/Chapters/chapter6/chapter6.tex
index c650ee42b7f0311a2266204549ac470588cc03e0..12badec3c7f35a34207229004c47e483088b794f 100644 (file)
--- a/THESE/Chapters/chapter6/chapter6.tex
+++ b/THESE/Chapters/chapter6/chapter6.tex
@@ -1,17 +1,21 @@
 \section{Introduction}
 \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 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 :
 
 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}


@@ -28,13 +32,13 @@ L'implémentation GPU de la  convolution non-séparable d'une fonction image $I$
   }
 \end{algorithm}
 
   }
 \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}
 
 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
 
 \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}
 
 \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.
 
 
 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
 
 \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}
 
 \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}
 
 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}
 
 \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


@@ -135,15 +140,16 @@ Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times
 \bottomrule
 \end{tabular}
 }  
 \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}
 
 \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}
 

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

 
 

-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
 \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 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}
 
 \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
  
\ No newline at end of file