Energy and transition-aware runtime task scheduling for multicore processors

• We propose a transition-aware task scheduling algorithm for multicore processors.
• Ignoring the transition overhead will defeat the benefit of task scheduling.
• We construct an ILP model to find the optimal solutions for off-line scheduling.
• We propose a heuristic algorithm for a runtime environment.
• We derive the complexity and theoretical bound for the heuristic algorithm.

Many embedded or portable devices have large demands on running real-time applications. The designers start to adopt the multicore processors in these devices. The multi-core processors, however, cause much higher power consumption than ever before. To resolve this problem, many researchers have focused their studies on designing the energy-aware task scheduling algorithms for multicore processors. Conventional scheduling algorithms assumed that each core can operate under different voltage levels. However, they have not considered the effects of voltage transition overheads, which may defeat the benefit of task scheduling. In this paper, we aim to resolve this scheduling problem with voltage transition overhead consideration. We formalize this problem by an integer linear programming model and propose a heuristic algorithm for a runtime environment. The experimental results show that the proposed online heuristic algorithm can obtain the comparable results with the optimal scheduling derived by the offline integer linear programming approach.