X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/1bdc5bd76352d829a51e2d6407ad331af7164113..5d5e214d54eab1411ef86a32e11fccfaa53dbc45:/THESE/Chapters/chapter1b/chapter1b.tex

diff --git a/THESE/Chapters/chapter1b/chapter1b.tex b/THESE/Chapters/chapter1b/chapter1b.tex
index 4b3d882..5cd5426 100644
--- a/THESE/Chapters/chapter1b/chapter1b.tex
+++ b/THESE/Chapters/chapter1b/chapter1b.tex
@@ -1,19 +1,19 @@
 \section{Pourquoi ?}
 S'il fallait en rÃ©duire les raisons Ã  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 Ã  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 est traitÃ© individuellement. L'amÃ©lioration des rÃ©solutions Ã  aussi contribuer Ã  faire Ã©voluer la nature de ces besoins de \textit{parallÃ¨le} Ã  \textit{massivement parallÃ¨le}, un Ã©cran actuel pouvant comporter plus de  2,5 millions de pixels. 
+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Ã© Ã  faire Ã©voluer la nature de ces besoins de \textit{parallÃ¨le} Ã  \textit{massivement parallÃ¨le}, un Ã©cran actuel pouvant comporter plus de  2,5 millions de pixels. 
 
-La technologie de fabrication Ã©tant identique Ã  celle de CPUs, c'est donc au niveau de la rÃ©partitions des fonctionnalitÃ©s que les GPUs se distinguent : lÃ  oÃ¹ un CPU comporte quelques c\oe urs de calcul et beaucoup de transistors dÃ©diÃ©s Ã  la rÃ©alisation de mÃ©moire cache et de contrÃ´le de flux, un GPU prÃ©sente plusieurs unitÃ©s comportant chacun une grande quantitÃ© de c\oe urs de calcul ne disposant que de trÃ¨s peu de mÃ©moire cache et de rudimentaires capacitÃ©s de contrÃ´le, comme l'illustrent les schÃ©mas de la figure \ref{fig-gpucpu1}.
+La technologie de fabrication des GPUs Ã©tant identique Ã  celle des CPUs, c'est donc au niveau de la rÃ©partition des fonctionnalitÃ©s que les GPUs se distinguent : lÃ  oÃ¹ un CPU comporte quelques c\oe urs de calcul et beaucoup de transistors dÃ©diÃ©s Ã  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 de rudimentaires capacitÃ©s de contrÃ´le, 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}).}
+  \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 \& Logical Unit.}
   \label{fig-gpucpu1}
 \end{figure}
 
-Cette spÃ©cialisation des circuit GPUs 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 GPU Nvidia\textregistered et pour les CPU Intel\textregistered.  
+Cette spÃ©cialisation des circuits GPUs 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 GPU Nvidia\textregistered et pour les CPU Intel\textregistered.  
 
-Les problÃ¨mes recquÃ©rant les capacitÃ©s de calcul spÃ©cifiques des GPU ne sont cependant pas limitÃ©s aux questions de rendu graphique, aussi les scientifiques ont-ils trÃ¨s vite cherchÃ© Ã  tirer parti de la puissance de calcul croissante des GPUs pour traiter d'autres types de problÃ¨mes, faisant sens Ã  l'acronyme GPGPU.
+Les problÃ¨mes requÃ©rant les capacitÃ©s de calcul spÃ©cifiques des GPU ne sont cependant pas limitÃ©s aux questions de rendu graphique, aussi les scientifiques ont-ils trÃ¨s vite cherchÃ© Ã  tirer parti de la puissance de calcul croissante des GPUs pour traiter d'autres types de problÃ¨mes, faisant sens Ã  l'acronyme GPGPU (General Purpose Graphical Processing Unit).
 
 \begin{figure}[h]
   \centering
@@ -23,27 +23,27 @@ Les problÃ¨mes recquÃ©rant les capacitÃ©s de calcul spÃ©cifiques des GPU ne sont
   \label{fig-gpucpu2}
 \end{figure}
 
-MalgrÃ© des caractÃ©ristiques prometteuses, les GPGPUs n'ont pas immÃ©diatement declenchÃ© une vague d'expÃ©rimentations scientifiques dans des domaines variÃ©s, l'essentiel des travaux Ã©tant liÃ©s Ã  la construction et la visualisation des donnÃ©es issues de l'instrumentation d'imagerie mÃ©dicale. 
+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 Ã  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 permetant d'Ã©crire facilement des fonctions s'exÃ©cutant en parallÃ¨le sur le GPU, que l'on appelle des \textit{kernels}. L'extension CUDA permet Ã©galement de gÃ©rer de maniÃ¨re transparente les changements d'Ã©chelle du parallÃ©lisme d'une architecture Ã  une autre ou tout simplement les dimensions de la grille de calcul. Ces possibiltÃ©s rendent l'accÃ¨s facile Ã  la programmation GPU.
+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 Ã  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 Ã  l'architecture dite \textit{Fermi} Ã  laquelle appartient le GPU C2070 qui a servi Ã  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), chacun groupe en comprenant 3 ou 4 pour un total de 14 SMs.
-Chaque SM hÃ©berge Ã  son tour 32 c\oe urs de calcul (les SPs).
-Les threads sont exÃ©cutÃ©s par paquets de 2$\times$16, soit 32 (les warps) sur les 32 c\oe urs de calcul. 
+Le circuit se divise en 4 groupes de processeurs de flux (les SMs = Streaming Multiprocessors), chaque groupe en comprenant 3 ou 4 pour un total de 14.
+Chaque SM hÃ©berge Ã  son tour 32 c\oe urs de calcul (les SPs = Streaming Processors).
+Les threads sont exÃ©cutÃ©s par \textit{warps} de 2$\times$16, soit 32, rÃ©partis sur les 32 c\oe urs de calcul. 
 
 \begin{figure}[h]
   \centering
-  \subfigure[Organisation en groupes de SMs ]{\includegraphics[height=5cm]{Chapters/chapter1b/img/fermi.png}}\quad
-  \subfigure[Constitution d'un SM.]{\includegraphics[height=5cm]{Chapters/chapter1b/img/fermi-sm.png}}
+  \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 GPU d'architecture Fermi, comme le C2070 (d'aprÃ¨s www.hpcresearch.nl).}
   \label{fig-c2070}
 \end{figure}
 
-Les ressources mÃ©moire sont de plusieurs nature tant du point de vue volume disponible, que portÃ©e ou bien dÃ©bit.  Il faut retenir que les registres sont peu nombreux, embarquÃ©s sur le circuit (on-chip) et prÃ©sentent les meilleures performances alors que la mÃ©moire principale, dite globale, est externe au circuit (off-chip), de grande capacitÃ© mais prÃ©sente des latences importantes de plusieurs centaines de cycles d'horloge.
+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 (on-chip), prÃ©sentent les meilleures performances alors que la mÃ©moire principale, dite globale, externe au circuit (off-chip) et de 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, issues d'expÃ©rimentations menÃ©es par nos soins Ã  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 Ã  la mÃ©moire globale.
@@ -66,40 +66,41 @@ Une petite quantitÃ© de mÃ©moire on-chip est prÃ©sente sur chaque SM et permet l
           Globale  &   off-chip  &grille&580/80/350 &144 & 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/}. Les mesures ont Ã©tÃ© obtenues Ã  l'aide des microprogrammes de test de \cite{wong2010demystifying}.}
+   \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}. Les mesures ont Ã©tÃ© obtenues Ã  l'aide des microprogrammes de test de \cite{wong2010demystifying}.}
       \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 Ã  l'intÃ©rieur du kernel, ce qui permet d'en individualiser le traitement.
-L'ensemble des threads est organisÃ© en plusieurs blocs indÃ©pendants, puis ces blocs en 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 Ã  une, deux ou trois dimensions.
-Le nombre total de threads appartenant Ã  un mÃªme bloc est cependant limitÃ©, selon la version de GPU, Ã  512 ou 1024. Le diagramme de la figure \ref{fig-threads} illustre l'organisation d'une grille de calcul Ã  2 dimensions et des ses blocs, Ã©galement Ã  2 dimensions, situation qui correspond Ã  la majoritÃ© des modÃ¨les d'exÃ©cution de nos \textit{kernels} de traitememnt d'image. 
+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 Ã  une, deux ou trois dimensions.
+Le nombre total de threads appartenant Ã  un mÃªme bloc est cependant limitÃ©, selon la version de GPU, Ã  512 ou 1024. Le diagramme de la figure \ref{fig-threads} illustre l'organisation d'une grille de calcul Ã  2 dimensions et de ses blocs, Ã©galement Ã  2 dimensions, situation qui correspond Ã  la majoritÃ© des modÃ¨les d'exÃ©cution de nos \textit{kernels} de traitement d'image. 
 
 \begin{figure}[h]
   \centering
-  \includegraphics[height=6cm]{Chapters/chapter1b/img/threads.png}
+  \includegraphics[height=8cm]{Chapters/chapter1b/img/threads.png}
   \caption{ReprÃ©sentation d'une grille de calcul en 2D et des blocs de threads, Ã  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 Ã  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. 
 
-Au sein d'un mÃªme bloc, les threads peuvent communiquer efficacement grÃ¢ce Ã  la mÃ©moire partagÃ©e, rapide et prÃ©sentant une faible latence.
-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 en obtenir les performances attendues. Le non respect de ces contraintes conduit le plus souvent Ã  un bout programme dont l'exÃ©cution s'avÃ¨re plus lente que son Ã©quivalent CPU.
+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 en obtenir les performances attendues. Le non-respect de ces contraintes conduit le plus souvent Ã  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 grile et ce, pour masquer les latences des accÃ¨s aux mÃ©moires, mais aussi celles des instructions arithmÃ©tiques.
+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, Ã  chaque instant, le rapport du nombre de blocs 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Ã©oire partagÃ©e) ou bien par une grille de calcul mal dimensionnÃ©e. L'ensemble des paramÃ¨tres intervenant dans le calcul l'\textit{occupancy} est pris en compte dans une feuille de tableur (l'\textit{occupancy calculator}) fournie par Nvidia pour aider les dÃ©veloppeurs Ã  bien employer les ressources des divers modÃ¨les de GPU.  
+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 Ã  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 registres possible ($63+1=64$), le bloc de thread 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 partgÃ©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 une \textit{occupancy} de $1024/1536=0.66$.
+\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 Ã  une rÃ©duction de l'effet des latences, comme le parallÃ©lisme d'instructions ou l'augmentation du volume des transactions. Ces techniques ainsi que l'emploi fin des mÃ©moires du GPU permettent d'obtenir des performances Ã©levÃ©es sur GPU, parfois inenvisageables en suivant les prÃ©scriptions du constructeur.   
+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 Ã  une rÃ©duction de l'effet des latences, comme le parallÃ©lisme d'instructions ou l'augmentation du volume des transactions. Ces techniques, ainsi que l'emploi fin des mÃ©moires du GPU permettent d'obtenir des performances Ã©levÃ©es, parfois inenvisageables en suivant les prescriptions du constructeur.   
+
+
 
