Welcome to data.at.preempted.net
ILP formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems
Wednesday, February 26 2014 @ 01:24 AM UTC
Contributed by: Sarad
To fully benefit from a multiprocessor system, the tasks of a program are to be carefully assigned and scheduled on the processors of the system such that the overall execution time is minimal. The associated task scheduling problem with communication delays, P|prec; cij |Cmax, is a well known NP-hard problem. We propose a novel Mixed Integer Linear Programming (MILP) solution to this scheduling problem, despite the fact that scheduling problems are often difficult to handle by MILP solvers. The proposed MILP solution uses problem specific knowledge to eliminate the need to linearise the bilinear equations arising out of communication delays. Further, the size of the proposed formulation in terms of variables is independent of the number of processors. We analyse and discuss the influence of the different MILP components in respect to characteristics of the task graph such as structure and communication to computation ratio. The proposed MILP formulation is experimentally compared with previous MILP formulations used to solve this scheduling problem. The proposed formulation displays a drastic improvement in performance, which allows to solve larger problems optimally. We also observe strengths and weaknesses of the formulation related to the input characteristics.
Copyright © 2017 data.at.preempted.net
All trademarks and copyrights on this page are owned by their respective owners.
Powered by Geeklog
Created this page in 0.03 seconds