Bounding series-parallel slowdown

Andras Salamon


We use directed acyclic graphs with node weights to model parallel programs. These are called activity-on-node networks or task graphs; each weight represents the duration of an activity. Programming constructs in parallel computing environments such as OpenCL and Matlab Parallel Computing Toolbox lead naturally to series-parallel activity networks. We consider series-parallelisations, formed by adding precedence constraints until the network becomes series-parallel. The slowdown ratio describes the resulting increase in makespan (execution time). Van Gemund conjectured that any network can be series-parallelised with slowdown at most 2, disregarding activity durations. We disprove this by considering neighbour synchronisation networks, and instead conjecture that if durations are known, then series-parallelisation is possible with slowdown at most 4/3. We show that the new conjecture is true for small networks, and outline a computer assisted proof technique for slightly larger networks. We also show that achieving 4/3 slowdown is in exp-APX, and appears to be NP-hard (joint work with Vashti Galpin, Edinburgh)

Thursday 11th June 2009, 14:00
Digital Technium, Room 05 (Access Grid Room) - Joint Seminar with Bath University
Department of Computer Science