Dans le jargon de la science des données, les graphiques sont des structures de nœuds et de lignes de connexion qui sont utilisées pour mapper des scores de relations de données complexes. L'analyse de graphiques est utile pour un large éventail d'applications, tels que le classement des pages Web, analyser les réseaux sociaux à la recherche d'idées politiques, ou tracer des structures neuronales dans le cerveau.

Composé de milliards de nœuds et de lignes, cependant, les grands graphiques peuvent atteindre des téraoctets. Les données graphiques sont généralement traitées dans une mémoire vive dynamique (DRAM) coûteuse sur plusieurs serveurs énergivores.

Des chercheurs du Laboratoire d'informatique et d'intelligence artificielle (CSAIL) du MIT ont maintenant conçu un appareil qui utilise un stockage flash bon marché (le type utilisé dans les smartphones) pour traiter des graphiques volumineux à l'aide d'un seul ordinateur personnel.

Le stockage flash est généralement beaucoup plus lent que la DRAM pour le traitement des données graphiques. Mais les chercheurs ont développé un dispositif composé d'un réseau de puces flash et d'un "accélérateur de calcul, " qui aide le flash à atteindre des performances de type DRAM.

L'alimentation de l'appareil est un nouvel algorithme qui trie toutes les demandes d'accès aux données graphiques dans un ordre séquentiel auquel Flash peut accéder rapidement et facilement. Il fusionne également certaines requêtes pour réduire les frais généraux - le temps de calcul combiné, Mémoire, bande passante, et d'autres ressources informatiques - de tri.

Les chercheurs ont utilisé l'appareil contre plusieurs systèmes traditionnels hautes performances traitant plusieurs grands graphiques, y compris l'énorme Web Data Commons Hyperlink Graph, qui compte 3,5 milliards de nœuds et 128 milliards de lignes de connexion. Pour traiter ce graphique, les systèmes traditionnels nécessitaient tous un serveur qui coûtait des milliers de dollars et contenait 128 gigaoctets de DRAM. Les chercheurs ont obtenu les mêmes performances en branchant deux de leurs appareils, totalisant 1 gigaoctet de DRAM et 1 téraoctet de mémoire flash, sur un ordinateur de bureau. De plus, en combinant plusieurs appareils, ils pouvaient traiter des graphiques massifs (jusqu'à 4 milliards de nœuds et 128 milliards de lignes de connexion) qu'aucun autre système ne pouvait gérer sur le serveur de 128 gigaoctets.

"L'essentiel est que nous pouvons maintenir la performance avec beaucoup plus petit, moins, et plus frais, comme dans la température et la consommation d'énergie, les machines, " dit Sang-Woo Jun, un étudiant diplômé du CSAIL et premier auteur d'un article décrivant le dispositif, qui est présenté au Symposium international sur l'architecture informatique (ISCA).

L'appareil pourrait être utilisé pour réduire les coûts et l'énergie associés à l'analyse graphique, et même améliorer les performances, dans une large gamme d'applications. Les chercheurs, par exemple, sont en train de créer un programme qui pourrait identifier les gènes qui causent des cancers. Les grandes entreprises technologiques telles que Google pourraient également tirer parti des appareils pour réduire leur empreinte énergétique en utilisant beaucoup moins de machines pour exécuter des analyses.

"Le traitement graphique est une idée tellement générale, " dit le co-auteur Arvind, le professeur Johnson en génie informatique. « Qu'est-ce que le classement des pages a en commun avec la détection de gènes ? Pour nous, c'est le même problème de calcul—juste des graphiques différents avec des significations différentes. Le type d'application que quelqu'un développe déterminera l'impact qu'elle aura sur la société."

Les co-auteurs de l'article sont Shuotao Xu, étudiant diplômé du CSAIL, et Andy Wright et Sizhuo Zhang, deux étudiants diplômés du CSAIL et du Département de génie électrique et informatique.

Trier et réduire

Dans l'analyse graphique, un système recherchera et mettra à jour la valeur d'un nœud en fonction de ses connexions avec d'autres nœuds, entre autres métriques. Dans le classement des pages Web, par exemple, chaque nœud représente une page Web. Si le nœud A a une valeur élevée et se connecte au nœud B, alors la valeur du nœud B augmentera également.

Les systèmes traditionnels stockent toutes les données graphiques dans la DRAM, ce qui les rend rapides dans le traitement des données mais aussi coûteux et gourmands en énergie. Certains systèmes déchargent une partie du stockage de données sur flash, ce qui est moins cher mais plus lent et moins efficace, ils nécessitent donc toujours des quantités substantielles de DRAM.

L'appareil des chercheurs fonctionne sur ce que les chercheurs appellent un algorithme de "tri-réduction", ce qui résout un problème majeur avec l'utilisation du flash comme principale source de stockage :les déchets.

Les systèmes d'analyse de graphes nécessitent un accès à des nœuds qui peuvent être très éloignés les uns des autres sur une structure de graphe clairsemée. Les systèmes demandent généralement un accès direct à, dire, 4 à 8 octets de données pour mettre à jour la valeur d'un nœud. La DRAM fournit cet accès direct très rapidement. Éclat, cependant, n'accède aux données que par blocs de 4 à 8 kilo-octets, mais ne met toujours à jour que quelques octets. Répéter cet accès pour chaque demande tout en sautant sur le graphique gaspille de la bande passante. "Si vous avez besoin d'accéder à l'intégralité des 8 kilo-octets, et n'utilisez que 8 octets et jetez le reste, tu finis par jeter 1, 000 fois la performance loin, " dit Jun.

L'algorithme de tri-réduction prend à la place toutes les demandes d'accès direct et les trie dans l'ordre séquentiel par identifiants, qui montrent la destination de la demande, comme le regroupement de toutes les mises à jour pour le nœud A, tout pour le nœud B, etc. Flash peut alors accéder à des morceaux de plusieurs kilo-octets de milliers de requêtes à la fois, le rendant beaucoup plus efficace.

Pour économiser encore plus de puissance de calcul et de bande passante, l'algorithme fusionne simultanément les données dans les plus petits groupes possibles. Chaque fois que l'algorithme note des identifiants correspondants, il les additionne en un seul paquet de données, tel que A1 et A2 devenant A3. Il continue ainsi, créer des paquets de données de plus en plus petits avec des identifiants correspondants, jusqu'à ce qu'il produise le plus petit paquet possible à trier. Cela réduit considérablement le nombre de demandes d'accès en double.

En utilisant l'algorithme de tri-réduction sur deux grands graphes, les chercheurs ont réduit d'environ 90 % le nombre total de données qui devaient être mises à jour en flash.

Calcul de déchargement

L'algorithme de tri-réduction est gourmand en calculs pour un ordinateur hôte, cependant, les chercheurs ont donc mis en place un accélérateur personnalisé dans l'appareil. L'accélérateur agit comme un point intermédiaire entre l'hôte et les puces flash, exécuter tous les calculs de l'algorithme. Cela décharge tellement d'énergie sur l'accélérateur que l'hôte peut être un PC ou un ordinateur portable à faible consommation qui gère les données triées et exécute d'autres tâches mineures.

"Les accélérateurs sont censés aider l'hôte à calculer, mais nous sommes allés si loin [avec les calculs] que l'hôte devient sans importance, " dit Arvind.

« Le travail du MIT montre une nouvelle façon d'effectuer des analyses sur de très grands graphiques :leur travail exploite la mémoire flash pour stocker les graphiques et exploite les « réseaux de portes programmables sur le terrain » [circuits intégrés personnalisés] d'une manière ingénieuse pour effectuer à la fois l'analyse et le traitement des données requis pour utiliser efficacement la mémoire flash, " dit Keshav Pingali, professeur d'informatique à l'Université du Texas à Austin. "À long terme, cela peut conduire à des systèmes capables de traiter efficacement de grandes quantités de données sur des ordinateurs portables ou de bureau, qui va révolutionner notre façon de traiter les mégadonnées."

Parce que l'hôte peut être si faible, Jun dit, un objectif à long terme est de créer une plate-forme à usage général et une bibliothèque de logiciels permettant aux consommateurs de développer leurs propres algorithmes pour des applications au-delà de l'analyse graphique. "Vous pouvez brancher cette plate-forme sur un ordinateur portable, télécharger [le logiciel], et écrivez des programmes simples pour obtenir des performances de classe serveur sur votre ordinateur portable, " il dit.

Cette histoire est republiée avec l'aimable autorisation de MIT News (web.mit.edu/newsoffice/), un site populaire qui couvre l'actualité de la recherche du MIT, innovation et enseignement.