For multi- and many-core CPUs, dynamic voltage and frequency scaling (DVFS) for individual cores provides an effective way for energy-efficient execution of applications. However, this requires additional hardware within the chip that regulates voltage and frequency for each hardware sub-component that can be scaled separately. Because of the significant cost of this control hardware, it is often not realistic to provide such a regulator for each individual core. Instead, chip manufacturers group cores into islands consisting of multiple cores with a common regulator, and energy optimizing solutions must take this constraint into account when assigning frequencies to jobs and cores. Crown Scheduling is a technique for the combined resource allocation, mapping and discrete DVFS-level selection for actor networks consisting of moldable parallel streaming tasks for energy efficient execution given a throughput constraint. We extend crown scheduling to compute correct schedules also in the presence of DVFS islands constraints. We find that, for most task sets, the crown scheduler computes almost equally good schedules for target architectures with and without island constraints.

Visual understanding of 3-D environments in real time, at low power, is a huge computational challenge. Often referred to as simultaneous localization and mapping (SLAM), it is central to applications spanning domestic and industrial robotics, autonomous vehicles, and virtual and augmented reality. This paper describes the results of a major research effort to assemble the algorithms, architectures, tools, and systems software needed to enable delivery of SLAM, by supporting applications specialists in selecting and configuring the appropriate algorithm and the appropriate hardware, and compilation pathway, to meet their performance, accuracy, and energy consumption goals. The major contributions we present are: 1) tools and methodology for systematic quantitative evaluation of SLAM algorithms; 2) automated, machine-learning-guided exploration of the algorithmic and implementation design space with respect to multiple objectives; 3) end-to-end simulation tools to enable optimization of heterogeneous, accelerated architectures for the specific algorithmic requirements of the various SLAM algorithmic approaches; and 4) tools for delivering, where appropriate, accelerated, adaptive SLAM solutions in a managed, JIT-compiled, adaptive runtime context.

We demonstrate how static, energy-efficient, compiler-generated schedules for independent, parallelizable tasks on parallel machines can be improved by modeling idle power. We assume that the static power consumption of a core comprises a notable fraction of the core's total power, which is more and more often the case. The improvement is achieved by optimally packing cores when deciding about core allocation, mapping and DVFS for each task so that all unused cores can be switched off and overall energy usage is minimized. We evaluate our proposal with a benchmark suite of task collections, and compare the resulting schedules with an optimal scheduler that does not take idle power and core switch-off into account. We find that we can reduce energy consumption by 66% for mostly sequential tasks on many cores and by up to 91% for a realistic multicore processor model.

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.