modelo HBJ

En ciencias de la computación , 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}$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 tiempo por palabra de máquina en el que un procesador puede inyectar o recibir${\displaystyle m}$Palabras de máquina de la red.
• ${\displaystyle T_{comp}}$es el mayor tiempo de cálculo empleado en un procesador.
• ${\displaystyle T_{comm}}$es el tiempo dedicado a la comunicación en la red.

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

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))}$
• Todos a todos:${\displaystyle O(p(\tau +\sigma m)))}$