Mit der Verbreitung datenbasierter Anwendungen in den letzten Jahren sind viele Anwendungen auf die erweiterte Analyse riesiger Datensätze angewiesen. Während MapReduce-basierte Frameworks wie Hadoop, erleichtern die Skalierung Ihrer Algorithmen auf große Datensätze, ihr restriktives Programmierframework macht es jedoch schwierig, Ihre vorhandenen Berechnungen an das MapReduce-Modell anzupassen.
Array-basierte Sprachen wie Rbieten einen viel natürlicheren und ausdrucksstärkeren Rahmen für Ihre statistischen Analysen. Seit seiner Einführung im Jahr 1996 hat sich R zu einer der beliebtesten Sprachen für Statistiker und Datenwissenschaftler weltweit entwickelt. Obwohl das Paket eine florierende Community und ein interaktives Ökosystem vorweisen kann, weist es auch erhebliche Einschränkungen auf. R ist ein Single-Thread-System und lässt sich bei größeren Datensätzen nicht gut skalieren. Dieser Nachteil macht effektive Statistikpakete, die von Statistikern geschrieben wurden, für nicht-triviale Datensätze unbrauchbar.
Wenn Ihr Algorithmus sehr datenintensiv ist, erweist sich Hadoop als die bessere Lösung. Mit etwas geschicktem Refactoring Ihres vorhandenen R-Codes ist es jedoch möglich, eine bessere Leistung aus R herauszuholen. Vor diesem Hintergrund habe ich beschlossen, den MPI-Wraparound für R zu testen. Drehzahl.

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

PR(A) – PageRank von Knoten A

d – Dämpfungsfaktor

PR(Tn)/C(Tn) – Anteil des Tn-Scores, der zu PR(A) beiträgt, wobei T1… Tn die Knoten sind, die mit A verbunden sind

Die einfachste Version von PageRank geht davon aus, dass alle Knoten anfangs den gleichen Rang haben und dass jeder Knoten bis zur Konvergenz gleiche Punktzahlen an seine Nachbarn verteilt. Dieser Algorithmus konvergiert, wenn die Differenz zwischen aufeinanderfolgenden Aktualisierungen des PageRank-Vektors kleiner als ein sehr kleiner Wert ist.

Strategien zur Parallelisierung

Diese Berechnung umfasst zwei Hauptdatenstrukturen. Die Adjazenzmatrix stellt den Graphen dar, und der PageRank-Vektor enthält die Werte aller Knoten. Jeder Thread bearbeitet zwar nur seinen Zeilenanteil der Adjazenzmatrix, doch muss der gesamte PageRank-Vektor nach jeder Iteration den Slave-Threads zur Verfügung gestellt werden. Dadurch wird sichergestellt, dass die aktualisierten PageRanks für die nächste Iteration verwendet werden. Ich habe die MPI-Operation verwendet. scatterv um die Adjazenzmatrix an die Slave-Threads zu verteilen, und die Operation allgatherv wurde benutzt um die Ergebnisse des partiellen PageRank-Vektors nach jeder Iteration zu sammeln.

Experimente auf der Neu skalieren Lernumgebung

Früher habe ich die Stanford-Netzwerkanalyseprojekt Datensätze für meine Experimente, insbesondere die Zitationsnetzwerk für Hochenergiephysik Datensatz. Der Graph enthält 34,546 Knoten und 421,578 Kanten. Die Laufzeit für die sequenzielle Vanilla-Version betrug 653.89 Sekunden.

Das Laufzeitdiagramm folgt einer exponentiell abnehmenden Verteilung, wobei die Laufzeitgewinne zwischen 12 (86.733 Sekunden) und 16 (68.38 Sekunden) Threads nachlassen.

Während die Skalierung auf sehr große Datensätze immer noch eine Herausforderung darstellt, kann R mithilfe von Frameworks wie Rmpi für Datensätze mittlerer Größe skaliert werden, wie auf der Rescale-Plattform gezeigt.
Sie können diese Simulation in Ihr Rescale-Konto importieren werden auf dieser Seite erläutertWenn Sie noch kein Rescale-Konto haben, gehen Sie bitte zu www.rescale.com/signup um sich noch heute für ein kostenloses Konto anzumelden.
Um mehr über Rescale zu erfahren, besuchen Sie bitte www.rescale.com. Um Rescale für technische und wissenschaftliche Simulationen zu verwenden, wenden Sie sich bitte an info@rescale.com.