Analysis of parallel algorithms: Difference between revisions

Revision as of 20:20, 25 January 2015

Revision as of 20:38, 25 January 2015

Line 5:

* The ''work'' of a computation executed by {{mvar|p}} processors is the total number of primitive operations that the processors perform.<ref name="casanova">{{cite book |title=Parallel Algorithms |first1=Henri |last1=Casanova |first2=Arnaud |last2=Legrand |first3=Yves |last3=Robert |publisher=CRC Press |year=2008 |pages=10}}</ref> Ignoring communication overhead from synchronizing the processors, this is equal to the time used to run the computation on a single processor, denoted {{math|''T''₁}}.

* The ''span'' or ''critical path length'' is the time {{math|''T''_∞}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms|3|779–784}}</ref>

* The ''cost'' of the computation is the quantity {{mvar|pT_p}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>

Line 15:

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''_p1'' ∕ ''T''_1p''}}. 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 because the work law implies that {{math|''T''₁ ∕ ''T_p'' ≤ ''p''}} ([[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"/>

* ''Parallelism'' is the ratio {{math|''T''₁ ∕ ''T''_∞}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math|p > ''T''₁ ∕ ''T_∞''}}, then {{math|''T''₁ ∕ ''T''_p ≤ ''T''₁ ∕ ''T_∞'' < p}}.<ref name="clrs"/>

* The ''slackness'' is {{math|''T''₁ ∕ (''pT''_∞)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar|p}} processors.<ref name="clrs"/>

==References==