2 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.
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.
5 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.
7 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.
8 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.
10 \section{Implémentation générique de la convolution non séparable}
12 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 :
14 \item Si $S_h > 0$ alors $I' = I_{\Omega}/S_h$
15 \item Si $S_h = 0$ alors $I' = I_{\Omega} + 128$
16 \item Si $S_h < 0$ alors $I' = I_{\Omega} + 255$
21 \caption{Convolution générique sur GPU}
22 \label{algo-convo-gene}
23 \ForEach(\tcc*[f]{\textbf{en parallèle}}){pixel $(x, y)$}{
24 Lire les niveaux de gris $I(x, y)$ des voisins sur $\Omega$ \;
25 Calculer la somme \( I_\Omega(x, y) = \sum_{(j,i) \in \Omega}I(x-j, y-j).h(j,i) \) \;
26 Normaliser $I_{\Omega}(x, y)$ pour obtenir $I'(x, y)$ \;
27 Mémoriser $I'(x, y)$ \;
31 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.
32 Par ailleurs, pour des raisons de lisibilité de ce premier code, chaque thread ne traite ici qu'un seul pixel.
34 \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}
36 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.
37 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.
42 \begin{tabular}{clrrrr}
44 &&\multicolumn{4}{c}{Taille d'image}\\
45 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
47 \multirow{2}*{3$\times$3}& temps exéc. (ms) & 0.077 & 0.297 & 1.178 & 4.700 \\
48 & débit global (MP/s)& 1165 & 1432 & 1549 & 1585 \\
50 \multirow{2}*{5$\times$5}& temps exéc. (ms) & 0.209 & 0.820 & {\bf 3.265} & 13.050\\
51 & débit global (MP/s)& 559 & 836 & {\bf 875} & 533 \\
53 \multirow{2}*{7$\times$7}& temps exéc. (ms) & 0.407 & 1.603 & 6.398 & 25.560\\
54 & débit global (MP/s)& 472 & 515 & 529 & 533 \\
58 \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.}
59 \label{tab-convo-gene3reg8-2070}
65 \begin{tabular}{clrrrr}
67 &&\multicolumn{4}{c}{Taille d'image}\\
68 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
70 \multirow{2}*{3$\times$3}& temps exéc. (ms) & 0.060 & 0.209 & 0.801 & 3.171 \\
71 & débit global (MP/s)& 1186 & 1407 & 1092 & 1075 \\
73 \multirow{2}*{5$\times$5}& temps exéc. (ms) & 0.148 & 0.556 & {\bf 2.189} & 8.7200\\
74 & débit global (MP/s)& 848 & 960 & {\bf 802} & 793 \\
76 \multirow{2}*{7$\times$7}& temps exéc. (ms) & 0.280 & 1.080 & 4.278 & 17.076\\
77 & débit global (MP/s)& 594 & 649 & 573 & 569 \\
81 \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.}
82 \label{tab-convo-gene3reg8-480}
85 \section{Implémentation optimisée de la convolution non séparable}
87 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.
89 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.
91 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).
93 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.
95 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.
97 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.
101 \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
102 \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}}
103 \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)$}
104 \label{fig-convo-overlap}
107 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$.
109 On peut dénombrer globalement les multiplicités comme suit :
111 \item les $(8-2k)$ colonnes centrales de la zone d'intéret, soient $(8-2k)(2k+1)$ pixels sont impliqués dans $k$ calculs.
112 \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.
113 \item Les deux colonnes extérieures ont ainsi leurs pixels impliqués chacun dans un seul calcul de convolution.
116 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.
117 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.
122 \begin{tabular}{clrrrr}
124 &&\multicolumn{4}{c}{Taille d'image}\\
125 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
127 \multirow{2}*{3$\times$3}& temps exéc. (ms) & 0.036 & 0.128 & 0.495 & 1.964 \\
128 & débit global (MP/s)& 1425 & 1862 & 2071 & 2138 \\
130 \multirow{2}*{5$\times$5}& temps exéc. (ms) & 0.069 & 0.253 & {\bf 0.987} & 3.926\\
131 & débit global (MP/s)& 1208 & 1524 & {\bf 1666} & 1711 \\
133 \multirow{2}*{7$\times$7}& temps exéc. (ms) & 0.110 & 0.413 & 1.615 & 6.416\\
134 & débit global (MP/s)& 1016 & 1237 & 1334 & 1364\\
138 \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 }
139 \label{tab-convo-8x8p}
142 \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}
144 \section{Cas de la convolution séparable}
146 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$.
148 $$h = h_v \times h_h = \begin{bmatrix}1\\2\\1\end{bmatrix} \times \begin{bmatrix}-1&2&-1\end{bmatrix} = \begin{bmatrix}
154 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.
156 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.
163 \textbf{Image}& Temps (ms)\\
165 $\mathbf{512\times 512}$ & 0.029\\
166 $\mathbf{1024\times 1024}$& 0.101\\
167 $\mathbf{2048\times 2048}$& 0.387\\
168 $\mathbf{4096\times 4096}$& 1.533\\
172 \caption{Coût, en ms, de la copie effectuée entre les deux phases de convolution 1D, sur C2070.}
173 \label{tab-convo-memcpy}
176 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.
178 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.
180 \lstinputlisting[label={lst-convo-1Dv},caption={Kernel réalisant la convolution verticale 3$\times$1.}]{Chapters/chapter6/code/convoSepShV.cu}
181 \lstinputlisting[label={lst-convo-1Dh},caption={Kernel réalisant la convolution horizontale 1$\times$3.}]{Chapters/chapter6/code/convoSepShH.cu}
183 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.
184 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.
189 \begin{tabular}{clrrrr}
191 &&\multicolumn{4}{c}{Taille d'image}\\
192 Masque&&$\mathbf{512\times 512}$&$\mathbf{1024\times 1024}$&$\mathbf{2048\times 2048}$&$\mathbf{4096\times 4096}$\\
194 \multirow{2}*{3$\times$3}& temps exéc. (ms) & 0.080 & 0.306 & 1.094 & 4.262 \\
195 & débit global (MP/s)& 1150 & 1415 & 1598 & 1654 \\
197 \multirow{2}*{5$\times$5}& temps exéc. (ms) & 0.087 & 0.333 & 1.191 & 4.631\\
198 & débit global (MP/s)& 1116 & 1365 & 1541 & 1596 \\
200 \multirow{2}*{7$\times$7}& temps exéc. (ms) & 0.095 & 0.333 & 1.260 & 5.000\\
201 & débit global (MP/s)& 1079 & 1365 & 1503 & 1542\\
203 \multirow{2}*{9$\times$9}& temps exéc. (ms) & 0.108 & 0.378 & 1.444 & 5.676\\
204 & débit global (MP/s)& 1024 & 1290 & 1410 & 1452\\
206 \multirow{2}*{11$\times$11}& temps exéc. (ms) & 0.115 & 0.404 & 1.545 & 6.105\\
207 & débit global (MP/s) & 997 & 1250 & 1364 & 1400\\
209 \multirow{2}*{13$\times$13}& temps exéc. (ms) & 0.126 & 0.468 & 1.722 & 6.736\\
210 & débit global (MP/s) & 957 & 1169 & 1290 & 1330\\
214 \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.}
215 \label{tab-convo-sep}
220 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.
221 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.
222 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.
224 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.
