Content deleted Content added
No edit summary |
Tag: Reverted |
||
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 ''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:
| |||