Content deleted Content added
10.1145/227234.227246 |
|||
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''<sub>1</sub>}}.
* The ''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 span may also be called the ''critical path length'' or the ''depth'' 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}}</ref> Minimizing the span is important in designing parallel algorithms, because the 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"/>
| |||