Stewart, Russell

Optimising makespan and energy consumption in task scheduling for parallel systems

Russell Stewart¹, Andrea Raith¹, and Oliver Sinnen²

1. Department of Engineering Science, University of Auckland

2. Department of Electrical and Computer Engineering, University of Auckland

In parallel computing multiple processors are employed to execute a program faster than it could be executed by a single processor. To achieve high efficiency, the scheduling of the tasks of an application onto the processors of the parallel system is crucial. Such a task schedule determines both the allocation of tasks to one of the processors, and the order in which they are executed. This task scheduling problem is a challenging optimisation problem (strongly NP-hard), even for the case where there is only one objective, e.g. to minimise the total execution time, also known as makespan. Today task scheduling is often a constrained optimisation problem, where the makespan needs to be minimised, while keeping energy consumption below a threshold. Here, we consider a multi-objective version of this scheduling problem that aims to minimise both makespan and energy consumption. Based on a model of processor energy consumption, a multi-objective integer linear programming problem is formulated. Different approaches to modelling energy consumption of processor idle times before, during, and after task execution, are described. The task scheduling problems can be solved using multi-objective optimisation methods based on weighted sum or \(\varepsilon\)-constraint methods. Computational performance and characteristics of Pareto sets of solutions of this multi-objective problem are discussed.

This presentation is eligible for the ORSNZ Young Practitioners Prize.