Parallélisme : travaux dirigés et pratiques

• cours 1 : Introduction Générale
• cours 2 : Algorithmes et Métriques
• cours 3 : P-Threads et C++11 Threads
• cours 4 : OpenMP
• cours 5 : MPI

2. Algorithmes et Métriques

Dans ce chapitre nous nous intéressons à quelques algorithmes que l'on peut paralléliser. Certains sont trivialement parallélisables, d'autres demandent un peu plus de travail et de rélexion. Le but est de se familiariser avec les techniques liées au passage du séquentiel au parallèle.

2.1. Réduction

On considère un tableau de $n$ éléments et un opérateur associatif et commutatif $⊕$ doté d'un élément neutre $I$. A partir du tableau

$$ [ a_0, a_1, ..., a_{n-1} ] $$

on désire obtenir un unique résultat :

$$ a_0 ⊕ a_1 ⊕ ... ⊕ a_{n-1} $$

On peut appliquer cet algorithme avec d'autres opérateurs comme la multiplication, minimum, maximum.

Pour que l'algorithme soit parallélisable efficacement il sufit que l'opérateur $⊕$ dispose des propriétés d'associativité et de commutativité :

• commutativité : $a ⊕ b = b ⊕ a$
• associativité : $a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c$

2.1.1. code séquentiel

Voici le code séquentiel (et parallèle) en C++ de la réduction qui est facilement vectorisable :

2.1.2. code parallèle

On dispose de $K$ processeurs et on répartit les indices à traiter entre les processeurs.

Pour la répartition des indices il existe deux possibilités à moins que les indices se répartissent équitablement :

• soit le dernier thread traite moins de valeurs que les autres
• soit le dernier thread traite plus de valeurs que les autres

2.1.2.a  le dernier thread traite moins de valeurs que les autres

Chaque thread traite au plus $ μ_1 = (N + K -1) / K $ valeurs

2.1.2.b  le dernier thread traite plus de valeurs que les autres

Chaque thread traite au moins $ μ_2 = N / K $ valeurs

2.1.2.c  répartition équitable

On répartit les $N$ éléments sur les $K$ threads, il reste alors $R = N - K (N/K)$ éléments que l'on assigne successivement à chaque thread :

2.1.3. Application : calcul d'intégrale

Pour calculer l'intégrale d'une fonction $f(x)$ entre $a$ et $b$ on utilise la méthode des rectangles (ou des trapèzes si on désire une meilleure précision) qui consiste à décomposer l'intervalle $[a..b]$ en un ensemble de petits rectangles dont on va calculer l'aire.

Plus le nombre de rectangles est important plus la précision du résultat sera proche de la valeur réelle.

$$ ∫_a^b f(x)\, dx = ∑↙{i=1}↖N f(a + i × δx) × δx = δx × ∑↙{i=1}↖N f(a + i × δx) $$

avec

$$ δx = {(b - a)} / N $$

2.1.3.a  code séquentiel

Le code en C++ du calcul de l'intégrale de $f(x) = x^2$ entre 0 et 3.0 est le suivant :

2.1.3.b  code parallèle

Si on dispose de $K$ processeurs ou machines, on répartit les calculs sur $K$ machines

Chaque $P_k, k ∊ [1..K]$ calcule en moyenne $γ = N/K$ valeurs :

2.2. courbe de Julia

Les courbes ou ensembles de Julia, du mathématicien français Gaston Julia (1893 à 1978) ou ensembles de Mandelbrot du mathématicien Benoît Mandelbrot (1924-2010) sont un bon exemple d'application du parallélisme.

Etant donné un nombre complexe $z_0$ qui correspond à un point dans le plan, on associe la suite : $z_{n+1} = z_n^2 + c$, où $c$ est une constante complexe.

Le plan est alors partagé entre :

• l'ensemble des points pour lesquels la suite est bornée (qualifiés de prisonniers de $f$)
• les autres points étant les fugitifs

L'ensemble de Julia associé à $z_n$ est alors la frontière commune de ces deux ensembles, en fait, la ligne de démarcation entre les prisonniers et les fugitifs.

2.3. Scan

2.3.1. principe

L'algorithme de scan (aussi qualifié de prefix sum, cumulative sum, inclusive scan et exclusive scan) possède de nombreuses applications en informatique. Il consiste étant donnée une séquence de nombres $[a_0, a_1, ..., a_{n-1}]$ et un opérateur binaire associatif $⊕$ doté d'un élément neutre $I$, à calculer une deuxième séquence :

• exclusive scan : $[I, a_0, a_0 ⊕ a_1, ... , a_0 ⊕ a_1 + ... + a_{n-2} ]$
• inclusive scan : $[a_0, a_0 ⊕ a_1, ... , a_0 ⊕ a_1 + ... + a_{n-1} ]$

Vous trouverez plusieurs applications sur le site suivant : toves.org (voir notamment la section 3.3. Adding big integers)

Voici une première version séquentielle des algorithmes :

Par exemple avec la séquence [1, 3, 5, 7, 9] et l'opérateur d'addition on obtient :

• exclusive scan : [0, 1, 4, 9, 16]
• inclusive scan : [1, 4, 9, 16, 25]

La complexité de cet algorithme est en $O(n)$

2.3.2. Versions parallèles

2.3.2.a  un premier algorithme naïf

Un premier algorithme parallèle peut être exhibé mais il n'est pas très efficace : il repose sur l'utilisation de deux tableaux qui sont utilisés successivement en entrée et en sortie

La complexité de cet algorithme est en $O(n × \log_2(n))$, elle augmente donc la complexité de l'algorithme séquentiel par un facteur $\log_2(n)$.

2.3.2.b  un second algorithme efficace

L'idée est d'utiliser un parcours sous forme d'arbre. On utilise deux phases appelées sweep (balayage) :

• la phase ascendante (up-sweep phase) correspond à un parcours des feuilles vers la racine : on calcule des sommes partielles pour chaque noeud interne. Il s'agit en fait d'un algorithme de réduction
• la phase descendante (down-sweep phase) correspond à un parcours de la racine vers les feuilles

Ce genre d'algorithme se révèle moins eficace que l'algorithme séquentiel mais peut être intéressant sur des architectures de type GPU.

a) phase up-sweep

la phase de balayage vers la haut consiste à parcourir le tableau sous la forme d'un arbre binaire en calculant des sommes partielles :

• on commence au niveau $d = 1$ avec les éléments d'indice modulo 2
• puis modulo 4 au niveau suivant $d = 2$
• jusqu'à atteindre la taille du tableau : $n = 8 = 2^{d = 3}$

Voici une première version avec $d ∈ [1..log_2(n)]$ :

// up-sweep - version 1
for d in range(1, log2(n)) do
        
        variable shift is integer = 2^d
        
        for i in range(1, n) do
                if integer.modulo(i, shift) = 0 then
                        a[i] = a[i] + a[i - shift / 2]
                end if
        end for 
        
end for 

Cependant ajouter un if dans le code n'apporte rien pour la parallélisation. Voici donc une autre version de l'up-sweep qui sera plus simplement parallélisable:

// up-sweep - version 2
for d in range(1, log2(n)) do

        variable shift is integer = 2^d
        
        for i in parallel range(shift, n) step shift do
                a[i] = a[i] + a[i - shift / 2]
        end for 
        
end for 

b) phase down-sweep

Voici la partie la plus complexe de l'algorithme pour un scan exclusif :

// exclusive down sweep

a[n] = 0

for d in range(log2(n), 1) step -1 do

        variable shift is integer = 2^d
        
        for i in parallel range(0, n-1) step 2^(d+1) do
        
                variable tmp is integer = a[i + shift / 2 - 1]
                a[i + shift / 2 - 1 ] = a[i + shift - 1 ];
                a[i + shift - 1 ] += tmp;
                
        end for 
        
end for 

Dans le cadre du scan inclusif il faut procéder ainsi :

// inclusive down sweep 
for d in range(1, log2(n)) do 
		
		variable shift  is integer = 2^d;
		variable offset is integer = 2^(log2(n) -d - 1)
		
		for i in parallel range(n / shift, n) step  n/shift do
			  a[i + offset] += a[i];
		end for

end for

Au final la prallélisation de cet algorithme n'est pas efficace :

2.4. Les algorithmes de tri

Il est important de choisir des algorithmes qui seront parallélisables naturellement. Par exemple le tri à bulle est dificilement parallélisable.

Nous verrons trois types de tri :

• tri pair-impair (odd-even)
• tri fusion (merge)
• tri bitonique (bitonic)

2.4.1. Tri pair-impair (odd-even sort)

Le principe du tri pair-impair est de comparer les couples/paires d'éléments d'un tableau.

• dans un premier temps on compare les couples d'indices pairs (0, 2, 4, ...), en d'autre termes on compare t[0] avec t[1], puis t[2] avec t[3], etc...
• puis dans un second temps les couples d'indices impaires (1, 3, 5, ...), en d'autres termes on compare t1] avec t[2], puis t[3] avec t[4], etc...

On recomence jusqu'à ce que le tableau soit trié.

Voici un exemple avec un tableau dont les valeurs sont trié en ordre inverse. On peut voir que les valeurs 5 et 12 aparaissent sur les diagonales lors des diférentes étapes de tri.

2.4.2. Tri fusion (merge sort)

Le tri fusion consiste :

• dans une première phase : à décomposer le tableau (split) en tableaux plus petits, on divise le tableau en 2 à chaque étape ce qui conduit à une décomposition arborescente en $log_2(n)$. Lorsque le tableau a une taille de deux éléments on trie les deux éléments du tableau
• dans une deuxième phase : à fusioner (merge) deux tableaux triés adjacents

2.4.3. Tri bitonique (bitonic sort)

Voir l'article Tri bitonique de Wikipédia en français.

Exemple des comparaisons à réaliser (image issue de Wikipedia)

Le tableau doit avoir une taille égale à une puissance de 2.

// note that the array must have a size equal to a power of 2
variable dim is integer = 5
variable arr is array [0..2^dim-1] of integer

procedure bitonic_sort(t is output array of integer)

	variable log2_n is integer = log(size) / log(2)
	
	for i in range(0, log2_n-1) do
		for j in range(0, i) do
			compare(t, i, j, t.size())
		end for
	end for
	
end procedure

procedure compare(t is output array of integer, p, q, size are integer) {

	variable d is integer = 1 << (p-q)
	variable up is boolean

	for i in range(0, size-1) do
		if ((i >> p) & 2) = 0 then
			up = true
		else
			up = false

		if (i & d) = 0 then
			if (t[i] > t[i + d]) = up then
				swap(t[i], t[i + d])	
			end if
		end if
	end for
	
end procedure

2.5. Métriques : accélération, efficacité, loi de Amdhal

Voir ce document pour de plus amples explications.

2.5.1. Amélioration

Pour comparer deux implantations (implantation de REFérence et OPTimisée), on peut définir trois valeurs

• le facteur d'amélioration ou accélération (speedup): $$acc = T_{REF}/T_{OPT}$$ qui sera supérieur à 1 si la version OPTimisée est effectivement plus efficace que la version de REFérence
• le pourcentage d'amélioration : $$pct = ({T_{OPT} - T_{REF}})/T_{REF} × 100$$ qui sera négatif si la version OPTimisée est effectivement plus efficace que la version de REFérence
• l'efficacité $E$ est le rapport entre l'accélération et le nombre de processeurs $$E(K) = {acc}/{K}$$

Accélération et pourcentage d'amélioration par rapport à un temps de référence de 100

$T_{OPT}$	100	90	80	70	60	50	40	30	20	10
accélération $(acc)$	1.00	1.11	1.25	1.43	1.67	2.00	2.50	3.33	5.00	10.00
pourcentage $(pct)$	0%	-10%	-20%	-30%	-40%	-50%	-60%	-70%	-80%	-90%

2.5.2. Loi de Amdahl

L'application de la loi de Amdahl (1967) en calcul parallèle permet de prédire l'accélération théorique que l'on peut espérer obtenir en utilisant plusieurs processeurs.

Soit un programme qui s'exécute en $T_1$ secondes et soient $Seq$ et $Par$ respectivement le pourcentage de temps passé en séquentiel et en parallèle, alors le temps d'exécution par un seul processeur est défini par:

$$T_1 = Seq × T_1 + Par × T_1 = (1 - Par) × T_1 + Par × T_1 $$

sachant que $Par + Seq = 1$. Par exemple si $Par=0.92$ alors 92% du temps est passé dans la section de code parallèle.

Si on utilise $K$ processeurs alors seule la partie parallèle en bénéficie. Le temps d'exécution $T_K$ pour $K$ processeurs est défini par : $$ T_K = Seq × T_1 + Par × T_1 / K $$

L'accélération pour $K$ processeurs est donnée par $acc = T_1 / T_K$ est alors :

$$ {T_1}/{T_K} = {(1 - Par) × T_1 + Par × T_1}/{(1 - Par) × T_1 + Par × T_1 / K} = 1 / {1 - Par + {Par}/ K} = 1 / {Seq + {1 - Seq}/ K} = 1/{Seq + {Par}/{K}} $$

Loi de Amdahl, $acc$ (Accélération) en fonction de $K$ (nombre de threads) pour $Par=0.92$

$K$	$Acc$	%	$Δ$ %
2	1.85	-46	46
4	3.23	-69	23
8	5.13	-80	11
10	5.81	-83	3
12	6.38	-84	1
20	7.94	-87	3

Notons que plus $Par$ est proche de 1, plus $acc$ est grand quand $K$ augmente, cf. l'image ci-dessous où $R=acc$ et $S=K$ le nombre de processeurs.

Tableau de valeurs pour la loi de Amdahl

K \ Par	0.5	0.6	0.7	0.8	0.9	0.92	0.95	0.99
2	1.33	1.43	1.54	1.67	1.82	1.85	1.90	1.98
4	1.60	1.82	2.11	2.50	3.08	3.23	3.48	3.88
8	1.78	2.11	2.58	3.33	4.71	5.13	5.93	7.48
10	1.82	2.17	2.70	3.57	5.26	5.81	6.90	9.17
12	1.85	2.22	2.79	3.75	5.71	6.38	7.74	10.81
16	1.88	2.29	2.91	4.00	6.40	7.27	9.14	13.91
20	1.90	2.33	2.99	4.17	6.90	7.94	10.26	16.81
32	1.94	2.39	3.11	4.44	7.80	9.20	12.55	24.43
64	1.97	2.44	3.22	4.71	8.77	10.60	15.42	39.26
128	1.98	2.47	3.27	4.85	9.34	11.47	17.41	56.39
256	1.99	2.49	3.30	4.92	9.66	11.96	18.62	72.11

Par exemple avec 99% du temps d'exécution parallélisable, on peut diviser le temps d'exécution par un facteur 16.81 lorsque l'on utilise 20 threads/processeurs.

2.5.3. Loi de Gustafson

La loi de Amdhal concerne l'accélération à travail ou charge constante. La loi de Gustafson prédit l’accélération théorique maximale obtenue en n'imposant pas que la taille du travail soit fixe.

D'après Wikipédia : Plus le nombre de données traitées en parallèles est grand, plus l’utilisation d'un grand nombre de processeurs est efficace. Mais surtout, il n'y a pas de limite théorique à l'accélération : on peut mettre autant de données que l'on veut, celles-ci sont toutes traitées par un processeur simultanément et le temps mis pour traiter s données sur s processeurs sera identique au temps mis pour traiter une donnée sur un seul processeur. Aucune limite n'existe concernant la quantité de données traitables simultanément, et donc au gain que l'on peut obtenir.

Elle traduit le fait que l'on peut traiter plus de données dans le même temps en augmentant le nombre de processeurs.

$$acc = Seq + K × Par = K + Seq × (1 - K)$$

Tableau de valeurs pour la loi de Gustafson

K / Par	0.5	0.6	0.7	0.8	0.9	0.92	0.95	0.99
2	1.50	1.60	1.70	1.80	1.90	1.92	1.95	1.99
4	2.50	2.80	3.10	3.40	3.70	3.76	3.85	3.97
8	4.50	5.20	5.90	6.60	7.30	7.44	7.65	7.93
10	5.50	6.40	7.30	8.20	9.10	9.28	9.55	9.91
12	6.50	7.60	8.70	9.80	10.90	11.12	11.45	11.89
20	10.50	12.40	14.30	16.20	18.10	18.48	19.05	19.81

2.5.4. Métrique de Karp–Flatt (1990)

Cette métrique permet de prendre en compte les couts de parallélisation.

Soit l'accélération $acc$ obtenue pour $K > 1$ processeurs, on calcule la métrique de Karp–Flatt $e$ comme suit : $$e= {{1}/{acc} - {1}/{K}}/{1 - {1}/{K}}$$

Plus $e$ est petit, meilleure est la parallélisation.