The first Operating-System-Directed Power-Management Summit

The first Operating-System-Directed Power-Management (OSPM) Summit took place at the ReTiS Lab of the Scuola Superiore Sant'Anna in Pisa on April 3 and 4, 2017. This summit was organized as a collection of collaborative sessions focused on trying to improve how operating-system-directed power management and the kernel's task scheduler can work together to achieve the goal of reducing energy consumption while still meeting performance and latency requirements. This subject is receiving great interest, not least since the advent of energy-aware scheduling (EAS) and heterogeneous CPU designs.

Since such a complex endeavor requires experts from multiple areas of expertise, the summit brought together people from academia, open-source maintainership (Peter Zijlstra, Rafael Wysocki, Thomas Gleixner), and industry (Google, Red Hat, Linaro, NVIDIA, LG Electronics, BayLibre, Huawei, Qualcomm, and ARM). The relaxed atmosphere of the venue and the manageable group of attendees allowed for intense debate and face-to-face discussions about current problems. Several proposals or proof-of-concept solutions were presented during the sessions.

The following chapters, clustered by functional area, summarize the discussions of the individual sessions. Each chapter headline represents a link to a YouTube recording of the corresponding session.

Per-entity load tracking

Another topic was the possible integration of a PELT-based mechanism for realtime class utilization tracking that would represent time stolen from the completely fair scheduling (CFS) class by realtime tasks. Currently, due to the lack of any utilization signal for realtime tasks, we go to maximum CPU frequency at the first tick after a realtime task is enqueued. When that task blocks and a CFS task starts running, the schedutil CPU-frequency governor receives the (by now decayed) CFS utilization value, which leads to a sudden CPU-frequency drop. This could be avoided by considering the realtime task utilization when invoking schedutil. The mechanism should work similarly to the calculation of the remaining CPU capacity for CFS tasks via scale_rt_capacity(), but for utilization instead.

A similar issue that was discussed is the frequency drop that occurs when a CFS task migrates away from an overloaded CPU.

PELT decay clamping/UTIL_EST. Morten Rasmussen showed the results of his PELT decay-clamping implementation, an idea that was first proposed by Paul Turner during the 2016 Linux Plumbers Conference in Santa Fe. The problem is that we lose history for a big task that sleeps for a long time. Decay clamping places a limit on the time for which a task’s load-tracking signals can decay after the task sleeps, making the task appear to have slept for less time. The actual implementation revealed some issues with the idea. Since entity load and utilization are accrued in a CFS run queue, they would have to be de-clamped in case the entity is attached or detached to or from the queue. Another issue is that the preempted time of a co-scheduled task is not accounted as sleep time.

Patrick Bellasi demonstrated an alternative approach, UTIL_EST, which keeps PELT as an estimator and adds a new signal, the estimated utilization (hence the name) as a sort-of low pass filter on PELT’s derived values. The current proposal tracks both the utilization at task deactivation time as well as an exponential moving average of these values. A series implementing this idea is going to be posted soon on the linux-kernel mailing list for a better evaluation.

Energy-aware scheduling

EAS: where we are. Morten Rasmussen started with a short introduction on EAS and its importance in maximizing both CPU utilization and power efficiency, along with a short overview of why frequency- and CPU-invariant scaling for PELT load and utilization signals is important. He made it clear that having an energy model is key for scheduling decisions based on energy consumption and that the EAS energy model is the best we can currently do. He continued by pointing out that there is no place to store energy data (energy consumption per operating performance point (OPP) and per idle state at every scheduling domain level) in mainline Linux.

The device tree would be a good place to store such information but there is a lot of resistance from the device-tree community. For them, energy data should describe hardware configuration (in this case CPU core) data, which should be provided by the core designer. Or at least they require a strictly defined method to determine the energy consumption. What they don't want is a situation where different vendors have different values for the same CPU core.

But energy data is a platform-specific property rather than a core-specific one, so each vendor would have to provide it. The methodology to obtain the values for the energy model is to measure the energy consumption while the platform is forced to run a workload on subsets of cores at fixed OPPs or idle at fixed idle states. The workload is not standardized and it is clear that the values gathered are for the instruction mix of this specific workload. This also requires that energy consumption is measurable at the core and cluster scheduling domain levels.

EAS uses the relative numbers of the energy model; in other words, the energy model is like a single tuning knob for EAS. This is another reason why the device-tree folks argue that it does not belong into the device tree. A possible simplification of the energy model based solely on CPU-level data and not on aggregate data (e.g. on cluster-level) might be the way forward.

Other discussion points were about the use of the proposed features outside of the Android-specific domain. There are other run-time systems (e.g. ChromeOS and Kubernetes) that might be interested in the proposed interface. Moreover, it can be used to improve existing features such as avoiding a jump to the maximum frequency every time a realtime task runs. Alternative implementations to boost the minimum capacity have been discussed but some of them were already rejected in the past for various reasons. There was no agreement that the control-group-based interface would be sufficient so it is likely that a per-task interface will have to be added. Overall the discussion was useful to make key maintainers aware of the proposal.

The rate-limiting mechanism, designed to prevent frequency updates from happening too often (which may lead to some undesirable effects), is arguably suboptimal, but some relatively inexpensive improvements appear to be possible. A few of them were discussed during the session, including allowing cpufreq drivers to instruct the governor to use shorter intervals between consecutive frequency updates by default, aggregating utilization updates that occur between consecutive frequency updates, and making the governor reduce frequencies less aggressively.

There was also some brief discussion regarding other schedutil improvements proposed so far, including cross-CPU utilization updates.

Realtime scheduling

SCHED_DEADLINE and reclaiming. Luca Abeni gave an overview of his work implementing the GRUB bandwidth reclaiming algorithm for SCHED_DEADLINE. In fact, one problem with using SCHED_DEADLINE is that it is not usually easy to come up with the right set of parameters (execution time, deadline, and period) to describe task behavior. Bandwidth reclaiming helps with this by allowing a task that occasionally needs more CPU time than its parameters would allow to reclaim bandwidth left over from other tasks. Another good reason to merge this patch is that it adds information about how much CPU capacity is required to service the deadline tasks. This information is key for proper clock-frequency selection (see below).

Luca’s patch set is pretty mature, so he should be able to get it merged relatively quickly after having addressed a few comments received during the discussion and as part of the review of the latest version on the list.

The changes required to modify clock frequency for SCHED_DEADLINE tasks, at least on platforms that require a non-atomic context to implement clock scaling (like ARM), generated a lively discussion instead. A major point of contention was the fact that the kernel threads responsible for changing clock frequency have to be able to preempt all other tasks, including SCHED_DEADLINE tasks. The currently proposed solution is based on a mechanism that treats these threads as "special"; they appear as SCHED_DEADLINE tasks with an immediate deadline and infinite bandwidth. While this seems to work in practice, it breaks admission control and priority inheritance from a theoretical point of view. However, the agreement seems to be that a solution that works in practice might be accepted to foster adoption and further experimentation with the schedutil governor while a better, longer-term approach, such as making clock-frequency changes atomic even on ARM, is sought.

The RFC still has to ripen quite a bit (starting with proper changelogs), but the necessity of extending SCHED_DEADLINE to deal with groups of tasks seemed to be acknowledged by the people attending the summit. However, the key question on how to properly integrate this new feature still has to be answered: how to make it work even when group scheduling is not in use.

Power management

It is implemented with the following four changes:

1. Prevent waking a CPU or cluster that hasn't reached its target residency yet (a CPU entering an idle state consumes more energy if the break-even point hasn’t been reached).
2. A newly idle CPU doesn’t pull tasks if it is the last CPU in the cluster, since there is a high probability the entire cluster will be powered down.
3. A newly idle CPU pulls tasks from another cluster if this allows that cluster to go idle.
4. Compute the average time it takes to execute the different steps (heuristic, entering idle state, switch timers, etc.) of the idle path. This will allow evaluation of whether it is worth entering a deeper idle state through the costly idle path or if we should bail out sooner.

These features can only work if we change the way how we compute the idle duration and if we have the next-event information available when the task scheduler makes its task placement decision. The change of the next event from average to deadline duration will allow for higher precision, since we then see how close a CPU or cluster is from being woken up.

Miscellaneous

Luca then handed over to his professor Paolo Valente, who moderated the more forward-looking and open-ended part of the session, trying to find intersections between I/O scheduling and OSPM. Starting with the current state of the art (a black slide causing the audience to giggle) he then gathered feedback around possible strategies for saving energy, such as idling during I/O or controlling components' OPPs.

Tooling

Tooling/LISA. Patrick Bellasi and Brendan Jackman showed how ARM is testing EAS behaviors. They presented the rt-app tool used to create synthetic workloads and the LISA toolkit that provides regression testing and interactive analysis of Linux kernel behavior.

Research

A hierarchical scheduling model for dynamic soft-realtime systems. Vladimir Nikolov presented a user-space based proposal for runtime administration of concurrent soft real-time applications, which is part of the ARTOS research project. The presented approach involves mechanisms for automated application monitoring and cost estimation, extraction of required processing bandwidth, and selection of optimal quality levels for the applications during runtime. Thereby, capacity reservations are established and updated at well-defined instants under the premise that applications and their tasks remain consistent with their actual measured costs. The system’s ability to handle cyclically occurring loads and to suppress recurring re-configurations of application quality levels were discussed as well. An interesting discussion was triggered around the abstraction levels proposed as well as the usefulness of an out-of-kernel solution.

Conclusions

This event has shown that there is a real need for detailed technical discussion on how to improve Linux OSPM and task scheduler coordination in addition to the limited amount of time available at the yearly Linux Plumbers Conference. Many of the sessions helped to accelerate the corresponding discussions on the linux-kernel mailing list. The organizers received positive feedback from the participants about the usefulness of such an event so they will look into scheduling a follow-on summit next year.

Many thanks to all presenters, participants, and note-takers as well as to the ReTiS Lab for providing the premises.