| ======================= |
| Energy Aware Scheduling |
| ======================= |
| |
| 1. Introduction |
| --------------- |
| |
| Energy Aware Scheduling (or EAS) gives the scheduler the ability to predict |
| the impact of its decisions on the energy consumed by CPUs. EAS relies on an |
| Energy Model (EM) of the CPUs to select an energy efficient CPU for each task, |
| with a minimal impact on throughput. This document aims at providing an |
| introduction on how EAS works, what are the main design decisions behind it, and |
| details what is needed to get it to run. |
| |
| Before going any further, please note that at the time of writing:: |
| |
| /!\ EAS does not support platforms with symmetric CPU topologies /!\ |
| |
| EAS operates only on heterogeneous CPU topologies (such as Arm big.LITTLE) |
| because this is where the potential for saving energy through scheduling is |
| the highest. |
| |
| The actual EM used by EAS is _not_ maintained by the scheduler, but by a |
| dedicated framework. For details about this framework and what it provides, |
| please refer to its documentation (see Documentation/power/energy-model.txt). |
| |
| |
| 2. Background and Terminology |
| ----------------------------- |
| |
| To make it clear from the start: |
| - energy = [joule] (resource like a battery on powered devices) |
| - power = energy/time = [joule/second] = [watt] |
| |
| The goal of EAS is to minimize energy, while still getting the job done. That |
| is, we want to maximize:: |
| |
| performance [inst/s] |
| -------------------- |
| power [W] |
| |
| which is equivalent to minimizing:: |
| |
| energy [J] |
| ----------- |
| instruction |
| |
| while still getting 'good' performance. It is essentially an alternative |
| optimization objective to the current performance-only objective for the |
| scheduler. This alternative considers two objectives: energy-efficiency and |
| performance. |
| |
| The idea behind introducing an EM is to allow the scheduler to evaluate the |
| implications of its decisions rather than blindly applying energy-saving |
| techniques that may have positive effects only on some platforms. At the same |
| time, the EM must be as simple as possible to minimize the scheduler latency |
| impact. |
| |
| In short, EAS changes the way CFS tasks are assigned to CPUs. When it is time |
| for the scheduler to decide where a task should run (during wake-up), the EM |
| is used to break the tie between several good CPU candidates and pick the one |
| that is predicted to yield the best energy consumption without harming the |
| system's throughput. The predictions made by EAS rely on specific elements of |
| knowledge about the platform's topology, which include the 'capacity' of CPUs, |
| and their respective energy costs. |
| |
| |
| 3. Topology information |
| ----------------------- |
| |
| EAS (as well as the rest of the scheduler) uses the notion of 'capacity' to |
| differentiate CPUs with different computing throughput. The 'capacity' of a CPU |
| represents the amount of work it can absorb when running at its highest |
| frequency compared to the most capable CPU of the system. Capacity values are |
| normalized in a 1024 range, and are comparable with the utilization signals of |
| tasks and CPUs computed by the Per-Entity Load Tracking (PELT) mechanism. Thanks |
| to capacity and utilization values, EAS is able to estimate how big/busy a |
| task/CPU is, and to take this into consideration when evaluating performance vs |
| energy trade-offs. The capacity of CPUs is provided via arch-specific code |
| through the arch_scale_cpu_capacity() callback. |
| |
| The rest of platform knowledge used by EAS is directly read from the Energy |
| Model (EM) framework. The EM of a platform is composed of a power cost table |
| per 'performance domain' in the system (see Documentation/power/energy-model.txt |
| for futher details about performance domains). |
| |
| The scheduler manages references to the EM objects in the topology code when the |
| scheduling domains are built, or re-built. For each root domain (rd), the |
| scheduler maintains a singly linked list of all performance domains intersecting |
| the current rd->span. Each node in the list contains a pointer to a struct |
| em_perf_domain as provided by the EM framework. |
| |
| The lists are attached to the root domains in order to cope with exclusive |
| cpuset configurations. Since the boundaries of exclusive cpusets do not |
| necessarily match those of performance domains, the lists of different root |
| domains can contain duplicate elements. |
| |
| Example 1. |
| Let us consider a platform with 12 CPUs, split in 3 performance domains |
| (pd0, pd4 and pd8), organized as follows:: |
| |
| CPUs: 0 1 2 3 4 5 6 7 8 9 10 11 |
| PDs: |--pd0--|--pd4--|---pd8---| |
| RDs: |----rd1----|-----rd2-----| |
| |
| Now, consider that userspace decided to split the system with two |
| exclusive cpusets, hence creating two independent root domains, each |
| containing 6 CPUs. The two root domains are denoted rd1 and rd2 in the |
| above figure. Since pd4 intersects with both rd1 and rd2, it will be |
| present in the linked list '->pd' attached to each of them: |
| |
| * rd1->pd: pd0 -> pd4 |
| * rd2->pd: pd4 -> pd8 |
| |
| Please note that the scheduler will create two duplicate list nodes for |
| pd4 (one for each list). However, both just hold a pointer to the same |
| shared data structure of the EM framework. |
| |
| Since the access to these lists can happen concurrently with hotplug and other |
| things, they are protected by RCU, like the rest of topology structures |
| manipulated by the scheduler. |
| |
| EAS also maintains a static key (sched_energy_present) which is enabled when at |
| least one root domain meets all conditions for EAS to start. Those conditions |
| are summarized in Section 6. |
| |
| |
| 4. Energy-Aware task placement |
| ------------------------------ |
| |
| EAS overrides the CFS task wake-up balancing code. It uses the EM of the |
| platform and the PELT signals to choose an energy-efficient target CPU during |
| wake-up balance. When EAS is enabled, select_task_rq_fair() calls |
| find_energy_efficient_cpu() to do the placement decision. This function looks |
| for the CPU with the highest spare capacity (CPU capacity - CPU utilization) in |
| each performance domain since it is the one which will allow us to keep the |
| frequency the lowest. Then, the function checks if placing the task there could |
| save energy compared to leaving it on prev_cpu, i.e. the CPU where the task ran |
| in its previous activation. |
| |
| find_energy_efficient_cpu() uses compute_energy() to estimate what will be the |
| energy consumed by the system if the waking task was migrated. compute_energy() |
| looks at the current utilization landscape of the CPUs and adjusts it to |
| 'simulate' the task migration. The EM framework provides the em_pd_energy() API |
| which computes the expected energy consumption of each performance domain for |
| the given utilization landscape. |
| |
| An example of energy-optimized task placement decision is detailed below. |
| |
| Example 2. |
| Let us consider a (fake) platform with 2 independent performance domains |
| composed of two CPUs each. CPU0 and CPU1 are little CPUs; CPU2 and CPU3 |
| are big. |
| |
| The scheduler must decide where to place a task P whose util_avg = 200 |
| and prev_cpu = 0. |
| |
| The current utilization landscape of the CPUs is depicted on the graph |
| below. CPUs 0-3 have a util_avg of 400, 100, 600 and 500 respectively |
| Each performance domain has three Operating Performance Points (OPPs). |
| The CPU capacity and power cost associated with each OPP is listed in |
| the Energy Model table. The util_avg of P is shown on the figures |
| below as 'PP':: |
| |
| CPU util. |
| 1024 - - - - - - - Energy Model |
| +-----------+-------------+ |
| | Little | Big | |
| 768 ============= +-----+-----+------+------+ |
| | Cap | Pwr | Cap | Pwr | |
| +-----+-----+------+------+ |
| 512 =========== - ##- - - - - | 170 | 50 | 512 | 400 | |
| ## ## | 341 | 150 | 768 | 800 | |
| 341 -PP - - - - ## ## | 512 | 300 | 1024 | 1700 | |
| PP ## ## +-----+-----+------+------+ |
| 170 -## - - - - ## ## |
| ## ## ## ## |
| ------------ ------------- |
| CPU0 CPU1 CPU2 CPU3 |
| |
| Current OPP: ===== Other OPP: - - - util_avg (100 each): ## |
| |
| |
| find_energy_efficient_cpu() will first look for the CPUs with the |
| maximum spare capacity in the two performance domains. In this example, |
| CPU1 and CPU3. Then it will estimate the energy of the system if P was |
| placed on either of them, and check if that would save some energy |
| compared to leaving P on CPU0. EAS assumes that OPPs follow utilization |
| (which is coherent with the behaviour of the schedutil CPUFreq |
| governor, see Section 6. for more details on this topic). |
| |
| **Case 1. P is migrated to CPU1**:: |
| |
| 1024 - - - - - - - |
| |
| Energy calculation: |
| 768 ============= * CPU0: 200 / 341 * 150 = 88 |
| * CPU1: 300 / 341 * 150 = 131 |
| * CPU2: 600 / 768 * 800 = 625 |
| 512 - - - - - - - ##- - - - - * CPU3: 500 / 768 * 800 = 520 |
| ## ## => total_energy = 1364 |
| 341 =========== ## ## |
| PP ## ## |
| 170 -## - - PP- ## ## |
| ## ## ## ## |
| ------------ ------------- |
| CPU0 CPU1 CPU2 CPU3 |
| |
| |
| **Case 2. P is migrated to CPU3**:: |
| |
| 1024 - - - - - - - |
| |
| Energy calculation: |
| 768 ============= * CPU0: 200 / 341 * 150 = 88 |
| * CPU1: 100 / 341 * 150 = 43 |
| PP * CPU2: 600 / 768 * 800 = 625 |
| 512 - - - - - - - ##- - -PP - * CPU3: 700 / 768 * 800 = 729 |
| ## ## => total_energy = 1485 |
| 341 =========== ## ## |
| ## ## |
| 170 -## - - - - ## ## |
| ## ## ## ## |
| ------------ ------------- |
| CPU0 CPU1 CPU2 CPU3 |
| |
| |
| **Case 3. P stays on prev_cpu / CPU 0**:: |
| |
| 1024 - - - - - - - |
| |
| Energy calculation: |
| 768 ============= * CPU0: 400 / 512 * 300 = 234 |
| * CPU1: 100 / 512 * 300 = 58 |
| * CPU2: 600 / 768 * 800 = 625 |
| 512 =========== - ##- - - - - * CPU3: 500 / 768 * 800 = 520 |
| ## ## => total_energy = 1437 |
| 341 -PP - - - - ## ## |
| PP ## ## |
| 170 -## - - - - ## ## |
| ## ## ## ## |
| ------------ ------------- |
| CPU0 CPU1 CPU2 CPU3 |
| |
| |
| From these calculations, the Case 1 has the lowest total energy. So CPU 1 |
| is be the best candidate from an energy-efficiency standpoint. |
| |
| Big CPUs are generally more power hungry than the little ones and are thus used |
| mainly when a task doesn't fit the littles. However, little CPUs aren't always |
| necessarily more energy-efficient than big CPUs. For some systems, the high OPPs |
| of the little CPUs can be less energy-efficient than the lowest OPPs of the |
| bigs, for example. So, if the little CPUs happen to have enough utilization at |
| a specific point in time, a small task waking up at that moment could be better |
| of executing on the big side in order to save energy, even though it would fit |
| on the little side. |
| |
| And even in the case where all OPPs of the big CPUs are less energy-efficient |
| than those of the little, using the big CPUs for a small task might still, under |
| specific conditions, save energy. Indeed, placing a task on a little CPU can |
| result in raising the OPP of the entire performance domain, and that will |
| increase the cost of the tasks already running there. If the waking task is |
| placed on a big CPU, its own execution cost might be higher than if it was |
| running on a little, but it won't impact the other tasks of the little CPUs |
| which will keep running at a lower OPP. So, when considering the total energy |
| consumed by CPUs, the extra cost of running that one task on a big core can be |
| smaller than the cost of raising the OPP on the little CPUs for all the other |
| tasks. |
| |
| The examples above would be nearly impossible to get right in a generic way, and |
| for all platforms, without knowing the cost of running at different OPPs on all |
| CPUs of the system. Thanks to its EM-based design, EAS should cope with them |
| correctly without too many troubles. However, in order to ensure a minimal |
| impact on throughput for high-utilization scenarios, EAS also implements another |
| mechanism called 'over-utilization'. |
| |
| |
| 5. Over-utilization |
| ------------------- |
| |
| From a general standpoint, the use-cases where EAS can help the most are those |
| involving a light/medium CPU utilization. Whenever long CPU-bound tasks are |
| being run, they will require all of the available CPU capacity, and there isn't |
| much that can be done by the scheduler to save energy without severly harming |
| throughput. In order to avoid hurting performance with EAS, CPUs are flagged as |
| 'over-utilized' as soon as they are used at more than 80% of their compute |
| capacity. As long as no CPUs are over-utilized in a root domain, load balancing |
| is disabled and EAS overridess the wake-up balancing code. EAS is likely to load |
| the most energy efficient CPUs of the system more than the others if that can be |
| done without harming throughput. So, the load-balancer is disabled to prevent |
| it from breaking the energy-efficient task placement found by EAS. It is safe to |
| do so when the system isn't overutilized since being below the 80% tipping point |
| implies that: |
| |
| a. there is some idle time on all CPUs, so the utilization signals used by |
| EAS are likely to accurately represent the 'size' of the various tasks |
| in the system; |
| b. all tasks should already be provided with enough CPU capacity, |
| regardless of their nice values; |
| c. since there is spare capacity all tasks must be blocking/sleeping |
| regularly and balancing at wake-up is sufficient. |
| |
| As soon as one CPU goes above the 80% tipping point, at least one of the three |
| assumptions above becomes incorrect. In this scenario, the 'overutilized' flag |
| is raised for the entire root domain, EAS is disabled, and the load-balancer is |
| re-enabled. By doing so, the scheduler falls back onto load-based algorithms for |
| wake-up and load balance under CPU-bound conditions. This provides a better |
| respect of the nice values of tasks. |
| |
| Since the notion of overutilization largely relies on detecting whether or not |
| there is some idle time in the system, the CPU capacity 'stolen' by higher |
| (than CFS) scheduling classes (as well as IRQ) must be taken into account. As |
| such, the detection of overutilization accounts for the capacity used not only |
| by CFS tasks, but also by the other scheduling classes and IRQ. |
| |
| |
| 6. Dependencies and requirements for EAS |
| ---------------------------------------- |
| |
| Energy Aware Scheduling depends on the CPUs of the system having specific |
| hardware properties and on other features of the kernel being enabled. This |
| section lists these dependencies and provides hints as to how they can be met. |
| |
| |
| 6.1 - Asymmetric CPU topology |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| |
| As mentioned in the introduction, EAS is only supported on platforms with |
| asymmetric CPU topologies for now. This requirement is checked at run-time by |
| looking for the presence of the SD_ASYM_CPUCAPACITY flag when the scheduling |
| domains are built. |
| |
| The flag is set/cleared automatically by the scheduler topology code whenever |
| there are CPUs with different capacities in a root domain. The capacities of |
| CPUs are provided by arch-specific code through the arch_scale_cpu_capacity() |
| callback. As an example, arm and arm64 share an implementation of this callback |
| which uses a combination of CPUFreq data and device-tree bindings to compute the |
| capacity of CPUs (see drivers/base/arch_topology.c for more details). |
| |
| So, in order to use EAS on your platform your architecture must implement the |
| arch_scale_cpu_capacity() callback, and some of the CPUs must have a lower |
| capacity than others. |
| |
| Please note that EAS is not fundamentally incompatible with SMP, but no |
| significant savings on SMP platforms have been observed yet. This restriction |
| could be amended in the future if proven otherwise. |
| |
| |
| 6.2 - Energy Model presence |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| EAS uses the EM of a platform to estimate the impact of scheduling decisions on |
| energy. So, your platform must provide power cost tables to the EM framework in |
| order to make EAS start. To do so, please refer to documentation of the |
| independent EM framework in Documentation/power/energy-model.txt. |
| |
| Please also note that the scheduling domains need to be re-built after the |
| EM has been registered in order to start EAS. |
| |
| |
| 6.3 - Energy Model complexity |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| The task wake-up path is very latency-sensitive. When the EM of a platform is |
| too complex (too many CPUs, too many performance domains, too many performance |
| states, ...), the cost of using it in the wake-up path can become prohibitive. |
| The energy-aware wake-up algorithm has a complexity of: |
| |
| C = Nd * (Nc + Ns) |
| |
| with: Nd the number of performance domains; Nc the number of CPUs; and Ns the |
| total number of OPPs (ex: for two perf. domains with 4 OPPs each, Ns = 8). |
| |
| A complexity check is performed at the root domain level, when scheduling |
| domains are built. EAS will not start on a root domain if its C happens to be |
| higher than the completely arbitrary EM_MAX_COMPLEXITY threshold (2048 at the |
| time of writing). |
| |
| If you really want to use EAS but the complexity of your platform's Energy |
| Model is too high to be used with a single root domain, you're left with only |
| two possible options: |
| |
| 1. split your system into separate, smaller, root domains using exclusive |
| cpusets and enable EAS locally on each of them. This option has the |
| benefit to work out of the box but the drawback of preventing load |
| balance between root domains, which can result in an unbalanced system |
| overall; |
| 2. submit patches to reduce the complexity of the EAS wake-up algorithm, |
| hence enabling it to cope with larger EMs in reasonable time. |
| |
| |
| 6.4 - Schedutil governor |
| ^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| EAS tries to predict at which OPP will the CPUs be running in the close future |
| in order to estimate their energy consumption. To do so, it is assumed that OPPs |
| of CPUs follow their utilization. |
| |
| Although it is very difficult to provide hard guarantees regarding the accuracy |
| of this assumption in practice (because the hardware might not do what it is |
| told to do, for example), schedutil as opposed to other CPUFreq governors at |
| least _requests_ frequencies calculated using the utilization signals. |
| Consequently, the only sane governor to use together with EAS is schedutil, |
| because it is the only one providing some degree of consistency between |
| frequency requests and energy predictions. |
| |
| Using EAS with any other governor than schedutil is not supported. |
| |
| |
| 6.5 Scale-invariant utilization signals |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| In order to make accurate prediction across CPUs and for all performance |
| states, EAS needs frequency-invariant and CPU-invariant PELT signals. These can |
| be obtained using the architecture-defined arch_scale{cpu,freq}_capacity() |
| callbacks. |
| |
| Using EAS on a platform that doesn't implement these two callbacks is not |
| supported. |
| |
| |
| 6.6 Multithreading (SMT) |
| ^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| EAS in its current form is SMT unaware and is not able to leverage |
| multithreaded hardware to save energy. EAS considers threads as independent |
| CPUs, which can actually be counter-productive for both performance and energy. |
| |
| EAS on SMT is not supported. |
