Channel based scheduling of parallelizable tasks

Considers the problem of scheduling a set of tasks on a parallel machine of identical processors. The tasks are parallelizable and can be run simultaneously on several processors, in which case the runtime is decreased, Our goal is to minimize the finishing time (or makespan) of the entire schedule. This problem is known to be NP-hard. We propose a new approach to scheduling, based on partitioning the available processors into a fixed number of computation channels. We assign tasks to channels based on their execution times and their speed-up function, assuming that these parameters are available prior to the execution of the task sequence. The channel approach is shown to be advantageous whenever the overall work needed to execute tasks does not decrease as a function of the number of processors assigned to it, i.e. in most common scenarios. For cases in which this function is a constant (and, therefore, the overall runtime per task decreases linearly with the number of processors executing it), we present a new scheduling heuristic called the partition-and-assignment (PA) algorithm. PA is shown to achieve a worst case bound of 2 to the optimal schedule. It runs in linear time, O(n+m), where m is the number of processors and n is the number of tasks. For the case of nonlinear speedup, we introduce a generalized version of PA (GPA), which achieves a bound of 2 to the optimum, and runs in time O(m log a+n), where a=min(n,m)