In parallel computing, the scheduling of the tasks of an application onto the processors of the parallel system is crucial. A task schedule determines both the allocation of tasks to the processors, and the order in which they are executed. Formally defined, 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, or vice versa, where the energy consumption needs to be minimised, while keeping the makespan below a threshold. In a generalisation of this problem, we consider here a bi-objective version of this scheduling problem that aims to minimise both makespan and energy consumption in a Pareto-efficient manner. Based on a model of processor energy consumption, a bi-objective integer linear programming problem is formulated. Different approaches to modelling processor static (background) energy consumption are described. The task scheduling problems can be solved using bi-objective optimisation methods based on weighted sum scalarisation or epsilon-constraint scalarisation. In an extensive evaluation, the computational performance and the characteristics of sets of Pareto-efficient solutions of this bi-objective problem are studied and discussed, with interesting insights into the nature and shape of the Pareto-efficient sets.
展开▼
