@mastersthesis{Salamon2001:thesis,
  abstract = "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. ",
  author = "Andr{\'a}s Z. Salamon",
  month = "jan",
  school = "University of the Witwatersrand, Johannesburg",
  title = "Task Graph Performance Bounds Through Comparison Methods",
  url = "ftp://ftp.cs.wits.ac.za/pub/research/reports/TR-Wits-CS-2001-0.pdf",
  year = "2001",
}