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

  • is number of processors.
  • is the problem size.
  • 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 machine words from the network.
  • is the largest computation time expended on a processor.
  • is the time spent in communication on the network.

This model assumes that for any subset of processors, a block permutation among the processors takes time, where 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:
  • Reduction :
  • Broadcast:
  • Parallel prefix:
  • All to all:

References

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


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.