A Note on Parallel Algorithmic Speedup Bounds

2011/04/20 by Neil J. Gunther, Gunther, Neil J.
Computer Science · #B.8 #C.4 #C.5.5 #D.4.8 #Distributed #F.1.2 #FOS: Computer and information sciences #Parallel #Performance (cs.PF) #and Cluster Computing (cs.DC) #cs.DC #cs.PF

paper · pdf · doi:10.48550/arxiv.1104.4078

5 pages, 1 figure

arxiv created 2011/04/20 · arxiv updated 2011/04/21

Abstract

A parallel program can be represented as a directed acyclic graph. An important performance bound is the time to execute the critical path through the graph. We show how this performance metric is related to Amdahl speedup and the degree of average parallelism. These bounds formally exclude superlinear performance.

Related

• Speedup and efficiency of computational parallelization: A unifying approach and asymptotic analysis
• A generalization of Amdahl's law and relative conditions of parallelism
• Bounds on series-parallel slowdown
• A sufficient condition for a linear speedup in competitive parallel computing
• On Characterizing the Data Movement Complexity of Computational DAGs for Parallel Execution