¿Hay algún problema / algoritmo famoso en la informática científica que no pueda acelerarse mediante paralelización?

¿Existen problemas / algoritmos famosos en la informática científica que no puedan acelerarse mediante paralelización? Al leer libros sobre CUDA me parece que la mayoría de las cosas pueden ser.

$C$$T$$C$$T$$C$$T$$T$$N$$C \sim \log T$

Ejemplos

• $C = T$
• $m\times m$$T = N = \mathcal O(m^2)$$C = m = \sqrt T$
• $T = N$$C = \log T$
• $\tau$$(0,1)^d$$k = \tau / \Delta t \sim \tau N^{1/d}$$C = k$$T = k N = \tau N^{(d+1)/d}$$P = T/C = N$$N^{1/d}$

Complejidad formal

$NC = P$

$NC$$O(log^c n)$$O(n^k)$$P=NC$$P$$P$$P$$P$$NC$$P$$NC$$P=NC$

$P$$P$

Comience por descifrar la Ley de Amdahl . Básicamente, cualquier cosa con una gran cantidad de pasos en serie se beneficiará insignificantemente del paralelismo. Algunos ejemplos incluyen análisis, expresiones regulares y la mayoría de las compresiones de alta relación.

Aparte de eso, el problema clave es a menudo un cuello de botella en el ancho de banda de la memoria. En particular, con la mayoría de las GPU, sus fracasos teóricos superan ampliamente la cantidad de números de coma flotante que puede obtener con sus ALU, ya que los algoritmos con baja intensidad aritmética (flops / caché-miss) pasarán una gran mayoría de tiempo esperando en la RAM.

Por último, cada vez que un fragmento de código requiere ramificación, es poco probable que obtenga un buen rendimiento, ya que la lógica de ALU generalmente es mayor que la lógica.

En conclusión, un ejemplo realmente simple de algo que sería difícil obtener una ganancia de velocidad de una GPU es simplemente contar el número de ceros en una matriz de enteros, ya que es posible que tenga que bifurcar a menudo, como máximo realice 1 operación (incremente en uno) en el caso de que encuentre un cero y realice al menos una recuperación de memoria por operación.

Un ejemplo libre del problema de ramificación es calcular un vector que es la suma acumulativa de otro vector. ([1,2,1] -> [1,3,4])

No sé si estos cuentan como "famosos", pero ciertamente hay una gran cantidad de problemas con los que la computación paralela no lo ayudará.

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).

Otra clase de problemas que son difíciles de paralelizar en la práctica son los problemas sensibles a los errores de redondeo, donde la estabilidad numérica se logra mediante la serialización.

Considere, por ejemplo, el proceso de Gram-Schmidt y su modificación en serie. El algoritmo funciona con vectores, por lo que puede usar operaciones de vectores paralelos, pero eso no escala bien. Si el número de vectores es grande y el tamaño del vector es pequeño, el uso de Gram-Schmidt clásico paralelo y la reortogonalización pueden ser estables y más rápidos que el Gram-Schmidt modificado simple, aunque implica hacer varias veces más trabajo.