Task Graph Performance Bounds Through Comparison Methods

When a parallel computation is represented in a formalism that imposes series-parallel structure on its task graph, it becomes amenable to automated analysis and scheduling. Unfortunately, its execution time will usually also increase as precedence constraints are added to ensure series-parallel structure. Bounding the slowdown ratio would allow an informed tradeoff between the benefits of a restrictive formalism and its cost in loss of performance.This dissertation deals with series-parallelising task graphs by adding precedence constraints to a task graph, to make the resulting task graph series-parallel. The weak bounded slowdown conjecture for series-parallelising task graphs is introduced. This states that the slowdown is bounded if information about the workload can be used to guide the selection of which precedence constraints to add. A theory of best series-parallelisations is developed to investigate this conjecture.Partial evidence is presented that the weak slowdown bound is likely to be 4/3, and this bound is shown to be tight