Bounds on series-parallel slowdown
| dc.creator | Salamon, András Z. | |
| dc.creator | Galpin, Vashti | |
| dc.date | 2009-04-29 | |
| dc.date.accessioned | 2026-07-07T13:09:52Z | |
| dc.date.available | 2026-07-07T13:09:52Z | |
| dc.description | 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. | |
| dc.description | 12 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/0904.4512 | |
| dc.identifier | http://arxiv.org/abs/0904.4512 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/228882 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | Computational Complexity | |
| dc.subject | Performance | |
| dc.subject | D.1.3; D.3.3; D.4.8; F.2.2; G.2.2 | |
| dc.title | Bounds on series-parallel slowdown | |
| dc.type | text |