en>Spinningspark: Reverted 2 edits by 117.199.112.60 (talk): That is not a reference. (TW)

2013-04-24T14:00:08Z

Reverted 2 edits by 117.199.112.60 (talk): That is not a reference. (TW)

New page

{{Orphan|date=March 2013}}

In [[Computer Science]] '''Helman-Bader-JaJa model'''
<ref>{{cite journal |last1=David R. |first1=Helman |last2=David A. |first2=Bader |last3=JaJa |first3=Joseph |year= 1998 |title= A Randomized Parallel Sorting Algorithm with an Experimental Study|journal=Journal of Parallel and Distributed Computing |volume=52 pages= 1-23 |publisher= |url=http://www.cc.gatech.edu/~bader/papers/JPDC-981462.pdf |accessdate=26 October 2012}}</ref> is a concise message passing model of parallel computation defined with the following parameters:

*<math>p</math> is number of processors.
*<math>n</math> is the problem size.
*<math>m</math> is number of machine words in a packet sent over the network.
*<math>\tau</math> is the [[Latency (engineering)|latency]], or time at which a processor takes to initiate a communication on a network.
*<math>\sigma</math> is the [[Bandwidth (computing)|bandwidth]], or time per machine word at which a processor can inject or receive <math>m</math> machine words from the network.
*<math>T_{comp}</math> is the largest computation time expended on a processor.
*<math>T_{comm}</math> is the time spent in communication on the network.

This model assumes that for any subset of <math>q</math> processors, a block permutation among the <math>q</math> processors takes <math>(\tau+\sigma m)</math> time, where <math>m</math> is the size of the largest block.

== Analysis of common parallel algorithms ==
Complexities of common parallel algorithms contained in the [[Message Passing Interface|MPI libraries]]:<ref>{{cite journal| last1=Bader| first1=David A.|last2=Jaja |first2=Joseph |title=Practical parallel algorithms for dynamic data redistribution, median finding, and selection|journal=``Proceedings of the 10th IEEE International Parallel Processing Symposium|year=1996|pages=292–301}}</ref>

*Point to point communication: <math>O(\tau+\sigma m) </math>

*Reduction :<math>O(log(p) (\tau+\sigma m)) </math>

*Broadcast: <math>O(log(p) (\tau+\sigma m)) </math>

*Parallel prefix: <math>O(log(p){n\over p} (\tau+\sigma m)) </math>

*All to all: <math>O(p(\tau+\sigma m)) ) </math>

==References==
{{Reflist}}

[[Category:Parallel computing]]

Variational method (quantum mechanics) - Revision history

en>Spinningspark: Reverted 2 edits by 117.199.112.60 (talk): That is not a reference. (TW)