HBJ model

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.
$τ$ is the latency, or time at which a processor takes to initiate a communication on a network.
$σ$ is the bandwidth, or time per machine word at which a processor can inject or receive $m$ machine words from the network.
$T_{c o m p}$ is the largest computation time expended on a processor.
$T_{c o m m}$ 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 $(τ + σ 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 (τ + σ m)$
Reduction : $O (l o g (p) (τ + σ m))$
Broadcast: $O (l o g (p) (τ + σ m))$
Parallel prefix: $O (l o g (p) \frac{n}{p} (τ + σ m))$
All to all: $O (p (τ + σ m)))$

References

↑ 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. doi:10.1006/jpdc.1998.1462. hdl:1903/835. Archived from the original (PDF) on 19 November 2012. Retrieved 26 October 2012.
↑ 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.

This computer science article is a stub. You can help Wikipedia by adding missing information.

[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. doi:10.1006/jpdc.1998.1462. hdl:1903/835. Archived from the original (PDF) on 19 November 2012. 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.