Accélérer l’exécution

lundi 21 février 2011

Mesure de l’accélération

L’accélération, souvent appelée speedup, donne le gain de temps apporté par la version parallélisée d’un programme par rapport à sa version séquentielle :

A(N) = \frac{T(1)}{T(N)}

  • A(N) : accélération sur N coeurs
  • T(N) : temps d’exécution total sur N coeurs

Accélération maximale - Loi de Amdahl

La loi de Amdahl montre que l’accélération maximale est bornée. Elle dépend du nombre de coeurs N et de la proportion séquentielle du programme, s :

A(N) =\frac{1}{s+(1-s)/N}

  • s : la fraction de temps que le programme passe dans la portion séquentielle
  • N : nombre de coeurs utilisés

Un programme ou une partie de programme sans proportion séquentielle (s=0), bénéficie directement de l’accélération :

A(N) = N

Dans le cas d’un programme standard avec une partie séquentielle et une partie parallèle, l’accélération est bornée par la partie séquentielle quelque soit le nombre de coeurs utilisés :

A(N) = \frac{1}{s+(1-s)/N} < \frac{1}{s}

Calcul de l’accélération

Prenons un programme standard que nous décomposons en 2 parties : une partie séquentielle et une partie parallèle. Nous définissons :

  • T(N) : temps d’exécution total sur N coeurs,
  • Tseq(N) : temps d’exécution de la portion séquencielle sur N coeurs,
  • Tpar(N) : temps d’exécution de la portion parallèle sur N coeurs,
  • s : la fraction de temps que le programme passe dans la portion séquentielle,

s=\frac{Tseq(1)}{T(1)}

La partie séquentielle regroupe les instructions qui s’exécutent en série, les unes à la suite des autres, sans concurrence possible, d’où :

Tseq(N) = Tseq(1)

La partie paralléle regroupe les instructions indépendantes les unes des autres et qui peuvent s’exécuter simultanément sur toutes les unités de calcul disponibles, d’où :

Tpar(N) = \frac{Tpar(1)}{N}

Exécution sur un seul coeur

Le temps d’exécution total de ce programme sur un seul coeur est noté :

\left \begin{array}{rclcl} T(1))&=&Tseq(1)&+&Tpar(1)\\&=&s.T(1)&+&(1-s).T(1)\\\end{array}\right

Exécution sur N coeurs

Le temps d’exécution total de ce même programme sur N coeurs est noté :

\left \begin{array}{rclcl} T(N)&=&Tseq(N)&+&Tpar(N)\\&=&Tseq(1)&+&Tpar(1)/N\\&=&s.T(1)&+&(1-s).T(1)/N\\\end{array}\right


RTRA

Navigation

Articles de la rubrique

Annonces

Stage : "Conteneurs dans un environnement HPC"

Rapport de stage de Jiaming HU :

PDF - 1.7 Mo
(mai - août 2017)

Stage : "Machines virtuelles et haute disponibilité"

Rapport de stage de Mahdi HAMMOUCHE :

PDF - 1.2 Mo
(juin - septembre 2016)

Stage : "Grappe de calcul HPC à éléments délocalisés"

Rapport de stage de Brahim BIKI :

PDF - 1.4 Mo
(mai-août 2015)

Stage : "Optimisation des ressources d’un cluster pour le calcul scientifique"

Rapport de stage de Damien Delhay :

PDF - 1.4 Mo
(mai-juillet 2014)

Stage : "Diagonalisation des matrices réelles sur GPU"

Rapport de stage de Kun SONG :

PDF - 803.4 ko
(mai - août 2013)

Stage : "Optimisation du transfert de données entre un CPU et un GPU"

Rapport de stage de Jean YAOKELI :

PDF - 915.4 ko
(mai - août 2012)