Parall elisation de l’algorithme TwigStack sur carte graphique · 2018. 3. 3. · Lewis Carroll 3

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



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


N



<?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



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



N



Exemple de requete

Requete




Reponse



N



Exemple de requete

Requete




Reponse



N



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


N




Plan





N




Arbre de la requete XPath

Element

Attribut

Text

library

category

book

title

@language

English

@name

France


parseurXPath


N




Chemins de la requete XPath

library

category

book

title

@language

English

@name

France

library

category

@name

France

library

category

book

title

@language

English


N




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


N




Plan





N




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


N




Plan





N




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


N





library

category

book@name

France

English

title

@language



1 2 5 6


Piles des noeudsde l'arbre de requête 7 8


N





library

category

book@name

France

English

title

@language



1 15 18 19


Piles des noeudsde l'arbre de requête20 21


N





<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>[...]


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]


N




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


N




Plan





N




Parallel TwigStack

A Study on Parallel Holistic Twig Joins for XML QueryProcessing

Imam MachdiPhD dissertation at Kitagawa Data Engineering lab., March 2010


N



Liens entre l’architecture materielle et logicielleDifficultees de debuggage

Plan





N




Architecture materielle


N




Architecture logicielle

...Grid

Block

Warp

Thread

Execution du code GPU depuis le code CPU

myCUDAKernel<<gridSize, blockSize>>(int* arg1, ...);


N




Liens entre les representations materielle et logicielle

... ...

⬇ représentation logicielle

représentation matérielle⬊


N




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


N




Plan





N




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.


N












N












N












N












N












N




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.


N



Parallelisation de TwigStack sur carte graphiquePour surmonter les limitations du GPUAmeliorations futures

Plan





N




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


N




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


N




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⁴⁹>



N




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


N




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

)


N




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


N




Plan





N




”Memory pool”

mémoire globale GPUbitfield des morceaux de mémoireverrou du

bitfield


N




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);


N




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)


N




Plan





N




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?


N




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


N




質問がありますか？

Des questions ?


N

Documents

Parall elisation de l’algorithme TwigStack sur carte graphique · 2018. 3. 3. · Lewis Carroll 3