HBJ model explained

In computer science, the Helman-Bader-JaJa model ^[1] 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:^[2]

• 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){n\over p} (\tau + \sigma m))

• All to all:

O(p(\tau + \sigma m)) )

Notes and References

1. David R. . Helman . David A. . Bader . JaJa . Joseph . 1998 . A Randomized Parallel Sorting Algorithm with an Experimental Study . Journal of Parallel and Distributed Computing . 52 . 1–23 . 10.1006/jpdc.1998.1462 . 1903/835 . 26 October 2012 . 19 November 2012 . https://web.archive.org/web/20121119012835/http://www.cc.gatech.edu/~bader/papers/JPDC-981462.pdf . dead .
2. Bader. David A.. Jaja . Joseph . Practical parallel algorithms for dynamic data redistribution, median finding, and selection. Proceedings of the 10th IEEE International Parallel Processing Symposium. 1996. 292–301.