<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\section{Pourquoi ?}
S'il fallait en rÃ©duire les raisons Ã&nbsp; une seule, c'est vraisemblablement la concurrence commerciale et la croissance du marchÃ© des jeux vidÃ©os qui a poussÃ© les fabricants de cartes graphiques Ã&nbsp; une innovation permanente qui a donnÃ©e naissance aux GPUs. 
Le rendu graphique dans ce cadre est une opÃ©ration exigeante en calcul mais intrinsÃ¨quement parallÃ¨le car chaque pixel y est traitÃ© individuellement. L'amÃ©lioration des rÃ©solutions a aussi contribuÃ© Ã&nbsp; faire Ã©voluer la nature de ces besoins de \textit{parallÃ¨le} Ã&nbsp; \textit{massivement parallÃ¨le}, un Ã©cran actuel pouvant comporter plus de  2,5 millions de pixels. 

La technologie de fabrication des GPUs Ã©tant identique Ã&nbsp; celle des CPUs, c'est donc au niveau de la rÃ©partition des fonctionnalitÃ©s que les GPUs se distinguent : lÃ&nbsp; oÃ¹ un CPU comporte quelques c\oe urs de calcul et beaucoup de transistors dÃ©diÃ©s Ã&nbsp; la rÃ©alisation de mÃ©moire cache et de contrÃ´le de flux, un GPU prÃ©sente plusieurs unitÃ©s comportant chacune une grande quantitÃ© de c\oe urs de calcul ne disposant que de trÃ¨s peu de mÃ©moire cache et des  capacitÃ©s de contrÃ´le rudimentaires, comme l'illustrent les schÃ©mas de la figure \ref{fig-gpucpu1}.

\begin{figure}[h]
  \centering
  \includegraphics[width=10cm]{Chapters/chapter1b/img/gpucpu1.png}
  \caption{Comparaison des structures d'un c\oe ur de GPU et d'un c\oe ur de CPU (d'aprÃ¨s \cite{CUDAPG}). ALU = Arithmetical \&amp; Logical Unit.}
  \label{fig-gpucpu1}
\end{figure}

Cette spÃ©cialisation des circuits GPU a permis d'en amÃ©liorer les performances brutes beaucoup plus rapidement que pour les CPUs, au fil des Ã©volutions de la technologie. Il en est allÃ© de mÃªme pour les dÃ©bits mÃ©moire thÃ©oriques. Les graphiques de la figure \ref{fig-gpucpu2} comparent les rythmes de ces Ã©volutions pour les GPUs Nvidia\textregistered~ et pour les CPUs Intel\textregistered.  

Les problÃ¨mes requÃ©rant les capacitÃ©s de calcul spÃ©cifiques des GPUs ne sont cependant pas limitÃ©s aux questions de rendu graphique, aussi les scientifiques ont-ils trÃ¨s vite cherchÃ© Ã&nbsp; tirer parti de la puissance de calcul croissante des GPUs pour traiter d'autres types de problÃ¨mes, faisant sens Ã&nbsp; l'acronyme GPGPU (General Purpose Graphical Processing Unit).

\begin{figure}[h]
  \centering
  \subfigure[Nombre maximum thÃ©orique d'opÃ©rations en virgule flottante par seconde en fonction de l'annÃ©e et de l'architecture.]{\includegraphics[width=9cm]{Chapters/chapter1b/img/gpucpu2a.png}}\\
  \subfigure[Bande passante thÃ©orique maximale des diverses architectures.]{\includegraphics[width=9cm]{Chapters/chapter1b/img/gpucpu2b.png}}
  \caption{Comparaison des performances des GPUs Nvidia et des CPU Intel (d'aprÃ¨s \cite{CUDAPG}).}
  \label{fig-gpucpu2}
\end{figure}

MalgrÃ© des caractÃ©ristiques prometteuses, les GPGPUs n'ont pas immÃ©diatement dÃ©clenchÃ© une vague d'expÃ©rimentations scientifiques dans des domaines variÃ©s, l'essentiel des travaux Ã©tant liÃ©s Ã&nbsp; la construction et la visualisation des donnÃ©es issues des instruments d'imagerie mÃ©dicale. 

C'est la parution de l'extension de langage CUDA qui a rÃ©ellement dÃ©mocratisÃ© l'emploi des GPGPUs et favorisÃ© l'Ã©mergence de travaux variÃ©s. CUDA est une extension de haut niveau du langage C permettant d'Ã©crire facilement des fonctions s'exÃ©cutant en parallÃ¨le sur le GPU, que Nvidia nomme \textit{kernels}. L'extension CUDA permet Ã©galement de gÃ©rer de maniÃ¨re transparente les changements d'Ã©chelle du parallÃ©lisme d'une architecture Ã&nbsp; une autre ou tout simplement les dimensions de la grille de calcul.

\section{Comment ?} 
\subsection{Le matÃ©riel}
Pour bien tirer parti des capacitÃ©s des GPUs, il est important d'en comprendre l'organisation matÃ©rielle. Nous limiterons cette prÃ©sentation Ã&nbsp; l'architecture dite \textit{Fermi} Ã&nbsp; laquelle appartient le GPU C2070 qui a servi Ã&nbsp; l'essentiel de nos expÃ©rimentations et dont la constitution  est dÃ©taillÃ©e par les diagrammes de la figure \ref{fig-c2070}.

Le circuit se divise en 4 groupes de processeurs de flux (les SMs = \textit{Streaming Multiprocessors}), chaque groupe en comprenant 3 ou 4 pour un total de 14.
Chaque SM hÃ©berge Ã&nbsp; son tour 32 c\oe urs de calcul (les SPs = \textit{Streaming Processors}).
Les threads sont exÃ©cutÃ©s par \textit{warps} de 2$\times$16, soit un par c\oe ur de calcul. 

\begin{figure}[h]
  \centering
  \subfigure[Organisation en groupes de SMs ]{\includegraphics[height=6cm]{Chapters/chapter1b/img/fermi.png}}\quad
  \subfigure[Constitution d'un SM.]{\includegraphics[height=6cm]{Chapters/chapter1b/img/fermi-sm.png}}
  \caption{Organisation des GPUs d'architecture Fermi, comme le C2070 (d'aprÃ¨s www.hpcresearch.nl).}
  \label{fig-c2070}
\end{figure}

Les ressources mÃ©moire sont de nature diverse, tant du point de vue du volume disponible, que de la portÃ©e ou du dÃ©bit. Retenons que les registres, peu nombreux et embarquÃ©s sur le circuit (\textit{on-chip}), prÃ©sentent les meilleures performances alors que la mÃ©moire principale, dite globale, externe au circuit (\textit{off-chip}) a une grande capacitÃ© mais prÃ©sente des latences importantes de plusieurs centaines de cycles d'horloge.
Le fabricant fournit des indications essentiellement qualitatives concernant les latences d'accÃ¨s aux mÃ©moires, mais ne fournit pas de chiffres sur les latences rÃ©elles en fonction des accÃ¨s et de la proximitÃ© du cache lorsqu'un des 3 niveaux est sollicitÃ©. Le tableau \ref{tab-gpu-memoire} prÃ©sente une synthÃ¨se des caractÃ©ristiques du modÃ¨le C2070, issue d'expÃ©rimentations menÃ©es par nos soins Ã&nbsp; l'aide des micro-tests prÃ©sentÃ©s dans  \cite{wong2010demystifying}.

Une petite quantitÃ© de mÃ©moire on-chip est prÃ©sente sur chaque SM et permet la communication entre les threads s'exÃ©cutant sur ce SM. Cette mÃ©moire est appelÃ©e \textit{mÃ©moire partagÃ©e} et permet des dÃ©bits bien supÃ©rieurs Ã&nbsp; la mÃ©moire globale.

\begin{table}[h]
  \centering
\begin{tabular}[htb]{lcccccc}
      \toprule
      &amp;\multicolumn{4}{c}{PropriÃ©tÃ©s}\\
              \cmidrule(r){2-6}
              &amp;Emplacement  &amp;PortÃ©e&amp;Latence &amp;dÃ©bit &amp;Taille  \\
              &amp;(on/off-chip)&amp;      &amp;(cycles)&amp;(Go/s)&amp;(octets)\\
              \cmidrule(r){2-6}
          Registres&amp;   on-chip   &amp;thread&amp;1         &amp;8000&amp; 32K par SM  \\
          PartagÃ©e &amp;   on-chip   &amp;bloc  &amp;38        &amp;1300&amp;  48K        \\
          \midrule
          Constante&amp;   off-chip  &amp;grille&amp;370/46/140 &amp;8000&amp; 64K        \\
          Texture  &amp;   off-chip  &amp;grille&amp;500/260/372&amp;N/C &amp; 6G         \\
          Locale   &amp;   off-chip  &amp;thread&amp;550        &amp;N/C &amp; 512K       \\
          Globale  &amp;   off-chip  &amp;grille&amp;580/80/350 &amp;144 &amp; 6G         \\
      \bottomrule
\end{tabular}
   \caption{CaractÃ©ristiques des diffÃ©rents types de mÃ©moire disponibles sur le GPU. Pour les mÃ©moires cachÃ©es, les latences sont donnÃ©es selon l'accÃ¨s \textit{sans-cache/L1/L2} et ont Ã©tÃ© obtenues Ã&nbsp; l'aide des microprogrammes de test de \cite{wong2010demystifying}. Les valeurs de dÃ©bit sont donnÃ©es par le constructeur.}
      \label{tab-gpu-memoire}
\end{table}

\subsection{Le logiciel}
Dans le modÃ¨le CUDA, chaque \textit{kernel} est exÃ©cutÃ© par un certain nombre de threads. Chaque thread possÃ¨de un identifiant unique, accessible Ã&nbsp; l'intÃ©rieur du kernel, ce qui permet d'en individualiser le traitement.
L'ensemble des threads est organisÃ© en plusieurs blocs indÃ©pendants, eux-mÃªme rassemblÃ©s en une grille. Pour faciliter la reprÃ©sentation de modÃ¨les variÃ©s, les blocs de threads ainsi que la grille de blocs peuvent Ãªtre dÃ©crits par des tableaux Ã&nbsp; une, deux ou trois dimensions.
Le nombre total de threads appartenant Ã&nbsp; un mÃªme bloc est cependant limitÃ©, selon la version de GPU, Ã&nbsp; 512 ou 1024. Le diagramme de la figure \ref{fig-threads} illustre l'organisation d'une grille de calcul Ã&nbsp; 2 dimensions et de ses blocs, Ã©galement Ã&nbsp; 2 dimensions, situation qui correspond Ã&nbsp; la majoritÃ© des modÃ¨les d'exÃ©cution de nos \textit{kernels} de traitement d'image. 

\begin{figure}[h]
  \centering
  \includegraphics[height=8cm]{Chapters/chapter1b/img/threads.png}
  \caption{ReprÃ©sentation d'une grille de calcul en 2D et des blocs de threads, Ã&nbsp; 2 dimensions, qui la composent.}
  \label{fig-threads}
\end{figure}

Au sein d'un mÃªme bloc, les threads peuvent communiquer efficacement entre eux grÃ¢ce Ã&nbsp; la mÃ©moire partagÃ©e, rapide et prÃ©sentant une faible latence.
En revanche, la communication inter-blocs passe nÃ©cessairement par la mÃ©moire globale dont l'emploi est pÃ©nalisant. 

L'emploi de la mÃ©moire partagÃ©e n'est cependant pas transparent comme peut l'Ãªtre un cache de niveau 1 (L1) et les motifs d'accÃ¨s doivent respecter un certain nombre de conditions pour obtenir les performances attendues. Le non-respect de ces contraintes conduit le plus souvent Ã&nbsp; des fragments de code dont l'exÃ©cution s'avÃ¨re plus lente que leurs Ã©quivalents CPU.

\subsection{L'occupancy}
Pour atteindre les meilleures performances possible, le fabricant Nvidia recommande d'avoir toujours suffisamment de threads dans chaque bloc et de blocs dans la grille et ce, pour masquer les latences des accÃ¨s aux mÃ©moires, mais aussi celles des instructions arithmÃ©tiques.
Il dÃ©finit un indice nommÃ© \textit{occupancy}, que l'on  pourrait franciser par \textit{charge} qui reprÃ©sente, Ã&nbsp; chaque instant, le rapport du nombre de threads actifs par SM sur le nombre maximum de threads actifs par SM (1536 sur C2070). 

La valeur de l'\textit{occupancy} peut se trouver limitÃ©e par un usage trop intensif des ressources mÃ©moire par les threads (registres, mÃ©moire partagÃ©e) ou bien par une grille de calcul mal dimensionnÃ©e. L'ensemble des paramÃ¨tres intervenant dans le calcul de l'\textit{occupancy} est pris en compte dans l'\textit{occupancy calculator}, feuille de calcul fournie par le fabricant pour aider les dÃ©veloppeurs Ã&nbsp; bien employer les ressources des divers modÃ¨les de GPU.  
 
Les limitations de l'\textit{occupancy} ont pour origine :
\begin{enumerate}
\item {\bf l'usage des registres}. Si chaque thread utilise le maximum de $64$ registres possible ($63$ pour l'utilisateur $+1$ pour le processeur), le bloc de threads affectÃ© au SM ne peut donc activer simultanÃ©ment que $32K/64=512$ threads, soit une \textit{occupancy} de $512/1536=0.33$.
\item {\bf l'usage de la mÃ©moire partagÃ©e}. L'architecture Fermi permet de choisir la rÃ©partition entre cache L1 et mÃ©moire partagÃ©e, soit 16K/48K, soit 48K/16K. En configuration 48K de mÃ©moire partagÃ©e, si chaque thread en emploie 48 octets, le GPU ne peut activer que $48K/48=1024$ threads, soit une \textit{occupancy} de $1024/1536=0.66$.
\item {\bf la taille des blocs}. Un SM ne pouvant activer que 8 blocs simultanÃ©ment, la taille des blocs limite donc potentiellement l'\textit{occupancy}. Si on exÃ©cute un \textit{kernel} sur une grille de calcul dont les blocs ont le minimum de 32 threads, les 8 blocs actifs reprÃ©senteront alors 256 threads, soit une \textit{occupancy} de $256/1536=0.16$.
\end{enumerate}

Nous verrons que cette notion d'\textit{occupancy}, si elle conserve du sens, peut toutefois Ãªtre remise en question en optimisant d'autres aspects permettant d'arriver Ã&nbsp; une rÃ©duction de l'effet des latences, comme le parallÃ©lisme d'instructions ou l'augmentation du volume des transactions. En effet, ces techniques, et surtout l'utilisation avisÃ©e des diffÃ©rents types de mÃ©moire du GPU permettent d'obtenir des performances Ã©levÃ©es, parfois inenvisageables en suivant les prescriptions du constructeur.

\section{Contraintes de conception}
Certaines de ces contraintes ont dÃ©jÃ&nbsp; Ã©tÃ© Ã©voquÃ©es rapidement, mais il nous semble important d'en donner ici une prÃ©sentation synthÃ©tique. 
\begin{enumerate}
\item \textbf{ContiguÃ¯tÃ©}. 
Les accÃ¨s alÃ©atoires Ã&nbsp; la mÃ©moire globale sont en rÃ¨gle gÃ©nÃ©rale trÃ¨s pÃ©nalisants. Toutefois, il est possible de tirer parti du cache de niveau 1 (Ã&nbsp; une dimension) en organisant les donnÃ©es pour que tous les threads d'un mÃªme warp accÃ¨dent Ã&nbsp; des donnÃ©es appartenant au mÃªme bloc de 128 octets de mÃ©moire. Le non-respect de cette contrainte de contiguÃ¯tÃ© (\textit{coalescence}) induit des accÃ¨s rÃ©alisÃ©s en plusieurs transactions serialisÃ©es et donc une perte potentiellement importante de performances.
\item \textbf{Conflits de banques}.
La mÃ©moire partagÃ©e, plus rapide que la mÃ©moire globale, peut sembler une solution Ã©vidente pour obtenir des performances Ã©levÃ©es. Cependant, elle est physiquement organisÃ©e en 32 \og banques \fg{} de largeur 32 bits et prÃ©sente elle aussi une contrainte majeure. Sur architecture Fermi, l'exÃ©cution des threads d'un warp est assurÃ©e par deux \textit{moteurs d'exÃ©cution} qui activent en parallÃ¨le chacun des deux demi-warp.  
Un \textbf{conflit de banque} se produit lorsque deux threads n'appartenant pas au mÃªme demi-warp accÃ¨dent Ã&nbsp; des donnÃ©es localisÃ©es dans la mÃªme banque de mÃ©moire partagÃ©e. La transaction parallÃ¨le est alors interrompue et sÃ©rialisÃ©e.
Ici encore, la perte de performance peut Ãªtre importante, mais il peut s'avÃ©rer trÃ¨s complexe, coÃ»teux, voire impossible d'organiser les donnÃ©es en mÃ©moire partagÃ©e de sorte Ã&nbsp; Ã©viter tout conflit de banque.
\item \textbf{Branches divergentes}.
Toute branche d'exÃ©cution divergente entraine une sÃ©rialisation des exÃ©cution des threads du warp auquel ils appartiennent. Il convient donc d'Ã©viter cette situation et d'organiser les traitements en consÃ©quence en privilÃ©giant le plus souvent un dÃ©coupage plus fin en plusieurs kernels Ã©lÃ©mentaires plutÃ´t que des kernels \og lourds \fg{}.
\item \textbf{Transferts GPU$\leftrightarrow$CPU}.
Les transferts de donnÃ©es entre la mÃ©moire globale du  GPU et celle de son hÃ´te CPU peuvent reprÃ©senter l'essentiel du temps de traitement total et doivent donc Ãªtre optimisÃ©es pour en rÃ©duire la frÃ©quence et le volume des donnÃ©es Ã&nbsp; copier. Cela peut parfois Ãªtre contradictoire avec la multiplication de petits kernels Ã©lÃ©mentaires.
Il est toutefois possible, lorsque la sÃ©quence de traitement le permet, de rÃ©aliser des transferts en temps masquÃ©, pendant l'exÃ©cution d'un kernel, en crÃ©ant plusieurs flux d'exÃ©cution.
\item \textbf{Partage des ressources d'un SM}
Le paragraphe sur l'\textit{occupancy} a abordÃ© cet aspect par un exemple. Il faut retenir que chaque SM possÃ¨de des ressources mÃ©moire (registres, mÃ©moire partagÃ©e) que les threads des blocs logiques de la grille de calcul se partagent au cours de l'exÃ©cution d'un kernel. L'Ã©quilibre entre l'utilisation de ces ressources et le dimensionnement de la grille de calcul relÃ¨ve d'un compromis parfois dÃ©licat Ã&nbsp; trouver pour obtenir les meilleures performances possibles. 
\item \textbf{Les latences}. L'exÃ©cution des kernels subit l'effet de latences d'origines diverses. Les latences d'accÃ¨s aux mÃ©moires (voir Table \ref{tab-gpu-memoire}), les latences des diffÃ©rentes instructions arithmÃ©tiques ou encore les latences crÃ©es par l'inter dÃ©pendance d'instructions consÃ©cutives. Il est impÃ©ratif de les prendre en considÃ©ration et de mettre en \oe uvre des techniques adaptÃ©es pour les masquer au mieux.   
\item \textbf{La mise au point}. L'ordonnancement des threads n'est pas prÃ©visible et les quelques outils d'aide Ã&nbsp; la mise au point (debug) permettent simplement de cibler un  thread  prÃ©sÃ©lectionnÃ© de la cible. Cela ne permet en aucun cas de dÃ©celer, par exemple, les conflits de banques provoquÃ©s par l'interaction d'au moins deux threads. Un outil de profilage dÃ©veloppÃ© par le fabricant fournit des informations importantes sur le nombre de conflits de banques et les origines probables des limitations de performance des kernels d'un programme. Il ne s'appuie cependant que sur un bloc de threads pour en extrapoler les rÃ©sultats Ã&nbsp; l'ensemble de la grille.        
\end{enumerate}   
L'ensemble de ces aspects rend difficile la conception d'implÃ©mentations GPU rapides car rares sont les transcriptions directes d'un code CPU qui ne se heurtent pas sÃ©vÃ¨rement Ã&nbsp; l'une ou l'autre des contraintes que l'on vient d'Ã©numÃ©rer. Les performances qui en rÃ©sultent sont alors trÃ¨s en deÃ§a de celles attendues, voire infÃ©rieures Ã&nbsp; celles de l'implÃ©mentation CPU. La mise au point Ã©tant par ailleurs trÃ¨s dÃ©licate, il nous semble important de proposer des kernels Ã©lÃ©mentaires dont on peut aisÃ©ment garantir les rÃ©sultats par des mÃ©thodes de test ne nÃ©cessitant pas de devoir implÃ©menter conjointement les versions CPU Ã©quivalentes des algorithmes concernÃ©s.   
</pre></body></html>