Analysis of parallel algorithms - Revision history

John of Reading: /* top */ Typo fixing, fixed "the the"

2025-01-27T11:51:19Z

top: Typo fixing, fixed "the the"

← Previous revision		Revision as of 11:51, 27 January 2025
Line 1:		Line 1:
	{{short description\|Subfield of computer science}}		{{short description\|Subfield of computer science}}

	In [[computer science]], '''analysis of parallel algorithms''' is the process of finding the [[computational complexity]] of [[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 algorithm]]s is similar to ~~the~~ [[analysis of algorithms\|the analysis]] of [[sequential algorithm]]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.		In [[computer science]], '''analysis of parallel algorithms''' is the process of finding the [[computational complexity]] of [[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 algorithm]]s is similar to [[analysis of algorithms\|the analysis]] of [[sequential algorithm]]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==		==Background==

OlliverWithDoubleL: short description, links

2025-01-17T08:41:55Z

short description, links

← Previous revision		Revision as of 08:41, 17 January 2025
Line 1:		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~~ executed in parallel – the amount of time, storage, or other resources needed to execute them. In many respects, ~~'''~~analysis of parallel ~~algorithms'''~~ is similar to the [[analysis of algorithms\|analysis of sequential ~~algorithms~~]], but is generally more involved because one must reason about the behavior of multiple cooperating 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.		In [[computer science]], '''analysis of parallel algorithms''' is the process of finding the [[computational complexity]] of [[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 algorithm]]s is similar to the [[analysis of algorithms\|the analysis]] of [[sequential algorithm]]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==		==Background==

CiaPan: /* Definitions */ restoring a destination {{anchor}} for existing links

2024-11-08T10:29:44Z

Definitions: restoring a destination {{anchor}} for existing links

← Previous revision		Revision as of 10:29, 8 November 2024
Line 53:		Line 53:

	==Definitions==		==Definitions==
			{{anchor\|Overview}}
	Suppose computations are executed on a machine that has {{mvar\|p}} processors. Let {{mvar\|T<sub>p</sub>}} 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:		Suppose computations are executed on a machine that has {{mvar\|p}} processors. Let {{mvar\|T<sub>p</sub>}} 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:

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2024-09-19T03:39:32Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 03:39, 19 September 2024
Line 66:		Line 66:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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>.		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>		* ''Efficiency'' is the speedup per processor, {{math\|''S<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>
	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>

KaiaVintr: /* Definitions */ add visible anchor for "Critical path"

2024-09-18T16:16:43Z

Definitions: add visible anchor for "Critical path"

← Previous revision		Revision as of 16:16, 18 September 2024
Line 56:		Line 56:

	* 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\|citeseerx=10.1.1.466.8142 }}</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''<sub>1</sub>}}.		* 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\|citeseerx=10.1.1.466.8142 }}</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''<sub>1</sub>}}.
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''{{visible anchor\|Critical path\|text=critical path}}''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>

Nyq: lc common adjective

2024-08-16T01:05:06Z

lc common adjective

← Previous revision		Revision as of 01:05, 16 August 2024
Line 14:		Line 14:
	\| doi =10.1016/0196-6774(82)90013-X }}</ref>		\| doi =10.1016/0196-6774(82)90013-X }}</ref>
	for conceptualizing and describing parallel algorithms.		for conceptualizing and describing parallel algorithms.
	In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is guided by the proof of a scheduling theorem due to Brent,<ref name="brent">{{Cite journal\|last=Brent\|first=Richard P.\|date=1974-04-01\|title=The Parallel Evaluation of General Arithmetic Expressions\|journal=Journal of the ACM\|volume=21\|issue=2\|pages=201–206\|doi=10.1145/321812.321815\|issn=0004-5411\|citeseerx=10.1.1.100.9361\|s2cid=16416106}}</ref> which is explained later in this article. The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. For example, the WT framework was adopted as the basic presentation framework in the parallel algorithms books (for the [[~~Parallel~~ random-access machine]] PRAM model)		In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is guided by the proof of a scheduling theorem due to Brent,<ref name="brent">{{Cite journal\|last=Brent\|first=Richard P.\|date=1974-04-01\|title=The Parallel Evaluation of General Arithmetic Expressions\|journal=Journal of the ACM\|volume=21\|issue=2\|pages=201–206\|doi=10.1145/321812.321815\|issn=0004-5411\|citeseerx=10.1.1.100.9361\|s2cid=16416106}}</ref> which is explained later in this article. The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. For example, the WT framework was adopted as the basic presentation framework in the parallel algorithms books (for the [[parallel random-access machine]] PRAM model)
	<ref name="jaja">{{cite book		<ref name="jaja">{{cite book
	\| first = Joseph		\| first = Joseph

Worldec478: added citation to book explaining analytical expressions for the speedup of many important parallel algorithms

2024-07-25T17:18:06Z

added citation to book explaining analytical expressions for the speedup of many important parallel algorithms

← Previous revision		Revision as of 17:18, 25 July 2024
Line 66:		Line 66:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''p''}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability\|scalable]].<ref name="casanova"/>		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>		* ''Efficiency'' is the speedup per processor, {{math\|''S<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>
	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>

JayBeeEll: Restored revision 1171117787 by 18.25.27.32 (talk): Rv refspam

2024-04-03T17:54:29Z

Restored revision 1171117787 by 18.25.27.32 (talk): Rv refspam

← Previous revision		Revision as of 17:54, 3 April 2024
Line 58:		Line 58:
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>


	Several useful results follow from the definitions of work, span and cost:		Several useful results follow from the definitions of work, span and cost:
Line 67:		Line 66:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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 <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>.		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>		* ''Efficiency'' is the speedup per processor, {{math\|''S<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>

	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
	* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />		* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />

62.76.220.20: /* Definitions */

2024-04-03T14:01:08Z

Definitions

← Previous revision		Revision as of 14:01, 3 April 2024
Line 58:		Line 58:
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>

	Analytical expressions for the speedup of many important parallel algorithms are presented in <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>

	Several useful results follow from the definitions of work, span and cost:		Several useful results follow from the definitions of work, span and cost:
Line 67:		Line 67:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''p''}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability\|scalable]].<ref name="casanova"/>		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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 <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>.

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

	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
	* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />		* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />

2A03:D000:1400:93EE:7D68:23BD:8EA6:9648: /* Definitions */

2024-04-03T13:32:31Z

Definitions

← Previous revision		Revision as of 13:32, 3 April 2024
Line 58:		Line 58:
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>
			Analytical expressions for the speedup of many important parallel algorithms are presented in <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>

	Several useful results follow from the definitions of work, span and cost:		Several useful results follow from the definitions of work, span and cost:

← Previous revision		Revision as of 16:16, 18 September 2024
Line 56:		Line 56:

	* 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\|citeseerx=10.1.1.466.8142 }}</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''<sub>1</sub>}}.		* 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\|citeseerx=10.1.1.466.8142 }}</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''<sub>1</sub>}}.
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''{{visible anchor\|Critical path\|text=critical path}}''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>

← Previous revision		Revision as of 17:54, 3 April 2024
Line 58:		Line 58:
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>


	Several useful results follow from the definitions of work, span and cost:		Several useful results follow from the definitions of work, span and cost:
Line 67:		Line 66:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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 <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>.		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>		* ''Efficiency'' is the speedup per processor, {{math\|''S<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>

	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
	* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />		* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />

← Previous revision		Revision as of 14:01, 3 April 2024
Line 58:		Line 58:
	* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>		* The ''depth'' or ''span'' is the length of the longest series of operations that have to be performed sequentially due to [[data dependency\|data dependencies]] (the ''critical path''). The depth may also be called the ''critical path length'' of the computation.<ref name="cacm">{{cite journal \|first=Guy \|last=Blelloch \|title=Programming Parallel Algorithms \|journal=[[Communications of the ACM]] \|volume=39 \|issue=3 \|year=1996 \|doi=10.1145/227234.227246 \|url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf \|pages=85–97\|citeseerx=10.1.1.141.5884 \|s2cid=12118850 }}</ref> Minimizing the depth/span is important in designing parallel algorithms, because the depth/span determines the shortest possible execution time.<ref name="spp">{{cite book \|author1=Michael McCool \|author2=James Reinders \|author3=Arch Robison \|title=Structured Parallel Programming: Patterns for Efficient Computation \|publisher=Elsevier \|year=2013 \|pages=4–5}}</ref> Alternatively, the span can be defined as the time {{math\|''T''<sub>∞</sub>}} spent computing using an idealized machine with an infinite number of processors.<ref name="clrs">{{Introduction to Algorithms\|3\|pages=779–784}}</ref>
	* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>		* The ''cost'' of the computation is the quantity {{mvar\|pT<sub>p</sub>}}. This expresses the total time spent, by all processors, in both computing and waiting.<ref name="casanova"/>

	Analytical expressions for the speedup of many important parallel algorithms are presented in <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>

	Several useful results follow from the definitions of work, span and cost:		Several useful results follow from the definitions of work, span and cost:
Line 67:		Line 67:
	Using these definitions and laws, the following measures of performance can be given:		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<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''p''}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability\|scalable]].<ref name="casanova"/>		* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math\|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. 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''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup\|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math\|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''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 <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>.

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

	* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>		* ''Parallelism'' is the ratio {{math\|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math\|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
	* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />		* The ''slackness'' is {{math\|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar\|p}} processors.<ref name="clrs" />