An Energy-Optimal Real-Time Scheduling Algorithm for Unrelated DVS-Enabled Parallel Machines

The category of unrelated parallel machines is one of the most realistic models of heterogeneous multiprocessor systems. In this model, the pair of task and machine (processor) jointly specifies the required execution time and energy to complete the task. In this paper, we consider the problem of scheduling real-time tasks on a set of unrelated parallel machines with the capability of voltage selection through Dynamic Voltage Scaling (DVS). The tasks can migrate among the processors and each processor is also permitted to switch among a set of discrete voltage levels (and thus, task-specific speed levels) to minimize the overall system energy usage. A polynomial-time Energy-Optimal Real-Time Scheduling Algorithm (EORTSA) is proposed: At first, the problem of energy-optimal task-to-machine and voltage-level-to-task assignments are formulated as a linear program and used as a polynomial-time schedule ability test for periodic tasks. Second, task sets which are passed the schedule ability test are feasibly scheduled on the machines using a matching-based algorithm. We prove that the worst number of migratory tasks is 2m, where m is the number of machines. Also, the worst-case total number of migrations, preemptions and voltage-level switches is of O(m^2) in each schedule e period, which is a period of time between two arbitrary consecutive task releases in the system. Comparisons with the PCG algorithm show up to 60% energy saving and reveal that EORTSA outperforms PCG in terms of average number of task migrations and preemptions, especially in systems with large number of tasks.