Límites a la computación paralela

Tengo curiosidad en un sentido amplio sobre lo que se sabe sobre algoritmos de paralelización en P. Encontré el siguiente artículo de Wikipedia sobre el tema:

http://en.wikipedia.org/wiki/NC_%28complexity%29

El artículo contiene la siguiente oración:

Se desconoce si NC = P, pero la mayoría de los investigadores sospechan que esto es falso, lo que significa que probablemente hay algunos problemas manejables que son "inherentemente secuenciales" y no pueden acelerarse significativamente mediante el uso de paralelismo

¿Suena esto razonable? ¿Hay casos conocidos en los que un problema en P no se puede acelerar utilizando paralelismo?

Ni siquiera se sabe si NC = P, pero los problemas P-completos parecen ser inherentemente difíciles de paralelizar. Estos incluyen programación lineal y Horn-SAT. (En contraste, los problemas en NC parecen razonablemente fáciles de paralelizar).

Ver pregunta Problemas entre NC y P: ¿Cuántos se han resuelto de esta lista? para material de referencia (incluidos enlaces a un libro de texto clásico que ahora está disponible para descarga gratuita), y más discusión sobre problemas que están en P pero que no se sabe que son paralelizables.

Ver pregunta Teorema de Ladner generalizado para la estructura de las clases de complejidad entre NC y P. Brevemente, si difieren, hay infinitas clases de complejidad estrictamente entre NC y P.

Ver pregunta NC = P consecuencias? para una buena demostración de Ryan Williams de que es posible amplificar colapsos en la jerarquía de clases de complejidad dentro de P en colapsos quizás más improbables como PSPACE = EXP .

Vale la pena señalar que una de las consecuencias de que Horn-SAT sea P-completo, y los enlaces anteriores, es que no parece posible paralelizar consultas SQL generales en bases de datos, a menos que también podamos reescribir cualquier cálculo a gran escala para usar solo Una cantidad razonable de almacenamiento. Esta es una discrepancia desconcertante: creo que es bastante controvertido afirmar que existen límites en la compresión , pero a menudo veo artículos que parecen construirse sobre el supuesto de que es posible paralelizar cualquier consulta de base de datos.

Bueno, si hubiera casos conocidos, entonces podríamos separar P y NC. Pero hay muchos problemas que se sabe que son P completos (es decir, bajo reducciones de espacio de registro), y presentan el mismo tipo de barreras para mostrar P = NC que los problemas NP completos para P = NP. Entre ellos se incluyen la programación lineal y la correspondencia (y los flujos máximos en general).

Ketan Mulmuley demostró un resultado que separa P y una forma débil de NC (sin operaciones de bit) en 1994. En cierto sentido, su programa actual para P vs NP despega desde donde lo dejó ( de una manera muy floja ).

El libro ' Limits on Parallel Computation ' tiene más información sobre esto.

Respondí una pregunta similar. ¿Hay algún problema / algoritmo famoso en la informática científica que no pueda acelerarse mediante la paralelización en el sitio de Computational Science ? Permítanme citarlo aquí, porque ofrece una perspectiva práctica sobre una instancia muy concreta de tal problema:

El método de marcha rápida (famoso) para resolver la ecuación de Eikonal no se puede acelerar mediante la paralelización. Existen otros métodos (por ejemplo, métodos de barrido rápido) para resolver la ecuación de Eikonal que son más susceptibles a la paralelización, pero incluso aquí el potencial de aceleración (paralela) es limitado.

El problema con la ecuación de Eikonal es que el flujo de información depende de la solución misma. Hablando en términos generales, la información fluye a lo largo de las características (es decir, los rayos de luz en la óptica), pero las características dependen de la solución misma. Y el flujo de información para la ecuación Eikonal discretizada es aún peor, ya que requiere aproximaciones adicionales (como las que están implícitamente presentes en los métodos de barrido rápido) si se desea una aceleración paralela.

Para ver las dificultades para la paralelización, imagine un bonito laberinto como en algunos de los ejemplos en la página web de Sethian . El número de celdas en el camino más corto a través del laberinto (probablemente) es un límite inferior para el número mínimo de pasos / iteraciones de cualquier algoritmo (paralelo) que resuelva el problema correspondiente.

(Escribo "(probablemente) es", porque los límites inferiores son notoriamente difíciles de probar, y a menudo requieren algunas suposiciones razonables sobre las operaciones utilizadas por un algoritmo).