Analysis of parallel algorithms: Difference between revisions

Revision as of 20:17, 25 January 2015

Revision as of 20:20, 25 January 2015

Line 11:

* ''Work law''. The cost is always at least the work: {{math|''pT_p'' ≥ ''T''₁}}. This follows from the fact {{mvar|p}} processors can perform at most {{mvar|p}} operations in parallel.<ref name="clrs"/><ref name="casanova"/>

* ''Span law''. A finite number {{mvar|p}} of processors cannot outperform an infinite number, so that {{math|''T_p'' ≥ ''T''_∞}}.<ref name="clrs"/>

Using these definitions and laws, the following measures of performance can be given:

* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math|''S_p'' {{=}} ''T_p'' /∕ ''T''₁}}. When the speedup is {{math|Ω(''n'')}} for input size {{mvar|n}} (using [[big O notation]]), the speedup is linear, which is optimal in the PRAM model ([[Speedup#Super-linear speedup|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math|''T_p'' /∕ ''T''₁ {{=}} p}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability|scalable]].<ref name="casanova"/>

* ''Efficiency'' is the speedup per processor, {{math|''S_p'' /∕ ''p''}}.<ref name="casanova"/>

==References==