Bounding series-parallel slowdown
- 15:00 18th June 2009 ( week Eighth Week, Trinity Term 2009 )Common Room (103)
Bounding series-parallel slowdown
(joint work with Vashti Galpin, Edinburgh)
Directed acyclic graphs with node weights can model parallel programs. This model is called an activity-on-node network or task graph, and each weight represents the time duration of an activity.
Programming constructs in parallel computing environments such as Matlab Parallel Computing Toolbox and OpenCL can be regarded as implicit series-parallelisation, that is, the addition of precedence constraints so that the network becomes series-parallel. The slowdown ratio describes the resulting increase in makespan (execution time). Van Gemund conjectured in 1997 that any network can be series-parallelised with slowdown at most 2, disregarding activity durations. I will demonstrate that this conjecture fails for neighbour synchronisation networks, and instead we propose the conjecture that series-parallelisation is possible with slowdown at most 4/3, if durations are known. This conjecture is true for small networks. However, achieving 4/3 slowdown is in exp-APX, and appears to be NP-hard. I will discuss practical implications for parallel programming.
(joint work with Vashti Galpin, Edinburgh)
Directed acyclic graphs with node weights can model parallel programs. This model is called an activity-on-node network or task graph, and each weight represents the time duration of an activity.
Programming constructs in parallel computing environments such as Matlab Parallel Computing Toolbox and OpenCL can be regarded as implicit series-parallelisation, that is, the addition of precedence constraints so that the network becomes series-parallel. The slowdown ratio describes the resulting increase in makespan (execution time). Van Gemund conjectured in 1997 that any network can be series-parallelised with slowdown at most 2, disregarding activity durations. I will demonstrate that this conjecture fails for neighbour synchronisation networks, and instead we propose the conjecture that series-parallelisation is possible with slowdown at most 4/3, if durations are known. This conjecture is true for small networks. However, achieving 4/3 slowdown is in exp-APX, and appears to be NP-hard. I will discuss practical implications for parallel programming.