HBJ model

Short description: Message-passing model of parallel computing

In computer science, the Helman-Bader-JaJa model is a concise message-passing model of parallel computing defined with the following parameters:

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

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

Analysis of common parallel algorithms

Complexities of common parallel algorithms contained in the MPI libraries:

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