2009/04/29 by András Z. Salamon, Salamon, András Z., Vashti Galpin +1
Computer Science · #Computational Complexity (cs.CC) #D.1.3 #D.3.3 #D.4.8 #Distributed #Distributed and Parallel Computing Systems #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems #Parallel #Parallel Computing and Optimization Techniques #Performance (cs.PF) #and Cluster Computing (cs.DC) #cs.CC #cs.DC #cs.PF
paper · pdf · doi:10.48550/arxiv.0904.4512
12 pages, 4 figures
arxiv created 2009/04/29 · openalex publication_date 2009/04/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We use activity networks (task graphs) to model parallel programs and consider series-parallel extensions of these networks. Our motivation is two-fold: the benefits of series-parallel activity networks and the modelling of programming constructs, such as those imposed by current parallel computing environments. Series-parallelisation adds precedence constraints to an activity network, usually increasing its makespan (execution time). The slowdown ratio describes how additional constraints affect the makespan. We disprove an existing conjecture positing a bound of two on the slowdown when workload is not considered. Where workload is known, we conjecture that 4/3 slowdown is always achievable, and prove our conjecture for small networks using max-plus algebra. We analyse a polynomial-time algorithm showing that achieving 4/3 slowdown is in exp-APX. Finally, we discuss the implications of our results.