Hlib Mykhailenko a soutenu sa thèse de doctorat le mercredi 14 juin 2017 à 14:30, à l’Inria, salle Euler violet.
Titre: Partitionnement réparti basé sur les sommets
Jury:
- Rapporteurs:
- Pietro Michardi (Eurecom)
- Matteo Sereno (Università degli Studi di Torino)
- Directeur de thèse:
- Fabrice Huet (University of Nice-Sophia Antipolis)
- Examinateurs:
- Guillaume Urvoy-Keller (Laboratory I3S)
- Damiano Carra (University of Verona)
- Giovanni Neglia (Inria Sophia Antipolis)
Résumé:
Pour traiter un graphe de manière répartie, le partitionnement est une étape préliminaire importante car elle influence de manière significative le temps final d\u2019exécutions. Dans cette thèse nous étudions le problème du partitionnement réparti de graphe. Des travaux récents ont montré qu’une approche basée sur le partitionnement des sommets plutôt que des arrêtes offre de meilleures performances pour les graphes de type power-laws qui sont courant dans les données réelles. Dans un premier temps nous avons étudié les différentes métriques utilisées pour évaluer la qualité d’un partitionnement. Ensuite nous avons analysé et comparé plusieurs logiciels d’analyse de grands graphes (Hadoop, Giraph, Giraph++, Distributed GrahpLab et PowerGraph), les comparant à une solution très populaire actuellement, Spark et son API de traitement de graphe appelée GraphX. Nous présentons les algorithmes de partitionnement les plus récents et introduisons une classification. En étudiant les différentes publications, nous arrivons à la conclusion qu’il n’est pas possible de comparer la performance relative de tout ces algorithmes. Nous avons donc décidé de les implémenter afin de les comparer expérimentalement. Les résultats obtenus montrent qu’un partitionneur de type Hybrid-Cut offre les meilleures performances. Dans un deuxième temps, nous étudions comment il est possible de prédire la qualité d’un partitionnement avant d’effectivement traiter le graphe. Pour cela, nous avons effectué de nombreuses expérimentations avec GraphX et effectué une analyse statistique précise des résultats en utilisation un modèle de régression linéaire. Nos expérimentations montrent que les métriques de communication sont de bons indicateurs de la performance. Enfin, nous proposons un environnement de partitionnement réparti basé sur du recuit simulé qui peut être utilisé pour optimiser une large parte des métriques de partitionnement. Nous fournissons des conditions suffisantes pour assurer la convergence vers l’optimum et discutons des métriques pouvant être effectivement optimisées de manière répartie. Nous avons implémenté cet algorithme dans GraphX et comparé ses performances avec JA-BE-JA-VC. Nous montrons que notre stratégie amène à des améliorations significatives.
