Réunion ANR - GCPMF15/01/2008

Xavier WARIN (EDF R&D - OSIRIS)Stéphane VIALLE (SUPELEC - IMS)

Constantinos MAKASSIKIS (SUPELEC - IMS, LORIA - AlGorille)

Distribution large échelle d’un algorithme financier de contrôle

stochastique

CIGC05 - GCPMF

2

Introduction

1

3

Introduction

• Objectif : Présentation de la distribution d’une application financière de valorisation d’actifs de stockage de gaz réalisée avec EDF.

• Application utilisée dans des projets d’investissements :– calcule le prix de location optimal d’un actif de

stockage;– utilise des modèles de prix complexes gourmands

en ressources et nécessitant une calibration.

4

Introduction

• Solution : distribution/parallélisation.– pour accélerer et passer à l’échelle

• Par rapport applications de type Bag of Tasks, mise en jeu :– de calculs intensifs ET– des communications fréquentes : redistribution régulière

de données et de résultats nécessite une optimisation des échanges de données

5

Contexte financier

2

6

Contexte financier

• Actif de stockage de gaz :– Cavité où est stocké le gaz

– Matériel (pompes, …) pour injecter/sous-tirer

– Contraintes de fonctionnement diverses

• Fluctuations des prix du gaz :– Cause : modification de la demande (hiver, été)– Conséquence : possibilité d’arbitrer pour profiter de la

dynamique des prix → valorisation

Gaz

OUT

IN

7

• La valorisation fait appel à :– des algorithmes de contrôle stochastique– des modèles de prix variés

Contexte financier

Dans notre cas le propriétaire veut déterminer à quel prix il va louer une partie de son actif. Pour ce faire, il se fonde sur les résultats potentiels de différentes stratégies de gestion qu’il aurait pu appliquer sur la portion louée s’il ne l’avait pas louée.

8

Distribution del’algorithme

3

9

Algorithme séquentiel

tn-1t0

Aujourd’hui Futur

tnCalculs

Stochastiques

Prix de location

à t0

Hypothèsesde terminaison

10

Algorithme séquentiel

• Pour chaque pas de temps (de tn-1 à t0)

• Pour chaque niveau de stock admissible

– Calcul complexe pour déterminer la meilleure décision à prendre au temps ti avec un niveau de stock si :

« Injecter, ne rien faire ou soutirer ? »

11

Difficultés de parallélisation

• Pour chaque pas de temps (de tn-1 à t0)

• Pour chaque niveau de stock admissible

– Calcul complexe pour déterminer la meilleure décision à prendre au temps ti avec un niveau de stock si :

« Injecter, ne rien faire ou soutirer ? »

• La parallélisation au niveau de la boucle la plus externe est impossible à cause des dépendances de l’algorithme.

• Le niveau le plus intéressant se trouve au niveau de la boucle sur les niveaux de stock.

12

Structures de données

• A chaque pas de temps utilisation de deux tableaux : OldRes et NewRes.

• OldRes : contient les résultats du pas de temps précédent.

• NewRes : pour mémoriser les résultats du pas de temps courant.

• Problème : à chaque pas de temps le travail s’effectue sur une zone contiguë mais à bornes variables.

Niveaux de stock

Alé

as d

e pr

ix

Calculs

NewRes

OldResRésultats à ti+1

Résultats à ti

A ti :

13

DevientRedistribution

Schéma de parallélisation

• En séquentiel, on peut se placer dans le cas ci-contre.

Solution 1 : • réplication des tableaux.• broadcast.

ti+1 :

ti :

Solution 2 :• optimisation de la taille des tableaux.• redistribution de ce qui est nécessaire.

NewRes

OldRes

NewRes

Calculs

• En parallèle :

14

Schéma de parallélisation

ti :

ti+1 :P2P1P0 Res à ti+1

P1 P2P0

P1 P2P0

P2P1P0

P2P1P0

BA

C D

1) Déterminer la nouvelle distribution des calculs à ti

3) Déterminer les données à envoyer par P1

2) Déterminer les données requises à ti par P1

5) Effectuer les communications selon le plan de routage (MPI)

6) Calculer Res à ti

P0 P1C A D

P2

- A BReceiveSend

4) Allouer structures de données de taille optimale

Sur P1:

Res à ti

Plan deroutage

15

Implémentations

4

16

Implémentations

• Deux implémentations :• (1) en Python avec MPI et C++ :

– Priorité au confort de l’utilisateur (paramétrage, visualisation …)

– Interfaçage Python/C++

– Interfaçage Python/MPI

• (2) en C++ avec MPI– Priorité à la performance– 3 versions : MPI_Bsend(), MPI_Ibsend() et MPI_Issend()

17

Etude des performances

5

18

Evaluation des performances

• Utilisation de la 2ième implémentation (MPI_Issend())• Expérimentations sur 3 architectures distribuées :

– Deux clusters de PCs (SUPELEC et GRID’5000/Sophia).

– Le supercalculateur Blue Gene/L de EDF R&D.

• Avec 3 modèles de prix du gaz :

********Gaussien 2 facteurs « G-2f »

***Normal Inverse Gaussien « NIG »

**Gaussien « G »

MémoireCalculs Besoins

Modèle

19

1,E+00

1,E+01

1,E+02

1,E+03

1,E+04

1 10 100 1000

Number of processors

Ex

ec

uti

on

tim

e (

s)

G on Blue Gene 1p/node

G on P4 cluster

G on Opteron cluster 1p/node

Performances avec « G »

8

15s64 1024

54min

14min

20

1,E+00

1,E+01

1,E+02

1,E+03

1,E+04

1,E+05

1,E+06

1 10 100 1000

Number of processors

Ex

ec

uti

on

tim

e (

s)

NIG on Blue Gene 2p/nodeNIG on P4 clusterNIG on Opteron cluster 2p/node

Performances avec « NIG »

128 1024

3min

6h40

21

Performances avec « G-2f »

• Besoin de beaucoup de mémoire– 11 Go pour l’exécution séquentielle – 10 CPUs avec 2 Go en parallèle

• Exécution rendue possible par notre distribution.

• Scale jusqu’à 1024 processeurs.

• Limitation :– Impossible de calculer un speedup rigoureux.– Donc étude d’extensibilité (seulement).

22

Performances avec « G-2f »

Blue Gene wins !

1,E+03

1,E+04

1,E+05

10 100 1000 10000

Number of processors

Ex

ecu

tio

n t

ime

(s

)

Blue Gene 2p/nodeBlue Gene 1p/nodeOpteron cluster 2p/nodeOpteron cluster 1p/nodeP4 cluster 1p/node

128

1024

16

14h

2h20

46min

23

Etude d’extensibilité avec « G-2f »

0

50

100

150

200

250

300

0,000,250,500,751,001,251,501,752,002,25

q-discretization (MWatt)

Re

qu

ire

d n

um

be

r o

f p

roc

es

so

rs

G-2f on Blue Gene 2p/node

G-2f on Opteron cluster 2p/node

Fine simulationsRough simulations

13052€

13589€

13870€

11065€

Accuracy level

Maintient du temps d’exécution à 12 000 secondes

24

Conclusion

6

25

Conclusion & Perspectives

• Algorithme itératif de contrôle stochastique dynamique avec distribution à chaque pas de temps des calculs et des données.

• Résultats issus des expérimentations témoignent de l’efficacité de notre distribution sur clusters de PCs (128 CPUs) et supercalculateur (1024 CPUs)– Accéleration de l’exécution sur trois modèles de prix aux

caractéristiques variées

– 2 modèles de référence et 1 nouveau modèle

26

Version n-dimensionnelle distribuée

Depuis octobre 2007 (EDF & Supélec) :

• Distribution d’une version de « contrôle stochastique multistocks » Distribution d’hypercubes de données et de calculs…

• Application à la gestion dynamique du portefeuille EDF : “ maximisation de l'espérance des gains liés à la gestion de stocks

d'eau et de stocks de produits à terme sous respect de contrainte de satisfaction de la demande. ”

WP6 : Contrôle stochastique en grande dimension.

• Vers une généralisation à N dimensions de la distribution d’un algorithme de contrôle stochastique

27

I. A chaque pas de temps :– Intersections et répartitions

d’hypercubes– Provisioning dynamique

des processeurs– Sauvegardes de résultats

intermédiaires

II. Simulations de Monte Carlo à partir des résultats intermédiaires : embarrassingly parallel

Version n-dimensionnelle distribuée

temps

Ti+1 Ti

Trajectoires deMonte Carlo

Une application plus complexe en deux parties :

28

Version n-dimensionnelle distribuée

• Un cas test sur 7 stocks dure :– 18 h sur les 32 PCs du cluster de SUPELEC ;– 5h30 sur 1024 nœuds de Blue Gene.

Les temps de calcul restent longs ... besoin de tolérance aux pannes.

Texec : opti15_dispo

0100002000030000400005000060000700008000090000

0 512 1024 1536 2048 2560 3072 3584 4096

Number of processors : P

Te

xe

c(P

) (

s)

Texec(P)

Tcalc-sh-cluster

29

Questions ?

?

30

31

32

Environnements d’expérimentation

Cluster SUPELEC32 nœuds monoprocesseurProcesseur: Pentium 4 à 3.0 GHz Mémoire vive: 2 GBRéseau d’interconnexion: Gigabit Ethernet

Cluster Grid’5000 (Sophia, Azur)72 nœuds biprocesseursProcesseur: Opteron 246 à 2.0 GHz Mémoire vive: 2 GB (partagés)Réseau d’interconnexion: Gigabit Ethernet

33

Environnements d’expérimentation

Blue Gene/L de EDF R&D4096 nœuds biprocesseursProcesseur : PowerPC à 700 MHz (faible consommation)Mémoire vive : 1 GB (partagé)Réseau d’interconnexion : Gigabit Ethernet ++

34

Quelle machine pour quel modèle ?

• Les performances permettent de proposer une architecture d’exécution adaptée selon le modèle envisagé :