Avec la prolifération des applications basées sur les données au cours des dernières années, de nombreuses applications en sont venues à s'appuyer sur des analyses avancées d'énormes ensembles de données. Alors que les frameworks basés sur MapReduce, tels que Hadoop, facilitent la mise à l'échelle de vos algorithmes sur de grands ensembles de données, leur cadre de programmation restrictif rend difficile l'adaptation de vos calculs existants au modèle de MapReduce.
Langages basés sur des tableaux tels que R, fournissent un cadre beaucoup plus naturel et expressif pour rédiger vos analyses statistiques. Depuis son introduction en 1996, R est devenu l’un des langages de prédilection des statisticiens et des data scientists du monde entier. Bien que le package bénéficie d’une communauté florissante et d’un écosystème interactif, il présente également des limites importantes. R est monothread et ne s'adapte pas bien aux ensembles de données plus volumineux. Cet inconvénient rend les progiciels statistiques efficaces, écrits par des statisticiens, inutiles pour les ensembles de données non triviaux.
Si votre algorithme est très gourmand en données, alors Hadoop s'avère être une meilleure solution. Cependant, avec une refactorisation intelligente de votre code R existant, il est possible d'obtenir de meilleures performances de R. Cela étant dit, j'ai décidé de tester le wraparound MPI pour R, Rmpi.
PageRank
PageRank est l'algorithme d'analyse de liens populaire, qui a lancé la puissance de Google. L’algorithme d’analyse des liens représente la probabilité qu’une personne navigue sur Internet au hasard et arrive à une page Web particulière. Les calculs du PageRank nécessitent plusieurs passes avant de converger. Lorsqu'un nœud est lié à un autre nœud, il contribue une partie de son score PageRank au score du PageRank global de ce nœud. Si un nœud avec un PageRank plus élevé est lié à un deuxième nœud, alors le deuxième nœud reçoit automatiquement un PageRank plus élevé. La fonction de mise à jour de l'algorithme est :
PR (A) = (1-d) + d (PR (T1) / C (T1) +… + PR (Tn) / C (Tn))
PR(A) – PageRank du nœud A
d – facteur d'amortissement
PR(Tn)/C(Tn) – partie du score de Tn contribué à PR(A) où T1… Tn sont les nœuds qui se lient à A
La version la plus naïve du PageRank suppose que tous les nœuds ont initialement le même rang et que chaque nœud distribue des scores égaux à ses voisins jusqu'à convergence. Cet algorithme converge lorsque la différence entre les mises à jour successives du vecteur PageRank est inférieure à une très petite valeur.
Stratégies de parallélisation
Il existe deux structures de données principales dans ce calcul. La matrice de contiguïté représente le graphique et le vecteur PageRank contient les scores de tous les nœuds. Bien que chaque thread ne fonctionne que sur sa partie de lignes de la matrice de contiguïté, l'intégralité du vecteur PageRank doit être mis à la disposition des threads esclaves après chaque itération. Cela garantit que les PageRanks mis à jour seront utilisés pour la prochaine itération. J'ai utilisé le fonctionnement MPI dispersion pour distribuer la matrice de contiguïté aux threads esclaves, et l'opération tousgatherv a été utilisé pour rassembler les résultats du vecteur PageRank partiel après chaque itération.
Des expériences sur le Redimensionner
J'ai utilisé l' Projet d'analyse du réseau de Stanford ensembles de données pour mes expériences, en particulier les Réseau de citations en physique des hautes énergies base de données. Le graphe contient 34,546 421,578 nœuds et 653.89 XNUMX arêtes. Le temps d'exécution de la version séquentielle vanille était de XNUMX secondes.
Le graphique d'exécution suit une distribution exponentielle décroissante, les gains d'exécution diminuant entre 12 (86.733 secondes) et 16 (68.38 secondes) threads.
Bien qu'il soit encore difficile de s'adapter à de très grands ensembles de données, R peut être adapté à des ensembles de données de taille moyenne à l'aide de frameworks, tels que Rmpi, comme démontré sur la plateforme Rescale.
Vous pouvez importer cette simulation sur votre compte Rescale ici. Si vous n'avez pas encore de compte Rescale, veuillez vous rendre sur www.rescale.com/signup pour créer un compte gratuit dès aujourd'hui.
Pour en savoir plus sur Rescale, veuillez visiter, www.rescale.com. Pour commencer à utiliser Rescale pour les simulations techniques et scientifiques, veuillez contacter info@rescale.com.
