Explicación de los algoritmos embarazosamente paralelos

En la programación paralela, un algoritmo vergonzosamente paralelo es aquel que no requiere comunicación o dependencia entre los procesos. A diferencia de los problemas de computación distribuida que necesitan comunicación entre tareas, especialmente en resultados intermedios, los algoritmos vergonzosamente paralelos son fáciles de realizar en granjas de servidores que carecen de la infraestructura especial utilizada en un verdadero clúster de supercomputadoras.

Debido a la naturaleza de los algoritmos embarazosamente paralelos, se adaptan bien a las grandes plataformas distribuidas basadas en Internet y no sufren una ralentización paralela. Lo contrario de los problemas vergonzosamente paralelos son problemas inherentemente seriales, que no se pueden paralelizar en absoluto.

El caso ideal de algoritmos vergonzosamente paralelos se puede resumir de la siguiente manera:

  • Todos los subproblemas o tareas se definen antes de que comiencen los cálculos.
  • Todas las sub-soluciones se almacenan en ubicaciones de memoria independientes (variables, elementos de matriz).
  • Por tanto, el cálculo de las sub-soluciones es completamente independiente.
  • Si los cálculos requieren alguna comunicación inicial o final, lo llamamos casi vergonzosamente paralelo.

Muchos pueden preguntarse la etimología del término "vergonzosamente". En este caso, la vergüenza no tiene nada que ver con la vergüenza; de hecho, significa una sobreabundancia, refiriéndose aquí a problemas de paralelización que son "vergonzosamente fáciles".

Un ejemplo común de un problema vergonzosamente paralelo es la reproducción de video en 3D manejada por una unidad de procesamiento de gráficos, donde cada cuadro o píxel puede manejarse sin interdependencia. Algunos otros ejemplos serían el software de plegado de proteínas que puede ejecutarse en cualquier computadora con cada máquina haciendo una pequeña parte del trabajo, generación de todos los subconjuntos, números aleatorios y simulaciones de Monte Carlo.