405 lines · plain
1=======================2Energy Aware Scheduling3=======================4 51. Introduction6---------------7 8Energy Aware Scheduling (or EAS) gives the scheduler the ability to predict9the impact of its decisions on the energy consumed by CPUs. EAS relies on an10Energy Model (EM) of the CPUs to select an energy efficient CPU for each task,11with a minimal impact on throughput. This document aims at providing an12introduction on how EAS works, what are the main design decisions behind it, and13details what is needed to get it to run.14 15Before going any further, please note that at the time of writing::16 17 /!\ EAS does not support platforms with symmetric CPU topologies /!\18 19EAS operates only on heterogeneous CPU topologies (such as Arm big.LITTLE)20because this is where the potential for saving energy through scheduling is21the highest.22 23The actual EM used by EAS is _not_ maintained by the scheduler, but by a24dedicated framework. For details about this framework and what it provides,25please refer to its documentation (see Documentation/power/energy-model.rst).26 27 282. Background and Terminology29-----------------------------30 31To make it clear from the start:32 - energy = [joule] (resource like a battery on powered devices)33 - power = energy/time = [joule/second] = [watt]34 35The goal of EAS is to minimize energy, while still getting the job done. That36is, we want to maximize::37 38 performance [inst/s]39 --------------------40 power [W]41 42which is equivalent to minimizing::43 44 energy [J]45 -----------46 instruction47 48while still getting 'good' performance. It is essentially an alternative49optimization objective to the current performance-only objective for the50scheduler. This alternative considers two objectives: energy-efficiency and51performance.52 53The idea behind introducing an EM is to allow the scheduler to evaluate the54implications of its decisions rather than blindly applying energy-saving55techniques that may have positive effects only on some platforms. At the same56time, the EM must be as simple as possible to minimize the scheduler latency57impact.58 59In short, EAS changes the way CFS tasks are assigned to CPUs. When it is time60for the scheduler to decide where a task should run (during wake-up), the EM61is used to break the tie between several good CPU candidates and pick the one62that is predicted to yield the best energy consumption without harming the63system's throughput. The predictions made by EAS rely on specific elements of64knowledge about the platform's topology, which include the 'capacity' of CPUs,65and their respective energy costs.66 67 683. Topology information69-----------------------70 71EAS (as well as the rest of the scheduler) uses the notion of 'capacity' to72differentiate CPUs with different computing throughput. The 'capacity' of a CPU73represents the amount of work it can absorb when running at its highest74frequency compared to the most capable CPU of the system. Capacity values are75normalized in a 1024 range, and are comparable with the utilization signals of76tasks and CPUs computed by the Per-Entity Load Tracking (PELT) mechanism. Thanks77to capacity and utilization values, EAS is able to estimate how big/busy a78task/CPU is, and to take this into consideration when evaluating performance vs79energy trade-offs. The capacity of CPUs is provided via arch-specific code80through the arch_scale_cpu_capacity() callback.81 82The rest of platform knowledge used by EAS is directly read from the Energy83Model (EM) framework. The EM of a platform is composed of a power cost table84per 'performance domain' in the system (see Documentation/power/energy-model.rst85for further details about performance domains).86 87The scheduler manages references to the EM objects in the topology code when the88scheduling domains are built, or re-built. For each root domain (rd), the89scheduler maintains a singly linked list of all performance domains intersecting90the current rd->span. Each node in the list contains a pointer to a struct91em_perf_domain as provided by the EM framework.92 93The lists are attached to the root domains in order to cope with exclusive94cpuset configurations. Since the boundaries of exclusive cpusets do not95necessarily match those of performance domains, the lists of different root96domains can contain duplicate elements.97 98Example 1.99 Let us consider a platform with 12 CPUs, split in 3 performance domains100 (pd0, pd4 and pd8), organized as follows::101 102 CPUs: 0 1 2 3 4 5 6 7 8 9 10 11103 PDs: |--pd0--|--pd4--|---pd8---|104 RDs: |----rd1----|-----rd2-----|105 106 Now, consider that userspace decided to split the system with two107 exclusive cpusets, hence creating two independent root domains, each108 containing 6 CPUs. The two root domains are denoted rd1 and rd2 in the109 above figure. Since pd4 intersects with both rd1 and rd2, it will be110 present in the linked list '->pd' attached to each of them:111 112 * rd1->pd: pd0 -> pd4113 * rd2->pd: pd4 -> pd8114 115 Please note that the scheduler will create two duplicate list nodes for116 pd4 (one for each list). However, both just hold a pointer to the same117 shared data structure of the EM framework.118 119Since the access to these lists can happen concurrently with hotplug and other120things, they are protected by RCU, like the rest of topology structures121manipulated by the scheduler.122 123EAS also maintains a static key (sched_energy_present) which is enabled when at124least one root domain meets all conditions for EAS to start. Those conditions125are summarized in Section 6.126 127 1284. Energy-Aware task placement129------------------------------130 131EAS overrides the CFS task wake-up balancing code. It uses the EM of the132platform and the PELT signals to choose an energy-efficient target CPU during133wake-up balance. When EAS is enabled, select_task_rq_fair() calls134find_energy_efficient_cpu() to do the placement decision. This function looks135for the CPU with the highest spare capacity (CPU capacity - CPU utilization) in136each performance domain since it is the one which will allow us to keep the137frequency the lowest. Then, the function checks if placing the task there could138save energy compared to leaving it on prev_cpu, i.e. the CPU where the task ran139in its previous activation.140 141find_energy_efficient_cpu() uses compute_energy() to estimate what will be the142energy consumed by the system if the waking task was migrated. compute_energy()143looks at the current utilization landscape of the CPUs and adjusts it to144'simulate' the task migration. The EM framework provides the em_pd_energy() API145which computes the expected energy consumption of each performance domain for146the given utilization landscape.147 148An example of energy-optimized task placement decision is detailed below.149 150Example 2.151 Let us consider a (fake) platform with 2 independent performance domains152 composed of two CPUs each. CPU0 and CPU1 are little CPUs; CPU2 and CPU3153 are big.154 155 The scheduler must decide where to place a task P whose util_avg = 200156 and prev_cpu = 0.157 158 The current utilization landscape of the CPUs is depicted on the graph159 below. CPUs 0-3 have a util_avg of 400, 100, 600 and 500 respectively160 Each performance domain has three Operating Performance Points (OPPs).161 The CPU capacity and power cost associated with each OPP is listed in162 the Energy Model table. The util_avg of P is shown on the figures163 below as 'PP'::164 165 CPU util.166 1024 - - - - - - - Energy Model167 +-----------+-------------+168 | Little | Big |169 768 ============= +-----+-----+------+------+170 | Cap | Pwr | Cap | Pwr |171 +-----+-----+------+------+172 512 =========== - ##- - - - - | 170 | 50 | 512 | 400 |173 ## ## | 341 | 150 | 768 | 800 |174 341 -PP - - - - ## ## | 512 | 300 | 1024 | 1700 |175 PP ## ## +-----+-----+------+------+176 170 -## - - - - ## ##177 ## ## ## ##178 ------------ -------------179 CPU0 CPU1 CPU2 CPU3180 181 Current OPP: ===== Other OPP: - - - util_avg (100 each): ##182 183 184 find_energy_efficient_cpu() will first look for the CPUs with the185 maximum spare capacity in the two performance domains. In this example,186 CPU1 and CPU3. Then it will estimate the energy of the system if P was187 placed on either of them, and check if that would save some energy188 compared to leaving P on CPU0. EAS assumes that OPPs follow utilization189 (which is coherent with the behaviour of the schedutil CPUFreq190 governor, see Section 6. for more details on this topic).191 192 **Case 1. P is migrated to CPU1**::193 194 1024 - - - - - - -195 196 Energy calculation:197 768 ============= * CPU0: 200 / 341 * 150 = 88198 * CPU1: 300 / 341 * 150 = 131199 * CPU2: 600 / 768 * 800 = 625200 512 - - - - - - - ##- - - - - * CPU3: 500 / 768 * 800 = 520201 ## ## => total_energy = 1364202 341 =========== ## ##203 PP ## ##204 170 -## - - PP- ## ##205 ## ## ## ##206 ------------ -------------207 CPU0 CPU1 CPU2 CPU3208 209 210 **Case 2. P is migrated to CPU3**::211 212 1024 - - - - - - -213 214 Energy calculation:215 768 ============= * CPU0: 200 / 341 * 150 = 88216 * CPU1: 100 / 341 * 150 = 43217 PP * CPU2: 600 / 768 * 800 = 625218 512 - - - - - - - ##- - -PP - * CPU3: 700 / 768 * 800 = 729219 ## ## => total_energy = 1485220 341 =========== ## ##221 ## ##222 170 -## - - - - ## ##223 ## ## ## ##224 ------------ -------------225 CPU0 CPU1 CPU2 CPU3226 227 228 **Case 3. P stays on prev_cpu / CPU 0**::229 230 1024 - - - - - - -231 232 Energy calculation:233 768 ============= * CPU0: 400 / 512 * 300 = 234234 * CPU1: 100 / 512 * 300 = 58235 * CPU2: 600 / 768 * 800 = 625236 512 =========== - ##- - - - - * CPU3: 500 / 768 * 800 = 520237 ## ## => total_energy = 1437238 341 -PP - - - - ## ##239 PP ## ##240 170 -## - - - - ## ##241 ## ## ## ##242 ------------ -------------243 CPU0 CPU1 CPU2 CPU3244 245 246 From these calculations, the Case 1 has the lowest total energy. So CPU 1247 is be the best candidate from an energy-efficiency standpoint.248 249Big CPUs are generally more power hungry than the little ones and are thus used250mainly when a task doesn't fit the littles. However, little CPUs aren't always251necessarily more energy-efficient than big CPUs. For some systems, the high OPPs252of the little CPUs can be less energy-efficient than the lowest OPPs of the253bigs, for example. So, if the little CPUs happen to have enough utilization at254a specific point in time, a small task waking up at that moment could be better255of executing on the big side in order to save energy, even though it would fit256on the little side.257 258And even in the case where all OPPs of the big CPUs are less energy-efficient259than those of the little, using the big CPUs for a small task might still, under260specific conditions, save energy. Indeed, placing a task on a little CPU can261result in raising the OPP of the entire performance domain, and that will262increase the cost of the tasks already running there. If the waking task is263placed on a big CPU, its own execution cost might be higher than if it was264running on a little, but it won't impact the other tasks of the little CPUs265which will keep running at a lower OPP. So, when considering the total energy266consumed by CPUs, the extra cost of running that one task on a big core can be267smaller than the cost of raising the OPP on the little CPUs for all the other268tasks.269 270The examples above would be nearly impossible to get right in a generic way, and271for all platforms, without knowing the cost of running at different OPPs on all272CPUs of the system. Thanks to its EM-based design, EAS should cope with them273correctly without too many troubles. However, in order to ensure a minimal274impact on throughput for high-utilization scenarios, EAS also implements another275mechanism called 'over-utilization'.276 277 2785. Over-utilization279-------------------280 281From a general standpoint, the use-cases where EAS can help the most are those282involving a light/medium CPU utilization. Whenever long CPU-bound tasks are283being run, they will require all of the available CPU capacity, and there isn't284much that can be done by the scheduler to save energy without severely harming285throughput. In order to avoid hurting performance with EAS, CPUs are flagged as286'over-utilized' as soon as they are used at more than 80% of their compute287capacity. As long as no CPUs are over-utilized in a root domain, load balancing288is disabled and EAS overridess the wake-up balancing code. EAS is likely to load289the most energy efficient CPUs of the system more than the others if that can be290done without harming throughput. So, the load-balancer is disabled to prevent291it from breaking the energy-efficient task placement found by EAS. It is safe to292do so when the system isn't overutilized since being below the 80% tipping point293implies that:294 295 a. there is some idle time on all CPUs, so the utilization signals used by296 EAS are likely to accurately represent the 'size' of the various tasks297 in the system;298 b. all tasks should already be provided with enough CPU capacity,299 regardless of their nice values;300 c. since there is spare capacity all tasks must be blocking/sleeping301 regularly and balancing at wake-up is sufficient.302 303As soon as one CPU goes above the 80% tipping point, at least one of the three304assumptions above becomes incorrect. In this scenario, the 'overutilized' flag305is raised for the entire root domain, EAS is disabled, and the load-balancer is306re-enabled. By doing so, the scheduler falls back onto load-based algorithms for307wake-up and load balance under CPU-bound conditions. This provides a better308respect of the nice values of tasks.309 310Since the notion of overutilization largely relies on detecting whether or not311there is some idle time in the system, the CPU capacity 'stolen' by higher312(than CFS) scheduling classes (as well as IRQ) must be taken into account. As313such, the detection of overutilization accounts for the capacity used not only314by CFS tasks, but also by the other scheduling classes and IRQ.315 316 3176. Dependencies and requirements for EAS318----------------------------------------319 320Energy Aware Scheduling depends on the CPUs of the system having specific321hardware properties and on other features of the kernel being enabled. This322section lists these dependencies and provides hints as to how they can be met.323 324 3256.1 - Asymmetric CPU topology326^^^^^^^^^^^^^^^^^^^^^^^^^^^^^327 328 329As mentioned in the introduction, EAS is only supported on platforms with330asymmetric CPU topologies for now. This requirement is checked at run-time by331looking for the presence of the SD_ASYM_CPUCAPACITY_FULL flag when the scheduling332domains are built.333 334See Documentation/scheduler/sched-capacity.rst for requirements to be met for this335flag to be set in the sched_domain hierarchy.336 337Please note that EAS is not fundamentally incompatible with SMP, but no338significant savings on SMP platforms have been observed yet. This restriction339could be amended in the future if proven otherwise.340 341 3426.2 - Energy Model presence343^^^^^^^^^^^^^^^^^^^^^^^^^^^344 345EAS uses the EM of a platform to estimate the impact of scheduling decisions on346energy. So, your platform must provide power cost tables to the EM framework in347order to make EAS start. To do so, please refer to documentation of the348independent EM framework in Documentation/power/energy-model.rst.349 350Please also note that the scheduling domains need to be re-built after the351EM has been registered in order to start EAS.352 353EAS uses the EM to make a forecasting decision on energy usage and thus it is354more focused on the difference when checking possible options for task355placement. For EAS it doesn't matter whether the EM power values are expressed356in milli-Watts or in an 'abstract scale'.357 358 3596.3 - Energy Model complexity360^^^^^^^^^^^^^^^^^^^^^^^^^^^^^361 362EAS does not impose any complexity limit on the number of PDs/OPPs/CPUs but363restricts the number of CPUs to EM_MAX_NUM_CPUS to prevent overflows during364the energy estimation.365 366 3676.4 - Schedutil governor368^^^^^^^^^^^^^^^^^^^^^^^^369 370EAS tries to predict at which OPP will the CPUs be running in the close future371in order to estimate their energy consumption. To do so, it is assumed that OPPs372of CPUs follow their utilization.373 374Although it is very difficult to provide hard guarantees regarding the accuracy375of this assumption in practice (because the hardware might not do what it is376told to do, for example), schedutil as opposed to other CPUFreq governors at377least _requests_ frequencies calculated using the utilization signals.378Consequently, the only sane governor to use together with EAS is schedutil,379because it is the only one providing some degree of consistency between380frequency requests and energy predictions.381 382Using EAS with any other governor than schedutil is not supported.383 384 3856.5 Scale-invariant utilization signals386^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^387 388In order to make accurate prediction across CPUs and for all performance389states, EAS needs frequency-invariant and CPU-invariant PELT signals. These can390be obtained using the architecture-defined arch_scale{cpu,freq}_capacity()391callbacks.392 393Using EAS on a platform that doesn't implement these two callbacks is not394supported.395 396 3976.6 Multithreading (SMT)398^^^^^^^^^^^^^^^^^^^^^^^^399 400EAS in its current form is SMT unaware and is not able to leverage401multithreaded hardware to save energy. EAS considers threads as independent402CPUs, which can actually be counter-productive for both performance and energy.403 404EAS on SMT is not supported.405