Fork / Join, Parallel Arrays, Lambdas : la programmation parallèle (trop ?) facile ! - José paumard Codeurs en seine 2013

Pourquoi développer des algorithmes parallèles ?


Pourquoi développer des applications multithread ?


Pourquoi développer des applications multithread ?

=

Pour exploiter la puissance des processeurs modernes.

Depuis 2005 bla bla bla

Depuis 2005 bla bla bla

Conséquence :

Il va falloir faire preuve d’intelligence

pour écrire des applications performantes !

Depuis 2005

Pour développer des applications perfomantes, il faut :

Depuis 2005

Pour développer des applications perfomantes, il faut :

1) Ecrire des traitements multithreads

2) Programmer chaque traitement (algorithme) en parallèle

Boite à outils

1) Ecrire des traitements multithreads : Java.util.concurrent

2) Programmer chaque traitement (algorithme) en parallèle

???

Boite à outils

Jusqu’en JDK 6 : rien…

Boite à outils

Jusqu’en JDK 6 : rien…

À partir de JDK 7 :

- Fork / Join

- Parallel Arrays : rend le Fork / Join compatible JDK 6

À partir de JDK 8 : les lambdas !

Fork / Join JDK 7 & 6

Que programme-t-on ?

Initialisation du pool

ForkJoinPool pool = new ForkJoinPool() ;

PrimeFactorsFinderRecursiveTask task =

new PrimeFactorsFinderRecursiveTask(1, 4000) ;

ForkJoinTask<PrimeFactors> pfsTask = pool.submit(task) ;

PrimeFactors pfs = pfsTask.get() ; // Eq join

public class PrimeFactorsFinderRecursiveTask

extends RecursiveTask<PrimeFactors> {

private int start, end ;

protected PrimeFactors compute() {

PrimeFactors pfs = new PrimeFactors() ;

if (end - start > MAX_ITERATIONS) { // I’m too big

// processing

ForkJoinTask<PrimeFactors> task = ... ;

task.fork() ;

PrimeFactors pfs = task.get() ;

...

} else {

...

}

return pfs ;

}

}







// processing


task.fork() ;


...

} else {

...

}

return pfs ;

}

}

Sous-tâche

envoyée au pool







// processing


task.fork() ;


...

} else {

...

}

return pfs ;

}

}

Appel à get()

bloquant







// processing


task.fork() ;


...

} else {

...

}

return pfs ;

}

}

Calcul

proprement dit

Quelle stratégie de découpage ?

Au niveau du code // 1ère strategie

if (end - start > MAX_ITERATIONS) { // Trop gros !

int m = (start + end) / 2 ;

PrimeFactorsFinderTask task1 =

new PrimeFactorsFinderTask(start, m) ;

PrimeFactorsFinderTask task2 =

new PrimeFactorsFinderTask(m, end) ;

task1.fork() ;

task2.fork() ;

PrimeFactors pfs1 = task1.join() ;

PrimeFactors pfs2 = task2.join() ;

pfs.add(pfs1) ;

pfs.add(pfs2) ;

}

// 2ème strategie

if (end - start > MAX_ITERATIONS) { // Trop gros !

List<ForkJoinTask<PrimeFactors>> pfsList = new ArrayList<ForkJoinTask<PrimeFactors>>() ; for (int i = start ; i < end – MAX_ITERATIONS ; i += MAX_ITERATIONS) { PrimeFactorsFinderRecursiveTask task = new PrimeFactorsFinderRecursiveTask( i, i + MAX_ITERATIONS) ; task.fork() ; pfsList.add(task) ; } for (ForkJoinTask<PrimeFactors> task : pfsList) { PrimeFactors pfsElement = task.join() ; pfs.add(pfsElement) ; } }

30% plus rapide…

Pièges du Fork / Join

La Java doc nous dit :

Computations should avoid synchronized blocks or methods

Donc si une tâche a un état, cet état doit être transmis aux sous-tâches par copie

Pièges du Fork / Join

La Java doc nous dit :

Computations should avoid synchronized blocks or methods

Donc si une tâche a un état, cet état doit être transmis aux sous-tâches par copie

Quelles conséquences sur les tableaux ?

Impossible avec le Fork / Join

Parallel Arrays JDK 6 & 7

Parallel Arrays

Parallel Arrays : JSR 166y, package extra166y

Dispo en Java 6, embarque le Fork / Join

Inconvénient : en Java 7 on a 2 classes ForkJoinPool, dans deux packages différents

Permet le calcul sur des tableaux de nombres (long ou double)

http://g.oswego.edu/dl/concurrency-interest/

Parallel Arrays

Initialisation

ForkJoinPool pool = new ForkJoinPool() ; // package !

ParralelLongArray a = ParralelLongArray.create(pool) ;

Parallel Arrays

Map :

Ops.LongOp add2 = new Ops.LongOp() {

@Override

public long op(long l1) {

return l1 + 2 ;

}

} ;

a2 = a.withMapping(add2) ;

Parallel Arrays

Filter :

Ops.LongPredicate filter = new Ops.LongPredicate() {

@Override

public boolean op(long l1) {

return l1 > 50 ;

}

}

a2 = a.withFilter(filter) ;

a2.all() ;

Parallel Arrays

Reduce :

Ops.LongReducer reducer = new Ops.LongReducer() {

@Override

public long op(long l1, long l2) {

return l1 + l2 ;

}

}

long reducedValue = a.reduce(reducer, 0L) ;

Parallel Arrays

Idée :

1) On définit des opérations

2) On « pousse » ces opérations vers le ParallelArrays, qui effectue le calcul, en parallèle !

Approche qui ressemble à la programmation fonctionnelle

Bilan pour les JDK 6 & 7

2 outils disponibles :

- Fork / Join, dans le JDK

- Les parallel arrays, API séparée

Pourquoi l’API Parallel Arrays n’est-elle pas dans le JDK ?

Bicoze, dans le JDK 8, on a les …

Et avec les lambdas…

… des nouveaux patterns arrivent !


Map :

List<Personne> personnes = new ArrayList<>() ; personnes.stream() .map(person -> person.getAge())


Filter :

List<Personne> personnes = new ArrayList<>() ; personnes.stream() .map(person -> person.getAge()) .filter(age -> age > 20)


Reduce :

List<Personne> personnes = new ArrayList<>() ; int somme = personnes.stream() .map(person -> person.getAge()) .filter(age -> age > 20) .reduce(0, (a1, a2) -> a1 + a2) ;


Et si on le veut en parallèle :

List<Personne> personnes = new ArrayList<>() ; int somme = personnes.parallelStream() .map(person -> person.getAge()) .filter(age -> age > 20) .reduce(0, (a1, a2) -> a1 + a2) ;

API Stream & Collector

Arrivée de deux API : Stream et Collector

Permettent tous les calculs imaginables sur les collections de grande taille…

En parallèle !

Exemple : tri d’une liste

Stream<String> stream = Stream.generate( () -> Long.toHexString(ThreadLocalRandom.current().nextLong()) ) ; Stream stream = stream1 .map(s -> s.substring(0, 10)) .limit(10_000_000) .sorted() ; Object [] sorted = stream.toArray() ;

Exécution : 14 s

Exemple : tri d’une liste

Stream<String> stream = Stream.generate( () -> Long.toHexString(ThreadLocalRandom.current().nextLong()) ) ; Stream stream = stream1.parallel() .map(s -> s.substring(0, 10)) .limit(10_000_000) .sorted() ; Object [] sorted = stream.toArray() ;

En parallèle : 3,5 s

Exécution : 14 s

Fork / Join, Lambdas

Comment utiliser ces outils efficacement ?

Utilisation

Malheureusement, il ne suffit pas d’appeler parallel() pour que ça marche …

Problèmes

1) Écrire des réductions « correctes »

2) Régler « correctement » l’algorithmique

3) Utiliser des algorithmes « corrects »

1er problème : associativité

Une réduction doit être associative

red(a, red(b, c)) = red(red(a, b), c)




a + (b + c) = (a + b) + c Correct




a + (b + c) = (a + b) + c Correct

(a + (b + c)2)2 = ((a + b) 2 + c)2 Oops !




a + (b + c) = (a + b) + c Correct

(a + (b + c)2)2 = ((a + b) 2 + c)2 Oops !

Le compilateur ou la JVM vont-ils m’aider ?

2ème problème : performance

Le calcul parallèle est-il vraiment plus rapide ?

• Exemple : tri d’une liste de long

long begin = System.nanoTime() ; List<String> hugeList = new ArrayList<>(N) ; // N = 16_000_000 for (int i = 0 ; i < N ; i++) { long l = random.nextLong() ; l = l > 0 ? l : -l ; hugeList.add(Long.toString(l, 32)) ; }

Tri en parallèle

Déroulement :

• Division de la liste en N sous-listes

• Tri de chaque liste sur un cœur : QuickSort

• Fusion des listes triés : MergeSort

Coût : calcul + déplacement des données de cœur en cœur

Performances

2 stratégies de découpage :

• Boucle for

• Dyadique

• Tri avec Collections.sort

CPU Intel core i7, 8 cœurs

Performances

4M

2M

1M

4M

2M

1M

2 tableaux : 16M et 32M de long

Performances

4M 13

2M 12

1M 20

4M

2M

1M

1) La bonne taille du paquet

Performances

4M 13

2M 12

1M 20

4M 33

2M 54

1M 93

1) La bonne taille du paquet … dépend de la taille du tableau !

Performances

4M 13 18

2M 12 20

1M 20 35

4M 33

2M 54

1M 93

2) La stratégie de division est importante !

Performances

4M 13 18

2M 12 20

1M 20 35

4M 33 47

2M 54 125

1M 93 211

2) La stratégie de division est importante ! et dépend de la taille du tableau !

4M 13 18

2M 12 20

1M 20 35

4M 33 47

2M 54 125

1M 93 211

MAIS…

Quelles sont les performances sans parallélisation ?

4M 13 18

2M 12 20

1M 20 35

4M 33 47

2M 54 125

1M 93 211

4M 13 18

2M 12 20

1M 20 35

4M 33 47

2M 54 125

1M 93 211

16M 18

32M 36

Écrire du code parallèle est complexe et coûteux

mais n’amène pas toujours des gains en performance !

3ème problème

Une anecdote

• Le 24/2/2012, Heinz Kabutz défie les lecteurs de son (excellent) blog Java Specialists :

• Calculer les 10 premiers et 10 derniers chiffres du nombre de Fibonacci d’indice 1 milliard

3ème problème

Nombre de Fibonacci

• F0 = 0, F1 = 1

• Fn = Fn – 1 + Fn – 2

F1_000_000 est un nombre trrrès grand !

3ème problème

Record à battre : 5800s (ou 2500 ?) sur un Core i7 à 8 cœurs

3ème problème


1ère amélioration : 3300s sur 4 cœurs

3ème problème


1ère amélioration : 3300s sur 4 cœurs

2ème amélioration : 51s sur 1 cœur (pas de parallélisation)

Où est le miracle ?

Pas de miracle…

- Utilisation de la librairie GNU GMP

- Utilisation d’une bonne implémentation de BigInteger

- Meilleur algorithme de calcul des nombres de Fibonacci

- Suppression de la récursivité

Où est le miracle ?

Pas de miracle…

- Utilisation de la librairie GNU GMP

- Utilisation d’une bonne implémentation de BigInteger

- Meilleur algorithme de calcul des nombres de Fibonacci

- Suppression de la récursivité

Quel rapport avec le parallélisme ??

Algorithmes

Entre 1990 et 2005, l’optimisation linéaire a gagné un facteur 43M

- 1k est du à la rapidité des processeurs

- 43k sont dus à celle des algorithmes

Avant de paralléliser mieux vaut s’assurer

que l’on utilise le bon algorithme

4ème problème

Étude de cas : le voyageur de commerce

Comment résoudre ce problème ?

4ème problème

Étude de cas : le voyageur de commerce

Comment résoudre ce problème

Pas d’algorithme direct, il nous faut une approche « stochastique » (= avec de l’aléatoire)

Et c’est encore un problème de tableaux !

Comment paralléliser ?

Problème de tableau, donc facile !

• On coupe le tableau en morceaux

• On déroule sur chaque morceau

• Et on fusionne

Sauf que …

Ca ne marche pas !

• Les propriétés de convergence sont perdues en parallèle

Sauf que …

Ca ne marche pas !

• Les propriétés de convergence sont perdues en parallèle

Le code compile

Il s’exécute

Le résultat est faux…

Conclusion

Conclusion

• 1975 : le langage C permet de ne plus gérer la pile à la main

Conclusion


• 1995 : Java permet de ne plus gérer la mémoire à la main

Conclusion


• 1995 : Java permet de ne plus gérer la mémoire à la main

• 2013 : Java (encore lui) permet de ne plus gérer le multicœur à la main !

Conclusion

Aujourd’hui le CPU lui-même devient une ressource parmi d’autres, au même titre que la mémoire

Les applications vont pouvoir s’exécuter en parallèle de façon transparente

Conclusion

Oui la parallélisation devient facile, comme elle ne l’a jamais été

• On appele parallel(), et en voiture !

Conclusion



Mais…

Conclusion



Mais…

• Mon traitement est-il plus rapide ?

• Mes résultats sont-ils corrects ?

Conclusion

Il y a quelques années on disait :

« un bon programmeur doit apprendre un nouveau langage tous les N mois / années »

Conclusion

Aujourd’hui mon conseil :

Conclusion


• 1er mois : apprendre le fonctionnement interne des CPU

Conclusion



• 2ème mois : apprendre à programmer les algorithmes complexes

Conclusion



• 2ème mois : apprendre à programmer les algorithmes complexes

• 3ème mois : apprendre la version parallèle de ces algorithmes

Conclusion

La parallélisation des traitements / algorithmes amène

- De nouvelles opportunités

- Des nouveaux problèmes

- De nouvelles catégories de bugs

Conclusion

La parallélisation des traitements / algorithmes amène

- De nouvelles opportunités

- Des nouveaux problèmes

- De nouvelles catégories de bugs

Et donc de nouveaux challenges !

Merci !

Q/R

Documents

Fork / Join, Parallel Arrays, Lambdas : la programmation parallèle (trop ?) facile ! - José paumard Codeurs en seine 2013