# HBJ model

In Computer Science Helman-Bader-JaJa model [1] is a concise message passing model of parallel computation defined with the following parameters:

• ${\displaystyle p}$ is number of processors.
• ${\displaystyle n}$ is the problem size.
• ${\displaystyle m}$ is number of machine words in a packet sent over the network.
• ${\displaystyle \tau }$ is the latency, or time at which a processor takes to initiate a communication on a network.
• ${\displaystyle \sigma }$ is the bandwidth, or time per machine word at which a processor can inject or receive ${\displaystyle m}$ machine words from the network.
• ${\displaystyle T_{comp}}$ is the largest computation time expended on a processor.
• ${\displaystyle T_{comm}}$ is the time spent in communication on the network.

This model assumes that for any subset of ${\displaystyle q}$ processors, a block permutation among the ${\displaystyle q}$ processors takes ${\displaystyle (\tau +\sigma m)}$ time, where ${\displaystyle m}$ is the size of the largest block.

## Analysis of common parallel algorithms

Complexities of common parallel algorithms contained in the MPI libraries:[2]

• Point to point communication: ${\displaystyle O(\tau +\sigma m)}$
• Reduction :${\displaystyle O(log(p)(\tau +\sigma m))}$
• Broadcast: ${\displaystyle O(log(p)(\tau +\sigma m))}$
• Parallel prefix: ${\displaystyle O(log(p){n \over p}(\tau +\sigma m))}$
• All to all: ${\displaystyle O(p(\tau +\sigma m)))}$

## References

1. ^ David R., Helman; David A., Bader; JaJa, Joseph (1998). "A Randomized Parallel Sorting Algorithm with an Experimental Study" (PDF). Journal of Parallel and Distributed Computing. 52: 1–23. Retrieved 26 October 2012.
2. ^ Bader, David A.; Jaja, Joseph (1996). "Practical parallel algorithms for dynamic data redistribution, median finding, and selection". Proceedings of the 10th IEEE International Parallel Processing Symposium: 292–301.