¿Cuáles son algunos indicios de que un algoritmo debe paralelizarse?

Question

Mi experiencia hasta ahora me ha demostrado que incluso con procesadores multi-core, la paralelización de un algoritmo no siempre lo acelerará notablemente. De hecho, a veces puede ralentizar las cosas. ¿Cuáles son algunas buenas pistas de que un algoritmo puede acelerarse significativamente al ser paralelizado?

(Por supuesto, dadas las advertencias con la optimización prematura y su correlación con el mal)

Answer 1

Para sacar el mayor provecho de paralelización, una tarea debe ser capaz de romperse en trozos supuesto de grano-similiar tamaño que son independientes (o principalmente) y requieren poca comunicación de datos o sincronización entre los fragmentos.

La paralelización de grano fino, casi siempre sufre un aumento de los gastos generales, y tendrá una aceleración finita independientemente del número de núcleos físicos disponibles.

[La advertencia a esto, es aquellas arquitecturas que tienen un no muy grande. de 'núcleos' (como las máquinas de conexión 64,000 núcleos). Estos son adecuados para cálculos que se pueden dividir en acciones relativamente simples asignadas a una topología particular (como una malla rectangular).]

Answer 2

Bueno, si necesita muchos bloqueos para que funcione, entonces es probablemente uno de esos algoritmos difíciles que no se paralelizan bien. ¿Hay alguna parte del algoritmo que se pueda dividir en partes separadas que no necesitan tocarse entre sí?

Answer 3

En primer lugar, echa un vistazo a este documento por el fallecido Jim Gray:

Distributed Computing Economics

En realidad, esto va a aclarar un malentendido sobre la base de lo que ha escrito en la pregunta. Obviamente, si el menos problemático es establecer su problema para ser discretizado, más difícil será.

Answer 4

Si puede dividir el trabajo en partes independientes, entonces puede ser bien paralelizado.

Recuerde también Amdahl's Law, que es un recordatorio aleccionador de lo poco que podemos esperar en términos de ganancias de rendimiento al agregar más núcleos a la mayoría de los programas.

Answer 5

Cada vez que tenga cálculos que dependen de cómputos anteriores, no es un problema paralelo. Cosas como el procesamiento lineal de imágenes, los métodos de fuerza bruta y los algoritmos genéticos se pueden paralelizar fácilmente.

Una buena analogía es ¿en qué trabajarías si pudieras hacer que un grupo de amigos hiciera diferentes partes a la vez? Por ejemplo, juntar los muebles de ikea podría paralelizarse bien si diferentes personas pueden trabajar en diferentes secciones, pero el papel tapiz rodante podría no hacerlo porque es necesario hacer las paredes en secuencia.

Answer 6

Si está haciendo grandes cálculos de matriz, como simulaciones que involucran modelos de elementos finitos, estos a menudo se pueden dividir en partes más pequeñas de manera directa. Las multiplicaciones Matrix-vector pueden beneficiarse mucho de la paralelización, suponiendo que se trata de matrices muy grandes. A menos que exista un cuello de botella de rendimiento real que haga que el código se ejecute lentamente, probablemente no sea necesario molestarse con el procesamiento en paralelo.