Analyse et exploration de graphes

Le calcul se fait habituellement avec un réseau dont l’état ne varie pas durant l’entier du processus. Mais de nouvelles connexions apparaissent constamment et ces dernières ne sont prises en compte que lors de l’initiation d’un nouveau calcul. Elles ne sont ainsi reflétées que tardivement dans le résultat.

Ce projet vise à inclure de nouvelles connexions lors du processus de calcul. Leur effet devient ainsi visible quasi immédiatement : si, par exemple, la durée de voyage sur un tronçon d’autoroute augmente suite à un accident, on peut immédiatement en tenir compte et indiquer une voie alternative plus rapide. Les chercheurs travaillent également à rendre ce mode de calcul possible non seulement sur de coûteux super-ordinateurs mais aussi sur des serveurs conventionnels.

Le calcul sur les réseaux cherche à extraire de l’intelligence à partir des connexions qu’établissent entre elles les entités d’un réseau. Le choix des annonces publicitaires présentées, par exemple, à un utilisateur de Facebook se base sur l’ensemble de ses connexions au sein de ce réseau. Sujet de recherche dès les premiers jours de l’informatique, ce domaine connait une renaissance depuis l’arrivée de réseaux de grande taille, dont l’exploitation des données nécessite de nouvelles plateformes de calcul.

Ce projet vise à développer une plateforme flexible pour le calcul à haute performance sur les réseaux de grande taille. Elle soutiendra, en particulier, des réseaux dits dynamiques, dont la structure peut évoluer lors du processus de calcul et fonctionnera, de plus, sur des ordinateurs conventionnels.

La démocratisation du calcul dynamique sur les réseaux de très grandes tailles, par le biais d’une plateforme fonctionnant sur des ordinateurs conventionnels, rend, de par son coût réduit, ce mode de calcul accessible à un plus grand nombre de laboratoires ou de sociétés.

Le plan initial prévoyait d'explorer Graph Analytics sur diverses plateformes pour déterminer s'il est possible de construire une plateforme unique qui fournit une bonne performance sur toutes ces plateformes, y compris toutes les combinaisons de traitement in-core et out-of-core, ainsi que les plateformes de machines individuelles et en cluster.

De grands progrès ont été réalisés avec le Usenix ATC Best Paper Award 2017 et plus généralement dans une thèse de doctorat menée dans le cadre de ce projet. Mais il s'est rapidement avéré que l'objectif global était trop ambitieux pour être atteint dans les délais impartis. En conséquence, les objectifs initiaux ont été modifiés à plusieurs égards. L'accent initial sur Graph Analytics a été élargi pour inclure Graph Minings, ce qui a été décrit dans une publication Eurosys de 2021.

Mais il s’est surtout avéré que le système de stockage de base du système out-of-core initial pour le traitement des graphes peut être utilisé à d’autres fins que le traitement des graphes. Dans une publication Eurosys de 2018, le système a été utilisé avec succès comme système de stockage de base pour le traitement général des Big Data. Un résultat très surprenant de cette ligne de travail a été que le système peut être utilisé avec grand succès pour distribuer les charges de travail des bases de données, comme le montrent une publication ASPLOS 2020 et une deuxième thèse de doctorat menée dans le cadre de ce projet.

Enfin, le projet a poursuivi une ligne de recherche indépendante sur l'ordonnancement d’ordinateurs multicore modernes, qui a notamment abouti à une publication Usenix ATC 2018 très bien accueillie comparant les planificateurs les plus couramment utilisés dans l'industrie.

Building Flexible Large-Graph Processing Systems on Commodity Hardware