algorithm - paralelo - multiplicacion de matrices mpi

Algoritmos paralelos y distribuidos para la multiplicación de matrices

Question

El problema surge cuando busqué la página de Wikipedia del algoritmo de multiplicación Matrix

Dice:

Este algoritmo tiene una longitud de ruta crítica de Θ((log n)^2) pasos, lo que significa que lleva mucho tiempo en una máquina ideal con un número infinito de procesadores; por lo tanto, tiene una aceleración máxima posible de Θ(n3/((log n)^2)) en cualquier computadora real.

( La cita es de la sección "Algoritmos paralelos y distribuidos / paralelismo de memoria compartida" ).

Como se supone que hay procesadores infinitos, la operación de multiplicación se debe hacer en O(1) . Y luego solo agregue todos los elementos, y esto también debería ser un tiempo constante. Por lo tanto, la ruta crítica más larga debe ser O (1) en lugar de Θ ((log n) ^ 2) .

Me preguntaba si hay diferencia entre O y Θ y ¿dónde me equivoco?

El problema ha sido resuelto, gracias a @Chris Beck. La respuesta debe separarse en dos partes.

Primero, un pequeño error es que no cuento el tiempo de suma. La suma toma O(log(N)) en funcionamiento _{(piense en la adición binaria)} .

Segundo, como señala Chris, los problemas no triviales toman tiempo O(log(N)) en el procesador. Sobre todo, la ruta crítica más larga debería ser O(log(N)^2) lugar de O(1) .

Para la confusión de O y Θ, encontré la respuesta en Big_O_Notation_Wikipedia .

Big O es la notación asintótica más comúnmente utilizada para comparar funciones, aunque en muchos casos Big O puede ser reemplazado por Big Theta Θ para límites más estrictos.

Me equivoqué en la última conclusión. El O(log(N)^2) no ocurre en la suma y el procesador, sino en el momento en que dividimos la matriz. Gracias @displayName por recordarme esto. Además, la respuesta de Chris para un problema no trivial sigue siendo muy útil para investigar el sistema paralelo. ¡Agradézcanles a todos los cálidos respondedores de corazón!

Answer 1

El "número infinito de procesadores" es quizás una manera pobre de expresarlo.

Cuando las personas estudian la computación paralela desde un punto de vista teórico, básicamente quieren preguntar "suponiendo que tengo más procesadores de los que necesito, qué tan rápido puedo hacerlo".

Es una pregunta bien definida: el hecho de que tenga una gran cantidad de procesadores no significa que la multiplicación de la matriz sea O (1).

Supongamos que toma cualquier algoritmo ingenuo para la multiplicación de matrices en un solo procesador. Entonces te digo que, si lo deseas, puedes tener un procesador para cada instrucción de ensamblaje, de modo que el programa puede "paralelizarse", ya que cada procesador realiza solo una instrucción y luego comparte su resultado con el siguiente.

El tiempo de ese cálculo no es "1" ciclo, porque algunos de los procesadores tienen que esperar que otros procesadores terminen, y esos procesadores están esperando procesadores diferentes, etc.

En términos generales, los problemas no triviales (problemas en los que ninguno de los bits de entrada son irrelevantes) requieren tiempo O(log n) en el cómputo paralelo; de lo contrario, el procesador "respuesta" al final ni siquiera tiene tiempo para depender de todos los bits de entrada.

Los problemas para los cuales el tiempo paralelo O(log n) es ajustado, se dice que son altamente paralelizables. Se conjetura ampliamente que algunos de ellos no tienen esta propiedad. Si eso no es cierto, entonces en términos de la teoría de la complejidad computacional, P se colapsaría a una clase inferior con la cual se supone que no.

Answer 2

La multiplicación de matrices se puede hacer en O(logn) usando n^3 procesadores. Aquí es cómo:

Entrada: dos matrices N x N M1 y M2 . M3 almacenará el resultado.

Asigna N procesadores para calcular el valor de M3[i][j] . M3[i][j] se define como Sum(M1[i][k] * M2[k][j]), k = 1..N . En el primer paso, todos los procesadores hacen una sola multiplicación. El primero hace M1[i][1] * M2[1][j] , el segundo hace M1[i][2] * M2[2][j] , .... Cada procesador mantiene su valor. Ahora tenemos que sumar todos estos pares multiplicados. Podemos hacer esto en el tiempo O(logn) si organizamos la suma en un árbol:

     4         Stage 3
   /   /
  2     2      Stage 2
 / /   / /
1   1 1   1    Stage 1

Ejecutamos este algoritmo en paralelo para todos (i, j) usando procesadores N^3 .

Answer 3

Hay dos aspectos en esta pregunta, abordando cuál será la pregunta completamente respondida.

• ¿Por qué no podemos llevar el tiempo de ejecución a O (1) lanzando una cantidad suficiente de procesadores?
• ¿Cómo es la longitud del camino crítico para la multiplicación de la matriz igual a Θ (log ² n)?

Yendo después de las preguntas una por una.

Infinita cantidad de procesadores

La respuesta simple a este punto es comprender dos términos a saber. Granularidad de Tarea y Dependencia de Tarea .

• Granularidad de la tarea: implica cuán fina es la descomposición de la tarea. Incluso si tiene procesadores infinitos, la descomposición máxima sigue siendo finita para un problema.
• Dependencia de tareas: implica que cuáles son los pasos que simplemente se pueden realizar secuencialmente. Como, no puedes modificar la entrada a menos que la hayas leído. Entonces la modificación siempre estará precedida por la lectura de la entrada y no puede hacerse en paralelo con ella.

Entonces, para un proceso que tiene cuatro pasos A, B, C, D tales que D depende de C, C depende de B y B depende de A , entonces un solo procesador funcionará tan rápido como 2 procesadores, funcionará tan rápido como 4 procesadores, funcionará tan rápido como procesadores infinitos.

Esto explica la primera viñeta.

Longitud de ruta crítica para la multiplicación de matriz paralela

1. Si tuviera que dividir una matriz cuadrada de tamaño n X n en cuatro bloques de tamaño [n/2] X [n/2] cada uno y luego continuar dividiendo hasta llegar a un solo elemento (o matriz de tamaño 1 X 1 ) la cantidad de niveles que tendría este diseño similar a un árbol es O (log (n)) .
2. Por lo tanto, para la multiplicación de matrices en paralelo, dado que tenemos que recursivamente dividir no una sino dos matrices de tamaño n, hasta su último elemento, toma O (log ² n) tiempo.
3. De hecho, este límite es más estricto y no es solo O (log ² n) , sino Θ (log ² n) .

Si probamos el tiempo de ejecución usando ^† Teorema maestro, podríamos calcular el mismo utilizando la recurrencia:

M (n) = 8 * M (n / 2) + Θ (Log n)

Este es el caso - 2 del Teorema Maestro y da el tiempo de ejecución como Θ (log ² n) .

La diferencia entre Big O y Theta es que Big O solo dice que un proceso no irá más allá de lo mencionado por Big O, mientras que Theta dice que la función no es solo tener un límite superior, sino también el límite inferior con lo que se menciona en Theta. . Por lo tanto, efectivamente, la trama de la complejidad de la función se intercalaría entre la misma función, multiplicada por dos constantes diferentes como se representa en la imagen a continuación, o en otras palabras, la función crecerá a la misma velocidad:

^{Imagen tomada de: http://xlinux.nist.gov/dads/Images/thetaGraph.gif}

Por lo tanto, diría que para su caso, puede ignorar la notación y no está "gravemente" equivocado entre los dos.

Para concluir...

Me gustaría definir otro término llamado Speedup o Paralelismo . Se define como la relación entre el mejor tiempo de ejecución secuencial (también llamado trabajo) y el tiempo de ejecución paralelo. El mejor tiempo de acceso secuencial, ya dado en la página de la wikipedia a la que te has vinculado es O (n ³ ) . El tiempo de ejecución paralelo es O (log ² n) .

Por lo tanto, la aceleración es = O (n ³ / log ² n) .

Y a pesar de que la aceleración parece tan simple y directa, lograrla en los casos reales es muy difícil debido a los costos de comunicación que son inherentes al movimiento de datos.

^† Teorema maestro

Sea a un entero mayor o igual a 1 yb sea ​​un número real mayor que 1. Sea c un número real positivo y d un número real no negativo. Dada una repetición de la forma -

T (n) = a * T (n / b) + n ^c cuando n> 1

entonces para n un poder de b , si

1. Log _b a <c, T (n) = Θ (n ^c );
2. Log _b a = c, T (n) = Θ (n ^c * Log n);
3. Log _b a> c, T (n) = Θ (n ^{log _b a} ).