Scheduling precedence graphs to minimize total system time in partitionable parallel architectures

Two issues are introduced into the scheduling problem: each of the sub-tasks can be performed using one of a number of parallel algorithms running on different configurations; and there is an overhead time to move data (reconfiguration time) from the configuration required by one algorithm to the configuration required by the algorithm of the successor sub-task. The execution time for each algorithm and the reconfiguration times between all pairs of algorithms are provided along with the precedence graph. The problem is to find for each sub-task the algorithm to be executed such that the total system time, which is the sum of the execution times and the data movement times of all the selected algorithms, is minimized. The authors show that the problem is NP-hard even when the total degree, of each node of the precedence graph is at most three. They show that it can be solved in polynomial time if the total degree of each node is at most two, thus completely closing the gap between the polynomially solvable cases and the NP-hard cases in terms of the maximum degree of the precedence graph