Parallélisation des métaheuristiquesSéminaire LOSI – 7 mai 2010

P. Lacomme, C. Prodhon(Equipe Clermont: Duhamel, Lacomme, Equipe UTT: Prins,

Prodhon)

Université de Clermont-Ferrand II, LIMOS, FranceUniversité de Technologie de Troyes, LOSI, France

2

But de l’exposé

Réflexion et travaux en cours (Troyes/Clermont) depuis 6 mois

Première étape pour la parallélisation

Etat d’avancement de nos réflexions

3

Parallélisation de métaheuristiques NVIDIA - CUDA Threads Choix

Mise en oeuvre Implémentation parallèle d’un

GRASPxELS HVRP Expérimentations numériques

Sommaire

4

Métaheuristiques parallèles

5

Quelques publicationsParallel GRASP with path-relinking for job shop scheduling R.M. Aiex, S. Binato, and M.G.C. ResendeParallel Computing, 29:393-430, 2003.

Uma investigação experimental da distribuição de probabilidade de tempo de soluçãoem heurísticas GRASP e sua aplicação na análise de implementações paralelas R.M. AiexPhD thesis, Department of Computer Science, Catholic University of Rio de Janeiro, Rio deJaneiro, Brazil, 2002.

Parallelization strategies for the metaheuristic GRASP A.C.F. AlvimMaster's thesis, Department of Computer Science, Catholic University of Rio de Janeiro, Rio deJaneiro, RJ 22453-900 Brazil, April 1998.

Load balancing in the parallelization of the metaheuristic GRASP A.C.F. Alvim and C.C. RibeiroTechnical report, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro,

RJ22453-900 Brazil, 1998.

Parallel strategies for GRASP with path-relinking R.M. Aiex and M.G.C. ResendeTechnical report, Internet and Network Systems Research Center, AT&T Labs Research, Florham Park, NJ,

2003.

6

Commentaires

Tabou parallèle Grasp parallèle etc…

Aucune métaheuristique parallèle n’est la meilleure méthode publiée

Architecture requise complexe, onéreuse, difficile d’accès.

7

Choix Techniques

8

Approches possibles (1/5)

CUDA Très fort parallélisme Utilise les cartes graphiques NVIDIA Problèmes de mémoire

Parallélisation par threads Exploite le processeur central Largement répandu

9

Approches possibles (2/5)

10

Approches possibles (3/5) Transfert mémoire centrale carte très couteux. Mémoire par thread très limitée Intéressant : faible volume de données

inadapté à la RO (exemple : matrice des distances)

Raksmey Phan, « Prise en main de la technologie CUDApour la programmation sur GPGPU », Projet 3ième annéeISIMAhttp://fc.isima.fr/~phan/ProjetZZ3/TutoCuda.pdf

11

Approches possibles (4/5)

Threads ? QT notion de threads Borland C++, Visual C++, Delphi

notion de threads

Un thread identifiant PUID sous Windows

12

Approches possibles (5/5)

Que faut il savoir sur les threads ?

Exploite le multi-cœurs

Pas de gestion automatique des ressources en exclusion mutuelles

plantage aléatoire débugage très difficile

13

Mise en oeuvre

14

Exemple (1/3)

Un type pointeur pour passer des

informationsà un thread

Le thread est uneprocédure !

15

Exemple (2/2)

16

Exemple (2/3)

17

Exemple (3/3)

18

Définition du temps de calcul

Temps utilisateur <> temps de calcul

Temps utilisateur !

19

Mesurer le CPU Time (1/3)

accéder à la liste des processus tournant sous Windows ;

trouver dans la liste le processus pour lequel on veut mesurer le CPU Time ;

effectuer la mesure

20

Mesurer le CPU Time (2/3)

21

Mesurer le CPU Time (3/3)

22

Mesurer le CPU Time

Voir manuel des bonnes pratiques !

23

Implémentation parallèle d’un GRASPxELS

24

Schéma classique d’optimisation

Determine a QDRS

A quasi-direct representation of solution (QDRS)

A solution S.

Improved solution S’fA quasi-direct

representation of solution (QDRS)

Heuristics dedicated to the

problem

A solution S.

f

A quasi-direct representation of solution (QDRS)

Initial set of QDRS

Initialization of the framework

Diversification Process

Local Search(LS)

f

Improvement of solution Framework iterations

25

Tournées de véhicules : deux espaces de recherche

Split

Concat

metaheuristic search space A routing solution

26

Proposition de parallèlisation

Solution

Random Sampling

Evolutionary Local Search

np GRASP iterations

Greedy randomized heuristic

Local Search

Solution S

Divide and conquert

Solution Solution Solution

Mutation

Local Search

Solution

Mutation

Local Search

Solution

Mutation

Local Search

Solution

ni ELS iterations

nc children-solutions

S replaced by best child in case of improvement

Selection

n ELS en parallèle

Synchronisation des n ELS

Redémarrage avec la meilleure sol. Commune aux n ELS

27

ExempleS0 : 10 324

Best sur 10 : 10 075

Best sur 10 : 9 633

Best sur 10 : 9 607

Best sur 10 : 9 545

Best sur 10 : 9 546

Best sur 10 : 9 884

Best sur 10 : 9 606

Best sur 10 : 9 536

Best sur 10 : 9 630

Best sur 10 : 9 636

Best sur 10 : 9 764

Best sur 10 : 9 696

Best sur 10 : 9 687

Best sur 10 : 9 618

Best sur 10 : 9 608

Best sur 10 : 9 759

Best sur 10 : 9 592

Best sur 10 : 9 592

Best sur 10 : 9 393

Best sur 10 : 9 287

Processeur 1 Processeur 2 Processeur 3 Processeur 4

Pour chaque processeur, on garde les 10 meilleurs

Les 4 meilleures solutions : 9287 (processeur 4), 9330 (P4), 9336 (P4), ??? (P??)

Best sur 10 : 9 881

Best sur 10 : 9 515

Best sur 10 : 9 390

Best sur 10 : 9 389

Best sur 10 : 9 386

Processeur 1Depart depuis:

9287Depart depuis:

9330

Best sur 10 : 9 881

Best sur 10 : 9 515

Best sur 10 : 9 390

Best sur 10 : 9 389

Best sur 10 : 9 386

Etc... Etc...

Depart depuis: 9336

28

Tests Numériques VFMP … HVRP

29

HVRP (1/3)

VRP + flotte hétérogène de véhicules Un dépôt : nœud 0 n nœuds (clients)

dj demande du nœud j

Cij coût du nœud i à j

Flotte de K types de véhicules Un type de véhicules nk véhicules Un type de véhicules Qk capacité des véhicules

30

Résultats publiés – HVRP

31

Nouvelles instances

32

Création

Géocodeur crée par Viannez Bajart et Christophe Charles – ISIMA – F2 3ième année

Utilise Google Api

Java + JavaScript

33

Présentation (1/5)

http://www.isima.fr/~lacomme/students.html

34

Présentation (2/5)

96 départements métropolitains

20 à 300 nœuds Distances non euclidiennes 8 types de véhicules

4 paquets d’instances < 100 nœuds DLP_HVRP_1 De 100 à 150 nœuds DLP_HVRP_2 De 150 à 200 nœuds DLP_HVRP_3 + de 200 noeuds DLP_HVRP_4

35

Présentation (3/5)

36

Présentation (4/5)

37

Présentation (5/5)

38

L’auvergne….

39

L’Aube…

40

Nightmare instances

41

GRASPxELS solutions (2/2)

Solutions de 5 à 35 trips

42

Machine de test

43

Machine (1/2)

Windows Server 2003

serveur HP proliant DL 785 G5

mémoire : 256 Go (PC2-5300 Registered DDR)

8 processeurs AMD Opteron™ 8356 quadricoeur (2,3 GHz, 75 W ACP)

44

Machine (2/2)

4 threads temps de communication nul 8 threads facteur de ralentissement de 2 16 threads facteur de ralentissement de 4 32 threads facteur de ralentissement de 8

BUS

45

Résultats numériques

46

Petites instances (1/3)

47

Petites instances (2/3)

Comparative study between total time and best time

0

200

400

600

800

1000

1200

1400

1600

1800

2000

1P 2P 4P 8P 16P 32P

Best time

Total time

48

Petites instances (3/3)

% of best solutions

0

10

20

30

40

50

60

70

80

90

100

1P 2P 4P 8P 16P 32P

49

Instances de taille moyenne (1/2)

Comparative study between the total time and the best time

0

200

400

600

800

1000

1200

1400

1600

1800

2000

1P 2P 4P 8P 16P 32P

50

Instances de taille moyenne (2/2)

% of best solutions

0,0

10,0

20,0

30,0

40,0

50,0

60,0

70,0

80,0

90,0

100,0

1P 2P 4P 8P 16P 32P

51

Tests - Conclusion

Architecture matérielle impact sur les temps de calcul

Grand intérêt de la paralélisation

Résultats intéressants qualité de résultats + convergence

52

Conclusion

53

Conclusion (1/2)

« Nos »premiers pas en méthode parallèle

Attention aux pièges

Intérêt démontré

54

Conclusion (2/2)

Alternative crédible à Cuda

Fort potentiel généralisation des architectures multi-cœurs

Demande une grosse expertise