From Wikipedia, the free encyclopedia
|This article is an orphan, as no other articles link to it. Please introduce links to this page from ; try the Find links tool for suggestions. (March 2013)|
- 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
- Point to point communication:
- Reduction :
- Parallel prefix:
- All to all:
- 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.
- 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.