Es posible porque PageRank era una forma de valor propio y es por eso que se introdujo MapReduce. Pero parece que hay problemas en la implementación real, como que cada computadora esclava tiene que mantener una copia de la matriz.cómo implementar el cálculo de valores propios con MapReduce/Hadoop?
PREÁMBULO:
Dado el secuestro de la derecha de los datos, se podría lograr resultados de computación en paralelo sin un conjunto completo de datos en cada máquina.
Tomemos por ejemplo el siguiente bucle:
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
m[i][j]++;
}
}
Y dada una matriz de la siguiente distribución: existen
j=0 j=1 j=2
i=0 [ ] [ ] [ ]
i=1 [ ] [ ] [ ]
i=2 [ ] [ ] [ ]
construcciones paralelas de tal manera que la columna de la J se puede enviar a cada equipo y la las columnas individuales se calculan en paralelo. La parte difícil de la paralelización viene cuando tienes bucles que contienen dependencias.
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
//For obvious reasons, matrix index verification code removed
m[i][j] = m[i/2][j] + m[i][j+7];
}
}
Obviamente un bucle como la de arriba se vuelve extremadamente problemático (notar los indexadores de la matriz.) Pero sí existen técnicas para desenrollar este tipo de bucles y la creación de algoritmos paralelos eficaces.
RESPUESTA:
Es posible que Google ha desarrollado una solución para calcular un valor propio sin mantener una copia de la matriz en todos los equipos esclavos. O bien, usaron algo como Monte Carlo o algún otro Approximation Algorithm para desarrollar un cálculo "lo suficientemente cerca".
De hecho, iría tan lejos como para decir que Google habrá hecho todo lo posible para hacer que cualquier cálculo requerido para su algoritmo de PageRank sea lo más eficiente posible. Cuando se ejecutan máquinas como these y this (observe el cable Ethernet) no puede transferir grandes conjuntos de datos (cientos de gig) porque es imposible debido a sus limitaciones de hardware de las tarjetas NIC básicas.
Dicho esto, Google es bueno para sorprender a la comunidad de programadores y su implementación podría ser completamente diferente.
postámbulo:
Algunos buenos recursos para computación paralela incluiría OpenMP y MPI. Ambas implementaciones paralelas abordan la informática paralela desde paradigmas muy diferentes, algunos de los cuales se derivan de la implementación de la máquina (clúster frente a computación distribuida).
"Es completamente posible que se calcule un valor propio sin mantener una copia de la matriz en todas las computadoras esclavas". ??? ¿Cómo llegaste a esa conclusión? Las matrices de PageRank son escasas. –
@Jason - Mi significado y cómo lo escribí no eran lo mismo. Hice una edición para ese efecto. Gracias por señalar eso. –
Sospecho que es intratable para la mayoría de las matrices, excepto aquellas con estructuras especiales (por ejemplo, matrices dispersas o w/ciertos patrones de bloque). Hay demasiado acoplamiento entre los coeficientes de la matriz y los valores propios.
PageRank usa un muy sparse matrix de una forma especial, y cualquier conclusión del cálculo de sus valores propios casi con certeza no se extiende a las matrices generales. (editar: aquí está another reference que se ve interesante)
Me puedo responder a mí mismo ahora.El algoritmo de PageRank aprovecha una matriz dispersa donde debe converger en el valor propio con varias auto-multiplicaciones. Por lo tanto, en la práctica de PageRank, el procedimiento de Mapa/Reducir es válido. Puede realizar una multiplicación de matriz en el procedimiento Map y formar una matriz dispersa en el procedimiento Reducir. Pero para el hallazgo de valores propios de la matriz general, sigue siendo un problema difícil.
PageRank resuelve el problema del autovector dominante al encontrar iterativamente la condición de flujo discreto de estado estable de la red.
Si NxM matriz A describe el peso enlace (cantidad de flujo) desde el nodo n al nodo m, entonces
p_{n+1} = A . p_{n}
En el límite donde p ha convergido a un estado estacionario (p_n + 1 = p_n) , este es un problema eigenvector con eigenvalue 1.
El algoritmo de PageRank no requiere que la matriz se mantenga en la memoria, pero es ineficiente en matrices densas (no dispersas). Para matrices densas, MapReduce es la solución incorrecta, necesita localidad e intercambio amplio entre nodos, y debería mirar a LaPACK y MPI y sus amigos.
Puede ver una implementación de pagerank de trabajo en el wukong library (transmisión de hadoop para ruby) o en el Heretrix pagerank submodule. (El código se ejecuta independientemente del heretrix Heretrix)
(exención de responsabilidad: Soy un autor de wukong.)
El Apache hama proyecto tiene alguna aplicación interesante del algoritmo de valor propio Jacobi. Funciona en hadoop. Tenga en cuenta que la rotación ocurre en el escaneo de la matriz no en el mapa de reducir.
Para MapReduce necesita un algoritmo de división y conquista. Eche un vistazo a http://en.wikipedia.org/wiki/Divide-and-conquer_eigenvalue_algorithm –