Fast algorithms for thermal constrained performance optimization in DAG scheduling on multi-core processors

Thermal management is highly crucial for efficient exploitation of the potentially enormous computational power offered by advanced multi-core processors. Higher temperatures can adversely affect these processors. Without any thermal constraint, a task graph may be scheduled to run on the cores at their maximum voltage. Very often, multiple factors lead to imposing constraints on temperature, ensuring that cores remain below a certain temperature range and yet deliver good performance. The challenge is how to schedule the same task graph under the imposed thermal constraints such that the performance degradation is the minimum. In this paper we present two algorithms for minimizing the performance degradation and the corresponding overhead while satisfying the thermal constraints. The proposed algorithms, named PAVD, and TAVD, adjust a given schedule of a task graph by decreasing the voltage level of judiciously selected tasks in each step. The algorithms differ in the way they select a task at each step and the amount of time spent in searching that task. TAVD selects the tasks by prioritizing among the cores and tasks which attained maximum temperature while PAVD selects the tasks with the minimum performance penalty. For comparison, we develop a simpler greedy-based approach to show that the problem is non-trivial. Extensive experiments using both random and application-oriented task graphs demonstrate that all three algorithms satisfy the imposed thermal constraints by trading-off performance, while each showing its own strength.