Slide 1Work and spanSlide 3Slide 4Slide 5Series CompositionParallel CompositionSpeedupParallelismComplexity measures for parallel computationLaws of parallel complexityDetailed complexity measures for data movement IDetailed complexity measures for data movement IIComplexity Measures for Parallel ComputationTP = execution time on P processorsWork and spanWork and spanTP = execution time on P processorsT1 = workWork and spanWork and spanTP = execution time on P processors*Also called critical-path lengthor computational depth.T1 = work T∞ = span*Work and spanWork and spanTP = execution time on P processorsT1 = work T∞ = span**Also called critical-path lengthor computational depth.WORK LAW∙TP ≥T1/PSPAN LAW∙TP ≥ T∞Work and spanWork and spanWork: T1(A∪B) =Series CompositionSeries CompositionAABBWork: T1(A∪B) = T1(A) + T1(B)Span: T∞(A∪B) = T∞(A) +T∞(B)Span: T∞(A∪B) =Parallel CompositionParallel CompositionAABBSpan: T∞(A∪B) = max{T∞(A), T∞(B)}Span: T∞(A∪B) =Work: T1(A∪B) =Work: T1(A∪B) = T1(A) + T1(B)Def. T1/TP = speedup on P processors.If T1/TP= (P), we have linear speedup,= P, we have perfect linear speedup,> P, we have superlinear speedup, (which is not possible in this model, because of the Work Law TP ≥ T1/P)SpeedupSpeedupParallelismParallelismBecause the Span Law dictates that TP ≥ T∞, the maximum possible speedup given T1 and T∞ isT1/T∞ = (potential) parallelism= the average amount of work per step along the span.Complexity measures for parallel computationComplexity measures for parallel computationProblem parameters:•n index of problem size•p number of processorsAlgorithm parameters:•tprunning time on p processors•t1time on 1 processor = sequential time = “work”•t∞time on unlimited procs = critical path length = “span”•v total communication volumePerformance measures•speedup s = t1 / tp•efficiency e = t1 / (p*tp) = s / p•(potential) parallelism pp = t1 / t∞Laws of parallel complexityLaws of parallel complexity•Work law: tp ≥ t1 / p• Span law: tp ≥ t∞ •Amdahl’s law:•If a fraction f, between 0 and 1, of the work must be done sequentially, then speedup ≤ 1 / f•Exercise: prove Amdahl’s law from the span law.Detailed complexity measures for data movement IDetailed complexity measures for data movement IMoving data between processors by message-passing•Machine parameters:•  or tstartup latency (message startup time in seconds) •  or tdata inverse bandwidth (in seconds per word)•between nodes of Triton,    × 10-6and    × 10-9•Time to send & recv or bcast a message of w words:  + w*•tcomm total commmunication time• tcomp total computation time•Total parallel time: tp = tcomp + tcommDetailed complexity measures for data movement IIDetailed complexity measures for data movement IIMoving data between cache and memory on one processor:•Assume just two levels in memory hierarchy, fast and slow•All data initially in slow memory•m = number of memory elements (words) moved between fast and slow memory •tm = time per slow memory operation•f = number of arithmetic operations•tf = time per arithmetic operation, tf << tm•q = f / m average number of flops per slow element access•Minimum possible time = f * tf when all data in fast memory•Actual time •f * tf + m * tm = f * tf * (1 + tm/tf * 1/q) •Larger q means time closer to minimum f *