View
4
Download
0
Category
Preview:
Citation preview
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de l’algorithme TwigStack sur cartegraphique
ST50 et Master AHPM - Projet de fin d’etudes
Vincent Jordan GI ILC
Suiveur en entreprise : Hiroyuki KitagawaSuiveur UTBM : Fabrice Lauri
14 decembre 2010
KDEDataBaseLab.
1 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
2 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
<?xml version="1.0" encoding="UTF-8" ?>
<library>
<category name="France">
<book>
<title language="English">The Little Prince</title>
<title language="日本語">星の王子さま</title>
<author>Antoine de Saint-Exupery</author>
</book>
</category>
<category name="England">
<book>
<title language="English">Alice in Wonderland</title>
<title language="日本語">ふしぎの国のアリス</title>
<author>Lewis Carroll</author>
</book>
</category>
</library>3 / 42
Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Exemple de requete
Requete
Quel est le titre en anglais des livres francais de la bibliotheque?
Requete XPath correspondante
/library/category[@name=France]/book/title[@language=English]
Reponse
<title language="English">The Little Prince</title>
4 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Exemple de requete
Requete
Quel est le titre en anglais des livres francais de la bibliotheque?
Requete XPath correspondante
/library/category[@name=France]/book/title[@language=English]
Reponse
<title language="English">The Little Prince</title>
4 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Exemple de requete
Requete
Quel est le titre en anglais des livres francais de la bibliotheque?
Requete XPath correspondante
/library/category[@name=France]/book/title[@language=English]
Reponse
<title language="English">The Little Prince</title>
4 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Algorithme de calcul des requetes XML
Holistic twig joins: optimal XML pattern matching
Nicolas Bruno, Nick Koudas, Divesh SrivastavaInternational Conference on Management of DataProceedings of the 2002 ACM SIGMOD international conference on Managementof data
5 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
6 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Arbre de la requete XPath
Element
Attribut
Text
library
category
book
title
@language
English
@name
France
/library/category[@name=France]/book/title[@language=English]
parseurXPath
7 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Chemins de la requete XPath
library
category
book
title
@language
English
@name
France
library
category
@name
France
library
category
book
title
@language
English
8 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
metadonnees XML
<library1>
<category2
name3="France4">
<book6>
<title7
language8="English9">
The11 Little12 Prince13
</title14>
</book15>
</category16>
</library17>
valeur gch drt proflibrary 1 17 0
category 2 16 1
book 6 15 2
title 7 14 3
name 3 5 2
language 8 10 4
France 4 4 3
English 9 9 5
The 11 11 4
Little 12 12 4
Prince 13 13 4
9 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
10 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
elem1/elem2[@arg1=text1][/elem3=text2]
requête XPath
fichier dedonnées XML
data
.xm
l
elem1
elem2
elem3@arg1
text1 text2
elem1
elem2
elem3
text2
elem1 1
2
3
4
5
18
17
10
6
5
0
1
2
3
4
arbre de la requête
metadonnées
...
arbre de requêteavec metadonnées
(1,18,0)...
(3,10,2)...
(4,6,3)...
(5,5,4)...
(8,8,3)...
(9,9,4)...
??
Phase 1Phase 2
Liste dechemins =résultatintermédaire
Liste d'arbres= résultat final
algorithme TwigStack
11 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
12 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
L’encodage compact sous forme de pile 1
library
category
book@name
France
English
title
@language
<library¹> <category² name³="France⁴"> <book⁵> <title⁶ language⁷="English⁸">The⁹ [...]</title¹²> </book¹³> </category¹⁴> <category¹⁵ name¹⁶="England¹⁷"> <book¹⁸> <title¹⁹ language²⁰="English²¹">Alice²² [...]</title²⁵> </book²⁶> </category²⁷></library²⁸>
library category book title @name @language France English
1 2 3 4
arbre de requête Données XML
Piles des noeudsde l'arbre de requête
13 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
L’encodage compact sous forme de pile 2
library
category
book@name
France
English
title
@language
<library¹> <category² name³="France⁴"> <book⁵> <title⁶ language⁷="English⁸">The⁹ [...]</title¹²> </book¹³> </category¹⁴> <category¹⁵ name¹⁶="England¹⁷"> <book¹⁸> <title¹⁹ language²⁰="English²¹">Alice²² [...]</title²⁵> </book²⁶> </category²⁷></library²⁸>
library category book title @name @language France English
1 2 5 6
arbre de requête Données XML
Piles des noeudsde l'arbre de requête 7 8
14 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
L’encodage compact sous forme de pile 3
library
category
book@name
France
English
title
@language
<library¹> <category² name³="France⁴"> <book⁵> <title⁶ language⁷="English⁸">The⁹ [...]</title¹²> </book¹³> </category¹⁴> <category¹⁵ name¹⁶="England¹⁷"> <book¹⁸> <title¹⁹ language²⁰="English²¹">Alice²² [...]</title²⁵> </book²⁶> </category²⁷></library²⁸>
library category book title @name @language France English
1 15 18 19
arbre de requête Données XML
Piles des noeudsde l'arbre de requête20 21
15 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
L’encodage compact sous forme de pile 4
<library¹> <category² name="by country"> <category⁶ name="Europe"> <category¹⁰ name="Western Europe"> <category¹⁴ name="France"> <book¹⁷> <title¹⁸ language¹⁹="English²⁰">The Little Prince</title> </book> </category> </category>[...]
library category book title @name @language France English
Piles des noeudsde l'arbre de requête1 2 1817 19 20
Le même tag XMLpeut être inclu
61014
!
/library//category[@name=France]//book/title[@language=English]
16 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Fusion (phase 2)
(1,48,0)
(2,26,1)
(3,3,2)
(4,4,3)
(5,25,2)
(6,12,3)
(7,7,4)
(8,8,5)
(1,48,0)
(2,26,1)
(30,47,2)
(31,37,3)
(32,32,4)
(33,33,5)
(1,48,0)
(27,48,1)
Ces noeudspeuvent être fusionnés
en fonctionde l'arbre de requête
17 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
18 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Pre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
Parallel TwigStack
A Study on Parallel Holistic Twig Joins for XML QueryProcessing
Imam MachdiPhD dissertation at Kitagawa Data Engineering lab., March 2010
19 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
20 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Architecture materielle
21 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Architecture logicielle
...Grid
Block
Warp
Thread
Execution du code GPU depuis le code CPU
myCUDAKernel<<gridSize, blockSize>>(int* arg1, ...);
22 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Liens entre les representations materielle et logicielle
... ...
⬇ représentation logicielle
représentation matérielle⬊
23 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Une architecture massivement parallele
Les tailles de Warp, block et grid ont des limites materielles
1 Taille d’un Warp: 32
2 Nombre maxi de thread par blocks : 512 (ou 16 warps)
3 Nombre maxi de thread actif simultanement pour chaquemultiprocesseur : 1024
4 Nombre maxi de warp sur un multiprocesseur : 32
5 Nombre maxi de block sur un multiprocesseur : 8
Exemple
32 threads x 4 warps x 8 blocks x 24 multiprocesseurs = 24.576
24 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
25 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Limitations de l’architecture materielle ”Tesla”
Architecture SIMT ”Single Instruction Multiple Threads”: Tousles threads dans le meme warp executent exactementla meme instruction au meme moment.
Pas d’appel de function Toutes les functions sont inlinees aumoment de la compilation. Les fonctions recursivesde sont pas autorisees.
Pas d’allocation dynamique de memoire Toute la memoire doitetre allouee avant l’execution.
Pas de synchronisation entre les threads Il n’est pas recommended’implementer une ”section critique”.
Pas de cache materiel chaque acces a la memoire globale coutedes centaines de cycles GPU.
Pas de pointeur sur la memoire locale cette possibilite ne dependque du compilateur.
26 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Liens entre l’architecture materielle et logicielleDifficultees de debuggage
Difficultes de debuggage consecutives a ces limitations
Les functions sont inlinees Pas de ”backtrace” des fonctions.
Pas d’appel de function Pas de ”printf”.
Pas d’allocation de memoire dynamique De gros morceaux dememoire sont alloue. Les mauvais acces memoire seproduisent souvent dans de la memoire allouee et nedeclanche pas d’erreur.
27 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
28 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
elem1/elem2[@arg1=text1][/elem3=text2]
requête XPath
fichier dedonnées XML
data
.xm
l
elem1
elem2
elem3@arg1
text1 text2
elem1
elem2
elem3
text2
elem1 1
2
3
4
5
18
17
10
6
5
0
1
2
3
4
arbre de la requête
metadonnées
...
arbre de requêteavec metadonnées
(1,18,0)...
(3,10,2)...
(4,6,3)...
(5,5,4)...
(8,8,3)...
(9,9,4)...
??
Phase 1Phase 2
Liste dechemins =résultatintermédaire
Liste d'arbres= résultat final
algorithme TwigStack
29 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
fichier decreationBD
fichier dedonnéesXML
fichier d'insertionBD
requêteXPath
A
B
Ca//b[c=d]
<?xml versi<a type="ma
CREATE TABLINSERT FROM
'a', 1, 15'b', 2, 7
générateurmetadonnées
sqlite3
ParseurXPath
Lecteurmetadonnées
AlgorithmeTwigStack
moteur de requêtes
sortie
incluparseurlibXML SAX
utiliseflex tockenizeurlemon parseurgenerateurs
incluclient BDsqlite3
incluruntimeCUDA
entrée
30 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Initialisation (→ CPU)
library
category book
@name
France
English
title
@language
(1,48,0)
(27,48,1) (2,26,1)
(5,25,2) (30,47,2)(28,28, 2) (3,3,2)
(4,4,3)
(6,12,3) (13,17,3) (31,37,3) (38,42,3)
(7,7,4) (14,14,4) (32,32,4) (39,39,4)
(8,8,5) (33,33,5)
<library¹> <category² name³="France⁴"> <book⁵> <title⁶ language⁷="English⁸">The⁹ [...]</title¹²> <title¹³ language¹⁴="日本語¹⁵">星の王子さま¹⁶</title¹⁷> <author¹⁸>Antoine¹⁹ de²⁰ Saint-Exupéry²¹</author²²> </book²⁵> </category²⁶> <category²⁷ name²⁸="England²⁹"> <book³⁰> <title³¹ language³²="English³³">Alice³⁴ [...]</title³⁷> <title³⁸ language³⁹="日本語⁴⁰">ふしぎの国のアリス⁴¹</title⁴²> <author⁴³>Lewis⁴⁴ Carroll⁴⁵</author⁴⁶> </book⁴⁷> </category⁴⁸></library⁴⁹>
/library/category[@name=France]/book/title[@language=English]
31 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Partitionnement (→ CPU)
library
category book
@name
France
English
title
@language
(1,58,0)
(27,57,1) (27,57,1) (2,26,1)
(5,25,2) (30,56,2) (30,56,2)(28,28, 2) (3,3,2)
(4,4,3)
(6,12,3) (13,17,3) (31,37,3) (38,42,3) (43,51,3)
(7,7,4) (14,14,4) (32,32,4) (39,39,4) (44,44,4)
(8,8,5) (33,33,5)
<library¹> <category² name³="France⁴"> <book⁵> <title⁶ language⁷="English⁸">The⁹ [...]</title¹²> <title¹³ language¹⁴="日本語¹⁵">星の王子さま¹⁶</title¹⁷> <author¹⁸>Antoine¹⁹ de²⁰ Saint-Exupéry²¹</author²²> </book²⁵> </category²⁶> <category²⁷ name²⁸="England²⁹"> <book³⁰> <title³¹ language³²="日本語³³">ふしぎの国のアリス³⁴</title³⁵> <title³⁶ language³⁷="English³⁸">Alice³⁹ in⁴⁰ wonderland⁴¹</title⁴²> <title⁴³ language⁴⁴="Français⁴⁵">Alice⁴⁶ au⁴⁷ pays⁴⁸ des⁴⁹ merveilles⁵⁰</title⁵¹> <author⁵²>Lewis⁵³ Carroll⁵⁴</author⁵⁵> </book⁵⁶> </category⁵⁷></library⁵⁸>
partition 1
partition 2
!(1,48,0);(27,57,1);(30,56,2) sont dupliqués carils sont nécessaire aux 2 partitions
32 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Execution de la phase 1 en parallele (→ GPU)
library
category
book@name
France
English
title
@language
(1,48,0)
(2,26,1)
(5,25,2)(3,3,2)
(4,4,3)
(6,12,3) (13,17,3)
(7,7,4) (14,14,4)
(8,8,5)
library
category
book@name
France
English
title
@language
(1,48,0)
(27,48,1)
(30,47,2)(28,28, 2)
(31,37,3) (38,42,3)
(32,32,4) (39,39,4)
(33,33,5)
thread 1 thread 2(1
,48,
0)
(2,2
6,1)
(3,3
,2)
(4,4
,3)
(5,2
5,2)
(6,1
2,3)
(7,7
,4)
(8,8
,5)
(1,4
8,0)
(2,2
6,1)
(30,
47,2
)
(31,
37,3
)
(32,
32,4
)
(33,
33,5
)
(1,4
8,0)
(27,
48,1
)
33 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Phase 2 : fusion (→ CPU)
(1,48,0)
(2,26,1)
(3,3,2)
(4,4,3)
(5,25,2)
(6,12,3)
(7,7,4)
(8,8,5)
(1,48,0)
(2,26,1)
(30,47,2)
(31,37,3)
(32,32,4)
(33,33,5)
(1,48,0)
(27,48,1)
Ces noeudspeuvent être fusionnés
en fonctionde l'arbre de requête
34 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
35 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
”Memory pool”
mémoire globale GPUbitfield des morceaux de mémoireverrou du
bitfield
36 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Structure de donnees v array
entête cases
de nouvelles cases peuvent être ajoutées en tête ou en fin de tableauavec un coût faible en accès mémoire.
NULL
NULL
pointeur surle tableau
0 1 2 3 4 5 6
Envoi d’un v array de la memoire CPU vers la memoire GPU
v_array_post_copy(
q_data->metadata_elems,
&cuda_malloc_func,
NULL, /* malloc function arg. (e.g memory pool) */
&cuda_memcpyH2D_func);
37 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Concu pour les GPU
1 Tous les morceaux de tableau ont la meme taille (→ gestionaire dememory)
2 Les morceaux de tableau contiennent vraiment les donnees(utilisation de memcpy), pas de pointeur (→ alignement qui permetune lecture de la memoire plus efficace)
3 Tres parametrable : les fonctions malloc, memcpy et free sontdonnees en parametre.Le meme code source peut etre utilise pour la partie CPU ainsi quepour la partie GPU (meme pour les transferts memoires”CPU→GPU” et ”GPU→CPU”).
4 Dans le cas ou chaque morceau contient 32 cases, un warp peuttravailler en utilisant 1 thread par case (pour une actionparallelisable)
38 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Plan
1 L’algorithme TwigStackPre-calcul des donneesSchema global de l’algorithmeL’encodage compact sous forme de pileParallelisation de TwigStack
2 L’architecture des cartes graphiques NVidiaLiens entre l’architecture materielle et logicielleDifficultees de debuggage
3 L’implementation effectueeParallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
39 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
Ameliorations futures
Memory pool ameliorer la gestion de la memoire libre (un simple”bitfield” pour l’instant)
XMalloc: A Scalable Lock-free Dynamic Memory Allocatorfor Many-core Machines
Xiaohuang Huang, Christopher I. Rodrigues, Stephen Jones, Ian Buck, andWen-mei HwuProceedings of the First International Workshop on Frontier of GPUComputing (FGC), in conjunction with the 10th IEEE International Conferenceon Computer and Information Technology (CIT 2010), June 2010.
Memoire partagee Un morceau de tableau pourrait etre stockeautomatiquement en memoire partagee
Parallelisation de la phase 2 (task parallelism)
Utiliser les 31 threads restant dans un warp?
40 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
mémoire globaleGPU
memory pool
mémoire allouée pendantl'exécution sur GPU
mémoire allouée avantl'exécution sur GPU
mémoire partagée
multicœur
copie de la mémoire globalevers la mémoire partagée
41 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
L’algorithme TwigStackL’architecture des cartes graphiques NVidia
L’implementation effectuee
Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures
質問がありますか？
Des questions ?
42 / 42Parallelisation de l’algorithme TwigStack sur carte graphique
N
Recommended