T-GPS traite un graphique avec un billion d’arêtes sur un seul ordinateur

T-GPS traite un graphique avec des trillions d'arêtes sur un seul ordinateur?

Technologie de simulation de traitement graphique (T-GPS) à l’échelle d’un billion. Crédit: KAIST

Une équipe de recherche KAIST a développé une nouvelle technologie qui permet le traitement d’un algorithme graphique à grande échelle sans stocker le graphique dans la mémoire principale ou sur le disque. Nommé T-GPS (Trillion-scale Graph Processing Simulation) par le développeur, le professeur Min-Soo Kim de la School of Computing de KAIST, il peut traiter un graphique avec un billion d’arêtes à l’aide d’un seul ordinateur.

Les graphiques sont largement utilisés pour représenter et analyser des objets du monde réel dans de nombreux domaines tels que les réseaux sociaux, l’intelligence d’affaires, la biologie et les neurosciences. Alors que le nombre d’applications graphiques augmente rapidement, le développement et le test de nouveaux algorithmes graphiques deviennent plus importants que jamais. De nos jours, de nombreuses applications industrielles nécessitent un algorithme graphique pour traiter un graphique à grande échelle (par exemple, un billion d’arêtes). Ainsi, lors du développement et du test d’algorithmes de graphes tels que pour un graphe à grande échelle, un graphe synthétique est généralement utilisé à la place d’un graphe réel. En effet, le partage et l’utilisation de graphes réels à grande échelle sont très limités car ils sont propriétaires ou pratiquement impossibles à collecter.

De manière classique, le développement et le test d’algorithmes de graphes se font via l’approche en deux étapes suivante: génération et stockage d’un graphe et exécution d’un algorithme sur le graphe à l’aide d’un moteur de traitement de graphes.

La première étape génère un graphe synthétique et le stocke sur des disques. Le graphe synthétique est généralement généré soit par des méthodes de génération basées sur des paramètres, soit par des méthodes de conversion ascendante de graphe. Le premier extrait un petit nombre de paramètres qui peuvent capturer certaines propriétés d’un graphe réel donné et génère le graphe synthétique avec les paramètres. Ce dernier redimensionne un graphe réel donné vers un graphe plus grand afin de préserver autant que possible les propriétés du graphe réel d’origine.

La deuxième étape charge le graphe stocké dans la mémoire principale du moteur de traitement de graphe tel qu’Apache GraphX ​​et exécute un algorithme de graphe donné sur le moteur. Étant donné que la taille du graphique est trop grande pour tenir dans la mémoire principale d’un seul ordinateur, le moteur graphique fonctionne généralement sur un cluster de plusieurs dizaines ou centaines d’ordinateurs. Par conséquent, le coût de l’approche classique en deux étapes est très élevé.

L’équipe de recherche a résolu le problème de l’approche conventionnelle en deux étapes. Il ne génère ni ne stocke un graphe synthétique à grande échelle. Au lieu de cela, il charge simplement le petit graphe réel initial dans la mémoire principale. Ensuite, T-GPS traite un algorithme de graphe sur le petit graphe réel comme si le graphe synthétique à grande échelle qui devrait être généré à partir du graphe réel existait dans la mémoire principale. Une fois l’algorithme terminé, T-GPS renvoie exactement le même résultat que l’approche classique en deux étapes.

L’idée clé du T-GPS est de générer uniquement la partie du graphe synthétique à laquelle l’algorithme a besoin d’accéder à la volée et de modifier le moteur de traitement de graphe pour reconnaître la partie générée à la volée comme la partie du graphe synthétique réellement générée.

L’équipe de recherche a montré que T-GPS peut traiter un graphique de 1 billion d’arêtes à l’aide d’un seul ordinateur, tandis que l’approche conventionnelle en deux étapes ne peut traiter qu’un graphique d’1 milliard d’arêtes en utilisant un groupe de onze ordinateurs de la même spécification. Ainsi, le T-GPS surpasse de 10 000 fois l’approche conventionnelle en termes de ressources informatiques. L’équipe a également montré que la vitesse de traitement d’un algorithme dans T-GPS est jusqu’à 43 fois plus rapide que l’approche conventionnelle. En effet, T-GPS n’a pas de surcharge de communication réseau, tandis que l’approche conventionnelle a beaucoup de surcharge de communication entre les ordinateurs.

Le professeur Kim pense que ce travail aura un impact important sur l’industrie informatique, où presque toutes les zones utilisent des données graphiques, ajoutant: « T-GPS peut augmenter considérablement à la fois l’échelle et l’efficacité du développement d’un nouvel algorithme graphique. »


Évaluation plus rapide des performances des super-graphiques


Plus d’information:
Park, H. et coll. (2021) « Trillion-scale Graph Processing Simulation based on Top-Down Graph Upscaling », IEEE ICDE 2021, Chania, Greece, 19-22 avril 2021. Disponible en ligne sur conference.computer.org/icdepub

Fourni par le Korea Advanced Institute of Science and Technology (KAIST)

Citation: T-GPS traite un graphique avec un billion d’arêtes sur un seul ordinateur (2021, 6 mai) récupéré le 6 mai 2021 sur https://techxplore.com/news/2021-05-t-gps-graph-trillion-edges. html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.