Algoritmos Paralelos y Rendimiento
El diseño de algoritmos paralelos busca cómputos que expongan abundante paralelismo con baja comunicación, y el análisis de rendimiento cuantifica qué tan bien explotan procesadores adicionales.
Definition
Un algoritmo paralelo especifica cómo un problema es resuelto por múltiples procesadores cooperando; su calidad se juzga por el trabajo (operaciones totales) y la profundidad (cadena de dependencia más larga), y por métricas de rendimiento como la aceleración y la eficiencia que miden el beneficio de usar p procesadores.
Scope
Este tema cubre modelos para diseñar y analizar algoritmos paralelos —notablemente el PRAM y su análisis de trabajo-profundidad—, el diseño de primitivas paralelas como sumas de prefijo (escaneo), reducción y ordenamiento, y el marco de rendimiento de aceleración (speedup), eficiencia, optimización de costos, isoeficiencia y las leyes de escalado de Amdahl y Gustafson. Proporciona la base analítica para razonar sobre programas paralelos en todos los modelos de programación.
Core questions
- ¿Cómo se caracteriza el paralelismo inherente de un problema por su trabajo y profundidad?
- ¿Cómo se definen y miden la aceleración, la eficiencia y la escalabilidad?
- ¿Cómo la fracción serial o el crecimiento de un problema determinan su escalabilidad paralela?
Key theories
- PRAM y análisis de trabajo-profundidad
- El modelo PRAM idealiza una máquina paralela con memoria compartida y pasos síncronos, lo que permite el análisis del trabajo (operaciones totales) y la profundidad (longitud de la ruta crítica) de un algoritmo, que en conjunto limitan su tiempo paralelo alcanzable.
- Aceleración, eficiencia e isoeficiencia
- La aceleración mide cuánto más rápido p procesadores resuelven un problema, la eficiencia lo normaliza por procesador, y la isoeficiencia expresa cómo el tamaño del problema debe crecer con el número de procesadores para mantener la eficiencia constante, capturando la escalabilidad.
- Leyes de Amdahl y Gustafson
- La ley de Amdahl limita la aceleración de tamaño fijo por la fracción serial, mientras que la ley de Gustafson observa que escalar el problema con la máquina permite una aceleración casi lineal, enmarcando conjuntamente el escalado fuerte versus el débil.
Clinical relevance
El análisis de trabajo-profundidad y las leyes de escalado guían si y cómo se debe paralelizar un cómputo y predicen su comportamiento a escala, informando el diseño de todo, desde núcleos de ordenamiento y gráficos hasta grandes simulaciones y entrenamiento de aprendizaje automático.
History
El argumento de Amdahl de 1967 y la refutación de Gustafson de 1988 enmarcaron el debate sobre la aceleración; el modelo PRAM y el marco de trabajo-profundidad maduraron a lo largo de la década de 1980 y fueron codificados en el texto de JaJa de 1992 y el análisis de escalabilidad de Grama y colegas, dando a la computación paralela su núcleo teórico.
Debates
- Escalado fuerte versus escalado débil
- La visión de escalado fuerte de Amdahl (problema fijo, más procesadores) predice rendimientos decrecientes, mientras que la visión de escalado débil de Gustafson (crecer el problema con los procesadores) predice una aceleración sostenida; cuál es la medida correcta depende de si el tamaño del problema o el tiempo de solución es fijo.
Key figures
- Joseph JaJa
- Gene Amdahl
- John Gustafson
- Vipin Kumar
Related topics
Seminal works
- jaja1992
- amdahl1967
- gustafson1988
Frequently asked questions
- ¿Cuál es la diferencia entre el trabajo y la profundidad de un algoritmo paralelo?
- El trabajo es el número total de operaciones realizadas en todos los procesadores, mientras que la profundidad (o extensión) es la longitud de la cadena más larga de operaciones dependientes. La profundidad limita el mejor tiempo de ejecución paralelo posible, y la relación trabajo-profundidad indica cuánto paralelismo está disponible.