HBJ model

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In Computer Science Helman-Bader-JaJa model [1] is a concise message passing model of parallel computation 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[edit]

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)) )


  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 pages= 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.