In computer science, the Helman-Bader-JaJa model is a concise message-passing model of parallel computing defined with the following parameters:
p {\displaystyle p} is number of processors.
n {\displaystyle n} is the problem size.
m {\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 m {\displaystyle m} machine words from the network.
T c o m p {\displaystyle T_{comp}} is the largest computation time expended on a processor.
T c o m m {\displaystyle T_{comm}} is the time spent in communication on the network. This model assumes that for any subset of q {\displaystyle q} processors, a block permutation among the q {\displaystyle q} processors takes ( τ + σ m ) {\displaystyle (\tau +\sigma m)} time, where m {\displaystyle 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 ( τ + σ m ) {\displaystyle O(\tau +\sigma m)}
Reduction : O ( l o g ( p ) ( τ + σ m ) ) {\displaystyle O(log(p)(\tau +\sigma m))}
Broadcast: O ( l o g ( p ) ( τ + σ m ) ) {\displaystyle O(log(p)(\tau +\sigma m))}
Parallel prefix: O ( l o g ( p ) n p ( τ + σ m ) ) {\displaystyle O(log(p){n \over p}(\tau +\sigma m))}
All to all: O ( p ( τ + σ m ) ) ) {\displaystyle O(p(\tau +\sigma m)))}
References