Analysis of parallel algorithms: Difference between revisions

Revision as of 16:16, 18 September 2024

Latest revision as of 11:51, 27 January 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{short description|Subfield of computer science}}

In [[computer science]], the '''analysis of parallel [[algorithms]]''' is the process of finding the [[computational complexity]] of algorithms[[algorithm]]s executed in [[Parallel computing|parallel]] – the amount of time, storage, or other [[System resource|resources]] needed to execute them. In many respects, '''analysis of [[parallel algorithms'''algorithm]]s is similar to the [[analysis of algorithms|the analysis]] of [[sequential algorithmsalgorithm]]s, but is generally more involved because one must reason about the behavior of multiple cooperating [[Thread (computing)|threads]] of execution. One of the primary goals of parallel analysis is to understand how a parallel algorithm's use of resources (speed, space, etc.) changes as the number of processors is changed.

==Background==

Line 53 ⟶ 54:

==Definitions==

{{anchor|Overview}}

Suppose computations are executed on a machine that has {{mvar|p}} processors. Let {{mvar|T_p}} denote the time that expires between the start of the computation and its end. Analysis of the computation's [[Time complexity|running time]] focuses on the following notions:

Line 66 ⟶ 68:

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|1=''S_p'' = ''T''₁ / ''T_p''}}. When the speedup is {{math|Ω(''p'')}} for {{mvar|p}} processors (using [[big O notation]]), the speedup is linear, which is optimal in simple models of computation 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|1=''T''₁ / ''T_p'' = ''p''}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability|scalable]].<ref name="casanova"/> Analytical expressions for the speedup of many important parallel algorithms are presented in this book.<ref>{{Cite book |last=Kurgalin |first=Sergei |title=The discrete math workbook: a companion manual using Python |last2=Borzunov |first2=Sergei |date=2020 |publisher=Springer Naturel |isbn=978-3-030-42220-2 |edition=2nd |series=Texts in Computer Science |___location=Cham, Switzerland}}</ref>.

* ''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:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>