¿Cuándo puede el paralelismo hacer que sus algoritmos se ejecuten más rápido? ¿Cuándo podría hacer que sus algoritmos funcionen más lentamente?

Además de las excelentes respuestas aquí, también debe considerar la disminución de los rendimientos frente al gasto.

Mi ejemplo favorito del “mundo real” es el reconocimiento de matrículas.

Digamos que en el proceso de reconocimiento (tiene que encontrarlo antes de poder leerlo) toma un promedio de 32 segundos encontrar una placa que mida 128 x 32 píxeles en una imagen de 1024 x 1024. (Los poderes de dos aquí son deliberados y, sorprendentemente, ayudan bastante).

Si aplicamos dos procesadores a la tarea, entonces deberíamos apostar que está hecha en 16 segundos, ¿verdad?

Lamentablemente no. Si la placa de número estaba en el punto muerto de la imagen, entonces cada procesador solo “vería” la mitad de la placa y, por lo tanto, no podría detectarla. Por lo tanto, tenemos que entregar a cada uno de los procesadores suficiente imagen adicional para garantizar que un procesador vea una placa completa.

Dividir la imagen verticalmente, inicialmente al menos, sería un ejemplo de paralelismo tonto. Cada procesador manejaría (512 + 64) * 1024 píxeles. Dividir horizontalmente es más inteligente; cada procesador manejaría 1024 * (512 + 16) píxeles, un ahorro de procesamiento del 8.33%.

Un poco de agitar las manos aquí; Para dividir una imagen de dimensión D en n partes iguales mientras se asegura que una parte debe contener una subimagen de dimensión d, entonces la dimensión de parte Dc debe ser al menos (D + (n-1) * d) / n. (MUCHAS advertencias, particularmente cuando n se acerca a D.)

En nuestro ejemplo, esto se descompone en 992 / n + 32.

[por ejemplo, donde n = 4, Dc = 280. Entonces los rangos Y se convierten en (0 – 279), (247 – 527), (495 – 775), (743 – 1023)]

Suponiendo que no haya otros gastos generales (y hay otros gastos generales … debería pensar mucho sobre cómo se accede a la memoria en este punto) y que el tiempo de reconocimiento promedio es directamente proporcional al número de píxeles, la versión de dos procesadores ahora debería tomar 16.5 segundos.

Si seguimos agregando procesadores y dividiendo la imagen verticalmente, podremos ir mucho más rápido; pero los resultados no son lineales.

El esfuerzo aquí es el total bruto de píxeles procesados.

Ha pasado mucho tiempo desde que vi esto y los números anteriores pueden aparecer por un píxel o dos. De memoria, llega un punto para n lo suficientemente grande donde vale la pena dividirlo horizontalmente.

Por lo general, sus algoritmos se beneficiarán del paralelismo siempre que los procesos paralelos sean independientes entre sí y siempre que use un número apropiado de hilos.
Por ejemplo, la ordenación de matrices no es el mejor algoritmo para beneficiarse del paralelismo, pero aún lo hace (consulte mergesort, por ejemplo)
Siempre que su algoritmo dependa de cualquier paso anterior, es mejor mantenerlos en el mismo hilo.
Pero el paralelismo es bueno, ¿verdad? Bueno, a veces. Si te excedes, volverá y morderá tu binario. Si usa más hilos de los que debería, el cambio de contexto termina tomando más tiempo que el algoritmo. ¡Sé sabio, ten cuidado y experimenta!

Me sorprende que nadie haya mencionado la Ley de Amdahl. La mayoría de las respuestas indican correctamente sus consecuencias. Dice así:

S (n) = 1 / (1 – p + p / n)

donde S (n) es aceleración, n es el número de procesadores y p es el porcentaje del tiempo de computación de una carga de trabajo dada que se puede hacer en paralelo entre n procesadores.

S (n) es un límite superior teórico sobre la ventaja que le darán los procesadores. Dado que f = 1 – p es el porcentaje de trabajo “fijo” que no se puede hacer en paralelo, solo dice que una hora de cálculo en serie lleva al menos 1 – p horas en completarse con cualquier número de procesadores, y el resto El p por ciento de la carga de trabajo no puede acelerarse en más de un factor de n.

En la práctica, el porcentaje de p realmente no se puede dividir en un número arbitrario de piezas más pequeñas, debido a la sobrecarga del sistema (sobrecarga fija en cada trabajo real del pantano del procesador), y la estructura del código en sí: para garantizar que el trabajo esté en paralelo , cada procesador tiene que ejecutar una unidad de trabajo independiente, y esas unidades pueden tener tamaños inherentemente diferentes.