+
+\section{Les implémentations GPU des techniques de segmentation}
+
+La problématique tant étudiée de la segmentation n'a pas échappé à l'engouement des chercheurs pour les processeurs graphiques modernes. Un certain nombre de travaux proposent ainsi des implémentations GPU plus ou moins directes de méthodes de segmentation tirant parti de l'architecture massivememnt parallèle de ces matériels.
+La majorité d'entre elles cherche à répondre à des besoins liés à l'imagerie médicale allant de la simple extraction des contours d'un organe, d'une tumeur, etc., à la mesure de leur volume ; le traitement en 3D n'étant dans ce cas pas un choix mais une obligation, justifiant d'autant plus l'emploi des GPU.
+ La natures des tissus et les formes à identifier sont extrêmement variées. Les images sont souvent très bruitées et les modèles de bruit divers selon l'instrumentation employée. Enfin, le diagnostique médical requerant la plus grande précision possible, aucune solution générique satisfaisante de segmentation n'a encore pu émerger dans ce cadre, laissant place à autant d'implémentations adaptées que de besoin médical spécifique.
+
+Beaucoup d'algorithmes récents destinés à la segmentation comportent plusieurs phases de calcul et mettent en \oe uvre différents algorithmes réalisant des fonctions élémentaires comme de la réduction de bruit ou du calcul d'histogramme.
+ Selon le type de traitement à effectuer sur le GPU, on peut-être amené à en concevoir des implémentations parallèles adaptées ou bien simplement exécuter indépendemment, pour chaque pixel par exemple, de multiples instances d'une version séquentielle classique du traitement.
+Dans les deux cas, on lira ``implémentation GPU'', mais cela recouvrira des réalités et parfois aussi des niveaux de performance très différents.
+
+\subsection{Calcul d'histogramme}
+Comme il a été dit au paragraphe \ref{sec-histo}, les segmentations par analyse d'histogramme sont aujourd'hui cantonnées à des applications très particulières et leurs implémentations GPU ne font pas l'objet de recherches, d'autant que dans la pratique, ces traitements sont souvent réalisés par des circuits spécialisés ou programmables de type FPGA et qu'il serait illusoire d'espérer les concurrencer par une solution de type gpu, plus coûteuse, plus volumineuse et vraisemblablement moins robuste.
+
+Le calcul d'histogramme est cependant utilisé de manière intensive dans certains algorithmes de haut-niveau, en particulier le \textit{level-set} et le \textit{gPb}. À ce titre, il faut citer les travaux de Fluck \textit{et al.} \cite{fluck2006gpu} qui apportent une réponse efficace au calcul d'histogramme sur le GPU leur permetttant de conserver les données dans la mémoire du processeur graphique tout au long de l'exécution de la segmentation par level-set qui leur a servi de motivation \cite{lefohn2003interactive}.
+
+Les résultats annoncés ont été obtenus sur un GPU GeForce 7900 et font état du calcul des deux histogrammes nécessaires ( 64 classes chacun) sur une image de 256$\times$256 pixels en niveau de gris en 1.6~ms.
+
+\subsection{Partitionnement de graphe}
+Le domaine du traitement des graphes est très actif et peut fournir des éléments pour la segmentation comme l'implémentation du \textit{minimum spanning tree} décrite dans \cite{Vineet:2009:FMS:1572769.1572796} qui annonce la construction du minimum spanning tree d'un graphe de 5 millions de n\oe uds et 30 millions de liens en moins d'une seconde.
+La parallèlisation GPU des opérations sur les graphes n'est pas simple en raison de l'indépendance des blocs de threads. Peu de travaux font encore état d'implémentations efficaces mettant en \oe uvre ces techniques.
+On ne recense que quelques propositions GPU de l'algorithme \textit{push-relabel} pour le partitionnement selon l'approche \textit{min cut/max flow} dont on ne retient que les trois remarquables détaillée ci-dessous.
+
+Dans \cite{dixit2005gpu} une approche assez directe est mise en \oe uvre et parvient à \textit{binariser} une image de 1~MP en 29~ms (GeForce 6800GT).
+
+Les auteurs de \cite{4563095} remarquent qu'après un nombre réduit d'itérations, très peu de n\oe ud se voient changer de segment. En conséquence, certains blocs de traitement sont activés alors qu'ils n'ont effectivement pas de traitement à effectuer et retardent ainsi les traitements éventuels des blocs en attente. Pour réduire les effet de ce comportement, un indicateur d'activité est calculé à chaque itération et pour chaque bloc, en se basant le nombre de changements de segment qui vient d'y être effectué. À l'itération suivante, seuls les blocs considérés comme \textit{probablement} actifs seront activés, réduisant ainsi la latence globale. Un reparamétrage dynamique du graphe après chaque itération est également éffectué selon la méthode décrite par Kohli et Torr \cite{kohli2007dynamic}. Ces optimisations permettent d'atteindre un débit d'environ 30 images de 0.3~MP par seconde sur GTX280, ce qui représente un bond en terme de performance.
+
+Enfin, Stitch a proposé dans \cite{graphcutscuda} des optimisations plus étroitement liées à l'architecture des GPUs Nvidia en faisant qu'un même thread mette à jour plusieurs liens du graphe et aussi en compactant la représentation des indicateurs de changement de segment par 32 par l'emploi d'un seul bit par lien. Cela a permis d'accélérer la convergence de l'algorithme, comme la montre la courbe de la figure \ref{fig-graphcutscuda} (tirée de \cite{graphcutscuda}), et d'atteindre les 70 images par seconde dans les même conditions que précédemment (sur C1060).
+Il faut noter aussi que sur C1060, l'implémentation décrite dans \cite{4563095} est moins performante, avec 17~fps, que sur la carte GTX280.
+
+\begin{figure}
+ \centering
+ \includegraphics[width=12cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/graphcutscuda_stitch.png}
+\caption{Évolution du nombre de pixels actifs pour les itération successives de l'implémentation de l'algorithme push-relabel de \cite{graphcutscuda}. Les petites images montrent la localisation des pixels actifs après chaque itération, en blanc.}
+\label{fig-graphcutscuda}
+\end{figure}
+
+\subsection{K-means, mean-shift et apparentés}
+La popularité de l'algorithme des \textit{k-means} a induit des tentatives de portage sur GPU dont \cite{che2008performance} qui a implémenté de manière directe l'etiquetage des éléments ainsi qu'une réduction partielle, par bloc, pour la mise à jour des centres ; la réduction finale étant réalisée par le CPU. Cette solution conduit à un transfert des données à chaque itération et ne permet pas d'atteindre des performances élevées. La mesure de performance a été faite avec la base de test KDD-Cup-99 \cite{kddcup99}, comportant 23 segments. Le temps annoncé pour l'exécution d'une seule itération sur un ensemble de 819200 éléments est de 200~ms. Toutefois, cette durée n'inclue pas la réduction ni les transferts et l'accélération revendiquée semble alors très discutable.
+
+Dans \cite{5170921}, l'ensemble des tâches d'étiquetage et de mise à jour des centres est réalisé sur le GPU. Une étape de réorganisation des données est encore exécutée sur le CPU, mais elle s'avère moins pénalisante que la solution présentée précédemment, puisqu'elle permet de présenter au GPU des données permettant d'optimiser l'exécution parallèle de l'étape de réduction suivante (mise à jour des centres). Les temps d'exécution par itération sont sensiblement les mêmes que pour \cite{che2008performance} mais ils incluent cette fois l'ensemble des calculs (hors transferts). Les auteurs fournissent cette fois des mesures des temps d'exécution à convergence, qui atteignent la vingtaine de secondes pour le même ensemble de test.
+
+La plus convaincante des implémentations de \textit{k-means} reste à notre connaissance celle décrite dans \cite{kmeansgpuopengl} et où la totalité du traitement est effectuée sur le GPU, moyennant l'emploi d'une texture par segment de données. Les mesures ont montré que cette multiplication du nombre des textures ne constituait pas un facteur de perte de performance, tout du moins jusqu'aux limites des tests, conduits avec un maximum de 32 segments dans des ensembles de 1 million d'éléments. Sur GPU GeForce 8500GT, les temps d'exécution obtenus dans ces conditions sont de 13.8~ms par itération, avec une dépendance très réduite vis à vis du nombre de segments.
+
+Des travaux à orientation non médicale mettent en \oe uvre sur GPU un algorithme de \textit{mean-shift} pour la poursuite de cibles dans des séquences vidéo \cite{li2009mean}. L'accélération otenue par rapport aux implémentations séquentielles existantes n'est que d'un facteur 2. La solution présentée effectue préalablement une réduction de l'espace colorimétrique via un regroupement par la méthode \textit{k-means}, utilisée dans une version séquentielle. Un gain potentiel de performance pourrait être apporté en employant une implémentation GPU du \textit{k-means}, mais serait toutefois limité en raison des itérations nécessaires plus nombreuses pour le traitement \textit{mean-shift}. Par ailleurs, l'implémentation proposée fait un usage intensif de la mémoire partagée et se heurte à sa limite de 16~Ko par bloc, obligeant à réduire la taille des blocs à l'exécution et avec eux, le parallélisme et vraisemblement aussi la performance de l'application. On peut malgré tout raisonnablement espérer qu'une telle solution présenterait des performances meilleures sur une carte de type Fermi possédant jusqu'à 48~Ko de mémoire partagée par bloc.
+
+\textit{Quick shift}, une approximation de l'algorithme mean-shift gaussien, c'est à dire utilisant des masques de pondération gaussiens, permettant d'obtenir un résultat en une seule passe (sans itérer) et proposée initiallement dans \cite{vedaldi2008quick} a été parallélisée sur GPU par ses auteurs et décrite dans \cite{fulkerson2012really}. La recherche de performance se traduit par des approximations, en particulier on restreint les calculs de pondération à des voisinages de rayon $3\sigma$ (écart type de la gaussienne définissant les coefficients du masque), considérant qu'au delà, les valeurs en sont négligeable.
+Ensuite on construit un arbre des liens entre les pixels, mais on limite la recherche à une distance maximale de $\sigma$. Par ailleurs, on diminue arbitrairement la dynamique de l'espace colométrique par 2. Enfin, la segmentation est obtenu par simple partionnnement de l'arbre selon un seuil $\tau$.
+Pour s'affranchir de la relative petite taille de la mémoire partagée sans devoir pâtir de la grande latence des accès à la mémoire globale de GPU, les auteurs ont ici choisi d'associer l'image et l'estimation de densité à des textures et ainsi bénéficier du mécanisme de cache.
+Les expérimentations ont été menées avec différentes valeurs de $\sigma$ et $tau$ choisies pour les résultats visuels qu'elles induisent et permettent de segmenter une image couleur de 1~MP en environ 1~s avec $\tau=10$ et $\sigma=6$. Toutefois, des valeurs plus petites, requérant moins de calculs, permettent des temps d'exécution beaucoup plus courts. Les courbes présentées permettent d'envisager, pour $\tau=4$ et $\sigma=2$, une réduction par 30, soit environ 33~ms. Une version améliorée récemment, dans laquelle les positions des centres sont stockées en registres, permet selon les auteurs, de diviser encore par 2 les temps d'exécution pour atteindre une segmentation en environ 16.5~ms.
+La figure \ref{fig-quickshift-yo}, tirée de \cite{fulkerson2012really}, présente quelques segmentations effectuées avec des valeurs différentes, permettant ainsi de juger des effets des variations des paramètres $\tau$ et $\sigma$.
+
+\begin{figure}
+ \centering
+\subfigure[Image originale]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-orig.png}}\quad
+\subfigure[$\tau=10$ et $\sigma=2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s2t10.png}}\quad
+\subfigure[$\tau=10$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t10.png}}\quad
+\subfigure[$\tau=20$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t20.png}}\quad
+\caption{Segmentation d'une image couleur de 512$\times$512 pixels par l'implémentation GPU quick-shift de \cite{fulkerson2012really}.}
+\label{fig-quickshift-yo}
+\end{figure}
+
+Récemment, Xiao et Liu ont décrit dans \cite{xiao2010efficient} une implémentation de l'algorithme \textit{mean-shift} qui utilise cette fois une construction de \textit{KD-tree} (arbre binaire à K dimensions) pour réduire l'espace colorimétrique et effectuer rapidement les recherches des plus proches voisins. L'ensemble s'exécute sur le GPU et permet ainsi d'obtenir des résultats beaucoup plus probants puisque les auteurs revendiquent une segmentation d'image couleur de 6.6 millions de pixels en 0.2 secondes. Malheureusement, il n'est pas dit combien de segments comprend l'image et il n'est fait référence qu'à une seule image, dont on déduit qu'il s'agit de l'image reproduite à la figure \ref{fig-meanshift-castle} afin de montrer les différences avec une implémentation standard du \textit{mean-shift}.
+
+\begin{figure}
+ \centering
+\subfigure[Image originale]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift.png}}\quad
+\subfigure[Image segmentée par mean-shift standard]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-std.png}}\quad
+\subfigure[Image segmentée par mean-shift kd-tree]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-kdtree.png}}
+\caption{Segmentation d'une image couleur de 2256$\times$3008 pixels.}
+\label{fig-meanshift-castle}
+\end{figure}
+
+\subsection{Snakes et Level set}
+Dès 2003, on recense d'importants travaux liés à l'imagerie médicale mettant en \oe uvre des algorithmes \textit{level set} sur GPU. C'est le cas de \cite{lefohn2003inter,lefohn2003interactive} où les auteurs décrivent une solution de visualisation des coupes d'une mesure volumique réalisés par résonnance magnétique (IRM) en exploitant pour la première fois le caractère creux du système d'équations à résoudre, \textit{i.e.} variante narrow-band, contrairement à la première solution 2D présentée dans \cite{rumpf2001level} qui implémente la version standard. En ne transférant au GPU, pour chaque itération, que les petits pavés de données actifs et en les rangeant alors de manière contigue en texture pour optimiser les accès en lecture, les auteurs sont ainsi parvenu à effectuer, pour des données volumiques de 256$\times$256$\times$175, entre 3.5 et 70 itérations par seconde, à comparer aux 50 itérations par seconde en 2D sur image de 128$^2$ pixels otenues dans \cite{rumpf2001level}. La limitation principale de cettesolution est celle des dimensions maximales admises pour une texture qui était de 2048$^2$ pour le GPU ATI Radeon 9800 pro employé (et programmé en openGL, car ni openCL ni CUDA n'étaient encore disponible à l'époque).
+Les autres solutions GPU proposées depuis sont également basées sur la variante \textit{narrow-band} (bande étroite) des \textit{level-set} \cite{lefohn2005streaming,cates2004gist,jeong2009scalable}, mais seule \cite{jeong2009scalable} s'affranchit des transferts CPU/GPU à chaque itération pour déterminer et transférer les pavés actifs. La solution retenue est d'employer les opérations atomiques pour assurer l'accès exclusif à la liste des pavés en mémoire GPU. Cela permet de descendre à 3~ms par itération pour une image de 512$^2$ pixels.
+
+La plus performante des implémentations à ce jour est celle décrite dans \cite{Roberts:2010:WGA:1921479.1921499} qui parvient à des itérations dont la durée varie, sur GTX280, de 1.8 à 6.5~ms pour des données volumiques de 256$^3$ pixels issues d'examen IRM, pour une moyenne de 3.2~ms sur les 2200 itérations de l'exemple fourni (cerveau en 7~s, Figure \ref{fig-l7-brain}). Une optimisation poussée y a été effectuée pour rendre l'algorithme efficace, en particulier au travers de la refonte du code responsable de la détermination des pavés actifs. Il parvient cette fois à déterminer l'ensemble minimal de pavés actifs et à rendre cette détermination efficace sur le GPU en gérant parallèlement plusieurs tampons, chacun associé à une direction particulière en 6-connexité. Une étape de résolution des doublons est ensuite effectuée avant de les compacter de manière contigue comme cela était déjà fait dans \cite{lefohn2003inter}.Tout cela est réalisé sans recourir à la mémoire partagée qui s'avère complexe voire impossile à utiliser efficacement lorsque les éléments à accéder sont très irrégulièrement répartis en mémoire.
+
+Ce faisant, le nombre cumulé total de pavés ainsi traités lors des 2200 itérations de la segmentation der l'image d'exemple s'élève à 294 millions à comparer aux 4877 millions traités par l'algorithme \textit{narrow-band} standard. Il est à noter que la durée d'exécution d'une itération dans cette variante dépend plus fortement de la proportion de pavés actifs que pour \textit{narrow-band} standard. Les deux courbes sont globalement affines et se croisent pour une proportion de pavés actifs proche de 10\%.
+Si l'on considère que malgré les stratégies adoptées, tenir à jour cette liste de pavés représente encore 77\% du temps de calcul, cela peut représenter une piste pour une optimisation supplémentaire qui ne semble pas su justifier avec l'image et l'initialisation dont les performances sont détaillées, mais qui pourrait l'être dans d'autres conditions, comme peut le suggérer le temps de segmentation de 16~s nécessaire pour l'image des reins (Figure \ref{fig-l7-reins}) et de l'aorte, aux dimensions comparables.
+
+\begin{figure}
+ \centering
+\subfigure[Cerveau 256$\times$256$\times$256 en 7~s]{\label{fig-l7-brain}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-brain7s.png}}\quad
+\subfigure[Reins et aorte, 256$\times$256$\times$272 en 16~s]{\label{fig-l7-reins}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-reins16s.png}}
+\caption{Segmentation d'images issues d'examens IRM par la méthode des level set à bande étroite.}
+\label{fig-l7-narrow}
+\end{figure}
+
+Les algorithmes de type \textit{snake}, très coûteux en temps de calcul, pouvaient prétendre à bénéficier largement de la technologie des GPU pour améliorer leurs performances, mais seule la variante paramétrique GVF à véritablement été implémentée de manière spécifique et efficace \cite{snakegvf06, bauer2009segmentation, li2011robust, snakegvfopencl12}. Les variantes de type géométrique, principalement en raison de l'irrégularité des motifs d'accès à la mémoire, restent à ce jour sans implémentation GPU.
+Parmi les premières solutions décrites, \cite{snakegvf06} propose une implémentation réalisée en openGL, où les données de gradient sont compactées en texture RVBA de manière à s'affranchir du format 16 bits de la représentation : les deux premiers canaux R et V contiennent les valeursreprésentant respectivement le gradients selon $dx$ et $dy$ sous une forme codée par la valeurs des 2 autres canaux.
+Par ailleurs, une approximation du système linéaire à résoudre est proposée afin de donner une structure bande symétrique à la matrice à inverser, ce qui améliore considérablement l'efficacité des accès aux données au travers du cache.
+
+\begin{figure}
+ \centering
+ \subfigure[Contour initial]{\label{fig-epaule-init}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-init.png}}\quad
+ \subfigure[Contour final]{\label{fig-epaule-fin}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-fin.png}}
+\caption{Segmentation d'une image d'épaule en 1024$^2$ pixels issue d'un examen IRM par l'implémentation du snake GVF de \cite{snakegvf06}. Le contour est représenté en rougeet le contour final est obtenu en 11~s. }
+\label{fig-snakegvf}
+\end{figure}
+
+Les performances annoncées montrent tout d'abord que l'approximation adoptée n'a qu'un impact extrêmement limité sur le résulat de la segmentation avec un écart radial maximal inférieur à 1.3 pixel par rapport au calcul exact effectué sur CPU. Enfin, la segmentation de l'image d'exemple en 1024$^2$ pixels s'effectue en un total de 11~s après l'initialisation manuelle reproduite à la figure \ref{fig-snakegvf}. Cela est annoncé comme presque 30 fois plus rapide que l'implémentation CPU de référence, mais demeure beaucoup trop lent pour un usage interactif.
+
+Une solution directe employant la transformée de fourier pour inverser le système à résoudre a été décrite récemment dans \cite{zheng2012fast}et programmée en employant la bibliothèque openGL. Les exemples fournis montrent des objets segmentés dans des images d'environ 10000 pixels en une durée de l'ordre de la demi seconde.
+
+En adaptant sur GPU une variante dite FD-snake \cite{li2011robust} du snake GVF (pour Fourier Descriptors) permettant une convergence plus rapide et un calcul parallèle beaucoup plus adapté au GPU, Li \textit{et al.} parviennent quant à eux à suivre les déformations d'un contour en temps réel dans des images issues d'examens échographique ; Un contour de 100 points pouvant converger convenablement en à peine 30~ms. Une contribution supplémentaire de cette implémentation est de permettre une initialisation simplifiée et semi-automatique du contour.
+
+La plus aboutie des implémentations actuelles du snake GVF est enfin celle présentée par Smistad \textit{et al.} dans \cite{snakegvfopencl12} et où les auteurs ont concentré leur effort sur l'optimisation des accès mémoire lors du calcul du GVF. Ils ont comparé 8 combinaisons possibles impliquant l'emploi des mémoires partagée et de texture ainsi que la représentation des nombres selon le format classique 32 bits ou selon un format compressé sur 16 bits. Il en ressort que l'association la plus performante est celle des textures et du format de données sur 16 bits.
+Les performances sont alors nettement en hausse avec des segmentations d'images médicales d'IRM de 512$^2$ pixels effectuées en 41~ms sur Nvidia C2070 et 28~ms sur ATI 5870 (512 itérations). L'implémentation réalisée en openGL permet d'exécuter le code sur les GPU des deux principaux fabricants.
+
+\subsection{Algorithmes hybrides}
+Le détecteur de contour \textit{gPb} décrit dans \cite{arbelaez2011contour} et que l'on considère comme la référence actuelle pour la semgentation d'objets et personnages dans des image naturelles, à été implémenté en CUDA par Catanzaro \textit{et al.} et est décrit dans \cite{5459410}. La qualité des contours extraits y est préservée et le temps de traitement y est réduit d'un facteur supérieur à 100 : les contours des images de 0.15~MP de la base de test BSDS \cite{martin2001database} sont ainsi traitées en 2 secondes environ sur GPU C1060.
+L'apport principal de ces travaux réside dans la solution conçue pour le calcul des histogrammes locaux, qui dans l'algorithme original s'étendaient sur des demi-disques centrés sur chaque pixel. La parallélisation réalisée fait l'approximation de chaque demi-disque en un rectangle de même surface dont un des grands cotés à le centre du disque pour milieu. Les rectangles sont ensuite pivotés par une rotation basée sur la discrétisation de Bresenham \cite{bresenham1965algorithm} pour en aligner les cotés avec les cotés de l'image et pouvoir employer la technique des images cumulées pour calculer rapidement l'histogramme.
+La figure \ref{fig-gPb} présente quelques résultats d'extraction de contours.
+\begin{figure}
+ \centering
+\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/gPb_examples.png}
+\caption{Extraction de contour par la version GPU de l'algorithme gPb. Les images sont issues de la base BSDS \cite{martin2001database}}
+\label{fig-gPb}
+\end{figure}
+
+\section{Conclusion}
+La présentation que nous venons de faire des principales techniques de filtrage et de ségmentation ainsi que des implémentations sur GPU qui leur ont été consacrées nous ont permis de mettre une évidence en lumière : malgré leur orientation grand public et les langages de huat niveau permettant d'accéder rapidement à la programmation GPU, la parallélisation efficace d'un algorithme séquentiel destiné à s'exécuter sur ces processeurs n'est pas triviale. Le modèle et les contraintes de programmation leur sont spécifiques et obtenir un code rapide découle nécessairement d'un compromis qui peut parfois être complexe à affiner.
+
+Ajoutons que les générations de GPU qui se succèdent conservent certes des caractéristiques communes mais diffèrent suffisemment quant-à la distribution des ressources, rendant toute généralité vaine et faisant qu'un code optimisé pour un modèle donné peut devenir moins rapide avec un modèle plus récent. Prenons l'exemple du nombre maximal de registres utilisables par thread ; il est de 128 sur GPU C1060 contre seulement de 63 pour un C2070. Un code faisant un usage optimisé des registres sur C1060 pourra s'exécuter plus lentement sur C2070. C'est un cas de figure sur lequel nous reviendrons plus en détail dans le chapitre consacré au filtre médian.
+
+Cet état de fait rend les résultats publiés par les chercheurs souvent délicats à intérpréter et plus encore à reproduire lorsque l'on souhaite comparer les performances de nos propres codes avec les références du moment, sauf à disposer d'un panel de cartes GPU représentant toutes les évolutions de l'architecture et ce pour au moins les deux grands fabricants de GPUs que sont ATI et Nvidia.
+
+Pour aider les développeurs à allouer les ressources de manière optimale, ou tout du moins estimer le dégré d'optimisation de leur code à l'aune de la vitesse d'exécution, Nvidia fournit une feuille de calcul appelée \textit{occupancy calculator} dans laquelle ont peut entrer les paramètres d'exécution d'un \textit{kernel} parallèle : nmobre de registres utilisés par chaque thread, quantité de mémoire partagée, modèle de GPU, dimensions de la grille. Le tableur retourne alors l'indice de charge (l'occupancy) qui traduit le rapport, à chaque instant, entre le nombre de warps actifs et le nombre maximal de warps par processeur (SM = Streaming Multiprocessor). L'occupancy se traduit donc par un indice compris entre 0 et 100\% et la recherche de performance semble devoir être la recherche de l'occupancy maximale.
+
+Toutefois, comme l'a clairement demontré Volkov dans \cite{volkov2010better}, ce paradigme peut aisément être remis en cause et Volkov parvient effectivement à améliorer les peformances d'un certain nombre d'exemples génériques dans des conditions de faible valeur d'occupancy.
+Enfin, nous avons pu constater deux grands modèles d'accès aux données : les algorithmes de filtrage usent quasiment tous de la mémoire partagée comme tampon d'accès aux données de l'image en mémoire globale (ou texture) alors que les algorithmes de segmentation performants s'en affranchissent. La raison en est clairement des motifs d'accès très irréguliers et non contigus pour ces derniers, rendant la gestion efficace de la mémoire partagée délicate et potentiellement si coûteuse qu'elle en devienne sans intérêt.
+Les chapitres suivants présentant nos contributions reviendront sur ces aspects en proposant des solutions pour accroître la performance des algorithmes parallélisés.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
