THESE/Chapters/chapter6/chapter6.tex

   1 \section{Introduction}
   2 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.
   3 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.
   4
   5 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.
   6
   7 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.
   8
   9 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.
  10 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.
  11
  12 \section{Implémentation générique de la convolution non séparable sur GPU}
  13
  14 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 :
  15 Si $S_h > 0$ alors $I' = I_{\Omega}/S_h$
  16
  17 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 :
  18 \begin{enumerate}
  19 \item Si $S_h = 0$ alors $I' = I_{\Omega} + 128$
  20 \item Si $S_h < 0$ alors $I' = I_{\Omega} + 255$
  21 \end{enumerate}
  22
  23
  24 \begin{algorithm}
  25 \caption{Convolution générique sur GPU}
  26 \label{algo-convo-gene}
  27   \ForEach(\tcc*[f]{\textbf{en parallèle}}){pixel $(x, y)$}{
  28     Lire les niveaux de gris $I(x, y)$ des voisins sur $\Omega$ \;
  29     Calculer la somme \( I_\Omega(x, y) = \sum_{(j,i) \in \Omega}I(x-j, y-j).h(j,i) \) \;
  30     Normaliser $I_{\Omega}(x, y)$ pour obtenir $I'(x, y)$ \;
  31     Mémoriser $I'(x, y)$ \;
  32   }
  33 \end{algorithm}
  34
  35 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.
  36 Par ailleurs, pour des raisons de lisibilité de ce premier code, chaque thread ne traite ici qu'un seul pixel.
  37
  38 \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}
  39
  40 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.
  41 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.
  42
  43 \begin{table}
  44 \centering
  45 {\normalsize
  46 \begin{tabular}{clrrrr}
  47 \toprule
  48 &&\multicolumn{4}{c}{Taille d'image}\\
  49 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
  50 \midrule
  51 \multirow{2}*{3$\times$3}& temps exéc. (ms)   & 0.077 & 0.297 & 1.178 & 4.700 \\
  52                          & débit global (MP/s)& 1165  & 1432  & 1549  & 1585  \\
  53 \midrule
  54 \multirow{2}*{5$\times$5}& temps exéc. (ms)   & 0.209 & 0.820 & {\bf 3.265} & 13.050\\
  55                          & débit global (MP/s)& 559   & 836   & {\bf 875}   & 533   \\
  56 \midrule
  57 \multirow{2}*{7$\times$7}& temps exéc. (ms)   & 0.407 & 1.603 & 6.398 & 25.560\\
  58                          & débit global (MP/s)& 472   & 515   & 529   & 533 \\
  59 \bottomrule
  60 \end{tabular}
  61 }
  62 \caption{Performances des kernels effectuant la convolution non-séparable sur le modèle du listing \ref{lst-convo-gene3reg8}, 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.}
  63 \label{tab-convo-gene3reg8-2070}
  64 \end{table}
  65
  66 \begin{table}
  67 \centering
  68 {\normalsize
  69 \begin{tabular}{clrrrr}
  70 \toprule
  71 &&\multicolumn{4}{c}{Taille d'image}\\
  72 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
  73 \midrule
  74 \multirow{2}*{3$\times$3}& temps exéc. (ms)   & 0.060 & 0.209 & 0.801 & 3.171 \\
  75                          & débit global (MP/s)& 1186  & 1407  & 1092  & 1075  \\
  76 \midrule
  77 \multirow{2}*{5$\times$5}& temps exéc. (ms)   & 0.148 & 0.556 & {\bf 2.189} & 8.7200\\
  78                          & débit global (MP/s)& 848   & 960   & {\bf 802}   & 793   \\
  79 \midrule
  80 \multirow{2}*{7$\times$7}& temps exéc. (ms)   & 0.280 & 1.080 & 4.278 & 17.076\\
  81                          & débit global (MP/s)& 594   & 649   & 573   & 569 \\
  82 \bottomrule
  83 \end{tabular}
  84 }
  85 \caption{Performances des kernels effectuant la convolution non-séparable sur le modèle du listing \ref{lst-convo-gene3reg8}, sur GPU GTX280. 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.}
  86 \label{tab-convo-gene3reg8-480}
  87 \end{table}
  88
  89 \section{Implémentation optimisée de la convolution non séparable sur GPU}
  90
  91 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.
  92
  93 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.
  94
  95 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).
  96
  97 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.
  98
  99 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{}.
 100
 101 \begin{figure}[ht]
 102   \centering
 103   \subfigure[Cas d'un masque de taille 3$\times$3 ($k=1$) où l'on dénombre 6 colonnes centrales, soit 18 pixels de multiplicité maximale 3.]{\includegraphics[width=0.4\linewidth]{Chapters/chapter6/img/convoOverlap1.png}}\quad
 104 \subfigure[Cas d'un masque de taille 5$\times$5 ($k=2$) où l'on dénombre 4 colonnes centrales, soit 20 pixels de multiplicité maximale 5.]{\includegraphics[width=0.5\linewidth]{Chapters/chapter6/img/convoOverlap2.png}}
 105 \caption{Multiplicité des implications des pixels de la zone d'intérêt d'un thread dans les calculs de convolution. Le nombre de calculs dans lequel est impliqué un pixel est inscrit en son centre. Le premier pixel du paquet, ou pixel de base, est repéré par ses coordonnées $(x, y)$ ; le dernier a pour coordonnées $(x+7,y)$}
 106 \label{fig-convo-overlap}
 107 \end{figure}
 108
 109 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$.
 110
 111 On peut dénombrer globalement les multiplicités comme suit :
 112 \begin{itemize}
 113 \item les $(8-2k)$ colonnes centrales de la zone d'intéret, soient $(8-2k)(2k+1)$ pixels sont impliqués dans $k$ calculs.
 114 \item les paires de colonnes symétriques par rapport au bloc des colonnes centrales précédentes ont leurs $2(2k+1)$ pixels impliqués dans $(k-1-e)$ calculs, si $e$ représente l'éloignement avec le bloc de colonnes centrales.
 115 \item Les deux colonnes extérieures ont ainsi leurs pixels impliqués chacun dans un seul calcul de convolution.
 116 \end{itemize}
 117
 118 Le listing \ref{lst-convo-8x8pL3} présente, pour exemple, le code implémentant ces solutions pour les masques de taille 3$\times$3.
 119 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.
 120 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.
 121
 122 Sur GTX280, cette implémentation atteint également des débits supérieurs aux précédents, mais surtout, surpasse 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.
 123
 124 \begin{table}
 125 \centering
 126 {\normalsize
 127 \begin{tabular}{clrrrr}
 128 \toprule
 129 &&\multicolumn{4}{c}{Taille d'image}\\
 130 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 131 \midrule
 132 \multirow{2}*{3$\times$3}& temps exéc. (ms)   & 0.036 & 0.128 & 0.495 & 1.964 \\
 133                          & débit global (MP/s)& 1425  & 1862  & 2071  & 2138  \\
 134 \midrule
 135 \multirow{2}*{5$\times$5}& temps exéc. (ms)   & 0.069 & 0.253 & {\bf 0.987} & 3.926\\
 136                          & débit global (MP/s)& 1208  & 1524  & {\bf 1666}  & 1711  \\
 137 \midrule
 138 \multirow{2}*{7$\times$7}& temps exéc. (ms)   & 0.110 & 0.413 & 1.615 & 6.416\\
 139                          & débit global (MP/s)& 1016  & 1237  & 1334  & 1364\\
 140 \bottomrule
 141 \end{tabular}
 142 }
 143 \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. }
 144 \label{tab-convo-8x8p}
 145 \end{table}
 146
 147 \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}
 148
 149 \section{Cas de la convolution séparable}
 150
 151 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$.
 152
 153 $$h = h_v \times h_h = \begin{bmatrix}1\\2\\1\end{bmatrix} \times \begin{bmatrix}-1&2&-1\end{bmatrix} = \begin{bmatrix}
 154 -1&2&-1\\
 155 -2&4&-2\\
 156 -1&2&-1
 157 \end{bmatrix}$$
 158
 159 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.
 160
 161 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.
 162
 163 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.
 164 Notons que ce type de kernel permet de travailler avec une taille de masque quelconque, passée en paramètre.
 165
 166 \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}
 167 \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}
 168
 169
 170 \begin{table}[h]
 171 \centering
 172 {\scriptsize
 173 \begin{tabular}{clrrrr}
 174 \toprule
 175 &&\multicolumn{4}{c}{Taille d'image}\\
 176 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 177 \midrule
 178 \multirow{2}*{3$\times$3}& temps exéc. (ms)   & 0.056 & 0.192 & 0.719 & 2.796 \\
 179                          & débit calcul (MP/s)& 4681  & 5461  & 5834  & 6000  \\
 180 \midrule
 181 \multirow{2}*{5$\times$5}& temps exéc. (ms)   & 0.060 & 0.213 & 0.794 & 3.073\\
 182                          & débit calcul (MP/s)& 4369  & 4923  & 5282  & 5460  \\
 183 \midrule
 184 \multirow{2}*{7$\times$7}& temps exéc. (ms)   & 0.064 & 0.225 & 0.886 & 3.490\\
 185                          & débit calcul (MP/s)& 4096  & 4660  & 4734  & 4807\\
 186 \bottomrule
 187 \end{tabular}
 188 }
 189 \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.}
 190 \label{tab-convons-nv}
 191 \end{table}
 192
 193 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.
 194 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}.
 195
 196 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.
 197 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}.
 198
 199 \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}
 200
 201 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.
 202 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.
 203
 204 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.
 205
 206 \begin{table}[h]
 207 \renewcommand{\arraystretch}{1.5}
 208 \centering
 209 {\scriptsize
 210 \begin{tabular}{cc}
 211 \toprule
 212  Image & \textbf{Total} (ms) \\
 213 \midrule
 214 {512$\times$512}  &{0.14} \\
 215 \midrule
 216 {1024$\times$1024}&{0.43} \\
 217 \midrule
 218 {2048$\times$2048}&{1.53} \\
 219 \midrule
 220 {4096$\times$4096}&{5.88} \\
 221 \bottomrule
 222 \end{tabular}}
 223 \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}.}
 224 \label{tab-convo-memcpy}
 225 \end{table}
 226
 227  \begin{table}[h]
 228  \centering
 229  {
 230 \scriptsize
 231  \begin{tabular}{cr}
 232  \toprule
 233  Image&Temps (ms)\\
 234  \midrule
 235  512$\times$512  &0.029\\
 236  \midrule
 237  1024$\times$1024& 0.101\\
 238  \midrule
 239  1024$\times$1024&0.387\\
 240  \midrule
 241  1024$\times$1024& 1.533\\
 242  \bottomrule
 243  \end{tabular}
 244  }
 245  \caption{Durée de la copie depuis la mémoire globale vers la mémoire texture, en fonction de la taille de l'image.}
 246  \label{tab-convons-memcpy}
 247  \end{table}
 248
 249
 250
 251
 252 \begin{table}[h]
 253 \centering
 254 {\scriptsize
 255 \begin{tabular}{clrrrr}
 256 \toprule
 257 &&\multicolumn{4}{c}{Taille d'image}\\
 258 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 259 \midrule
 260 \multirow{2}*{3$\times$3}& temps exéc. (ms)   & 0.042 & 0.142 & 0.550 & 2.390 \\
 261                          & débit calcul (MP/s)& 6242  & 7384  & 7626  & 7020  \\
 262 \midrule
 263 \multirow{2}*{5$\times$5}& temps exéc. (ms)   & 0.046 & 0.160 & 0.604 & 2.578\\
 264                          & débit calcul (MP/s)& 5699  & 6554  & 6944  & 6508  \\
 265 \midrule
 266 \multirow{2}*{7$\times$7}& temps exéc. (ms)   & 0.054 & 0.192 & 0.731 & 2.987\\
 267                          & débit calcul (MP/s)& 4855  & 5461  & 5738  & 5617\\
 268 \bottomrule
 269 \end{tabular}
 270 }
 271 \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.}
 272 \label{tab-convons-optim}
 273 \end{table}
 274
 275 \begin{table}[h]
 276 \centering
 277 {\scriptsize
 278 \begin{tabular}{crrrr}
 279 \toprule
 280 &\multicolumn{4}{c}{Taille d'image}\\
 281 Masque&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
 282 \midrule
 283 {3$\times$3}& 1380  & 1817  & 2016  & 2028  \\
 284 \midrule
 285 {5$\times$5}& 1351  & 1762  & 1965  & 1983 \\
 286 \midrule
 287 {7$\times$7}& 1298  & 1672  & 1855  & 1892 \\
 288 \bottomrule
 289 \end{tabular}
 290 }
 291 \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.}
 292 \label{tab-convons-tpg}
 293 \end{table}
 294
 295 \section{Conclusion}
 296
 297 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.
 298 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.
 299 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.
 300
 301 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}.
 302 \begin{figure}[h]
 303   \hfill
 304   \subfigure[Sélection des paramètres.]{\includegraphics[height=4cm]{Chapters/chapter6/img/convomed1.png}}\hfill
 305   \subfigure[Téléchargement des fichiers.]{\includegraphics[height=4cm]{Chapters/chapter6/img/convomed2.png}}\hfill
 306   \caption{Générateur de codes sources pour les filtres GPU rapides.}
 307  \label{fig-convomed-copie}
 308 \end{figure}
 309
 310
 311