Summary We investigate static scheduling of taskgraphs onto parallel machines where the frequency of processors can be scaled at runtime. Given a deadline until which execution of the resulting schedule must be completed, we aim at minimizing the energy consumed by the parallel processors during execution. We present optimal and heuristic solutions to this problem and partial problems. We quantify the increase in energy consumption when switching from a globally optimal solution via a combination of optimal partial solutions to heuristic solutions. We find that, on our set of benchmark taskgraphs, the increase is 32.56% on average for a combination of heuristic solutions and thus tolerable.

Workflows of dependent tasks are a widespread model for parallel applications, often statically scheduled prior to application. Static schedules can tolerate processor failures due to permanent faults by placing duplicate tasks during the scheduling process. Schedules for workflows with deadlines can be extended to include frequency scaling information to optimize energy consumption. Frequency scaling can also be used in case of a fault to minimize its effects on the schedule makespan, however for the price of additional energy consumption. We investigate the interplay between these two parameters and quantify the energy increase to be expected in case of a fault and a given makespan increase. This knowledge enables the user to inform the scheduler about the makespan increase that is tolerable in case of a fault, where tolerable includes both the related performance aspects and the expected increase in energy. To achieve this, we model small taskgraphs from a benchmark suite as integer linear programs and determine with the help of a solver energy-optimal schedules for the fault-free case and for all possible fault positions with several levels of makespan increase. We present averages and distribution depending on makespan increase for a processor with hypothetical power profile. Additionally, we present two heuristics to modify task frequency settings in case of a fault, to restrict the makespan increase to a given value. Comparison with optimal frequency settings from the benchmark suite indicate that the heuristics only incur a small energy overhead.

We investigate deadline scheduling of independent tasks on parallel processors with discrete frequency levels, when the latency for frequency scaling cannot be neglected. This situation frequently occurs in applications, e.g. streaming applications with soft real-time requirements. We demonstrate that previous algorithms for energy-optimal static scheduling of independent tasks are non-optimal in this setting. We present a scheduling heuristic based on bin packing with a cost function that takes latency for frequency scaling into account. We evaluate our heuristic against previous approaches with benchmark task sets and achieve energy reductions between 3% and 13%. We further demonstrate that for a concrete embedded multicore processor, the power curves vary over the identical cores, so that the processor looks heterogeneous from a power perspective. We adapt our bin packing heuristic and demonstrate that for the benchmark task sets, further energy reductions up to 4% can be achieved.

Static schedules can be a preferable alternative for applications with timing requirements and predictable behavior since the processing resources can be more precisely allocated for the given workload. Unused resources are handled by power management systems to either scale down or shut off parts of the chip to save energy. In order to efficiently implement power management, especially in many-core systems, an accurate model is important in order to make the appropriate power management decisions at the right time. For making correct decisions, practical issues such as latency for controlling the power saving techniques should be considered when deriving the system model, especially for fine timing granularity. In this paper we present an accurate energy model for many-core systems which includes switching latency of modern power saving techniques. The model is used when calculating an optimal static schedule for many-core task execution on systems with dynamic frequency levels and sleep state mechanisms. We create the model parameters for an embedded processor, and we validate it in practice with synthetic benchmarks on real hardware.

Exploiting effectively massively parallel architectures is a major challenge that stream programming can help to face. We investigate the problem of generating energy-optimal code for a collection of streaming tasks that include parallelizable or moldable tasks on a generic manycore processor with dynamic discrete frequency scaling. In this paper we consider crown scheduling, a novel technique for the combined optimization of resource allocation, mapping and discrete voltage/frequency scaling for moldable streaming task collections in order to optimize energy efficiency given a throughput constraint. We present optimal off-line algorithms for separate and integrated crown scheduling based on integer linear programming (ILP) and heuristics able to compute solution faster and for bigger problems. We make no restricting assumption about speedup behavior.

Exploiting effectively massively parallel architectures is a major challenge that stream programming can help facilitate. We investigate the problem of generating energy-optimal code for a collection of streaming tasks that include parallelizable or moldable tasks on a generic manycore processor with dynamic discrete frequency scaling. Streaming task collections differ from classical task sets in that all tasks are running concurrently, so that cores typically run several tasks that are scheduled round-robin at user level in a data-driven way. A stream of data flows through the tasks and intermediate results may be forwarded to other tasks, as in a pipelined task graph. In this article, we consider crown scheduling , a novel technique for the combined optimization of resource allocation, mapping, and discrete voltage/frequency scaling for moldable streaming task collections in order to optimize energy efficiency given a throughput constraint. We first present optimal offline algorithms for separate and integrated crown scheduling based on integer linear programming (ILP). We make no restricting assumption about speedup behavior. We introduce the fast heuristic Longest Task, Lowest Group (LTLG) as a generalization of the Longest Processing Time (LPT) algorithm to achieve a load-balanced mapping of parallel tasks, and the Height heuristic for crown frequency scaling. We use them in feedback loop heuristics based on binary search and simulated annealing to optimize crown allocation. Our experimental evaluation of the ILP models for a generic manycore architecture shows that at least for small and medium-sized streaming task collections even the integrated variant of crown scheduling can be solved to optimality by a state-of-the-art ILP solver within a few seconds. Our heuristics produce makespan and energy consumption close to optimality within the limits of the phase-separated crown scheduling technique and the crown structure. Their optimization time is longer than the one of other algorithms we test, but our heuristics consistently produce better solutions.