Modelo HBJ

Modelo de paso de mensajes de computación paralela

En informática , el modelo Helman-Bader-JaJa ^[1] es un modelo conciso de paso de mensajes de computación paralela definido con los siguientes parámetros:

• ${\displaystyle p}$es el número de procesadores.
• ${\displaystyle n}$¿Cuál es el tamaño del problema?
• ${\displaystyle m}$es el número de palabras de máquina en un paquete enviado a través de la red.
• ${\displaystyle \tau }$es la latencia o el tiempo que tarda un procesador en iniciar una comunicación en una red.
• ${\displaystyle \sigma }$es el ancho de banda , o el tiempo por palabra de máquina en el que un procesador puede inyectar o recibir palabras de máquina de la red. ${\displaystyle m}$
• ${\displaystyle T_{comp}}$es el mayor tiempo de cálculo empleado en un procesador.
• ${\displaystyle T_{comm}}$Es el tiempo empleado en la comunicación en la red.

Este modelo supone que, para cualquier subconjunto de procesadores, una permutación de bloques entre los procesadores lleva tiempo, donde es el tamaño del bloque más grande. ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle (\tau +\sigma m)}$ ${\displaystyle m}$

Análisis de algoritmos paralelos comunes

Complejidades de los algoritmos paralelos comunes contenidos en las bibliotecas MPI : ^[2]

• Comunicación punto a punto: ${\displaystyle O(\tau +\sigma m)}$
• Reducción : ${\displaystyle O(log(p)(\tau +\sigma m))}$
• Transmisión: ${\displaystyle O(log(p)(\tau +\sigma m))}$
• Prefijo paralelo: ${\displaystyle O(log(p){n \over p}(\tau +\sigma m))}$
• De todos a todos: ${\displaystyle O(p(\tau +\sigma m)))}$

Referencias

1. David R., Helman; David A., Bader; JaJa, Joseph (1998). "Un algoritmo de ordenamiento paralelo aleatorio con un estudio experimental" (PDF) . Journal of Parallel and Distributed Computing . 52 : 1–23. doi :10.1006/jpdc.1998.1462. hdl :1903/835. Archivado desde el original (PDF) el 19 de noviembre de 2012 . Consultado el 26 de octubre de 2012 .
2. Bader, David A.; Jaja, Joseph (1996). "Algoritmos paralelos prácticos para la redistribución dinámica de datos, la búsqueda de medianas y la selección". Actas del 10.º Simposio Internacional de Procesamiento Paralelo del IEEE : 292–301.