Apprendre et réfléchir sur le calcul graphique

Un bon logiciel ne se trouve pas grâce à l'analyse du programme et à la vérification des erreurs, mais est construit par les bonnes personnes.

Les graphiques sont devenus un objet informatique de plus en plus important. La structure graphique est une abstraction des relations de groupe et peut décrire des objets et des relations riches. Le cœur du calcul graphique est de savoir comment modéliser les données dans une structure graphique et comment transformer la solution du problème en un problème informatique sur la structure graphique. Lorsque le problème implique une analyse de corrélation, le calcul graphique peut souvent apporter une solution naturelle au problème. exprimé sous la forme d'une série d'opérations et de calculs sur des structures graphiques. Par exemple, l'algorithme PageRank basé sur la structure graphique des liens de pages Web est utilisé pour obtenir le poids de la page Web, qui est utilisé comme référence pour le classement des moteurs de recherche. Les données de comportement des utilisateurs de la structure graphique sont utilisées pour obtenir des résultats précis. analyse des préférences de groupe et résultats de recommandations de produits personnalisés.

1. Qu'est-ce que l'informatique graphique ?

L'informatique graphique est une technologie qui étudie les choses dans le monde humain et les relations entre les choses, et les décrit, les caractérise, les analyse et les calcule. Le graphe ici est « graphe », pas le graphe « image », qui vient de la théorie des graphes en mathématiques.

Les graphiques sont la méthode de connexion la plus flexible, permettant aux entités d'être connectées sans restrictions. L’informatique graphique n’est pas seulement une technologie, mais un moyen de comprendre le monde. Les données graphiques peuvent bien décrire les connexions entre les choses, notamment en décrivant la direction et les attributs des connexions. Du point de vue de la structure des données, les graphiques sont une expression native des relations entre les objets. Dans une certaine mesure, les bases de données relationnelles devraient être appelées bases de données de tables, tandis que les bases de données graphiques devraient être appelées bases de données relationnelles. Le calcul graphique au sens large fait référence à divers traitements basés sur des données graphiques, y compris des bases de données graphiques.

La technologie informatique graphique résout les problèmes de faible efficacité et de coût élevé des requêtes associées dans les modes informatiques traditionnels. Elle décrit complètement les relations dans le domaine du problème et possède des capacités d'analyse de données riches, efficaces et agiles. Ses caractéristiques sont les suivantes :

.
• Modèle de données basé sur l'abstraction graphique
• Abstraction parallèle du modèle de données graphique
• Optimisation du système de modèle graphique

Pour le calcul graphique, le coût des performances, le mécanisme de tolérance aux pannes et l'évolutivité sont tous très importants.

2. Regard sur l'informatique graphique du point de vue du développement historique

L'informatique graphique remonte aux bases de données arborescentes des années 1960. Dans les années 1970 et 1980, des modèles et des technologies orientés graphes d'attributs sont apparus, tels que LDM (. Modèle Logique de Données), etc. Jusqu’en 2007, la première base de données graphique commerciale Neo4j a été créée, marquant ainsi l’entrée dans une phase de développement de l’informatique graphique.

Le véritable début de la recherche sur l'informatique graphique a été le développement de MapReduce, un modèle informatique pour le traitement parallèle du Big Data par Google en 2004. Le lancement de ce modèle a eu un énorme impact révolutionnaire sur le traitement parallèle du Big Data. Par la suite, en 2006, l'équipe Apache Hadoop a introduit le système de fichiers distribués Hadoop (HDFS) et le nouveau framework Hadoop MapReduce. En 2009, l'AMP Lab de l'Université de Californie à Berkeley a développé le système Spark.

Depuis 2010, les orientations de recherche en informatique graphique telles que l'architecture distribuée à grande échelle, la prise en charge multimodale et la conception de langages de requête graphique ont progressivement attiré l'attention. Google a proposé Pregel, un système informatique graphique distribué conçu pour les caractéristiques des algorithmes graphiques, suivant le modèle informatique BSP ; puis l'équipe du projet CMU Select Laboratory GraphLab a proposé le modèle informatique GAS. . Bien que Pregel et GraphLab soient tous deux des cadres de traitement pour des calculs d'apprentissage automatique complexes et soient utilisés pour les calculs d'itération, leurs méthodes de mise en œuvre empruntent des chemins différents : Pregel est basé sur un mécanisme de transmission de messages en gros blocs et GraphLab est basé sur le mécanisme de partage de mémoire. un impact profond sur la conception ultérieure d’autres systèmes informatiques graphiques.

Google a proposé le concept de graphe de connaissances en mai 2012, qui est une nouvelle façon de relier les informations. Son unité de base est le triplet « entité-relation-entité », et les entités sont connectées les unes aux autres par le biais de relations constituant une connaissance en réseau. structure. Le cœur de l'établissement du graphe de connaissances est le mécanisme de raisonnement des connaissances des ordinateurs, et l'informatique graphique fournit un support technique sous-jacent important pour celui-ci.

En 2015, avec la croissance rapide du volume de données, le marché des applications s'est progressivement ouvert et la demande d'évolutivité et d'efficacité des systèmes informatiques graphiques a continué d'augmenter. La recherche universitaire et industrielle dans le domaine de l'informatique graphique en Chine a commencé à développer progressivement ses propres systèmes et plates-formes d'informatique graphique, comme Gemini de l'Université Tsinghua, etc.

Ces dernières années, avec le développement de la technologie de l'intelligence artificielle, les réseaux de neurones graphiques ont également montré leurs prouesses dans l'industrie.

3. Examen du calcul graphique à partir du modèle de cadre

Le cadre du calcul graphique suit essentiellement le modèle informatique BSP (Bulk Synchronous Parallell). La caractéristique unique du mécanisme de synchronisation groupée du mode BSP réside dans l’introduction du concept de superstep. Un processus de calcul se compose d'une série de super-étapes globales. Chaque super-étape comprend trois étapes : calcul parallèle (calcul local), communication globale (communication de données non locales) et synchronisation de clôture (attente de la fin du comportement de communication).

Le mode BSP présente les caractéristiques suivantes :

Divise les calculs en super-étapes une par une, évitant ainsi les blocages ;

Sépare les processeurs et les routeurs, en mettant l'accent sur la séparation des tâches informatiques et des tâches de communication, tandis que les routeurs complètent uniquement la messagerie point à point. et ne fournit pas de fonctions telles que l'assemblage, la copie et la diffusion, ce qui non seulement masque la topologie spécifique du réseau d'interconnexion, mais simplifie également le protocole de communication

 ;

Adoptez le mode synchrone pour implémenter la synchronisation globale et un niveau à gros grain contrôlable dans le matériel afin d'exécuter des algorithmes parallèles synchrones étroitement couplés.

Certains frameworks de calcul graphique représentatifs sont les suivants :

• Neo4j-APOC : basé sur la base de données graphique, il prend en charge certains algorithmes graphiques de base et la version distribuée n'est pas open source.
• Pregel : proposé par Google en 2009, il est le fondateur du modèle de calcul graphique, et de nombreux travaux ultérieurs ont été influencés par ses idées. Pas open source.
• Giraph : implémentation open source de Facebook basée sur les idées de Pregel.
• Gémeaux : L'Université Tsinghua a mis en œuvre un certain nombre d'améliorations basées sur les idées de Pregel, avec d'excellentes performances. Seule une démo gratuite est fournie, la version commerciale n'est pas open source.
• KnightKing : Un framework de calcul graphique spécialement conçu pour les algorithmes de marche de Walker, qui n'est pas universel.
• GraphX ​​: Un framework de calcul graphique implémenté par la Fondation Apache basé sur Spark, avec une forte activité communautaire.
• GraphLab (PowerGraph) : logiciel commercial, non open source. A été acquis par Apple.
• Plato : implémentation open source C++ de Tencent basée sur les idées de Gemini et KnightKing. Il s'agit d'un framework de calcul graphique hautes performances, évolutif et facile à brancher.

4. Examiner les calculs graphiques du point de vue des algorithmes

L'algorithme graphique fait référence à une méthode simple qui utilise des sommets et des arêtes spécifiques pour trouver des réponses. De nombreux algorithmes graphiques couramment utilisés peuvent être utilisés pour les graphiques non orientés, les graphiques orientés et les réseaux. Pour les données graphiques, les algorithmes de parcours (profondeur/largeur en premier) constituent la base d'autres algorithmes. Les algorithmes graphiques typiques incluent le PageRank, le chemin le plus court, la branche connectée, l'ensemble indépendant maximum, l'arbre couvrant minimum et la propagation des croyances bayésiennes. L'arbre couvrant minimum d'un graphique représente souvent le coût le plus bas ou le coût minimum de la vie, et l'algorithme de Prim et l'algorithme de Kruskal sont couramment utilisés. La découverte de communauté, le chemin le plus court, le tri topologique et le chemin critique ont également des algorithmes correspondants.

Les algorithmes graphiques incluent diverses technologies d'analyse de données telles que la recherche, la correspondance, la classification et l'évaluation. Ils peuvent être grossièrement divisés en deux catégories à partir de la dimension de la structure de l'algorithme : les algorithmes centrés sur le parcours et les algorithmes centrés sur le calcul. Les algorithmes centrés sur la traversée doivent parcourir le graphe à partir de sommets spécifiques d'une manière spécifique, et il existe une grande quantité d'accès aléatoire. Les algorithmes centrés sur le calcul nécessitent un grand nombre d’opérations dans un cycle d’itération et ont une localité de données relativement bonne.

5. En regardant le calcul graphique du point de vue de l'architecture informatique

Le calcul graphique est généralement un calcul basé sur les données. La structure informatique ne peut pas être prédite avec précision avant son exécution, et il n'y a pas de modèle évident dans le formulaire. est difficile de le diviser de manière efficace et de haute qualité. Les mécanismes de mise en cache existants ne peuvent souvent qu'accélérer l'accès aux données avec une bonne localité, et l'accès à de grandes quantités de données placera souvent le processeur dans un état d'attente pour les E/S.

La charge de calcul graphique est complexe et il n’existe pas de charge de calcul graphique la plus représentative. Les arêtes reliant les sommets ne constituent qu’un petit sous-ensemble d’innombrables connexions possibles et sont très irrégulières. Dans le processus de calcul graphique, la localité spatio-temporelle de la lecture et de l’écriture est difficile à saisir, et l’occupation de la bande passante est difficile à prédire.

La plupart des algorithmes peuvent occuper moins de 50 % de la bande passante mémoire. Qu'est-ce qui limite l'utilisation de la bande passante mémoire ? Le processeur doit obtenir des instructions, il y a un espace entre les fenêtres d'instructions et les opérandes du registre doivent attendre que les opérandes soient disponibles et les dépendances associées ne seront pas libérées. En raison du taux élevé de réussite des instructions, le parallélisme au niveau de la mémoire peut être réduit, ce qui rend difficile l'utilisation complète de la bande passante mémoire de la plate-forme. Un faible taux d'utilisation des données du cache signifie qu'il est difficile pour les applications de bénéficier de la localité spatiale et que la stratégie de prélecture des données sera inefficace. La prélecture des données contribue généralement à améliorer les performances, mais elle génère également un grand nombre d’opérations de prélecture inutiles. Pour les applications avec une bande passante mémoire ou une capacité de cache limitées, la prélecture des données peut entraîner un certain gaspillage de ressources. Dans le cas de l'informatique multithread, le déclenchement d'un accès à la mémoire à distance avec une latence plus élevée annulera également les avantages du multithread.

Quel type de cœur de processeur est nécessaire pour le calcul graphique ? Généralement, on utilise une architecture avec de nombreux petits cœurs de calcul et un nombre élevé de threads, ce qui convient au traitement de calculs de grands graphes pour lesquels les processeurs multicœurs traditionnels ne sont pas bons. Dans le calcul simultané de plusieurs graphiques, il existe deux stratégies : l'allocation partagée et l'allocation exclusive. La stratégie d'allocation partagée signifie que chacune des m requêtes est traitée en parallèle à l'aide de n cœurs logiques, et que le système d'exploitation gère la commutation des différentes requêtes sur les cœurs logiques. La stratégie d'allocation exclusive fait référence à l'allocation de n/m cœurs logiques à chaque requête afin que les cœurs logiques n'aient pas besoin de basculer entre les tâches. La stratégie d'allocation exclusive est plus adaptée aux calculs de graphiques simultanés. L'exclusivité peut généralement réduire la durée d'exécution globale pour les mêmes requêtes simultanées. La faible contention du cache de réorganisation peut être la raison pour laquelle la stratégie exclusive est meilleure que la stratégie partagée dans les scénarios de calcul graphique simultané.

En ce qui concerne la consommation d'énergie provoquée par le calcul graphique, les changements de charge provoquent des fluctuations de puissance du système, et les pics et les creux peuvent s'échelonner. L'augmentation des tâches simultanées modifiera le rapport pic/creux et augmentera la consommation d'énergie. De manière générale, en termes de consommation d'énergie du processeur, les algorithmes centrés sur le calcul consomment en moyenne une grande quantité d'énergie par instruction, tandis que les algorithmes centrés sur le parcours ont l'effet inverse en termes de consommation d'énergie de la mémoire, les algorithmes centrés sur le calcul consomment moins de mémoire. La consommation d'énergie moyenne est faible, et l'inverse est vrai pour les algorithmes centrés sur la traversée.

La plupart des applications basées sur l'informatique graphique sont limitées en mémoire, mais l'utilisation de la mémoire est également insuffisante en raison des limitations des composants principaux. Un nombre suffisant de threads actifs créent un accès simultané, ce qui peut améliorer l'utilisation. Davantage de threads sont nécessaires, mais en raison du déséquilibre entre les threads, ils risquent de ne pas être utilisés efficacement. Une stratégie parallèle plus évolutive doit être fournie pour optimiser l'utilisation de la mémoire à large bande passante des processeurs multicœurs. La consommation d'énergie et le comportement de la consommation d'énergie sont différents du point de vue des instructions et du point de vue du calcul des sommets, nécessitant des méthodes de gestion de l'énergie précises, et des ajustements approfondis peuvent ne pas être efficaces.

6. Visualisez le calcul graphique à partir du système

Sur la base des scénarios d'utilisation et de l'architecture de la plate-forme informatique des systèmes informatiques graphiques à grande échelle, ils peuvent être divisés en systèmes informatiques graphiques à mémoire mono-machine, systèmes informatiques graphiques à mémoire externe mono-machine. et des systèmes informatiques de graphes à mémoire distribuée et des systèmes informatiques de graphes à mémoire distribuée.

Le système de traitement de graphiques à mémoire mono-machine est un système de traitement de graphiques qui s'exécute dans un environnement à machine unique et met en mémoire tampon toutes les données graphiques dans la mémoire. Le système de traitement graphique à mémoire externe autonome est un algorithme graphique efficace dans lequel le système de traitement graphique s'exécute dans un environnement autonome et interagit en permanence avec la mémoire et le disque via le calcul des données graphiques. Le système de mémoire distribuée est un système de traitement de graphiques fonctionnant dans un environnement de cluster distribué, et toutes les données graphiques sont chargées dans la mémoire. Le système informatique graphique à mémoire externe distribuée étend les systèmes hors cœur d'une seule machine en clusters et peut traiter des graphiques avec des arêtes de l'ordre de plusieurs milliards.

7. Regard sur le calcul graphique à partir de l'IA

Le réseau neuronal graphique (GNN) généré par la fusion de l'IA et du calcul graphique est actuellement un domaine important et en développement rapide. Comment combiner les données relationnelles entre différentes entités avec des réseaux de neurones ? Le réseau neuronal graphique utilise l'apprentissage des représentations. Grâce à la structure du graphique, chaque nœud ou bord est d'abord représenté par un vecteur, puis traité ultérieurement à l'aide d'un réseau neuronal. Cela élargit la portée de l’utilisation des réseaux neuronaux et introduit la relation entre les entités dans le traitement de l’IA.

Le réseau neuronal graphique peut être considéré comme un processus d'apprentissage de fonctionnalités graphiques, telles que des fonctionnalités représentatives de nœuds ou des fonctionnalités représentatives au niveau du graphique. Il prend généralement les attributs du graphique et la structure du graphique en entrée et génère un ensemble de données. représentations de nœuds mises à jour. Généralement, ce processus est également appelé opération de filtrage de graphiques. Le filtrage du graphique met à jour les fonctionnalités des nœuds mais ne modifie pas la structure du graphique. Le développement des réseaux neuronaux graphiques est développé à partir de différentes motivations théoriques. Par exemple, si le GNN est considéré comme une généralisation par convolution de la distance non euclidienne, il est développé sur la base de signaux graphiques. Désormais, la plupart des GNN sont basés sur des méthodes de transmission de messages neuronaux. algorithme de passage proposé par analogie au raisonnement probabiliste dans les modèles graphiques.

Qu'il s'agisse d'une méthode spectrale ou d'une idée basée sur l'espace, le réseau neuronal graphique peut enfin être unifié dans un cadre basé sur la transmission de messages. L'idée de base du framework de transmission de messages GNN est qu'à chaque itération, chaque nœud agrège les informations de ses nœuds voisins. À mesure que le nombre d’itérations augmente, chaque nœud contient une plus grande gamme d’informations sur le graphique. Par exemple, après k itérations, le nœud central peut obtenir les informations de ses k-hops voisins. L'idée clé est de générer des représentations de nœuds basées sur la structure graphique et les informations sur les fonctionnalités connues. GNN utilise les informations sur la structure et les caractéristiques des nœuds sur le graphique pour générer des représentations d'intégration profonde, tandis que la méthode d'intégration de graphique traditionnelle utilise uniquement les informations structurelles du graphique pour générer des intégrations de couches via une recherche dans la table.

7.1 GNN VS MLP/CNN/RNN

Les voisins des nœuds dans les données graphiques ont deux caractéristiques : premièrement, le nombre est incertain et la seconde est l'ordre. Par conséquent, MLP/CNN/RNN ne peut pas traiter directement de tels non-. Données européennes. Elles ne peuvent être modélisées qu’avec GNN. En fait, GNN peut être considéré comme un modèle plus général. Par exemple, RNN est équivalent à GNN sur un graphe linéaire et Transformer est équivalent à GNN sur un graphe complet.

7.2 GNN VS Graph Embedding

De nombreuses méthodes d'intégration de graphiques ont émergé avant GNN et sont largement utilisées dans l'étape de rappel vectoriel des services de recherche. De telles méthodes sont inspirées de Word2vec, de l'Item2Vec original à Node2Vec Basé sur l'amélioration de. équilibrant l'homogénéité et la structure, à MetaPath2Vec basé sur l'amélioration de l'hétérogénéité du graphique et l'introduction de données d'attributs pour atténuer la rareté des données comportementales, ces méthodes suivent toutes le paradigme Skip-Gram.

Par rapport à ces méthodes, GNN peut être formé de bout en bout en fonction de la tâche cible, tandis que l'intégration de graphiques s'apparente davantage à une pré-formation. L'intégration qu'il apprend n'est pas nécessairement liée à la tâche cible, en particulier dans les scénarios commerciaux avec. de grandes tailles d'échantillons, l'intégration obtenue par la formation de bout en bout est plus efficace que l'intégration obtenue par la pré-formation.

La structure de réseau hiérarchique de GNN est facile à combiner avec d'autres technologies d'apprentissage en profondeur, telles que GCN+Attentinotallow=GAT. GNN peut être appliqué aux tâches inductives, c'est-à-dire lorsque la structure du graphique change et que de nouveaux nœuds sont ajoutés, s'il s'agit d'une méthode d'incorporation de graphique, le modèle doit être recyclé et GNN peut utiliser une méthode similaire à GraphSage Node. -Échantillonnage judicieux, utilisant le modèle déjà formé, déduit directement de nouveaux nœuds et diverses fonctionnalités peuvent être utilisées dans le processus de transmission des messages.

7.3 GNN VS Feature Concat & Filtrage collaboratif et perte de proximité

Feature Concat signifie épisser des fonctionnalités ensemble, puis apprendre des informations d'association d'attributs de premier ordre via l'intersection de fonctionnalités. Le filtrage collaboratif peut également apprendre des informations de corrélation comportementale de premier ordre grâce aux comportements historiques des utilisateurs. La perte de proximité signifie ajouter des termes réguliers à la fonction de perte pour rendre les nœuds adjacents plus similaires, mais d'une part c'est une manière implicite, d'autre part si vous voulez vous assurer que les relations de similarité d'ordre élevé sont apprises, vous devez ajouter plus complexe Le terme régulier d'ordre K est également l'un des points de départ lorsque GCN a été proposé. Par rapport à ces trois méthodes, GNN peut apprendre explicitement des informations de corrélation d'ordre élevé en empilant plusieurs couches.

Il existe une condition clé qui doit être remplie dans la conception de réseaux de neurones graphiques, à savoir l'invariance de permutation ou l'équivariance de permutation. Autrement dit, lorsque la fonction conçue traite les données du graphique, elle ne sera pas affectée par l'ordre des nœuds, ou. la sortie du domaine de transformation séquentielle lors de l'entrée. L'ordre est cohérent.

8. Résumé

Graph est la méthode de connexion la plus flexible, permettant aux entités d'être connectées sans restrictions. L'informatique graphique est un domaine qui étudie comment calculer, stocker et gérer efficacement des données graphiques dans de grandes quantités de données. Elle peut être appliquée à un large éventail de scénarios commerciaux, tels que la gestion des risques des marchés financiers, la recherche en sciences de la vie, la prestation de soins de santé et la surveillance. et réponse aux accidents de la route, gestion intelligente des infrastructures, etc. L'informatique graphique qui traite efficacement des données à grande échelle peut favoriser le développement de domaines d'application émergents tels que l'analyse des réseaux sociaux, l'analyse du Web sémantique, l'analyse des réseaux d'informations biologiques et le traitement du langage naturel.

[Matériaux de référence]

"Graph Computing of Artificial Intelligence", Institut d'intelligence artificielle de l'Université Tsinghua, Institut d'intelligence artificielle Zhiyuan de Pékin, Centre commun de recherche Tsinghua-Academy of Engineering Knowledge Intelligence, 2019-2

​​https : //www.php.cn/link/c9e5c2b59d98488fe1070e744041ea0e​​

​​https://www.php.cn/link/d40d35b3063c11244fbf38e9b55074be​​

​​ https https://www.php.cn / lien/315f006f691ef2e689125614ea22cc61​​

​​https://www.php.cn/link/51d1cd3a02276948f566e6ea0a7d78cb​​

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!