Acabo de leer un artículo sobre un avance enmultiplicación de matrices; un algoritmo que es O (n ^ 2.373). Pero supongo que la multiplicación de matrices es algo que puede ser paralelizado. Entonces, si alguna vez comenzamos a producir procesadores de milésimos núcleos, ¿será esto irrelevante? ¿Cómo cambiarían las cosas?
Respuestas
7 para la respuesta № 1Si la computación cuántica llega a algo práctico algún día, entonces sí, la complejidad de los algoritmos cambiará.
Mientras tanto, paralelizando un algoritmo, conun número fijo de procesadores, justs divide su tiempo de ejecución proporcional (y eso, en el mejor de los casos, cuando no hay dependencias entre las tareas realizadas en cada procesador). Eso significa, dividir el tiempo de ejecución por una constante, por lo que la complejidad sigue siendo la misma.
10 para la respuesta № 2
La ejecución paralela no cambia los conceptos básicos dela complejidad de un algoritmo en particular: en el mejor de los casos, simplemente se toma el tiempo para un tamaño determinado y se divide por el número de núcleos. Esto puede reducir el tiempo para un tamaño determinado en un factor constante, pero no tiene efecto en el La complejidad del algoritmo.
Al mismo tiempo, la ejecución paralela a veces cambia cual Algoritmo (s) que desea utilizar para tareas particulares. Algunos algoritmos que funcionan bien en el código de serie simplemente no se dividen en tareas paralelas muy bien. Otros que tienen mayor complejidad podría ser más rápido para problemas de tamaño práctico porque se ejecutan mejor en paralelo.
Para un número extremadamente grande de núcleos, ella complejidad del cálculo en sí puede ser secundaria a la simple obtención de los datos necesarios de todos los núcleos para realizar el cálculo. la mayoría de los cálculos de big-O no tienen en cuenta estos efectos para un cálculo en serie, pero puede ser muy importante para los cálculos paralelos, especialmente para algunos modelos de máquinas paralelas que no dan acceso uniforme a todos los nodos.
4 para la respuesta № 3
Por La ley de amdahl, para el mismo tamaño de problema, la paralelización llegará a un punto derendimiento decreciente con el aumento en el número de núcleos (teóricamente). En realidad, a partir de cierto grado de paralelización, la sobrecarga de la paralelización realmente disminuirá el rendimiento del programa.
Sin embargo, por Ley de gustafson, el aumento de número de núcleos realmente ayudaa medida que aumenta el tamaño del problema. Esa es la motivación detrás de la computación en grupo. Como tenemos más poder de cómputo, podemos abordar el problema a mayor escala o con mayor precisión con la ayuda de la paralelización.
Algoritmos que aprendemos como es, pueden o no serparalelizable. A veces, se debe usar un algoritmo separado para ejecutar de manera eficiente la misma tarea en paralelo. De cualquier manera, la notación Big-O debe volver a analizarse para que el caso paralelo tenga en cuenta el efecto de la paralelización en la complejidad temporal del algoritmo.