Energy Aware Scheduling
Subsystems (7)
v4 cover Energy Aware Scheduling
The Energy Aware Scheduler (EAS) based on Morten Rasmussen's posting on LKML [1] is currently part of the AOSP Common Kernel and runs on today's smartphones with Arm's big.LITTLE CPUs. This series implements a new and largely simplified version of EAS based on an Energy Model (EM) of the platform with only costs information for the active states of the CPUs.
The patch-set is organized in three main parts.
1. Patches 01-04/12 introduce a centralized and independent EM management framework
2. Patches 05-10/12 make use of the EM in the scheduler to bias task placement decisions
3. Patches 11-12/12 give an Arm64 example on how to register an Energy Model in the new framework
1. The Energy Model Framework
The energy consumed by the CPUs can be provided to the OS in different ways depending on the source of information (firmware or device tree for example). The EM framework introduced in patch 03/12 addresses this issue by aggregating the data coming from the drivers in a standard way and making it available to interested clients (thermal or the task scheduler, for example).
Although this series comprises patches for the task scheduler as a user of the EM, the framework itself as introduced in patch 03/12 is meant to be _independent_ from any other subsystem.
The overall design of the EM framework is depicted on the diagram below (focused on Arm drivers for the example, but applicable to any architecture).
+---------------+ +-----------------+ +---------+ | Thermal (IPA) | | Scheduler (EAS) | | Other ? | +---------------+ +-----------------+ +---------+ | | em_fd_energy() | | | em_cpu_get() | +-----------+ | +--------+ | | | v v v +---------------------+ | | +---------------+ | Energy Model | | arch_topology | | |<--------| driver | | Framework | +---------------+ | | em_rescale_cpu_capacity() +---------------------+ ^ ^ ^ | | | em_register_freq_domain() +----------+ | +---------+ | | | +---------------+ +---------------+ +--------------+ | cpufreq-dt | | arm_scmi | | Other | +---------------+ +---------------+ +--------------+ ^ ^ ^ | | | +--------------+ +---------------+ +--------------+ | Device Tree | | Firmware | | ? | +--------------+ +---------------+ +--------------+
Drivers can register data in the EM framework using the em_register_freq_domain() API. They are expected to provide a callback
function that the EM framework can use to build energy cost tables and store them in shared data structures. Then, clients such as the task scheduler are allowed to read those shared structures using the em_fd_energy() and em_cpu_get() APIs. The EM framework also provides another API enabling to dynamically re-scale the CPU capacity values of the EM, if needed. The rationale behind this need for dynamic re-scaling and more details about the different APIs of the framework can be found in patch 03/12.
2. Energy-aware task placement in the task scheduler
Patches 05-10/12 make use of the newly introduced EM in the scheduler to bias task placement decisions. When the system is detected as non-”overutilized”, an EM is available, and the platform has an asymmetric CPU capacity topology (e.g. big.LITTLE), the consequences on energy of placing a waking task on a CPU are taken into account to avoid energy-inefficient CPUs if possible. Patches 05-07/12 modify the scheduler topology code in order to: 1) check if all conditions for EAS are met when the scheduling domains are built; and 2) create data structures holding references on the EM tables that can be accessed in latency sensitive code paths (e.g. wake-up path).
An “overutilized” flag (patch 08/12) is attached to the root domain, and is set whenever a CPU is utilized at more than 80% of its capacity. Patches 09-10/12 introduce the new energy-aware wake-up path which makes use of the data structures introduced in patches 05-07/10 whenever the system isn’t overutilized.
3. Arm example of driver modifications to register an EM
Patches 11-12/12 show an example of how drivers should be modified to register an EM in the new framework and potentially re-scale it. The patches target Arm drivers, as an example, but the same ideas should be applicable for others architectures. Patch 11/12 calls the re-scaling API of the EM framework from the arch_topology driver which changes the CPU capacity values after CPUFreq is up and running. Patch 12/12 changes the cpufreq-dt driver (used for testing on Hikey960, see Section 4.) to provide estimated power values to the EM framework using coefficients read from DT. This patch has been made simple and self-contained intentionally in order to show an example of usage of the EM framework.
4. Test results
Two fundamentally different tests were executed. Firstly the energy test case shows the impact on energy consumption this patch-set has using a synthetic set of tasks. Secondly the performance test case provides the conventional hackbench metric numbers.
The tests run on two arm64 big.LITTLE platforms: Hikey960 (4xA73 + 4xA53) and Juno r0 (2xA57 + 4xA53).
Base kernel is tip/sched/core (4.17-rc6), with some Hikey960 and Juno specific patches, the SD_ASYM_CPUCAPACITY flag set at DIE sched domain level for arm64 and schedutil as cpufreq governor [2].
4.1 Energy test case
10 iterations of between 10 and 50 periodic rt-app tasks (16ms period, 5% duty-cycle) for 30 seconds with energy measurement. Unit is Joules. The goal is to save energy, so lower is better.
4.1.1 Hikey960
Energy is measured with an ACME Cape on an instrumented board. Numbers include consumption of big and little CPUs, LPDDR memory, GPU and most of the other small components on the board. They do not include consumption of the radio chip (turned-off anyway) and external connectors.
+----------+-----------------+-------------------------+ | | Without patches | With patches | +----------+--------+--------+------------------+------+ | Tasks nb | Mean | RSD* | Mean | RSD* | +----------+--------+--------+------------------+------+ | 10 | 33.15 | 1.8% | 28.36 (-14.45%) | 1.3% | | 20 | 50.91 | 3.1% | 42.79 (-15.95%) | 1.4% | | 30 | 63.97 | 5.0% | 57.35 (-10.35%) | 2.4% | | 40 | 92.99 | 4.7% | 82.10 (-11.71%) | 6.3% | | 50 | 133.08 | 5.1% | 106.89 (-19.68%) | 5.8% | +----------+--------+--------+------------------+------+
4.1.2 Juno r0
Energy is measured with the onboard energy meter. Numbers include consumption of big and little CPUs.
+----------+-----------------+------------------------+ | | Without patches | With patches | +----------+--------+--------+-----------------+------+ | Tasks nb | Mean | RSD* | Mean | RSD* | +----------+--------+--------+-----------------+------+
| 10 | 11.97 | 2.2% | 7.64 (-36.17%) | 2.7% | | 20 | 20.66 | 2.9% | 13.92 (-29.74%) | 2.2% | | 30 | 33.18 | 1.9% | 23.22 (-30.02%) | 2.7% | | 40 | 45.71 | 0.7% | 33.99 (-25.64%) | 5.9% | | 50 | 56.92 | 0.4% | 53.58 ( -5.87%) | 1.0% | +----------+--------+--------+-----------------+------+
4.2 Performance test case
30 iterations of perf bench sched messaging --pipe --thread --group G --loop L with G=[1 2 4 8] and L=50000 (Hikey960)/16000 (Juno r0).
4.2.1 Hikey960
The impact of thermal capping was mitigated thanks to a heatsink, a fan, and a 10 sec delay between two successive executions.
+----------------+-----------------+------------------------+ | | Without patches | With patches | +--------+-------+---------+-------+----------------+-------+ | Groups | Tasks | Mean | RSD* | Mean | RSD* | +--------+-------+---------+-------+----------------+-------+ | 1 | 40 | 8.24 | 0.96% | 8.36 (+1.56%) | 1.48% | | 2 | 80 | 15.53 | 0.74% | 15.72 (+1.23%) | 0.65% | | 4 | 160 | 31.97 | 0.50% | 32.35 (+1.18%) | 0.44% | | 8 | 320 | 66.31 | 0.47% | 67.11 (+1.20%) | 0.37% | +--------+-------+---------+-------+----------------+-------+
4.2.2 Juno r0
+----------------+-----------------+------------------------+ | | Without patches | With patches | +--------+-------+---------+-------+----------------+-------+ | Groups | Tasks | Mean | RSD* | Mean | RSD* | +--------+-------+---------+-------+----------------+-------+ | 1 | 40 | 7.70 | 0.96% | 7.63 (-0.91%) | 1.14% | | 2 | 80 | 13.94 | 1.05% | 13.88 (-0.43%) | 1.20% | | 4 | 160 | 26.32 | 1.66% | 26.04 (-1.06%) | 1.38% | | 8 | 320 | 52.41 | 2.86% | 52.07 (-0.65%) | 2.41% | +--------+-------+---------+-------+----------------+-------+
*RSD: Relative Standard Deviation (std dev / mean)
5. Version history:
Changes v3[3]->v4:
- Replaced spinlock in EM framework by smp_store_release/READ_ONCE
- Fixed missing locks to protect rcu_assign_pointer in EM framework
- Fixed capacity calculation in EM framework on 32 bits system
- Fixed compilation issue for CONFIG_ENERGY_MODEL=n
- Removed cpumask from struct em_freq_domain, now dynamically allocated
- Power costs of the EM are specified in milliwatts
- Added example of CPUFreq driver modification
- Added doc/comments in the EM framework and better commit header
- Fixed integration issue with util_est in cpu_util_next()
- Changed scheduler topology code to have one freq. dom. list per rd
- Split sched topology patch in smaller patches
- Added doc/comments explaining the heuristic in the wake-up path
- Changed energy threshold for migration to from 1.5% to 6%
Changes v2[4]->v3:
- Removed the PM_OPP dependency by implementing a new EM framework
- Modified the scheduler topology code to take references on the EM data structures
- Simplified the overutilization mechanism into a system-wide flag
- Reworked the integration in the wake-up path using the sd_ea shortcut
- Rebased on tip/sched/core (247f2f6f3c70 "sched/core: Don't schedule threads on pre-empted vCPUs")
Changes v1[5]->v2:
- Reworked interface between fair.c and energy.[ch] (Remove #ifdef CONFIG_PM_OPP from energy.c) (Greg KH)
- Fixed licence & header issue in energy.[ch] (Greg KH)
- Reordered EAS path in select_task_rq_fair() (Joel)
- Avoid prev_cpu if not allowed in select_task_rq_fair() (Morten/Joel)
- Refactored compute_energy() (Patrick)
- Account for RT/IRQ pressure in task_fits() (Patrick)
- Use UTIL_EST and DL utilization during OPP estimation (Patrick/Juri)
- Optimize selection of CPU candidates in the energy-aware wake-up path
- Rebased on top of tip/sched/core (commit b720342849fe “sched/core:
Update Preempt_notifier_key to modern API”)
[1] https://lkml.org/lkml/2015/7/7/754
[2] http://www.linux-arm.org/git?p=linux-qp.git;a=shortlog;h=refs/heads/upstream/eas_v4
[3] https://marc.info/?l=linux-kernel&m=152691273111941&w=2
[4] https://marc.info/?l=linux-kernel&m=152302902427143&w=2
[5] https://marc.info/?l=linux-kernel&m=152153905805048&w=2
Morten Rasmussen (1):
sched: Add over-utilization/tipping point indicator
Quentin Perret (11):
sched: Relocate arch_scale_cpu_capacity
sched/cpufreq: Factor out utilization to frequency mapping
PM: Introduce an Energy Model management framework
PM / EM: Expose the Energy Model in sysfs sched/topology: Reference the Energy Model of CPUs when available sched/topology: Lowest energy aware balancing sched_domain level
pointer
sched/topology: Introduce sched_energy_present static key sched/fair: Introduce an energy estimation helper function sched/fair: Select an energy-efficient CPU on task wake-up
OPTIONAL: arch_topology: Start Energy Aware Scheduling
OPTIONAL: cpufreq: dt: Register an Energy Model
drivers/base/arch_topology.c | 15 ++ drivers/cpufreq/cpufreq-dt.c | 45 +++- include/linux/energy_model.h | 141 ++++++++++++ include/linux/sched/cpufreq.h | 6 + include/linux/sched/topology.h | 19 ++ kernel/power/Kconfig | 15 ++ kernel/power/Makefile | 2 + kernel/power/energy_model.c | 367 +++++++++++++++++++++++++++++++ kernel/sched/cpufreq_schedutil.c | 3 +- kernel/sched/fair.c | 238 +++++++++++++++++++- kernel/sched/sched.h | 64 ++++-- kernel/sched/topology.c | 203 +++++++++++++++++ 12 files changed, 1090 insertions(+), 28 deletions(-) create mode 100644 include/linux/energy_model.h create mode 100644 kernel/power/energy_model.c
Signature · 1 line
2.17.1
RFC PATCH v4 1/12 sched: Relocate arch_scale_cpu_capacity
By default, arch_scale_cpu_capacity() is only visible from within the kernel/sched folder. Relocate it to include/linux/sched/topology.h to make it visible to other clients needing to know about the capacity of CPUs, such as the Energy Model framework.
--- include/linux/sched/topology.h | 19 +++++++++++++++++++ kernel/sched/sched.h | 18 ------------------ 2 files changed, 19 insertions(+), 18 deletions(-)
include/linux/sched/topology.h +19 -0
@@ -202,6 +202,17 @@ extern void set_sched_topology(struct sched_domain_topology_level *tl);# define SD_INIT_NAME (type)#endif +#ifndef arch_scale_cpu_capacity +static __always_inline +unsigned long arch_scale_cpu_capacity (struct sched_domain *sd,int cpu) +{ +if (sd && (sd->flags &SD_SHARE_CPUCAPACITY ) && (sd->span_weight >1 )) +return sd->smt_gain / sd->span_weight; + +return SCHED_CAPACITY_SCALE ; +} +#endif +#else /* CONFIG_SMP */ struct sched_domain_attr ;
@@ -217,6 +228,14 @@ static inline bool cpus_share_cache(int this_cpu, int that_cpu) return true; } +#ifndef arch_scale_cpu_capacity +static __always_inline +unsigned long arch_scale_cpu_capacity (void __always_unused *sd,int cpu) +{ +return SCHED_CAPACITY_SCALE ; +} +#endif +#endif /* !CONFIG_SMP */ static inline int task_node (const struct task_struct *p)
kernel/sched/sched.h +0 -18
@@ -1730,30 +1730,12 @@ unsigned long arch_scale_freq_capacity(int cpu)#ifdef CONFIG_SMP extern void sched_avg_update (struct rq *rq); -#ifndef arch_scale_cpu_capacity -static __always_inline -unsigned long arch_scale_cpu_capacity (struct sched_domain *sd,int cpu) -{ -if (sd && (sd->flags &SD_SHARE_CPUCAPACITY ) && (sd->span_weight >1 )) -return sd->smt_gain / sd->span_weight; - -return SCHED_CAPACITY_SCALE ; -} -#endif -static inline void sched_rt_avg_update (struct rq *rq,u64 rt_delta) { rq->rt_avg += rt_delta *arch_scale_freq_capacity (cpu_of (rq));sched_avg_update (rq); }#else -#ifndef arch_scale_cpu_capacity -static __always_inline -unsigned long arch_scale_cpu_capacity (void __always_unused *sd,int cpu) -{ -return SCHED_CAPACITY_SCALE ; -} -#endif static inline void sched_rt_avg_update (struct rq *rq,u64 rt_delta) { }static inline void sched_avg_update (struct rq *rq) { }#endif
Signature · 1 line
2.17.1
RFC PATCH v4 2/12 sched/cpufreq: Factor out utilization to frequency mapping
In reply to Quentin PerretThe schedutil governor maps utilization values to frequencies by applying a 25% margin. Since this sort of mapping mechanism can be needed by other users (i.e. EAS), factor the utilization-to-frequency mapping code out of schedutil and move it to include/linux/sched/cpufreq.h to avoid code duplication. The new map_util_freq() function is inlined to avoid overheads.
--- include/linux/sched/cpufreq.h | 6 ++++++ kernel/sched/cpufreq_schedutil.c | 3 ++- 2 files changed, 8 insertions(+), 1 deletion(-)
include/linux/sched/cpufreq.h +6 -0
@@ -20,6 +20,12 @@ void cpufreq_add_update_util_hook(int cpu, struct update_util_data *data,void (*func)(struct update_util_data *data,u64 time, unsigned int flags));void cpufreq_remove_update_util_hook (int cpu); + +static inline unsigned long map_util_freq (unsigned long util, +unsigned long freq,unsigned long cap) +{ +return (freq + (freq >>2 )) * util / cap; +}#endif /* CONFIG_CPU_FREQ */ #endif /* _LINUX_SCHED_CPUFREQ_H */
kernel/sched/cpufreq_schedutil.c +2 -1
@@ -13,6 +13,7 @@#include "sched.h" +#include <linux/sched/cpufreq.h> #include <trace/events/power.h> struct sugov_tunables {
@@ -163,7 +164,7 @@ static unsigned int get_next_freq(struct sugov_policy *sg_policy,unsigned int freq =arch_scale_freq_invariant () ? policy->cpuinfo.max_freq : policy->cur; - freq = (freq + (freq >>2 )) * util / max; + freq =map_util_freq (util, freq, max);if (freq == sg_policy->cached_raw_freq && sg_policy->next_freq !=UINT_MAX )return sg_policy->next_freq;
Signature · 1 line
2.17.1
RFC PATCH v4 3/12 PM: Introduce an Energy Model management framework
In reply to Quentin PerretSeveral subsystems in the kernel (task scheduler and/or thermal at the time of writing) can benefit from knowing about the energy consumed by CPUs. Yet, this information can come from different sources (DT or firmware for example), in different formats, hence making it hard to exploit without a standard API.
As an attempt to address this, introduce a centralized Energy Model (EM) management framework which aggregates the power values provided by drivers into a table for each frequency domain in the system. The power cost tables are made available to interested clients (e.g. task scheduler or thermal) via platform-agnostic APIs. The overall design is represented by the diagram below (focused on Arm-related drivers as an example, but hopefully applicable to any architecture):
+---------------+ +-----------------+ +---------+
| Thermal (IPA) | | Scheduler (EAS) | | Other ? |
+---------------+ +-----------------+ +---------+
| | em_fd_energy() |
| | em_cpu_get() |
+-----------+ | +--------+
| | |
v v v
+---------------------+
| | +---------------+
| Energy Model | | arch_topology |
| |<--------| driver |
| Framework | +---------------+
| | em_rescale_cpu_capacity()
+---------------------+
^ ^ ^
| | | em_register_freq_domain()
+----------+ | +---------+
| | |
+---------------+ +---------------+ +--------------+
| cpufreq-dt | | arm_scmi | | Other |
+---------------+ +---------------+ +--------------+
^ ^ ^
| | |
+--------------+ +---------------+ +--------------+
| Device Tree | | Firmware | | ? |
+--------------+ +---------------+ +--------------+Drivers (typically, but not limited to, CPUFreq drivers) can register data in the EM framework using the em_register_freq_domain() API. The calling driver must provide a callback function with a standardized signature that will be used by the EM framework to build the power cost tables of the frequency domain. This design should offer a lot of flexibility to calling drivers which are free of reading information from any location and to use any technique to compute power costs. Moreover, the capacity states registered by drivers in the EM framework are not required to match real performance states of the target. This is particularly important on targets where the performance states are not known by the OS.
On the client side, the EM framework offers APIs to access the power cost tables of a CPU (em_cpu_get()), and to estimate the energy consumed by the CPUs of a frequency domain (em_fd_energy()). Clients such as the task scheduler can then use these APIs to access the shared data structures holding the Energy Model of CPUs.
The EM framework also provides an API (em_rescale_cpu_capacity()) to re-scale the capacity values of the model asynchronously, after it has been created. This is required for architectures where the capacity scale factor of CPUs can change at run-time. This is the case for Arm/Arm64 for example where the arch_topology driver recomputes the capacity scale factors of the CPUs after the maximum frequency of all CPUs has been discovered. Although complex, the process of creating and re-scaling the EM has to be kept in two separate steps to fulfill the needs of the different users. The thermal subsystem doesn't use the capacity values and shouldn't have dependencies on subsystems providing them. On the other hand, the task scheduler needs the capacity values, and it will benefit from seeing them up-to-date when applicable.
--- include/linux/energy_model.h | 140 ++++++++++++++++++ kernel/power/Kconfig | 15 ++ kernel/power/Makefile | 2 + kernel/power/energy_model.c | 273 +++++++++++++++++++++++++++++++++++ 4 files changed, 430 insertions(+) create mode 100644 include/linux/energy_model.h create mode 100644 kernel/power/energy_model.c
include/linux/energy_model.h new file +140 -0
@@ -0,0 +1,140 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_ENERGY_MODEL_H +#define _LINUX_ENERGY_MODEL_H +#include <linux/cpumask.h> +#include <linux/jump_label.h> +#include <linux/kobject.h> +#include <linux/rcupdate.h> +#include <linux/sched/cpufreq.h> +#include <linux/types.h> + +#ifdef CONFIG_ENERGY_MODEL +struct em_cap_state { +unsigned long capacity; +unsigned long frequency;/* Kilo-hertz */ +unsigned long power;/* Milli-watts */ +}; + +struct em_cs_table { +struct em_cap_state *state;/* Capacity states, in ascending order. */ +int nr_cap_states; +struct rcu_head rcu; +}; + +struct em_freq_domain { +struct em_cs_table *cs_table;/* Capacity state table, RCU-protected */ +unsigned long cpus[0 ];/* CPUs of the frequency domain. */ +}; + +#define EM_CPU_MAX_POWER 0xFFFF + +struct em_data_callback { +/** +* active_power() - Provide power at the next capacity state of a CPU +* @power : Active power at the capacity state in mW (modified) +* @freq : Frequency at the capacity state in kHz (modified) +* @cpu : CPU for which we do this operation +* +* active_power() must find the lowest capacity state of 'cpu' above +* 'freq' and update 'power' and 'freq' to the matching active power +* and frequency. +* +* The power is the one of a single CPU in the domain, expressed in +* milli-watts. It is expected to fit in the [0, EM_CPU_MAX_POWER] +* range. +* +* Return 0 on success. +*/ +int (*active_power) (unsigned long *power,unsigned long *freq,int cpu); +}; +#define EM_DATA_CB (_active_power_cb) { .active_power = &_active_power_cb } + +void em_rescale_cpu_capacity (void ); +struct em_freq_domain *em_cpu_get (int cpu); +int em_register_freq_domain (cpumask_t *span,unsigned int nr_states, +struct em_data_callback *cb); + +/** +* em_fd_energy() - Estimates the energy consumed by the CPUs of a freq. domain +* @fd : frequency domain for which energy has to be estimated +* @max_util : highest utilization among CPUs of the domain +* @sum_util : sum of the utilization of all CPUs in the domain +* +* em_fd_energy() dereferences the capacity state table of the frequency +* domain, so it must be called under RCU read lock. +* +* Return: the sum of the energy consumed by the CPUs of the domain assuming +* a capacity state satisfying the max utilization of the domain. +*/ +static inline unsigned long em_fd_energy (struct em_freq_domain *fd, +unsigned long max_util,unsigned long sum_util) +{ +struct em_cs_table *cs_table; +struct em_cap_state *cs; +unsigned long freq; +int i; + + cs_table =rcu_dereference (fd->cs_table); +if (!cs_table) +return 0 ; + +/* Map the utilization value to a frequency */ + cs = &cs_table->state[cs_table->nr_cap_states -1 ]; + freq =map_util_freq (max_util, cs->frequency, cs->capacity); + +/* Find the lowest capacity state above this frequency */ +for (i =0 ; i < cs_table->nr_cap_states; i++) { + cs = &cs_table->state[i]; +if (cs->frequency >= freq) +break ; + } + +return cs->power * sum_util / cs->capacity; +} + +/** +* em_fd_nr_cap_states() - Get the number of capacity states of a freq. domain +* @fd : frequency domain for which want to do this +* +* Return: the number of capacity state in the frequency domain table +*/ +static inline int em_fd_nr_cap_states (struct em_freq_domain *fd) +{ +struct em_cs_table *table; +int nr_states; + +rcu_read_lock (); + table =rcu_dereference (fd->cs_table); + nr_states = table->nr_cap_states; +rcu_read_unlock (); + +return nr_states; +} + +#else +struct em_freq_domain {}; +struct em_data_callback {}; +#define EM_DATA_CB (_active_power_cb) { } + +static inline int em_register_freq_domain (cpumask_t *span, +unsigned int nr_states,struct em_data_callback *cb) +{ +return -EINVAL ; +} +static inline struct em_freq_domain *em_cpu_get (int cpu) +{ +return NULL ; +} +static inline unsigned long em_fd_energy (struct em_freq_domain *fd, +unsigned long max_util,unsigned long sum_util) +{ +return 0 ; +} +static inline int em_fd_nr_cap_states (struct em_freq_domain *fd) +{ +return 0 ; +} +static inline void em_rescale_cpu_capacity (void ) { } +#endif + +#endif
kernel/power/Kconfig +15 -0
@@ -297,3 +297,18 @@ config PM_GENERIC_DOMAINS_OF config CPU_PM bool + +config ENERGY_MODEL + bool "Energy Model for CPUs" + depends on SMP + depends on CPU_FREQ + default n + help + Several subsystems (thermal and/or the task scheduler for example) + can leverage information about the energy consumed by CPUs to make + smarter decisions. This config option enables the framework from + which subsystems can access the energy models. + + The exact usage of the energy model is subsystem-dependent. + + If in doubt, say N.
kernel/power/Makefile +2 -0
@@ -15,3 +15,5 @@ obj-$(CONFIG_PM_AUTOSLEEP) += autosleep.o obj-$(CONFIG_PM_WAKELOCKS) += wakelock.o obj-$(CONFIG_MAGIC_SYSRQ) += poweroff.o + +obj-$(CONFIG_ENERGY_MODEL) += energy_model.o
kernel/power/energy_model.c new file +273 -0
273 lines not on this page · raw message
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 27 lines · Quentin Perret
include/linux/energy_model.h new file +27
-0+/** +* em_fd_energy() - Estimates the energy consumed by the CPUs of a freq. domain +* @fd : frequency domain for which energy has to be estimated +* @max_util : highest utilization among CPUs of the domain +* @sum_util : sum of the utilization of all CPUs in the domain +* +* em_fd_energy() dereferences the capacity state table of the frequency +* domain, so it must be called under RCU read lock. +* +* Return: the sum of the energy consumed by the CPUs of the domain assuming +* a capacity state satisfying the max utilization of the domain. +*/ +static inline unsigned long em_fd_energy (struct em_freq_domain *fd, +unsigned long max_util,unsigned long sum_util) +{ +struct em_cs_table *cs_table; +struct em_cap_state *cs; +unsigned long freq; +int i; + + cs_table =rcu_dereference (fd->cs_table); +if (!cs_table) +return 0 ; + +/* Map the utilization value to a frequency */ + cs = &cs_table->state[cs_table->nr_cap_states -1 ]; + freq =map_util_freq (max_util, cs->frequency, cs->capacity);
include/linux/energy_model.h line 93
Quoted 10 lines
include/linux/energy_model.h new file +10
-0+ +/* Find the lowest capacity state above this frequency */ +for (i =0 ; i < cs_table->nr_cap_states; i++) { + cs = &cs_table->state[i]; +if (cs->frequency >= freq) +break ; + } + +return cs->power * sum_util / cs->capacity; +}
I keep reading @max_util as the highest possible util (iow capacity) of the freq domain, instead of the current highest instant capacity across the CPUs in the domain.
At the same time I'm struggling for a better name. Maybe just @util? But that would then maybe confuse against @sum_util. argh..
And I'm confused by what exactly this function computes; are you (through sum_util) effectively setting idle power at 0?
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 43 lines · Peter Zijlstra
Quoted 27 lines · Quentin Perret
include/linux/energy_model.h new file +27
-0+/** +* em_fd_energy() - Estimates the energy consumed by the CPUs of a freq. domain +* @fd : frequency domain for which energy has to be estimated +* @max_util : highest utilization among CPUs of the domain +* @sum_util : sum of the utilization of all CPUs in the domain +* +* em_fd_energy() dereferences the capacity state table of the frequency +* domain, so it must be called under RCU read lock. +* +* Return: the sum of the energy consumed by the CPUs of the domain assuming +* a capacity state satisfying the max utilization of the domain. +*/ +static inline unsigned long em_fd_energy (struct em_freq_domain *fd, +unsigned long max_util,unsigned long sum_util) +{ +struct em_cs_table *cs_table; +struct em_cap_state *cs; +unsigned long freq; +int i; + + cs_table =rcu_dereference (fd->cs_table); +if (!cs_table) +return 0 ; + +/* Map the utilization value to a frequency */ + cs = &cs_table->state[cs_table->nr_cap_states -1 ]; + freq =map_util_freq (max_util, cs->frequency, cs->capacity);include/linux/energy_model.h line 93
Quoted 10 lines
include/linux/energy_model.h new file +10
-0+ +/* Find the lowest capacity state above this frequency */ +for (i =0 ; i < cs_table->nr_cap_states; i++) { + cs = &cs_table->state[i]; +if (cs->frequency >= freq) +break ; + } + +return cs->power * sum_util / cs->capacity; +}I keep reading @max_util as the highest possible util (iow capacity) of the freq domain, instead of the current highest instant capacity across the CPUs in the domain.
Quoted 2 lines
At the same time I'm struggling for a better name. Maybe just @util? But that would then maybe confuse against @sum_util. argh..
Right, I see your point ... I'm happy to change to 'util' if you prefer. One can argue that this is more consistent with the 'util' used in sugov_next_freq_shared() ...
Quoted 3 lines
And I'm confused by what exactly this function computes; are you (through
sum_util) effectively setting idle power at 0?
Yes, the EM only includes costs for active states, at least for now, so we don't take idle time into consideration. Extending the model should be doable later I suppose, as a second step (if proven useful ...).
Peter Zijlstra
maintainerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
In reply to Quentin PerretQuoted 5 lines · Quentin Perret
include/linux/energy_model.h new file +5
-0+/** +* em_fd_nr_cap_states() - Get the number of capacity states of a freq. domain +* @fd : frequency domain for which want to do this +* +* Return: the number of capacity state in the frequency domain table
include/linux/energy_model.h line 109
Quoted 10 lines
include/linux/energy_model.h new file +10
-0+*/ +static inline int em_fd_nr_cap_states (struct em_freq_domain *fd) +{ +struct em_cs_table *table; +int nr_states; + +rcu_read_lock (); + table =rcu_dereference (fd->cs_table); + nr_states = table->nr_cap_states; +rcu_read_unlock ();
So right here, we can continue to free @table...
include/linux/energy_model.h line 112
Quoted 3 lines
include/linux/energy_model.h new file +3
-0+ +return nr_states; +}
and then what does the value we return mean?
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 19 lines · Peter Zijlstra
Quoted 5 lines · Quentin Perret
include/linux/energy_model.h new file +5
-0+/** +* em_fd_nr_cap_states() - Get the number of capacity states of a freq. domain +* @fd : frequency domain for which want to do this +* +* Return: the number of capacity state in the frequency domain table include/linux/energy_model.h line 109
Quoted 10 lines
include/linux/energy_model.h new file +10
-0+*/ +static inline int em_fd_nr_cap_states (struct em_freq_domain *fd) +{ +struct em_cs_table *table; +int nr_states; + +rcu_read_lock (); + table =rcu_dereference (fd->cs_table); + nr_states = table->nr_cap_states; +rcu_read_unlock ();So right here, we can continue to free @table...
Quoted 5 lines
include/linux/energy_model.h line 112
Quoted 3 lines
include/linux/energy_model.h new file +3
-0+ +return nr_states; +}and then what does the value we return mean?
Hmm that's a good point. In practice the number of entries in the table never changes, so that makes no sense to keep that value in the RCU-protected struct. I can just move nr_cap_states in struct freq_domain directly and access it without RCU protection, it is simply not needed.
I'll change that for the next version.
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
In reply to Quentin PerretQuoted 6 lines · Quentin Perret
+/*
fd_update_cs_table()- Computes the capacity values of acs_table
+ *
+ * This assumes a linear relation between capacity and frequency. As such,
+ * the capacity of a CPU at the n^th capacity state is computed as:
+ * capactity(n) =max_capacity* freq(n) /freq_max
+ */
Broken comment style
kernel/power/energy_model.c line 69
Quoted 11 lines
kernel/power/energy_model.c new file +11
-0+static void fd_update_cs_table (struct em_cs_table *cs_table,int cpu) +{ +unsigned long cmax =arch_scale_cpu_capacity (NULL , cpu); +int max_cap_state = cs_table->nr_cap_states -1 ; +unsigned long fmax = cs_table->state[max_cap_state].frequency; +int i; + +for (i =0 ; i < cs_table->nr_cap_states; i++) { +u64 cap = (u64 )cmax * cs_table->state[i].frequency; +do_div (cap, fmax); + cs_table->state[i].capacity = (unsigned long )cap;
I prefer div64_*() over do_div(), the calling convention the latter always confuses the heck out of me.
So this then becomes something like:
cs_table->state[i].capacity = div64_u64(cmax * cs_table->state[i].frequency, fmax);
Quoted 2 lines
(quoted diff) +2
-0+ } +}
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 25 lines · Peter Zijlstra
Quoted 6 lines · Quentin Perret
+/*
fd_update_cs_table()- Computes the capacity values of acs_table
+ *
+ * This assumes a linear relation between capacity and frequency. As such,
+ * the capacity of a CPU at the n^th capacity state is computed as:
+ * capactity(n) =max_capacity* freq(n) /freq_max
+ */Broken comment style
kernel/power/energy_model.c line 69
Quoted 11 lines
kernel/power/energy_model.c new file +11
-0+static void fd_update_cs_table (struct em_cs_table *cs_table,int cpu) +{ +unsigned long cmax =arch_scale_cpu_capacity (NULL , cpu); +int max_cap_state = cs_table->nr_cap_states -1 ; +unsigned long fmax = cs_table->state[max_cap_state].frequency; +int i; + +for (i =0 ; i < cs_table->nr_cap_states; i++) { +u64 cap = (u64 )cmax * cs_table->state[i].frequency; +do_div (cap, fmax); + cs_table->state[i].capacity = (unsigned long )cap;I prefer div64_*() over
do_div(), the calling convention the latter always confuses the heck out of me.
Quoted 4 lines
So this then becomes something like:
cs_table->state[i].capacity = div64_u64(cmax * cs_table->state[i].frequency, fmax);
Ok, I'll change both.
Thanks,
Quentin
Vincent Guittot
maintainerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
In reply to Quentin PerretQuoted 165 lines · Quentin Perret
Several subsystems in the kernel (task scheduler and/or thermal at the time of writing) can benefit from knowing about the energy consumed by CPUs. Yet, this information can come from different sources (DT or firmware for example), in different formats, hence making it hard to exploit without a standard API.
As an attempt to address this, introduce a centralized Energy Model (EM) management framework which aggregates the power values provided by drivers into a table for each frequency domain in the system. The power cost tables are made available to interested clients (e.g. task scheduler or thermal) via platform-agnostic APIs. The overall design is represented by the diagram below (focused on Arm-related drivers as an example, but hopefully applicable to any architecture):
+---------------+ +-----------------+ +---------+ | Thermal (IPA) | | Scheduler (EAS) | | Other ? | +---------------+ +-----------------+ +---------+ | | em_fd_energy() | | | em_cpu_get() | +-----------+ | +--------+ | | | v v v +---------------------+ | | +---------------+ | Energy Model | | arch_topology | | |<--------| driver | | Framework | +---------------+ | | em_rescale_cpu_capacity() +---------------------+ ^ ^ ^ | | | em_register_freq_domain() +----------+ | +---------+ | | | +---------------+ +---------------+ +--------------+ | cpufreq-dt | | arm_scmi | | Other | +---------------+ +---------------+ +--------------+ ^ ^ ^ | | | +--------------+ +---------------+ +--------------+ | Device Tree | | Firmware | | ? | +--------------+ +---------------+ +--------------+Drivers (typically, but not limited to, CPUFreq drivers) can register data in the EM framework using the
em_register_freq_domain()API. The calling driver must provide a callback function with a standardized signature that will be used by the EM framework to build the power cost tables of the frequency domain. This design should offer a lot of flexibility to calling drivers which are free of reading information from any location and to use any technique to compute power costs. Moreover, the capacity states registered by drivers in the EM framework are not required to match real performance states of the target. This is particularly important on targets where the performance states are not known by the OS.On the client side, the EM framework offers APIs to access the power cost tables of a CPU (
em_cpu_get()), and to estimate the energy consumed by the CPUs of a frequency domain (em_fd_energy()). Clients such as the task scheduler can then use these APIs to access the shared data structures holding the Energy Model of CPUs.The EM framework also provides an API (
em_rescale_cpu_capacity()) to re-scale the capacity values of the model asynchronously, after it has been created. This is required for architectures where the capacity scale factor of CPUs can change at run-time. This is the case for Arm/Arm64 for example where thearch_topologydriver recomputes the capacity scale factors of the CPUs after the maximum frequency of all CPUs has been discovered. Although complex, the process of creating and re-scaling the EM has to be kept in two separate steps to fulfill the needs of the different users. The thermal subsystem doesn't use the capacity values and shouldn't have dependencies on subsystems providing them. On the other hand, the task scheduler needs the capacity values, and it will benefit from seeing them up-to-date when applicable.Cc Peter Zijlstra <[email protected]>Cc "Rafael J. Wysocki" <[email protected]>Signed-off-by Quentin Perret <[email protected]>--- include/linux/energy_model.h | 140 ++++++++++++++++++ kernel/power/Kconfig | 15 ++ kernel/power/Makefile | 2 + kernel/power/energy_model.c | 273 +++++++++++++++++++++++++++++++++++ 4 files changed, 430 insertions(+) create mode 100644 include/linux/energy_model.h create mode 100644 kernel/power/energy_model.cinclude/linux/energy_model.h new file +73
-0@@ -0,0 +1,140 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_ENERGY_MODEL_H +#define _LINUX_ENERGY_MODEL_H +#include <linux/cpumask.h> +#include <linux/jump_label.h> +#include <linux/kobject.h> +#include <linux/rcupdate.h> +#include <linux/sched/cpufreq.h> +#include <linux/types.h> + +#ifdef CONFIG_ENERGY_MODEL +struct em_cap_state { + unsigned long capacity; + unsigned long frequency; /* Kilo-hertz */ + unsigned long power; /* Milli-watts */ +}; + +struct em_cs_table { + struct em_cap_state *state; /* Capacity states, in ascending order. */ + int nr_cap_states; + struct rcu_head rcu; +}; + +struct em_freq_domain { + struct em_cs_table *cs_table; /* Capacity state table, RCU-protected */ + unsigned long cpus[0]; /* CPUs of the frequency domain. */ +}; + +#define EM_CPU_MAX_POWER 0xFFFF + +struct em_data_callback { + /** + * active_power() - Provide power at the next capacity state of a CPU + * @power : Active power at the capacity state in mW (modified) + * @freq : Frequency at the capacity state in kHz (modified) + * @cpu : CPU for which we do this operation + * + * active_power() must find the lowest capacity state of 'cpu' above + * 'freq' and update 'power' and 'freq' to the matching active power + * and frequency. + * + * The power is the one of a single CPU in the domain, expressed in + * milli-watts. It is expected to fit in the [0, EM_CPU_MAX_POWER] + * range. + * + * Return 0 on success. + */ + int (*active_power) (unsigned long *power, unsigned long *freq, int cpu); +}; +#define EM_DATA_CB(_active_power_cb) { .active_power = &_active_power_cb } + +void em_rescale_cpu_capacity(void); +struct em_freq_domain *em_cpu_get(int cpu); +int em_register_freq_domain(cpumask_t *span, unsigned int nr_states, + struct em_data_callback *cb); + +/** + * em_fd_energy() - Estimates the energy consumed by the CPUs of a freq. domain + * @fd : frequency domain for which energy has to be estimated + * @max_util : highest utilization among CPUs of the domain + * @sum_util : sum of the utilization of all CPUs in the domain + * + * em_fd_energy() dereferences the capacity state table of the frequency + * domain, so it must be called under RCU read lock. + * + * Return: the sum of the energy consumed by the CPUs of the domain assuming + * a capacity state satisfying the max utilization of the domain. + */ +static inline unsigned long em_fd_energy(struct em_freq_domain *fd, + unsigned long max_util, unsigned long sum_util) +{ + struct em_cs_table *cs_table; + struct em_cap_state *cs;
include/linux/energy_model.h line 83
Quoted 10 lines
include/linux/energy_model.h new file +10
-0+unsigned long freq; +int i; + + cs_table =rcu_dereference (fd->cs_table); +if (!cs_table) +return 0 ; + +/* Map the utilization value to a frequency */ + cs = &cs_table->state[cs_table->nr_cap_states -1 ]; + freq =map_util_freq (max_util, cs->frequency, cs->capacity);
The 2 lines above deserve more explanation:
1st, you get the max capacity of the freq domain
Then, you estimate what will be the selected frequency according to the max_utilization.
Might worth to mention that we must keep sync how sched_util and EM select a freq for a given capacity which is the reason of patch 02
include/linux/energy_model.h line 92
Quoted 9 lines
include/linux/energy_model.h new file +9
-0+ +/* Find the lowest capacity state above this frequency */ +for (i =0 ; i < cs_table->nr_cap_states; i++) { + cs = &cs_table->state[i]; +if (cs->frequency >= freq) +break ; + } + +return cs->power * sum_util / cs->capacity;
IIUC the formula above, you consider that all CPUs in a frequency domain has the same capacity. This sounds a reasonable assumption but it would be good to write that somewhere
Quoted 2 lines
include/linux/energy_model.h new file +2
-0+} +
Peter Zijlstra
maintainerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 4 lines · Vincent Guittot
IIUC the formula above, you consider that all CPUs in a frequency domain has the same capacity. This sounds a reasonable assumption but it would be good to write that somewhere
Yes, I think there used to be a WARN and kill EM for that, but I cannot seem to locate that in the current code.
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Vincent Guittot
IIUC the formula above, you consider that all CPUs in a frequency domain has the same capacity. This sounds a reasonable assumption but it would be good to write that somewhere
Yes, I think there used to be a WARN and kill EM for that, but I cannot seem to locate that in the current code.
There is something if the EM is too complex to be used by the scheduler. But nothing about that assumption (yet).
I'll fix that in v5
Thanks,
Quentin
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
In reply to Vincent GuittotHi Vincent,
Quoted 15 lines · Vincent Guittot
Quoted 14 lines · Quentin Perret
include/linux/energy_model.h new file +14
-0+static inline unsigned long em_fd_energy (struct em_freq_domain *fd, +unsigned long max_util,unsigned long sum_util) +{ +struct em_cs_table *cs_table; +struct em_cap_state *cs; +unsigned long freq; +int i; + + cs_table =rcu_dereference (fd->cs_table); +if (!cs_table) +return 0 ; + +/* Map the utilization value to a frequency */ + cs = &cs_table->state[cs_table->nr_cap_states -1 ];
Quoted 8 lines
Quoted 1 line
+ freq =
map_util_freq(max_util, cs->frequency, cs->capacity);The 2 lines above deserve more explanation:
1st, you get the max capacity of the freq domain
Then, you estimate what will be the selected frequency according to themax_utilization.
Might worth to mention that we must keep sync howsched_utiland EM select a freq for a given capacity which is the reason of patch 02
Agreed, this could benefit from more explanations. I'll comment that better in the next version.
Quoted 14 lines
include/linux/energy_model.h line 92
Quoted 10 lines
include/linux/energy_model.h new file +9
-0+ +/* Find the lowest capacity state above this frequency */ +for (i =0 ; i < cs_table->nr_cap_states; i++) { + cs = &cs_table->state[i]; +if (cs->frequency >= freq) +break ; + } + +return cs->power * sum_util / cs->capacity;IIUC the formula above, you consider that all CPUs in a frequency domain has the same capacity. This sounds a reasonable assumption but it would be good to write that somewhere
That's correct, we agreed on the assumption that CPUs in the same freq domain must have the same micro-arch, and consequently the same capacity.
But you're right, that needs at the very least to be documented. Or even better, I should check that when the EM is created and bail out with an error message if that's not the case. That shouldn't be too hard to implement, I think.
Thanks,
Quentin
Dietmar Eggemann
reviewerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
In reply to Quentin PerretOn 06/28/2018 01:40 PM, Quentin Perret wrote:
[...]
Quoted 33 lines
kernel/power/energy_model.c new file +33
-0+/** +* em_rescale_cpu_capacity() - Re-scale capacity values of the Energy Model +* +* This re-scales the capacity values for all capacity states of all frequency +* domains of the Energy Model. This should be used when the capacity values +* of the CPUs are updated at run-time, after the EM was registered. +*/ +void em_rescale_cpu_capacity (void ) +{ +struct em_cs_table *old_table, *new_table; +struct em_freq_domain *fd; +int nr_states, cpu; + +mutex_lock (&em_fd_mutex); +rcu_read_lock (); +for_each_possible_cpu (cpu) { +/* Re-scale only once per frequency domain. */ + fd =READ_ONCE (per_cpu (em_data, cpu)); +if (!fd || cpu !=cpumask_first (to_cpumask (fd->cpus))) +continue ; + +/* Copy the existing table. */ + old_table =rcu_dereference (fd->cs_table); + nr_states = old_table->nr_cap_states; + new_table =alloc_cs_table (nr_states); +if (!new_table) + goto out; +memcpy (new_table->state, old_table->state, + nr_states *sizeof (*new_table->state)); + +/* Re-scale the capacity values of the copy. */ +fd_update_cs_table (new_table, +cpumask_first (to_cpumask (fd->cpus)));
kernel/power/energy_model.c line 205
Quoted 10 lines
kernel/power/energy_model.c new file +10
-0+ +/* Replace the fd table with the re-scaled version. */ +rcu_assign_pointer (fd->cs_table, new_table); +call_rcu (&old_table->rcu, rcu_free_cs_table); + } +out: +rcu_read_unlock (); +mutex_unlock (&em_fd_mutex); +} +EXPORT_SYMBOL_GPL (em_rescale_cpu_capacity);
This em_rescale_cpu_capacity() function is still very much specific to systems with asymmetric cpu capacity (Arm big.Little/DynamIQ). Only after cpufreq is up we can determine the capacity of a CPU, hence we need this one to set the CPU capacity values for the individual performance states.
Can you not calculate capacity 'on the fly' just using freq and max freq as well as arch_scale_cpu_capacity() which gives you max capacity?
capacity = arch_scale_cpu_capacity() * freq / max_freq
In this case we could get rid of the 'ugly' EM rescaling infrastructure.
[...]
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 5 lines · Dietmar Eggemann
On 06/28/2018 01:40 PM, Quentin Perret wrote:
Thisem_rescale_cpu_capacity()function is still very much specific to systems with asymmetric cpu capacity (Arm big.Little/DynamIQ). Only after cpufreq is up we can determine the capacity of a CPU, hence we need this one to set the CPU capacity values for the individual performance states.
The abstraction is that this function is needed by all systems where the capacities of CPUs are discovered late, or can be changed at run-time. But yeah, AFAICT this applies mainly to Arm big.LITTLE and/or DynamIQ systems, at least for now.
Quoted 7 lines
Can you not calculate capacity 'on the fly' just using freq and max freq as well as
arch_scale_cpu_capacity()which gives you max capacity?capacity =
arch_scale_cpu_capacity()* freq /max_freqIn this case we could get rid of the 'ugly' EM rescaling infrastructure.
Indeed, having 'capacity' values in the EM framework is just an optimization for the scheduler, so that it doesn't need to compute them in the wake-up path. I could get rid of the whole em_rescale_cpu_capacity() mess (and by the same occasion the RCU protection of the tables ...) if I removed the 'capacity' values from the EM. But that means a slightly higher complexity on the scheduler side.
As you said, the capacity of a CPU at a specific OPP is:
cap(opp) = freq(opp) * scale_cpu / max_freq
Now, we estimate the energy consumed by this CPU as:
nrg = power(opp) * util / cap(opp)
because 'util / cap(opp)' represents its percentage of busy time. If I inject the first equation in the second, I get:
nrg = power(opp) * util * max_freq / (scale_cpu * freq(opp))
and this can be re-arranged as:
nrg = (power(opp) * max_freq / freq(opp)) * (util / scale_cpu)
In the above equation, the first term between () is static so I could pre-compute it as a 'cost' for that OPP and store it in the EM table:
cost(opp) = power(opp) * max_freq / freq(opp)
And then the energy calculation would be something like:
nrg = cost(opp) * util / scale_cpu
If 'scale_cpu' was static, I could fold it into 'cost' and avoid the cost of the division. But it's not really, so I can either re-do the division all the time on the scheduler side, or play with RCU to cache the result of the division in the EM framework.
(I now realize that the current implementation of em_fd_energy() does 'cs->power * sum_util / cs->capacity' but the power / capacity ratio is constant so, if we decide to keep the capacity values in the EM, I should still cache 'power / capacity' in the EM tables and actually save the division ...)
This is really a performance vs. code complexity trade-off. I made the choice of performance since we're talking about the scheduler here, but I'm not sure how much we really save by saving this division TBH.
Thoughts ?
Thanks,
Quentin
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 6 lines · Quentin Perret
Indeed, having 'capacity' values in the EM framework is just an optimization for the scheduler, so that it doesn't need to compute them in the wake-up path. I could get rid of the whole
em_rescale_cpu_capacity()mess (and by the same occasion the RCU protection of the tables ...) if I removed the 'capacity' values from the EM.
Another thing to take into consideration here is basically that the thermal subsystem (IPA) will be impacted by the RCU protection on the cs_table. However, since the 'frequency' and 'power' fields do not change at run-time, and since IPA doesn't need the 'capacity' value, there is no good reason to have IPA do rcu_read_lock() all over the place, so arguably something needs to be fixed here.
One possibility is to remove entirely the following struct:
struct em_cap_state {
unsigned long capacity;
unsigned long frequency; /* Kilo-hertz */
unsigned long power; /* Milli-watts */
};and to have three independent vectors (of the same size) for frequency, power and capacity. That way only the 'capacity' vector would be RCU protected, and IPA could use 'frequency' and 'power' directly, without further protections.
A second possibility is to remove the capacity values from the EM altogether (as I suggested in my previous message) and to get rid of the need for RCU protection at the same occasion.
The second option simplifies the code of the EM framework significantly (no more em_rescale_cpu_capacity()) and shouldn't introduce massive overheads on the scheduler side (the energy calculation already requires one multiplication and one division, so nothing new on that side). At the same time, that would make it a whole lot easier to interface the EM framework with IPA without having to deal with RCU all over the place.
So, if there are no objections, I'll try to explore that possibility for v5.
I hope that makes sense
Thanks,
Quentin
Dietmar Eggemann
reviewerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 1 line · Quentin Perret
On Tuesday 10 Jul 2018 at 09:32:02 (+0100), Quentin Perret wrote:
[...]
Quoted 14 lines
Another thing to take into consideration here is basically that the thermal subsystem (IPA) will be impacted by the RCU protection on the
cs_table. However, since the 'frequency' and 'power' fields do not change at run-time, and since IPA doesn't need the 'capacity' value, there is no good reason to have IPA dorcu_read_lock()all over the place, so arguably something needs to be fixed here.One possibility is to remove entirely the following struct:
struct em_cap_state { unsigned long capacity; unsigned long frequency; /* Kilo-hertz */ unsigned long power; /* Milli-watts */ };
Quoted 8 lines
and to have three independent vectors (of the same size) for frequency, power and capacity. That way only the 'capacity' vector would be RCU protected, and IPA could use 'frequency' and 'power' directly, without further protections.
A second possibility is to remove the capacity values from the EM altogether (as I suggested in my previous message) and to get rid of the need for RCU protection at the same occasion.
I see an impact of 'calculating capacity on the fly' in compute_energy()->em_fd_energy(). Running the first energy test case (# task equal 10) on the Juno r0 board with function profiling gives me:
v4:
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 14620 30790.86 us 2.106 us 8.421 us compute_energy 682 1512.960 us 2.218 us 0.154 us compute_energy 1207 2627.820 us 2.177 us 0.172 us compute_energy 93 206.720 us 2.222 us 0.151 us A57 - cpu [1-2] compute_energy 153 160.100 us 1.046 us 0.190 us compute_energy 136 130.760 us 0.961 us 0.077 us
v4 + 'calculating capacity on the fly':
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 11623 26941.12 us 2.317 us 12.203 us compute_energy 5062 11771.48 us 2.325 us 0.819 us compute_energy 4391 10396.78 us 2.367 us 1.753 us compute_energy 2234 5265.640 us 2.357 us 0.955 us A57 - cpu [1-2] compute_energy 59 66.020 us 1.118 us 0.112 us compute_energy 229 234.880 us 1.025 us 0.135 us
The code is not optimized, I just replaced cs->capacity with arch_scale_cpu_capacity(NULL, cpu) (max_cap) and 'max_cap * cs->frequency / max_freq' respectively. There are 3 compute_energy() calls per wake-up on a system with 2 frequency domains.
Quoted 7 lines
The second option simplifies the code of the EM framework significantly (no more
em_rescale_cpu_capacity()) and shouldn't introduce massive overheads on the scheduler side (the energy calculation already requires one multiplication and one division, so nothing new on that side). At the same time, that would make it a whole lot easier to interface the EM framework with IPA without having to deal with RCU all over the place.
IMO, em_rescale_cpu_capacity() is just the capacity related example what the EM needs if its values can be changed at runtime. There might be other use cases in the future like changing power values depending on temperature. So maybe it's a good idea to not have this 'EM values can change at runtime' feature in the first version of the EM and emphasize on simplicity of the code instead (if we can eliminate the extra runtime overhead).
[...]
Re: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Hi Dietmar,
Quoted 30 lines · Dietmar Eggemann
On 07/16/2018 12:29 PM, Quentin Perret wrote:
I see an impact of 'calculating capacity on the fly' in compute_energy()->em_fd_energy(). Running the first energy test case (# task equal 10) on the Juno r0 board with function profiling gives me:v4:
Function Hit Time Avg s^2
A53 - cpu [0,3-5]compute_energy 14620 30790.86 us 2.106 us 8.421 us compute_energy 682 1512.960 us 2.218 us 0.154 us compute_energy 1207 2627.820 us 2.177 us 0.172 us compute_energy 93 206.720 us 2.222 us 0.151 us A57 - cpu [1-2] compute_energy 153 160.100 us 1.046 us 0.190 us compute_energy 136 130.760 us 0.961 us 0.077 usv4 + 'calculating capacity on the fly':
Function Hit Time Avg s^2
A53 - cpu [0,3-5]compute_energy 11623 26941.12 us 2.317 us 12.203 us compute_energy 5062 11771.48 us 2.325 us 0.819 us compute_energy 4391 10396.78 us 2.367 us 1.753 us compute_energy 2234 5265.640 us 2.357 us 0.955 us A57 - cpu [1-2] compute_energy 59 66.020 us 1.118 us 0.112 us compute_energy 229 234.880 us 1.025 us 0.135 us
Quoted 5 lines
The code is not optimized, I just replaced
cs->capacitywitharch_scale_cpu_capacity(NULL, cpu)(max_cap) and 'max_cap*cs->frequency/max_freq' respectively.
There are 3compute_energy()calls per wake-up on a system with 2 frequency domains.
First, thank you very much for looking into this :-)
So, I guess you see this overhead because of the extra division involved by computing 'cap = max_cap * cs->frequency / max_freq'. However, I think there is an opportunity to optimize things a bit and avoid that overhead entirely. My suggestion is to remove the 'capacity' field from the em_cap_state struct and to add a 'cost' parameter instead:
struct em_cap_state {
unsigned long frequency;
unsigned long power;
unsigned long cost;
};I define the 'cost' of a capacity state as:
cost = power * max_freq / freq;
Since 'power', 'max_freq' and 'freq' do not change at run-time (as opposed to 'capacity'), this coefficient is static and computed when the table is first created. Then, based on this, you can implement em_fd_energy() as follows:
static inline unsigned long em_fd_energy(struct em_freq_domain *fd,
unsigned long max_util, unsigned long sum_util)
{
unsigned long freq, scale_cpu;
struct em_cap_state *cs;
int i, cpu;
/* Map the utilization value to a frequency */
cpu = cpumask_first(to_cpumask(fd->cpus));
scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
cs = &fd->table[fd->nr_cap_states - 1];
freq = map_util_freq(max_util, cs->frequency, scale_cpu);
/* Find the lowest capacity state above this frequency */
for (i = 0; i < fd->nr_cap_states; i++) {
cs = &fd->table[i];
if (cs->frequency >= freq)
break;
}
/*
* The capacity of a CPU at a specific performance state is defined as:
*
* cap = freq * scale_cpu / max_freq
*
* The energy consumed by this CPU can be estimated as:
*
* nrg = power * util / cap
*
* because (util / cap) represents the percentage of busy time of the
* CPU. Based on those definitions, we have:
*
* nrg = power * util * max_freq / (scale_cpu * freq)
*
* which can be re-arranged as a product of two terms:
*
* nrg = (power * max_freq / freq) * (util / scale_cpu)
*
* The first term is static, and is stored in the em_cap_state struct
* as 'cost'. The parameters of the second term change at run-time.
*/
return cs->cost * sum_util / scale_cpu;
}With the above implementation, there is no additional division in em_fd_energy() compared to v4, so I would expect to see no significant difference in computation time.
I tried to reproduce your test case and I get the following numbers on my Juno r0 (using the performance governor):
v4:
***
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 1796 12685.66 us 7.063 us 0.039 us compute_energy 4214 28060.02 us 6.658 us 0.919 us compute_energy 2743 20167.86 us 7.352 us 0.067 us compute_energy 13958 97122.68 us 6.958 us 9.255 us A57 - cpu [1-2] compute_energy 86 448.800 us 5.218 us 0.106 us compute_energy 163 847.600 us 5.200 us 0.128 us
'v5' (with 'cost'):
*******************
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 1695 11153.54 us 6.580 us 0.022 us compute_energy 16823 113709.5 us 6.759 us 27.109 us compute_energy 677 4490.060 us 6.632 us 0.028 us compute_energy 1959 13595.66 us 6.940 us 0.029 us A57 - cpu [1-2] compute_energy 211 1089.860 us 5.165 us 0.122 us compute_energy 83 420.860 us 5.070 us 0.075 us
So I don't observe any obvious regression with my optimization applied. The v4 branch I used is the one mentioned in the cover letter:
http://www.linux-arm.org/git?p=linux-qp.git;a=shortlog;h=refs/heads/upstream/eas_v4
And I just pushed the WiP branch I used to compare against:
http://www.linux-arm.org/git?p=linux-qp.git;a=shortlog;h=refs/heads/upstream/eas_v5-WiP-compute_energy_profiling
Is this also fixing the regression on your side ?
Quoted 9 lines
Quoted 8 lines
The second option simplifies the code of the EM framework significantly (no more
em_rescale_cpu_capacity()) and shouldn't introduce massive overheads on the scheduler side (the energy calculation already requires one multiplication and one division, so nothing new on that side). At the same time, that would make it a whole lot easier to interface the EM framework with IPA without having to deal with RCU all over the place.
Quoted 6 lines
IMO,
em_rescale_cpu_capacity()is just the capacity related example what the EM needs if its values can be changed at runtime. There might be other use cases in the future like changing power values depending on temperature. So maybe it's a good idea to not have this 'EM values can change at runtime' feature in the first version of the EM and emphasize on simplicity of the code instead (if we can eliminate the extra runtime overhead).
I agree that it would be nice to keep it simple in the beginning. If there is strong and demonstrated use-case for updating the EM at run-time later, then we can re-introduce the RCU protection. But until then, we can avoid the complex implementation at no obvious cost (given my results above) so that sounds like a good trade-off to me :-)
Thanks,
Quentin
Dietmar Eggemann
reviewerRe: [RFC PATCH v4 03/12] PM: Introduce an Energy Model management framework
Quoted 4 lines · Quentin Perret
Hi Dietmar,
Quoted 1 line · Dietmar Eggemann
On 07/16/2018 12:29 PM, Quentin Perret wrote:
[...]
Quoted 98 lines
So, I guess you see this overhead because of the extra division involved by computing 'cap =
max_cap*cs->frequency/max_freq'. However, I think there is an opportunity to optimize things a bit and avoid that overhead entirely. My suggestion is to remove the 'capacity' field from theem_cap_statestruct and to add a 'cost' parameter instead:struct em_cap_state { unsigned long frequency; unsigned long power; unsigned long cost; };I define the 'cost' of a capacity state as:
cost = power * max_freq / freq;Since 'power', '
max_freq' and 'freq' do not change at run-time (as opposed to 'capacity'), this coefficient is static and computed when the table is first created. Then, based on this, you can implementem_fd_energy()as follows:static inline unsigned long em_fd_energy(struct
em_freq_domain*fd,
unsigned longmax_util, unsigned longsum_util){ unsigned long freq, scale_cpu; struct em_cap_state *cs; int i, cpu; /* Map the utilization value to a frequency */ cpu = cpumask_first(to_cpumask(fd->cpus)); scale_cpu = arch_scale_cpu_capacity(NULL, cpu); cs = &fd->table[fd->nr_cap_states - 1]; freq = map_util_freq(max_util, cs->frequency, scale_cpu); /* Find the lowest capacity state above this frequency */ for (i = 0; i < fd->nr_cap_states; i++) { cs = &fd->table[i]; if (cs->frequency >= freq) break; } /* * The capacity of a CPU at a specific performance state is defined as: * * cap = freq * scale_cpu / max_freq * * The energy consumed by this CPU can be estimated as: * * nrg = power * util / cap * * because (util / cap) represents the percentage of busy time of the * CPU. Based on those definitions, we have: * * nrg = power * util * max_freq / (scale_cpu * freq) * * which can be re-arranged as a product of two terms: * * nrg = (power * max_freq / freq) * (util / scale_cpu) * * The first term is static, and is stored in the em_cap_state struct * as 'cost'. The parameters of the second term change at run-time. */ return cs->cost * sum_util / scale_cpu; }With the above implementation, there is no additional division in
em_fd_energy()compared to v4, so I would expect to see no significant difference in computation time.I tried to reproduce your test case and I get the following numbers on my Juno r0 (using the performance governor):
v4:
***
Function Hit Time Avg s^2
A53 - cpu [0,3-5]compute_energy 1796 12685.66 us 7.063 us 0.039 us compute_energy 4214 28060.02 us 6.658 us 0.919 us compute_energy 2743 20167.86 us 7.352 us 0.067 us compute_energy 13958 97122.68 us 6.958 us 9.255 us A57 - cpu [1-2] compute_energy 86 448.800 us 5.218 us 0.106 us compute_energy 163 847.600 us 5.200 us 0.128 us'v5' (with 'cost'):
*******************
Function Hit Time Avg s^2
A53 - cpu [0,3-5]compute_energy 1695 11153.54 us 6.580 us 0.022 us compute_energy 16823 113709.5 us 6.759 us 27.109 us compute_energy 677 4490.060 us 6.632 us 0.028 us compute_energy 1959 13595.66 us 6.940 us 0.029 us A57 - cpu [1-2] compute_energy 211 1089.860 us 5.165 us 0.122 us compute_energy 83 420.860 us 5.070 us 0.075 us
Quoted 3 lines
So I don't observe any obvious regression with my optimization applied. The v4 branch I used is the one mentioned in the cover letter:
http://www.linux-arm.org/git?p=linux-qp.git;a=shortlog;h=refs/heads/upstream/eas_v4
Yeah, just realized that I used the wrong eas_v4 branch. With the one you mentioned here I still get ~0.2-0.3us diff with the non-optimized approach but at least values in the same ballpark as yours (performance governor to keep s^2 low):
v4:
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 233 1455.140 us 6.245 us 0.022 us
...
A57 - cpu [1-2]
compute_energy 130 602.980 us 4.638 us 0.043 us
v4 + '(naive) calculating capacity on the fly':
Function Hit Time Avg s^2
A53 - cpu [0,3-5]
compute_energy 531 3460.200 us 6.516 us 0.044 us
A57 - cpu [1-2]
compute_energy 141 700.220 us 4.966 us 0.106 us
Quoted 4 lines
And I just pushed the WiP branch I used to compare against:
http://www.linux-arm.org/git?p=linux-qp.git;a=shortlog;h=refs/heads/upstream/eas_v5-WiP-compute_energy_profilingIs this also fixing the regression on your side ?
I assume with you 'unsigned long cost' optimization I will get the same test result than you so I guess that's the optimization which assures that we don't have to pay the simplification of the EM with scheduler runtime.
[...]
Quoted 7 lines
Quoted 6 lines
IMO,
em_rescale_cpu_capacity()is just the capacity related example what the EM needs if its values can be changed at runtime. There might be other use cases in the future like changing power values depending on temperature. So maybe it's a good idea to not have this 'EM values can change at runtime' feature in the first version of the EM and emphasize on simplicity of the code instead (if we can eliminate the extra runtime overhead).
Quoted 5 lines
I agree that it would be nice to keep it simple in the beginning. If there is strong and demonstrated use-case for updating the EM at run-time later, then we can re-introduce the RCU protection. But until then, we can avoid the complex implementation at no obvious cost (given my results above) so that sounds like a good trade-off to me :-)
Agreed.
[...]
RFC PATCH v4 4/12 PM / EM: Expose the Energy Model in sysfs
In reply to Quentin PerretExpose the Energy Model (read-only) of all frequency domains in sysfs for convenience. To do so, add a kobject to the CPU subsystem under the umbrella of which a kobject for each frequency domain is attached.
The resulting hierarchy is as follows for a platform with two frequency domains for example:
/sys/devices/system/cpu/energy_model
├── fd0
│ ├── capacity
│ ├── cpus
│ ├── frequency
│ └── power
└── fd4
├── capacity
├── cpus
├── frequency
└── powerIn this implementation, the kobject abstraction is only used as a convenient way of exposing data to sysfs. However, it could also be used in the future to allocate and release frequency domains in a more dynamic way using reference counting.
--- include/linux/energy_model.h | 1 + kernel/power/energy_model.c | 94 ++++++++++++++++++++++++++++++++++++ 2 files changed, 95 insertions(+)
include/linux/energy_model.h +1 -0
@@ -23,6 +23,7 @@ struct em_cs_table {struct em_freq_domain {struct em_cs_table *cs_table;/* Capacity state table, RCU-protected */ +struct kobject kobj;unsigned long cpus[0 ];/* CPUs of the frequency domain. */ };
kernel/power/energy_model.c +94 -0
112 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH v4 5/12 sched/topology: Reference the Energy Model of CPUs when available
In reply to Quentin PerretThe existing scheduling domain hierarchy is defined to map to the cache topology of the system. However, Energy Aware Scheduling (EAS) requires more knowledge about the platform, and specifically needs to know about the span of Frequency Domains (FD), which do not always align with caches.
To address this issue, use the Energy Model (EM) of the system to extend the scheduler topology code with a representation of the FDs, alongside the scheduling domains. More specifically, a linked list of FDs is attached to each root domain. When multiple root domains are in use, each list contains only the FDs covering the CPUs of its root domain. If a FD spans over CPUs of two different root domains, it will be duplicated in both lists.
The lists are fully maintained by the scheduler from partition_sched_domains() in order to cope with hotplug and cpuset changes. As for scheduling domains, the list are protected by RCU to ensure safe concurrent updates.
--- kernel/sched/sched.h | 23 +++++++ kernel/sched/topology.c | 129 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 152 insertions(+)
kernel/sched/sched.h +23 -0
@@ -44,6 +44,7 @@#include <linux/ctype.h> #include <linux/debugfs.h> #include <linux/delayacct.h> +#include <linux/energy_model.h> #include <linux/init_task.h> #include <linux/kprobes.h> #include <linux/kthread.h>
@@ -673,6 +674,12 @@ static inline bool sched_asym_prefer(int a, int b)return arch_asym_cpu_priority (a) >arch_asym_cpu_priority (b); } +struct freq_domain { +struct em_freq_domain *obj; +struct freq_domain *next; +struct rcu_head rcu; +}; +/* * We add the notion of a root-domain which will be used to define per-domain * variables. Each exclusive cpuset essentially defines an island domain by
@@ -721,6 +728,14 @@ struct root_domain {struct cpupri cpupri;unsigned long max_cpu_capacity; + +#ifdef CONFIG_ENERGY_MODEL +/* +* NULL-terminated list of frequency domains intersecting with the +* CPUs of the rd. Protected by RCU. +*/ +struct freq_domain *fd; +#endif };extern struct root_domain def_root_domain;
@@ -2169,3 +2184,11 @@ static inline unsigned long cpu_util_cfs(struct rq *rq) return util; }#endif + +#ifdef CONFIG_SMP +#ifdef CONFIG_ENERGY_MODEL +#define freq_domain_span (fd) (to_cpumask(((fd)->obj->cpus))) +#else +#define freq_domain_span (fd) NULL +#endif +#endif
kernel/sched/topology.c +129 -0
153 lines not on this page · raw message
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerRe: [RFC PATCH v4 05/12] sched/topology: Reference the Energy Model of CPUs when available
Quoted 25 lines · Quentin Perret
kernel/sched/topology.c +13
-0@@ -201,6 +201,19 @@ sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)return 1 ; } +#ifdef CONFIG_ENERGY_MODEL +static void free_fd (struct freq_domain *fd) +{ +struct freq_domain *tmp; + +while (fd) { + tmp = fd->next; +kfree (fd); + fd = tmp; + } +} +#endif +static void free_rootdomain (struct rcu_head *rcu) { struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
kernel/sched/topology.c static void free_rootdomain(struct rcu_head *rcu) · line 229
Quoted 6 lines
kernel/sched/topology.c +3
-0@@ -211,6 +224,9 @@ static void free_rootdomain(struct rcu_head *rcu)free_cpumask_var (rd->rto_mask);free_cpumask_var (rd->online);free_cpumask_var (rd->span); +#ifdef CONFIG_ENERGY_MODEL +free_fd (rd->fd); +#endif
If you provide a stub function, you can reduce #ifdef.
kernel/sched/topology.c static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve · line 1654
Quoted 8 lines
kernel/sched/topology.c +1
-0kfree (rd); }@@ -1635,6 +1651,104 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_levereturn sd; } +#ifdef CONFIG_ENERGY_MODEL
< snip content >
kernel/sched/topology.c static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve · line 1655
Quoted 1 line
kernel/sched/topology.c +1
-0+#endif
And is there any reason this #ifdef cannot be merged with the one above?
That is, try and do a pass of #ifdef reduction on this file.
Re: [RFC PATCH v4 05/12] sched/topology: Reference the Energy Model of CPUs when available
Quoted 13 lines · Peter Zijlstra
kernel/sched/topology.c static void free_rootdomain(struct rcu_head *rcu) · line 229
Quoted 10 lines · Quentin Perret
static void
free_rootdomain(struct rcu_head *rcu){kernel/sched/topology.c +3
-0struct root_domain *rd = container_of(rcu, struct root_domain, rcu);@@ -211,6 +224,9 @@ static void free_rootdomain(struct rcu_head *rcu)free_cpumask_var (rd->rto_mask);free_cpumask_var (rd->online);free_cpumask_var (rd->span); +#ifdef CONFIG_ENERGY_MODEL +free_fd (rd->fd); +#endif If you provide a stub function, you can reduce #ifdef.
I cannot just stub free_fd since the 'fd' member of the root_domain is also defined only for CONFIG_ENERGY_MODEL=y.
But I can introduce a free_rd_fd(fd) function that will be stubbed if you think that's better. Or make sure to have 'fd' attached to the root_domain even for CONFIG_ENERGY_MODEL=n.
Quoted 8 lines
Quoted 8 lines
kernel/sched/topology.c +0
-0kfree (rd); }@@ -1635,6 +1651,104 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_levereturn sd; }
Quoted 7 lines
Review static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve · line 1654
Quoted 1 line
(quoted diff) +1
-0+#ifdef CONFIG_ENERGY_MODEL< snip content >
Review static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve · line 1655
Quoted 1 line
(quoted diff) +1
-0+#endifAnd is there any reason this #ifdef cannot be merged with the one above?
Not really, it was just easier to keep build_freq_domains() close to partition_sched_domains() while writing/reading the code but that is a very weak argument, I agree. I'll move all of that to the ifdef above.
Quoted 1 line
That is, try and do a pass of #ifdef reduction on this file.
Ok I'll look into that.
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 05/12] sched/topology: Reference the Energy Model of CPUs when available
In reply to Quentin Perretkernel/sched/topology.c void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[], · line 2035
Quoted 2 lines · Quentin Perret
kernel/sched/topology.c +2
-0+if (cpumask_equal (doms_new[i], doms_cur[j]) + &&cpu_rq (cpumask_first (doms_cur[j]))->rd->fd)
Please put the operator at the end of the previous line, not the begin of the next line when splitting.
Re: [RFC PATCH v4 05/12] sched/topology: Reference the Energy Model of CPUs when available
Quoted 6 lines · Peter Zijlstra
kernel/sched/topology.c void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[], · line 2035
Quoted 2 lines · Quentin Perret
kernel/sched/topology.c +2
-0+if (cpumask_equal (doms_new[i], doms_cur[j]) + &&cpu_rq (cpumask_first (doms_cur[j]))->rd->fd)Please put the operator at the end of the previous line, not the begin of the next line when splitting.
I did that to be consistent with the to similar loops above, but n/p, I'll change it :-)
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 05/12] sched/topology: Reference the Energy Model of CPUs when available
Quoted 10 lines · Quentin Perret
Quoted 6 lines · Peter Zijlstra
kernel/sched/topology.c void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[], · line 2035
Quoted 2 lines · Quentin Perret
kernel/sched/topology.c +2
-0+if (cpumask_equal (doms_new[i], doms_cur[j]) + &&cpu_rq (cpumask_first (doms_cur[j]))->rd->fd)Please put the operator at the end of the previous line, not the begin of the next line when splitting.
I did that to be consistent with the to similar loops above, but n/p, I'll change it :-)
In that case, feel free to fix those too ;-)
RFC PATCH v4 6/12 sched/topology: Lowest energy aware balancing sched_domain level pointer
In reply to Quentin PerretAdd another member to the family of per-cpu sched_domain shortcut pointers. This one, sd_ea, points to the lowest level at which energy aware scheduling should be used.
Generally speaking, the largest opportunity to save energy via scheduling comes from a smarter exploitation of heterogeneous platforms (i.e. big.LITTLE). Consequently, the sd_ea shortcut is wired to the lowest scheduling domain at which the SD_ASYM_CPUCAPACITY flag is set. For example, it is possible to apply energy-aware scheduling within a socket on a multi-socket system, as long as each socket has an asymmetric topology. Cross-sockets wake-up balancing will only happen when the system is over-utilized, or this_cpu and prev_cpu are in different sockets.
--- kernel/sched/sched.h | 1 + kernel/sched/topology.c | 4 ++++ 2 files changed, 5 insertions(+)
kernel/sched/sched.h +1 -0
@@ -1168,6 +1168,7 @@ DECLARE_PER_CPU(int, sd_llc_id); DECLARE_PER_CPU(struct sched_domain_shared *, sd_llc_shared); DECLARE_PER_CPU(struct sched_domain *, sd_numa); DECLARE_PER_CPU(struct sched_domain *, sd_asym); +DECLARE_PER_CPU(struct sched_domain *, sd_ea);struct sched_group_capacity {atomic_t ref;
kernel/sched/topology.c +4 -0
@@ -414,6 +414,7 @@ DEFINE_PER_CPU(int, sd_llc_id); DEFINE_PER_CPU(struct sched_domain_shared *, sd_llc_shared); DEFINE_PER_CPU(struct sched_domain *, sd_numa); DEFINE_PER_CPU(struct sched_domain *, sd_asym); +DEFINE_PER_CPU(struct sched_domain *, sd_ea);static void update_top_cache_domain (int cpu) {
@@ -439,6 +440,9 @@ static void update_top_cache_domain(int cpu) sd =highest_flag_domain (cpu,SD_ASYM_PACKING );rcu_assign_pointer (per_cpu (sd_asym, cpu), sd); + + sd =lowest_flag_domain (cpu,SD_ASYM_CPUCAPACITY ); +rcu_assign_pointer (per_cpu (sd_ea, cpu), sd); }/*
Signature · 1 line
2.17.1
RFC PATCH v4 7/12 sched/topology: Introduce sched_energy_present static key
In reply to Quentin PerretIn order to ensure a minimal performance impact on non-energy-aware systems, introduce a static_key guarding the access to Energy-Aware Scheduling (EAS) code.
The static key is set iff all the following conditions are met for at least one root domain:
1. all online CPUs of the root domain are covered by the Energy
Model (EM);
2. the complexity of the root domain's EM is low enough to keep
scheduling overheads low; 3. the root domain has an asymmetric CPU capacity topology (detected by looking for the SD_ASYM_CPUCAPACITY flag in the sched_domain hierarchy).
The static key is checked in the rd_freq_domain() function which returns the frequency domains of a root domain when they are available. As EAS cannot be enabled with CONFIG_ENERGY_MODEL=n, rd_freq_domain() is stubbed to 'NULL' to let the compiler remove the unused EAS code by constant propagation.
--- kernel/sched/sched.h | 17 ++++++++++ kernel/sched/topology.c | 72 ++++++++++++++++++++++++++++++++++++++++- 2 files changed, 88 insertions(+), 1 deletion(-)
kernel/sched/sched.h +17 -0
@@ -2188,8 +2188,25 @@ static inline unsigned long cpu_util_cfs(struct rq *rq)#ifdef CONFIG_SMP #ifdef CONFIG_ENERGY_MODEL +extern struct static_key_false sched_energy_present; +/** +* rd_freq_domain - Get the frequency domains of a root domain. +* +* Must be called from a RCU read-side critical section. +*/ +static inline struct freq_domain *rd_freq_domain (struct root_domain *rd) +{ +if (!static_branch_unlikely (&sched_energy_present)) +return NULL ; + +return rcu_dereference (rd->fd); +}#define freq_domain_span (fd) (to_cpumask(((fd)->obj->cpus)))#else +static inline struct freq_domain *rd_freq_domain (struct root_domain *rd) +{ +return NULL ; +}#define freq_domain_span (fd) NULL#endif #endif
kernel/sched/topology.c +71 -1
101 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH v4 8/12 sched: Add over-utilization/tipping point indicator
In reply to Quentin PerretFrom: Morten Rasmussen <[email protected]>
Energy-aware scheduling is only meant to be active while the system is _not_ over-utilized. That is, there are spare cycles available to shift tasks around based on their actual utilization to get a more energy-efficient task distribution without depriving any tasks. When above the tipping point task placement is done the traditional way based on load_avg, spreading the tasks across as many cpus as possible based on priority scaled load to preserve smp_nice. Below the tipping point we want to use util_avg instead. We need to define a criteria for when we make the switch.
The util_avg for each cpu converges towards 100% (1024) regardless of how many task additional task we may put on it. If we define over-utilized as:
sum_{cpus}(rq.cfs.avg.util_avg) + margin > sum_{cpus}(rq.capacity)
some individual cpus may be over-utilized running multiple tasks even when the above condition is false. That should be okay as long as we try to spread the tasks out to avoid per-cpu over-utilization as much as possible and if all tasks have the _same_ priority. If the latter isn't true, we have to consider priority to preserve smp_nice.
For example, we could have n_cpus nice=-10 util_avg=55% tasks and n_cpus/2 nice=0 util_avg=60% tasks. Balancing based on util_avg we are likely to end up with nice=-10 tasks sharing cpus and nice=0 tasks getting their own as we 1.5*n_cpus tasks in total and 55%+55% is less over-utilized than 55%+60% for those cpus that have to be shared. The system utilization is only 85% of the system capacity, but we are breaking smp_nice.
To be sure not to break smp_nice, we have defined over-utilization conservatively as when any cpu in the system is fully utilized at it's highest frequency instead:
cpu_rq(any).cfs.avg.util_avg + margin > cpu_rq(any).capacity
IOW, as soon as one cpu is (nearly) 100% utilized, we switch to load_avg to factor in priority to preserve smp_nice.
With this definition, we can skip periodic load-balance as no cpu has an always-running task when the system is not over-utilized. All tasks will be periodic and we can balance them at wake-up. This conservative condition does however mean that some scenarios that could benefit from energy-aware decisions even if one cpu is fully utilized would not get those benefits.
For system where some cpus might have reduced capacity on some cpus (RT-pressure and/or big.LITTLE), we want periodic load-balance checks as soon a just a single cpu is fully utilized as it might one of those with reduced capacity and in that case we want to migrate it.
--- kernel/sched/fair.c | 48 +++++++++++++++++++++++++++++++++++++++++--- kernel/sched/sched.h | 3 +++ 2 files changed, 48 insertions(+), 3 deletions(-)
kernel/sched/fair.c +45 -3
@@ -5374,6 +5374,24 @@ static inline void hrtick_update(struct rq *rq) }#endif +#ifdef CONFIG_SMP +static inline unsigned long cpu_util (int cpu); +static unsigned long capacity_of (int cpu); + +static inline bool cpu_overutilized (int cpu) +{ +return (capacity_of (cpu) *1024 ) < (cpu_util (cpu) * capacity_margin); +} + +static inline void update_overutilized_status (struct rq *rq) +{ +if (!READ_ONCE (rq->rd->overutilized) &&cpu_overutilized (rq->cpu)) +WRITE_ONCE (rq->rd->overutilized,1 ); +} +#else +static inline void update_overutilized_status (struct rq *rq) { } +#endif +/* * The enqueue_task method is called before nr_running is * increased. Here we update the fair scheduling stats and
@@ -5384,6 +5402,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se; +int task_new = !(flags &ENQUEUE_WAKEUP );/* * The code below (indirectly) updates schedutil which looks at
@@ -5431,8 +5450,12 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)update_cfs_group (se); } -if (!se) +if (!se) {add_nr_running (rq,1 ); +if (!task_new) +update_overutilized_status (rq); + + }hrtick_update (rq); }
@@ -8114,11 +8137,12 @@ static bool update_nohz_stats(struct rq *rq, bool force)* @local_group: Does group contain this_cpu. * @sgs: variable to hold the statistics for this group. * @overload: Indicate more than one runnable task for any CPU. +* @overutilized: Indicate overutilization for any CPU. */ static inline void update_sg_lb_stats (struct lb_env *env,struct sched_group *group,int load_idx,int local_group,struct sg_lb_stats *sgs, -bool *overload) +bool *overload,int *overutilized) {unsigned long load;int i, nr_running;
@@ -8145,6 +8169,9 @@ static inline void update_sg_lb_stats(struct lb_env *env,if (nr_running >1 ) *overload = true; +if (cpu_overutilized (i)) + *overutilized =1 ; +#ifdef CONFIG_NUMA_BALANCING sgs->nr_numa_running += rq->nr_numa_running; sgs->nr_preferred_running += rq->nr_preferred_running;
@@ -8282,6 +8309,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sg_lb_stats tmp_sgs;int load_idx, prefer_sibling =0 ;bool overload = false; +int overutilized =0 ;if (child && child->flags &SD_PREFER_SIBLING ) prefer_sibling =1 ;
@@ -8308,7 +8336,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd }update_sg_lb_stats (env, sg, load_idx, local_group, sgs, - &overload); + &overload, &overutilized);if (local_group) goto next_group;
@@ -8360,6 +8388,13 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd/* update overload indicator if we are at root domain */ if (env->dst_rq->rd->overload != overload) env->dst_rq->rd->overload = overload; + +/* Update over-utilization (tipping point, U >= 0) indicator */ +if (READ_ONCE (env->dst_rq->rd->overutilized) != overutilized) +WRITE_ONCE (env->dst_rq->rd->overutilized, overutilized); + }else { +if (!READ_ONCE (env->dst_rq->rd->overutilized) && overutilized) +WRITE_ONCE (env->dst_rq->rd->overutilized,1 ); } }
@@ -8579,6 +8614,11 @@ static struct sched_group *find_busiest_group(struct lb_env *env)* this level. */ update_sd_lb_stats (env, &sds); + +if (rd_freq_domain (env->dst_rq->rd) && + !READ_ONCE (env->dst_rq->rd->overutilized)) + goto out_balanced; + local = &sds.local_stat; busiest = &sds.busiest_stat;
@@ -9936,6 +9976,8 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)if (static_branch_unlikely (&sched_numa_balancing))task_tick_numa (rq, curr); + +update_overutilized_status (task_rq (curr)); }/*
kernel/sched/sched.h +3 -0
@@ -698,6 +698,9 @@ struct root_domain {/* Indicate more than one runnable task for any CPU */ bool overload; +/* Indicate one or more cpus over-utilized (tipping point) */ +int overutilized; +/* * The bit corresponding to a CPU gets set here if such CPU has more * than one runnable -deadline task (as it is below for RT tasks).
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerRe: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
Quoted 9 lines · Quentin Perret
kernel/sched/fair.c +1
-0@@ -5384,6 +5402,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se; +int task_new = !(flags &ENQUEUE_WAKEUP );/* * The code below (indirectly) updates schedutil which looks at
kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5456
Quoted 8 lines
kernel/sched/fair.c +3
-1@@ -5431,8 +5450,12 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)update_cfs_group (se); } -if (!se) +if (!se) {add_nr_running (rq,1 ); +if (!task_new) +update_overutilized_status (rq);
I'm confused... why only for !ENQUEUE_WAKEUP and why use a local variable for something that's used only once?
Quoted 4 lines
kernel/sched/fair.c +1
-0+ }hrtick_update (rq); }
Re: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Quentin Perret
kernel/sched/fair.c +1
-0@@ -5384,6 +5402,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se; +int task_new = !(flags &ENQUEUE_WAKEUP );/* * The code below (indirectly) updates schedutil which looks at @@ -5431,8 +5450,12 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)update_cfs_group (se); }
Quoted 7 lines
kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5456
Quoted 5 lines
kernel/sched/fair.c +3
-1-if (!se) +if (!se) {add_nr_running (rq,1 ); +if (!task_new) +update_overutilized_status (rq);I'm confused... why only for !ENQUEUE_WAKEUP
So, what we try to do here is to _not_ set the overutilized flag based on the utilization of a new task, because its utilization is 'wrong'. That should help avoiding spurious transitions above the overutilized threshold.
Was there also something else Morten ?
Quoted 2 lines
and why use a local
variable for something that's used only once?
No good reasons. An older version of this patch used 'task_new' in two different locations. This is no longer true, I'll clean that up for v5.
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
Quoted 22 lines · Quentin Perret
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Quentin Perret
kernel/sched/fair.c +1
-0@@ -5384,6 +5402,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) {struct cfs_rq *cfs_rq;struct sched_entity *se = &p->se; +int task_new = !(flags &ENQUEUE_WAKEUP );/* * The code below (indirectly) updates schedutil which looks at @@ -5431,8 +5450,12 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)update_cfs_group (se); }Quoted 7 lines
kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5456
Quoted 5 lines
kernel/sched/fair.c +3
-1-if (!se) +if (!se) {add_nr_running (rq,1 ); +if (!task_new) +update_overutilized_status (rq);I'm confused... why only for !ENQUEUE_WAKEUP
Quoted 4 lines
So, what we try to do here is to _not_ set the overutilized flag based on the utilization of a new task, because its utilization is 'wrong'. That should help avoiding spurious transitions above the overutilized threshold.
That most certainly deserves a comment, also didn't util_est fix some of that wrong-ness?
Re: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Quentin Perret
So, what we try to do here is to _not_ set the overutilized flag based on the utilization of a new task, because its utilization is 'wrong'. That should help avoiding spurious transitions above the overutilized threshold.
That most certainly deserves a comment,
Ok, will do.
Quoted 1 line
also didn't
util_estfix some of that wrong-ness?
When a new task is enqueued, we don't have util_est samples yet, so the task's util_est is equal to its util_avg. So util_est won't help here, unfortunately.
But it does help in the wake-up path to predict what OPP will be selected (see cpu_util_next() in patch 09/12).
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
In reply to Quentin PerretQuoted 7 lines · Quentin Perret
static inline void update_sg_lb_stats(struct
lb_env*env,(quoted diff) +1
-1struct sched_group *group, int load_idx, int local_group, struct sg_lb_stats *sgs, - bool *overload) + bool *overload, int *overutilized)
Review static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd · line 8342
Quoted 8 lines
(quoted diff) +1
-1@@ -8308,7 +8336,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd } update_sg_lb_stats(env, sg, load_idx, local_group, sgs, - &overload); + &overload, &overutilized); if (local_group) goto next_group;
I'm thinking maybe we should reduce arguments here a little.
@load_idx and @local_group look to be trivially computable..
and possibly we could frob overload and overutilized in a single variable with some flags?
kernel/sched/fair.c +6 -7
@@ -8114,10 +8114,12 @@ static bool update_nohz_stats(struct rq *rq, bool force)* @overload: Indicate more than one runnable task for any CPU. */ static inline void update_sg_lb_stats (struct lb_env *env, -struct sched_group *group,int load_idx, -int local_group,struct sg_lb_stats *sgs, +struct sched_group *group, +struct sg_lb_stats *sgs,bool *overload) { +int local_group =cpumask_test_cpu (env->dst_cpu,sched_group_span (sd)); +int load_idx =get_sd_load_idx (env->sd, env->idle);unsigned long load;int i, nr_running;
@@ -8278,7 +8280,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sched_group *sg = env->sd->groups;struct sg_lb_stats *local = &sds->local_stat;struct sg_lb_stats tmp_sgs; -int load_idx, prefer_sibling =0 ; +int prefer_sibling =0 ;bool overload = false;if (child && child->flags &SD_PREFER_SIBLING )
@@ -8289,8 +8291,6 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd env->flags |=LBF_NOHZ_STATS ;#endif - load_idx =get_sd_load_idx (env->sd, env->idle); - do { struct sg_lb_stats *sgs = &tmp_sgs; int local_group;
@@ -8305,8 +8305,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdupdate_group_capacity (env->sd, env->dst_cpu); } -update_sg_lb_stats (env, sg, load_idx, local_group, sgs, - &overload); +update_sg_lb_stats (env, sg, sgs, &overload);if (local_group) goto next_group;
Peter Zijlstra
maintainerRe: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
In reply to Quentin Perretkernel/sched/sched.h struct root_domain { · line 699
Quoted 3 lines · Quentin Perret
kernel/sched/sched.h +0
-0@@ -698,6 +698,9 @@ struct root_domain {/* Indicate more than one runnable task for any CPU */ bool overload;
While there, make that an int.
Quoted 9 lines
kernel/sched/sched.h +3
-0+/* Indicate one or more cpus over-utilized (tipping point) */ +int overutilized; +/* * The bit corresponding to a CPU gets set here if such CPU has more * than one runnable -deadline task (as it is below for RT tasks). Signature · 1 line
2.17.1
Re: [RFC PATCH v4 08/12] sched: Add over-utilization/tipping point indicator
Quoted 6 lines · Peter Zijlstra
kernel/sched/sched.h struct root_domain { · line 699
Quoted 3 lines · Quentin Perret
kernel/sched/sched.h +0
-0@@ -698,6 +698,9 @@ struct root_domain {/* Indicate more than one runnable task for any CPU */ bool overload;While there, make that an int.
That's what I've done at [1] - I guess that's the fun part of having those two patch sets in flight at the same time...
[1]: https://lore.kernel.org/lkml/[email protected]/
Quoted 10 lines
Quoted 10 lines
kernel/sched/sched.h +3
-0+/* Indicate one or more cpus over-utilized (tipping point) */ +int overutilized; +/* * The bit corresponding to a CPU gets set here if such CPU has more * than one runnable -deadline task (as it is below for RT tasks). Signature · 1 line
2.17.1
RFC PATCH v4 9/12 sched/fair: Introduce an energy estimation helper function
In reply to Quentin PerretIn preparation for the definition of an energy-aware wakeup path, introduce a helper function to estimate the consequence on system energy when a specific task wakes-up on a specific CPU. compute_energy() estimates the capacity state to be reached by all frequency domains and estimates the consumption of each online CPU according to its Energy Model and its percentage of busy time.
--- kernel/sched/fair.c | 69 ++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 2 +- 2 files changed, 70 insertions(+), 1 deletion(-)
kernel/sched/fair.c +69 -0
@@ -6621,6 +6621,75 @@ static int wake_cap(struct task_struct *p, int cpu, int prev_cpu)return min_cap *1024 <task_util (p) * capacity_margin; } +/* +* Predicts what cpu_util(@cpu) would return if @p was migrated (and enqueued) +* to @dst_cpu. +*/ +static unsigned long cpu_util_next (int cpu,struct task_struct *p,int dst_cpu) +{ +struct cfs_rq *cfs_rq = &cpu_rq (cpu)->cfs; +unsigned long util_est, util =READ_ONCE (cfs_rq->avg.util_avg); + +/* +* If @p migrates from @cpu to another, remove its contribution. Or, +* if @p migrates from another CPU to @cpu, add its contribution. In +* the other cases, @cpu is not impacted by the migration, so the +* util_avg should already be what we want. +*/ +if (task_cpu (p) == cpu && dst_cpu != cpu) + util =max_t (long, util -task_util (p),0 ); +else if (task_cpu (p) != cpu && dst_cpu == cpu) + util +=task_util (p); + +if (sched_feat (UTIL_EST )) { + util_est =READ_ONCE (cfs_rq->avg.util_est.enqueued); + +/* +* During wake-up, the task isn't enqueued yet and doesn't +* appear in the cfs_rq->avg.util_est.enqueued of any rq, +* so just add it (if needed) to "simulate" what will be +* cpu_util() after the task has been enqueued. +*/ +if (dst_cpu == cpu) + util_est +=_task_util_est (p); + + util =max (util, util_est); + } + + return min_t(unsigned long, util, capacity_orig_of(cpu)); +} + +/* +* Estimates the total energy that would be consumed by all online CPUs if @p +* was migrated to @dst_cpu. compute_energy() predicts what will be the +* utilization landscape of all CPUs after the task migration, and uses the +* Energy Model to compute what would be the system energy if we decided to +* actually migrate that task. +*/ +static long compute_energy (struct task_struct *p,int dst_cpu, +struct freq_domain *fd) +{ +long util, max_util, sum_util, energy =0 ; +int cpu; + +while (fd) { + max_util = sum_util =0 ; +for_each_cpu_and (cpu,freq_domain_span (fd), cpu_online_mask) { + util =cpu_util_next (cpu, p, dst_cpu); + util +=cpu_util_dl (cpu_rq (cpu)); +/* XXX: add RT util_avg when available. */ + + max_util =max (util, max_util); + sum_util += util; + } + + energy +=em_fd_energy (fd->obj, max_util, sum_util); + fd = fd->next; + } + +return energy; +} +/* * select_task_rq_fair: Select target runqueue for the waking task in domains * that have the 'sd_flag' flag set. In practice, this is SD_BALANCE_WAKE,
kernel/sched/sched.h +1 -1
@@ -2170,7 +2170,7 @@ static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) {}# define arch_scale_freq_invariant () false#endif -#ifdef CONFIG_CPU_FREQ_GOV_SCHEDUTIL +#ifdef CONFIG_SMP static inline unsigned long cpu_util_dl (struct rq *rq) {return (rq->dl.running_bw *SCHED_CAPACITY_SCALE ) >>BW_SHIFT ;
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerRe: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 1 line · Quentin Perret
+static long
compute_energy(struct task_struct *p, int dst_cpu, struct freq_domain *fd)
kernel/sched/fair.c static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) · line 6677
Quoted 7 lines
kernel/sched/fair.c +7
-0+{ +long util, max_util, sum_util, energy =0 ; +int cpu; + +while (fd) { + max_util = sum_util =0 ; +for_each_cpu_and (cpu,freq_domain_span (fd), cpu_online_mask) {
I had a wee little wtf moment when I realized this crosses root_domain boundaries but that that is actually desired. A comment might be in order.
kernel/sched/fair.c static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) · line 6683
Quoted 6 lines
kernel/sched/fair.c +6
-0+ util =cpu_util_next (cpu, p, dst_cpu); + util +=cpu_util_dl (cpu_rq (cpu)); +/* XXX: add RT util_avg when available. */ + + max_util =max (util, max_util); + sum_util += util;
Did you want to use sugov_get_util() here? There is no way we're going to duplicate all that.
ISTR we already established the whole EAS was going to require using schedutil anyway.
Quoted 8 lines
kernel/sched/fair.c +8
-0+ } + + energy +=em_fd_energy (fd->obj, max_util, sum_util); + fd = fd->next; + } + +return energy; +}
Re: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 14 lines · Peter Zijlstra
Quoted 1 line · Quentin Perret
+static long
compute_energy(struct task_struct *p, int dst_cpu, struct freq_domain *fd)kernel/sched/fair.c static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) · line 6677
Quoted 7 lines
kernel/sched/fair.c +7
-0+{ +long util, max_util, sum_util, energy =0 ; +int cpu; + +while (fd) { + max_util = sum_util =0 ; +for_each_cpu_and (cpu,freq_domain_span (fd), cpu_online_mask) {I had a wee little wtf moment when I realized this crosses
root_domainboundaries but that that is actually desired. A comment might be in order.
Indeed, the selection of CPU candidates is guaranteed to be within the root_domain, but the boundaries for the energy calculation can be different. The OPP in a FD can be driven by a CPU outside of the root_domain we're currently looking at ... I'll add a comment about that.
I guess it is also worth mentioning that in the case mentioned above the scheduling decisions made inside one root domain can indirectly be impacted by the scheduling decisions made in another root domain. Some CPUs inside one root domain might look expensive to use simply because they run at a high OPP because of other CPUs of the same FD being over-used in another root domain.
This is arguably not desirable, but I'm not sure if this is a problem. It would be wise for users not to split a frequency domain in multiple root domains IMO but we can't really prevent them from doing so ...
Another solution would be to ignore the CPUs outside of the root_domain and to accept that this can lead to sub-optimal scheduling decisions from an energy standpoint.
Quoted 10 lines
kernel/sched/fair.c static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) · line 6683
Quoted 7 lines
kernel/sched/fair.c +6
-0+ util =cpu_util_next (cpu, p, dst_cpu); + util +=cpu_util_dl (cpu_rq (cpu)); +/* XXX: add RT util_avg when available. */ + + max_util =max (util, max_util); + sum_util += util;Did you want to use
sugov_get_util()here? There is no way we're going to duplicate all that.
I need to look into how we can do that ... Sugov looks at the current util landscape while EAS tries to predict the _future_ util landscape. Merging the two means I need to add a task and a dst_cpu as parameters of sugov_get_util() and call cpu_util_next() from there, which doesn't feel so clean ...
Also, if we merge sugov_get_util() and sugov_aggregate_util() with Vincent's patch-set I'll need to make sure to return two values with sugov_get_util(): 1) the sum of the util of all classes; and 2) the util that will be used to request an OPP. 1) should be used in sum_util and
2) could (but I don't think it's is a good idea) be used for max_util.
This probably won't be pretty :/
Peter Zijlstra
maintainerRe: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 10 lines · Quentin Perret
Quoted 2 lines · Peter Zijlstra
Did you want to use
sugov_get_util()here? There is no way we're going to duplicate all that.I need to look into how we can do that ... Sugov looks at the current util landscape while EAS tries to predict the _future_ util landscape. Merging the two means I need to add a task and a
dst_cpuas parameters ofsugov_get_util()and callcpu_util_next()from there, which doesn't feel so clean ...
Just pass in the util_cfs as computed by cpu_util_next(), then schedutil will pass in cpu_util_cfs(), the rest is all the same I think.
See below.
Quoted 5 lines
Also, if we merge
sugov_get_util()andsugov_aggregate_util()with Vincent's patch-set I'll need to make sure to return two values withsugov_get_util(): 1) the sum of the util of all classes; and 2) the util that will be used to request an OPP. 1) should be used insum_utiland
2) could (but I don't think it's is a good idea) be used formax_util.
I am confused, the max/sum thing is composed of the same values, just a different operator. Both take 'util':
+ util = schedutil_get_util(cpu, cpu_util_next(cpu, p, dst_cpu))
+ max_util = max(util, max_util);
+ sum_util += util;
unsigned long schedutil_get_util(int cpu, unsigned long util_cfs)
{
struct rq *rq = cpu_rq(cpu);
unsigned long util, irq, max;
max = arch_scale_cpu_capacity(NULL, cpu);
if (rt_rq_is_runnable(&rq->rt))
return max;
/*
* Early check to see if IRQ/steal time saturates the CPU, can be
* because of inaccuracies in how we track these -- see
* update_irq_load_avg().
*/
irq = cpu_util_irq(rq);
if (unlikely(irq >= max))
return max;
/*
* Because the time spend on RT/DL tasks is visible as 'lost' time to
* CFS tasks and we use the same metric to track the effective
* utilization (PELT windows are synchronized) we can directly add them
* to obtain the CPU's actual utilization.
*/
util = util_cfs;
util += cpu_util_rt(rq);
/*
* We do not make cpu_util_dl() a permanent part of this sum because we
* want to use cpu_bw_dl() later on, but we need to check if the
* CFS+RT+DL sum is saturated (ie. no idle time) such that we select
* f_max when there is no idle time.
*
* NOTE: numerical errors or stop class might cause us to not quite hit
* saturation when we should -- something for later.
*/
if ((util + cpu_util_dl(rq)) >= max)
return max;
/*
* There is still idle time; further improve the number by using the
* irq metric. Because IRQ/steal time is hidden from the task clock we
* need to scale the task numbers:
*
* 1 - irq
* U' = irq + ------- * U
* max
*/
util *= (max - irq);
util /= max;
util += irq;
/*
* Bandwidth required by DEADLINE must always be granted while, for
* FAIR and RT, we use blocked utilization of IDLE CPUs as a mechanism
* to gracefully reduce the frequency when no tasks show up for longer
* periods of time.
*
* Ideally we would like to set bw_dl as min/guaranteed freq and util +
* bw_dl as requested freq. However, cpufreq is not yet ready for such
* an interface. So, we only do the latter for now.
*/
return min(max, util + cpu_bw_dl(rq));
}Re: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 27 lines · Peter Zijlstra
Quoted 10 lines · Quentin Perret
Quoted 2 lines · Peter Zijlstra
Did you want to use
sugov_get_util()here? There is no way we're going to duplicate all that.I need to look into how we can do that ... Sugov looks at the current util landscape while EAS tries to predict the _future_ util landscape. Merging the two means I need to add a task and a
dst_cpuas parameters ofsugov_get_util()and callcpu_util_next()from there, which doesn't feel so clean ...Just pass in the
util_cfsas computed bycpu_util_next(), then schedutil will pass incpu_util_cfs(), the rest is all the same I think.See below.
Quoted 5 lines
Also, if we merge
sugov_get_util()andsugov_aggregate_util()with Vincent's patch-set I'll need to make sure to return two values withsugov_get_util(): 1) the sum of the util of all classes; and 2) the util that will be used to request an OPP. 1) should be used insum_utiland
2) could (but I don't think it's is a good idea) be used formax_util.I am confused, the max/sum thing is composed of the same values, just a different operator. Both take 'util':
kernel/sched/fair.c static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) · line 6683
Quoted 3 lines
kernel/sched/fair.c +3
-0+ util =schedutil_get_util (cpu,cpu_util_next (cpu, p, dst_cpu)) + max_util = max(util, max_util); + sum_util += util;
'max_util' is basically the util we use to request an OPP. 'sum_util' is how long the CPUs will be running. For now it's the same thing because I just used the util of the different classes and assumed that OPPs follow utilization, but if we start using sugov_get_util() things will become more complex, especially because of RT tasks.
In your example, schedutil_get_util() will return arch_scale_cpu_capacity() if a RT task is running. We're going to select an OPP with that so that's what you want to put in max_util. But we also need to know how long we are going to run at that OPP to compute the energy, and in this case arch_scale_cpu_capacity is probably _not_ what you want to account in sum_util ...
Now, I'm not sure if accounting the RT-go-to-max thing here is really going to help us. This is really an ON/OFF thing, so depending on 'luck', the OPP landscape that you'll observe in compute_energy() can be very different depending on whether or not a RT task is running in a FD. And that will change abruptly when the RT task goes to sleep.
What I'm proposing is to predict in compute_energy() what is the OPP at which CFS tasks run (cfs_util + dl_util +rt_util, to make it simple), and ignore the oddity of having an RT task running. But that makes it harder to factorize things with schedutil more than they are, that is true ...
I hope that makes sense
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 2 lines · Quentin Perret
'
max_util' is basically the util we use to request an OPP. 'sum_util' is how long the CPUs will be running.
A indeed. But yes bit of a mess, but it wants doing I think. Perhaps a little something like the below... The alternative is two separate but closely related functions, not sure which is better.
enum schedutil_type {
frequency_util,
energy_util,
};
unsigned longschedutil_freq_util(int cpu, unsigned long util_cfs, enum schedutil_type type)
{
struct rq *rq = cpu_rq(cpu);
unsigned long util, irq, max;
max = arch_scale_cpu_capacity(NULL, cpu);
if (type == frequency_util && rt_rq_is_runnable(&rq->rt))
return max;
/*
* Early check to see if IRQ/steal time saturates the CPU, can be
* because of inaccuracies in how we track these -- see
* update_irq_load_avg().
*/
irq = cpu_util_irq(rq);
if (unlikely(irq >= max))
return max;
/*
* Because the time spend on RT/DL tasks is visible as 'lost' time to
* CFS tasks and we use the same metric to track the effective
* utilization (PELT windows are synchronized) we can directly add them
* to obtain the CPU's actual utilization.
*/
util = util_cfs;
util += cpu_util_rt(rq);
if (type == frequency_util) {
/*
* For frequency selection we do not make cpu_util_dl()
* a permanent part of this sum because we want to use
* cpu_bw_dl() later on, but we need to check if the
* CFS+RT+DL sum is saturated (ie. no idle time) such
* that we select f_max when there is no idle time.
*
* NOTE: numerical errors or stop class might cause us
* to not quite hit saturation when we should --
* something for later.
*/
if ((util + cpu_util_dl(rq)) >= max)
return max;
} else {
/*
* OTOH, for energy computation we need the estimated
* running time, so include util_dl and ignore dl_bw.
*/
util += cpu_util_dl(rq);
if (util >= max)
return max;
}
/*
* There is still idle time; further improve the number by using the
* irq metric. Because IRQ/steal time is hidden from the task clock we
* need to scale the task numbers:
*
* 1 - irq
* U' = irq + ------- * U
* max
*/
util *= (max - irq);
util /= max;
util += irq;
if (type == frequency_util) {
/*
* Bandwidth required by DEADLINE must always be granted
* while, for FAIR and RT, we use blocked utilization of
* IDLE CPUs as a mechanism to gracefully reduce the
* frequency when no tasks show up for longer periods of
* time.
*
* Ideally we would like to set bw_dl as min/guaranteed
* freq and util + bw_dl as requested freq. However,
* cpufreq is not yet ready for such an interface. So,
* we only do the latter for now.
*/
util += cpu_bw_dl(rq);
}
return min(max, util);
}Re: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 5 lines · Peter Zijlstra
Quoted 2 lines · Quentin Perret
'
max_util' is basically the util we use to request an OPP. 'sum_util' is how long the CPUs will be running.A indeed. But yes bit of a mess, but it wants doing I think.
OK, understood.
Quoted 8 lines
Perhaps a little something like the below... The alternative is two separate but closely related functions, not sure which is better.
enum
schedutil_type{
frequency_util,
energy_util,
};
Hmm, this should work ... Should we also try to avoid the code duplication in scale_rt_capacity() ? This doesn't want dependencies on schedutil I assume so a little bit of extra work is required.
What about moving schedutil_freq_util() to sched.h and give it a more generic name (total_cpu_util() ?) with no dependencies on CONFIG_CPU_FREQ_GOV_SCHEDUTIL ? Also, 'energy_util' would have to be renamed I guess (busy_time_util ?).
Then scale_rt_capacity() can be turned into something like (totally untested):
static unsigned long scale_rt_capacity(int cpu)
{
unsigned long util = total_cpu_util(cpu, 0, busy_time_util);
return arch_scale_cpu_capacity(NULL, cpu) - util;
}Thoughts ?
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 4 lines · Quentin Perret
What about moving
schedutil_freq_util()tosched.hand give it a more generic name (total_cpu_util()?) with no dependencies onCONFIG_CPU_FREQ_GOV_SCHEDUTIL? Also, 'energy_util' would have to be renamed I guess (busy_time_util?).
Bit big for an inline, and I don't think there's much point using all this without schedutil. You already rely on it anyhow.
Re: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Quentin Perret
What about moving
schedutil_freq_util()tosched.hand give it a more generic name (total_cpu_util()?) with no dependencies onCONFIG_CPU_FREQ_GOV_SCHEDUTIL? Also, 'energy_util' would have to be renamed I guess (busy_time_util?).Bit big for an inline,
True, but that will be used in the wake-up path ...
Quoted 2 lines
and I don't think there's much point using all
this without schedutil.
For that total_cpu_util() function I was suggesting, the main point would be to avoid code duplication with scale_rt_capacity(). Not sure if that matters ?
Thanks,
Quentin
Peter Zijlstra
maintainerRe: [RFC PATCH v4 09/12] sched/fair: Introduce an energy estimation helper function
In reply to Quentin PerretQuoted 6 lines · Quentin Perret
I guess it is also worth mentioning that in the case mentioned above the scheduling decisions made inside one root domain can indirectly be impacted by the scheduling decisions made in another root domain. Some CPUs inside one root domain might look expensive to use simply because they run at a high OPP because of other CPUs of the same FD being over-used in another root domain.
That's simply how it is. There's nothing you can do about it, they share a clock, teh end.
RFC PATCH v4 10/12 sched/fair: Select an energy-efficient CPU on task wake-up
In reply to Quentin PerretIf an Energy Model (EM) is available and if the system isn't overutilized, re-route waking tasks into an energy-aware placement algorithm. The selection of an energy-efficient CPU for a task is achieved by estimating the impact on system-level active energy resulting from the placement of the task on the CPU with the highest spare capacity in each frequency domain. This strategy spreads tasks in a frequency domain and avoids overly aggressive task packing. The best CPU energy-wise is then selected if it saves a large enough amount of energy with respect to prev_cpu.
Although it has already shown significant benefits on some existing targets, this approach cannot scale to platforms with numerous CPUs. This is an attempt to do something useful as writing a fast heuristic that performs reasonably well on a broad spectrum of architectures isn't an easy task. As such, the scope of usability of the energy-aware wake-up path is restricted to systems with the SD_ASYM_CPUCAPACITY flag set, and where the EM isn't too complex.
--- kernel/sched/fair.c | 121 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 117 insertions(+), 4 deletions(-)
kernel/sched/fair.c +117 -4
@@ -6690,6 +6690,110 @@ static long compute_energy(struct task_struct *p, int dst_cpu,return energy; } +/* +* find_energy_efficient_cpu(): Find most energy-efficient target CPU for the +* waking task. find_energy_efficient_cpu() looks for the CPU with maximum +* spare capacity in each frequency domain and uses it as a potential +* candidate to execute the task. Then, it uses the Energy Model to figure +* out which of the CPU candidates is the most energy-efficient. +* +* The rationale for this heuristic is as follows. In a frequency domain, +* all the most energy efficient CPU candidates (according to the Energy +* Model) are those for which we'll request a low frequency. When there are +* several CPUs for which the frequency request will be the same, we don't +* have enough data to break the tie between them, because the Energy Model +* only includes active power costs. With this model, if we assume that +* frequency requests follow utilization (e.g. using schedutil), the CPU with +* the maximum spare capacity in a frequency domain is guaranteed to be among +* the best candidates of the frequency domain. +* +* In practice, it could be preferable from an energy standpoint to pack +* small tasks on a CPU in order to let other CPUs go in deeper idle states, +* but that could also hurt our chances to go cluster idle, and we have no +* ways to tell with the current Energy Model if this is actually a good +* idea or not. So, find_energy_efficient_cpu() basically favors +* cluster-packing, and spreading inside a cluster. That should at least be +* a good thing for latency, and this is consistent with the idea that most +* of the energy savings of EAS come from the asymmetry of the system, and +* not so much from breaking the tie between identical CPUs. That's also the +* reason why EAS is enabled in the topology code only for systems where +* SD_ASYM_CPUCAPACITY is set. +*/ +static int find_energy_efficient_cpu (struct task_struct *p,int prev_cpu, +struct freq_domain *fd) +{ +unsigned long prev_energy =ULONG_MAX , best_energy =ULONG_MAX ; +int cpu, best_energy_cpu = prev_cpu; +struct freq_domain *head = fd; +unsigned long cpu_cap, util; +struct sched_domain *sd; + +sync_entity_load_avg (&p->se); + +if (!task_util_est (p)) +return prev_cpu; + +/* +* Energy-aware wake-up happens on the lowest sched_domain starting +* from sd_ea spanning over this_cpu and prev_cpu. +*/ + sd =rcu_dereference (*this_cpu_ptr (&sd_ea)); +while (sd && !cpumask_test_cpu (prev_cpu,sched_domain_span (sd))) + sd = sd->parent; +if (!sd) +return prev_cpu; + +while (fd) { +unsigned long cur_energy, spare_cap, max_spare_cap =0 ; +int max_spare_cap_cpu =-1 ; + +for_each_cpu_and (cpu,freq_domain_span (fd),sched_domain_span (sd)) { +if (!cpumask_test_cpu (cpu, &p->cpus_allowed)) +continue ; + +/* Skip CPUs that will be overutilized. */ + util =cpu_util_next (cpu, p, cpu); + cpu_cap =capacity_of (cpu); +if (cpu_cap *1024 < util * capacity_margin) +continue ; + +/* Always use prev_cpu as a candidate. */ +if (cpu == prev_cpu) { + prev_energy =compute_energy (p, prev_cpu, head); +if (prev_energy < best_energy) + best_energy = prev_energy; +continue ; + } + +/* Find the CPU with the max spare cap the fd. */ + spare_cap = cpu_cap - util; +if (spare_cap > max_spare_cap) { + max_spare_cap = spare_cap; + max_spare_cap_cpu = cpu; + } + } + +/* Evaluate the energy impact of using this CPU. */ +if (max_spare_cap_cpu >=0 ) { + cur_energy =compute_energy (p, max_spare_cap_cpu, head); +if (cur_energy < best_energy) { + best_energy = cur_energy; + best_energy_cpu = max_spare_cap_cpu; + } + } + fd = fd->next; + } + +/* +* We pick the best CPU only if it saves at least 6% of the +* energy used by prev_cpu. +*/ +if ((prev_energy - best_energy) > (prev_energy >>4 )) +return best_energy_cpu; + +return prev_cpu; +} +/* * select_task_rq_fair: Select target runqueue for the waking task in domains * that have the 'sd_flag' flag set. In practice, this is SD_BALANCE_WAKE,
@@ -6706,18 +6810,26 @@ static int select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags) { struct sched_domain *tmp, *sd = NULL; +struct freq_domain *fd;int cpu =smp_processor_id ();int new_cpu = prev_cpu; -int want_affine =0 ; +int want_affine =0 , want_energy =0 ;int sync = (wake_flags &WF_SYNC ) && !(current->flags &PF_EXITING ); +rcu_read_lock ();if (sd_flag &SD_BALANCE_WAKE ) {record_wakee (p); - want_affine = !wake_wide (p) && !wake_cap (p, cpu, prev_cpu) - &&cpumask_test_cpu (cpu, &p->cpus_allowed); + fd =rd_freq_domain (cpu_rq (cpu)->rd); + want_energy = fd && !READ_ONCE (cpu_rq (cpu)->rd->overutilized); + want_affine = !wake_wide (p) && !wake_cap (p, cpu, prev_cpu) && +cpumask_test_cpu (cpu, &p->cpus_allowed); + } + +if (want_energy) { + new_cpu =find_energy_efficient_cpu (p, prev_cpu, fd); + goto unlock; } -rcu_read_lock ();for_each_domain (cpu, tmp) {if (!(tmp->flags &SD_LOAD_BALANCE ))break ;
@@ -6752,6 +6864,7 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_fif (want_affine) current->recent_used_cpu = cpu; } +unlock:rcu_read_unlock ();return new_cpu;
Signature · 1 line
2.17.1
RFC PATCH v4 11/12 OPTIONAL: arch_topology: Start Energy Aware Scheduling
In reply to Quentin PerretEnergy Aware Scheduling (EAS) starts when the scheduling domains are built if the Energy Model (EM) is present. However, in the typical case of Arm/Arm64 systems, the EM is provided after the scheduling domains are first built at boot time, which results in EAS staying disabled.
Fix this issue by re-building the scheduling domain from the arch topology driver, once CPUfreq is up and running and when the CPU capacities have been updated to their final value.
--- drivers/base/arch_topology.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+)
drivers/base/arch_topology.c +15 -0
@@ -10,7 +10,9 @@#include <linux/arch_topology.h> #include <linux/cpu.h> #include <linux/cpufreq.h> +#include <linux/cpuset.h> #include <linux/device.h> +#include <linux/energy_model.h> #include <linux/of.h> #include <linux/slab.h> #include <linux/string.h>
@@ -173,6 +175,9 @@ static cpumask_var_t cpus_to_visit;static void parsing_done_workfn (struct work_struct *work); static DECLARE_WORK(parsing_done_work, parsing_done_workfn); +static void start_eas_workfn (struct work_struct *work); +static DECLARE_WORK(start_eas_work, start_eas_workfn); + static int init_cpu_capacity_callback(struct notifier_block *nb, unsigned long val,
@@ -204,6 +209,7 @@ init_cpu_capacity_callback(struct notifier_block *nb,free_raw_capacity ();pr_debug ("cpu_capacity: parsing done\n" );schedule_work (&parsing_done_work); +schedule_work (&start_eas_work); }return 0 ;
@@ -249,6 +255,15 @@ static void parsing_done_workfn(struct work_struct *work) free_cpumask_var(cpus_to_visit); } +static void start_eas_workfn (struct work_struct *work) +{ +/* Make sure the EM knows about the updated CPU capacities. */ +em_rescale_cpu_capacity (); + +/* Inform the scheduler about the EM availability. */ +rebuild_sched_domains (); +} +#else core_initcall (free_raw_capacity);#endif
Signature · 1 line
2.17.1
RFC PATCH v4 12/12 OPTIONAL: cpufreq: dt: Register an Energy Model
In reply to Quentin Perret*******************************************************************
* This patch illustrates the usage of the newly introduced Energy *
* Model framework and isn't supposed to be merged as-is. *
*******************************************************************
The Energy Model framework provides an API to register the active power of CPUs. Call this API from the cpufreq-dt driver with an estimation of the power as P = C * V^2 * f with C, V, and f respectively the capacitance of the CPU and the voltage and frequency of the OPP.
The CPU capacitance is read from the "dynamic-power-coefficient" DT binding (originally introduced for thermal/IPA), and the voltage and frequency values from PM_OPP.
--- drivers/cpufreq/cpufreq-dt.c | 45 +++++++++++++++++++++++++++++++++++- 1 file changed, 44 insertions(+), 1 deletion(-)
drivers/cpufreq/cpufreq-dt.c +44 -1
@@ -16,6 +16,7 @@#include <linux/cpu_cooling.h> #include <linux/cpufreq.h> #include <linux/cpumask.h> +#include <linux/energy_model.h> #include <linux/err.h> #include <linux/module.h> #include <linux/of.h>
@@ -149,8 +150,47 @@ static int resources_available(void)return 0 ; } +static int of_est_power (unsigned long *mW,unsigned long *KHz,int cpu) +{ +unsigned long mV, Hz, MHz; +struct device *cpu_dev; +struct dev_pm_opp *opp; +struct device_node *np; +u32 cap; +u64 tmp; + + cpu_dev =get_cpu_device (cpu); +if (!cpu_dev) +return -ENODEV ; + + np =of_node_get (cpu_dev->of_node); +if (!np) +return -EINVAL ; + +if (of_property_read_u32 (np,"dynamic-power-coefficient" , &cap)) +return -EINVAL ; + + Hz = *KHz *1000 ; + opp =dev_pm_opp_find_freq_ceil (cpu_dev, &Hz); +if (IS_ERR (opp)) +return -EINVAL ; + + mV =dev_pm_opp_get_voltage (opp) /1000 ; +dev_pm_opp_put (opp); + + MHz = Hz /1000000 ; + tmp = (u64 )cap * mV * mV * MHz; +do_div (tmp,1000000000 ); + + *mW = (unsigned long )tmp; + *KHz = Hz /1000 ; + +return 0 ; +} +static int cpufreq_init (struct cpufreq_policy *policy) { +struct em_data_callback em_cb =EM_DATA_CB (of_est_power);struct cpufreq_frequency_table *freq_table;struct opp_table *opp_table =NULL ;struct private_data *priv;
@@ -159,7 +199,7 @@ static int cpufreq_init(struct cpufreq_policy *policy)unsigned int transition_latency;bool fallback = false;const char *name; -int ret; +int ret, nr_opp; cpu_dev =get_cpu_device (policy->cpu);if (!cpu_dev) {
@@ -226,6 +266,7 @@ static int cpufreq_init(struct cpufreq_policy *policy) ret = -EPROBE_DEFER ; goto out_free_opp; } + nr_opp = ret;if (fallback) {cpumask_setall (policy->cpus);
@@ -278,6 +319,8 @@ static int cpufreq_init(struct cpufreq_policy *policy) policy->cpuinfo.transition_latency = transition_latency; policy->dvfs_possible_from_any_cpu = true; +em_register_freq_domain (policy->cpus, nr_opp, &em_cb); +return 0 ; out_free_cpufreq_table:
Signature · 1 line
2.17.1
Vincent Guittot
maintainerRe: [RFC PATCH v4 12/12] OPTIONAL: cpufreq: dt: Register an Energy Model
Quoted 59 lines · Quentin Perret
*******************************************************************
* This patch illustrates the usage of the newly introduced Energy *
* Model framework and isn't supposed to be merged as-is. *
*******************************************************************The Energy Model framework provides an API to register the active power of CPUs. Call this API from the cpufreq-dt driver with an estimation of the power as P = C * V^2 * f with C, V, and f respectively the capacitance of the CPU and the voltage and frequency of the OPP.
The CPU capacitance is read from the "dynamic-power-coefficient" DT binding (originally introduced for thermal/IPA), and the voltage and frequency values from
PM_OPP.Cc "Rafael J. Wysocki" <[email protected]>Cc Viresh Kumar <[email protected]>Signed-off-by Quentin Perret <[email protected]>--- drivers/cpufreq/cpufreq-dt.c | 45 +++++++++++++++++++++++++++++++++++- 1 file changed, 44 insertions(+), 1 deletion(-)drivers/cpufreq/cpufreq-dt.c +22
-0@@ -16,6 +16,7 @@#include <linux/cpu_cooling.h> #include <linux/cpufreq.h> #include <linux/cpumask.h> +#include <linux/energy_model.h> #include <linux/err.h> #include <linux/module.h> #include <linux/of.h> @@ -149,8 +150,47 @@ static int resources_available(void)return 0 ; } +static int of_est_power (unsigned long *mW,unsigned long *KHz,int cpu) +{ +unsigned long mV, Hz, MHz; +struct device *cpu_dev; +struct dev_pm_opp *opp; +struct device_node *np; +u32 cap; +u64 tmp; + + cpu_dev =get_cpu_device (cpu); +if (!cpu_dev) +return -ENODEV ; + + np =of_node_get (cpu_dev->of_node); +if (!np) +return -EINVAL ; + +if (of_property_read_u32 (np,"dynamic-power-coefficient" , &cap)) +return -EINVAL ; + + Hz = *KHz *1000 ;
drivers/cpufreq/cpufreq-dt.c static int resources_available(void) · line 183
Quoted 10 lines
drivers/cpufreq/cpufreq-dt.c +10
-0+ opp =dev_pm_opp_find_freq_ceil (cpu_dev, &Hz); +if (IS_ERR (opp)) +return -EINVAL ; + + mV =dev_pm_opp_get_voltage (opp) /1000 ; +dev_pm_opp_put (opp); + + MHz = Hz /1000000 ; + tmp = (u64 )cap * mV * mV * MHz; +do_div (tmp,1000000000 );
Could you explain the formula above ? and especially the 1000000000 it seems related to the use of mV and mW instead of uV and uW ...
Can't you just optimize that into
tmp = (u64)cap * mV * mV * Hz;do_div(tmp, 1000);
Quoted 42 lines
drivers/cpufreq/cpufreq-dt.c +12
-2+ + *mW = (unsigned long )tmp; + *KHz = Hz /1000 ; + +return 0 ; +} +static int cpufreq_init (struct cpufreq_policy *policy) { +struct em_data_callback em_cb =EM_DATA_CB (of_est_power);struct cpufreq_frequency_table *freq_table;struct opp_table *opp_table =NULL ;struct private_data *priv;@@ -159,7 +199,7 @@ static int cpufreq_init(struct cpufreq_policy *policy)unsigned int transition_latency;bool fallback = false;const char *name; -int ret; +int ret, nr_opp; cpu_dev =get_cpu_device (policy->cpu);if (!cpu_dev) {@@ -226,6 +266,7 @@ static int cpufreq_init(struct cpufreq_policy *policy) ret = -EPROBE_DEFER ; goto out_free_opp; } + nr_opp = ret;if (fallback) {cpumask_setall (policy->cpus);@@ -278,6 +319,8 @@ static int cpufreq_init(struct cpufreq_policy *policy) policy->cpuinfo.transition_latency = transition_latency; policy->dvfs_possible_from_any_cpu = true; +em_register_freq_domain (policy->cpus, nr_opp, &em_cb); +return 0 ; out_free_cpufreq_table: --2.17.1
Re: [RFC PATCH v4 12/12] OPTIONAL: cpufreq: dt: Register an Energy Model
Quoted 27 lines · Vincent Guittot
Quoted 26 lines · Quentin Perret
drivers/cpufreq/cpufreq-dt.c +26
-0+static int of_est_power (unsigned long *mW,unsigned long *KHz,int cpu) +{ +unsigned long mV, Hz, MHz; +struct device *cpu_dev; +struct dev_pm_opp *opp; +struct device_node *np; +u32 cap; +u64 tmp; + + cpu_dev =get_cpu_device (cpu); +if (!cpu_dev) +return -ENODEV ; + + np =of_node_get (cpu_dev->of_node); +if (!np) +return -EINVAL ; + +if (of_property_read_u32 (np,"dynamic-power-coefficient" , &cap)) +return -EINVAL ; + + Hz = *KHz *1000 ; + opp =dev_pm_opp_find_freq_ceil (cpu_dev, &Hz); +if (IS_ERR (opp)) +return -EINVAL ; + + mV =dev_pm_opp_get_voltage (opp) /1000 ;
Quoted 8 lines
drivers/cpufreq/cpufreq-dt.c static int resources_available(void) · line 183
Quoted 5 lines
drivers/cpufreq/cpufreq-dt.c +5
-0+dev_pm_opp_put (opp); + + MHz = Hz /1000000 ; + tmp = (u64 )cap * mV * mV * MHz; +do_div (tmp,1000000000 );Could you explain the formula above ? and especially the 1000000000 it seems related to the use of mV and mW instead of uV and uW ...
That's correct, this is just a matter of units. I simply tried to reproduce here what is currently done for IPA:
https://elixir.bootlin.com/linux/latest/source/drivers/thermal/cpu_cooling.c#L252
Quoted 4 lines
Can't you just optimize that into
tmp = (u64)cap * mV * mV * Hz;do_div(tmp, 1000);
I don't think that'll work. If you use Hz instead of MHz you'll need to divide tmp by 1000000000000000 to get milli-watts, as specified by the EM framework.
FYI, I don't consider this patch to be ready to be merged. I kept it self-contained and simple for the example but I actually think that this of_est_power function should probably be factored-out somewhere else. scpi-cpufreq could use it as well. Anyway, I guess we can discuss that later once the APIs of the EM framework are agreed :-)
Thanks,
Quentin
Vincent Guittot
maintainerRe: [RFC PATCH v4 12/12] OPTIONAL: cpufreq: dt: Register an Energy Model
Hi Quentin,
I have noticed the new version but prefer to continue on this thread to keep the history of the discussion.
Quoted 38 lines · Quentin Perret
Quoted 27 lines · Vincent Guittot
Quoted 26 lines · Quentin Perret
drivers/cpufreq/cpufreq-dt.c +26
-0+static int of_est_power (unsigned long *mW,unsigned long *KHz,int cpu) +{ +unsigned long mV, Hz, MHz; +struct device *cpu_dev; +struct dev_pm_opp *opp; +struct device_node *np; +u32 cap; +u64 tmp; + + cpu_dev =get_cpu_device (cpu); +if (!cpu_dev) +return -ENODEV ; + + np =of_node_get (cpu_dev->of_node); +if (!np) +return -EINVAL ; + +if (of_property_read_u32 (np,"dynamic-power-coefficient" , &cap)) +return -EINVAL ; + + Hz = *KHz *1000 ; + opp =dev_pm_opp_find_freq_ceil (cpu_dev, &Hz); +if (IS_ERR (opp)) +return -EINVAL ; + + mV =dev_pm_opp_get_voltage (opp) /1000 ;Quoted 8 lines
drivers/cpufreq/cpufreq-dt.c static int resources_available(void) · line 183
Quoted 5 lines
drivers/cpufreq/cpufreq-dt.c +5
-0+dev_pm_opp_put (opp); + + MHz = Hz /1000000 ; + tmp = (u64 )cap * mV * mV * MHz; +do_div (tmp,1000000000 );Could you explain the formula above ? and especially the 1000000000 it seems related to the use of mV and mW instead of uV and uW ...
Quoted 4 lines
That's correct, this is just a matter of units. I simply tried to reproduce here what is currently done for IPA:
https://elixir.bootlin.com/linux/latest/source/drivers/thermal/cpu_cooling.c#L252
ok, so you copy/paste what is done in cpu cooling device ?
Nevertheless I still have some concerns with the formula used here and in cpu cooling device:
https://elixir.bootlin.com/linux/latest/source/Documentation/devicetree/bindings/arm/cpus.txt#L273
The documentation says
Pdyn = dynamic-power-coefficient * V^2 * f where voltage is in uV, frequency is in MHz.
and dynamic power coefficient in units of mW/MHz/uV^2.
This implies that the results is in mW and we can summarize the formula with :
mW = C * (uV)^2 * Mhz with C = dynamic-power-coefficient then uV = 1000*mV
mW = C * (1000*mV)^2 * Mhz
mW = C * 1000000 * mV * mV * Mhz
Which is different from what is used here and in cpu cooling device. I may have done something wrong with the formula but i can't catch it... My brain is not yet fully back from vacations
Mhz = Hz / 1000000
mW = C * mV * mV * 1000000 * Hz / 1000000
mW = C * mV * mV * Hz
Let take a simple example with
C = 1
Voltage = 1000 uV = 1 mV
freq = 2 Mhz = 2000000 Hz
mW = C * (uV)^2 * Mhz = 1 * (1000)^2 * 2 = 2000000
mW = C * mV * mV * Hz = 1 * 1 * 1 * 2000000 = 2000000
mW = C * mV * mV * MHz / 1000000000 = 1 * 1 * 1 * 2 / 1000000000 = 0
so there is a mismatch between the formula in the documentation and the formula used in cpu_cooling.c (and in this patch).
That being said, I can understand that we can easily overflow the result if we use some kind of realistic values like the one for hikey960:
dynamic-power-coefficient for cpu4 is : 550
for highest OPP of cpu4:
opp-hz = /bits/ 64 <2362000000>;
opp-microvolt = <1100000>;
Which gives with the formula in the documentation:
mW = 550 * (1100000)^2 * 2362 = 1,571911×10^18 which is quite huge even for a big core running at max freq
and with the formula in cpu_cooling.c:
mW = 550 * 1100 * 1100 * 2362 / 1000000000 = 1571 which seems to be a bit more reasonable
So it seems that the dynamic-power-coefficient unit is not mW/MHz/uV^2 but mW/Ghz/V^2
And given that we use integer, we provide Voltage and frequency by (mV/1000) and (Mhz/1000) and factorize all /1000
May be Javi who added the formula for cpu cooling can confirm on this ?
Quoted 5 lines
Quoted 5 lines
Can't you just optimize that into
tmp = (u64)cap * mV * mV * Hz;do_div(tmp, 1000);
In fact the do_div is not needed, I thought that dyn coef unit was uW/Mhz/uV^2 whereas it's written mW/MHz/uV^2
Quoted 10 lines
I don't think that'll work. If you use Hz instead of MHz you'll need to divide tmp by 1000000000000000 to get milli-watts, as specified by the EM framework.
FYI, I don't consider this patch to be ready to be merged. I kept it self-contained and simple for the example but I actually think that this
of_est_powerfunction should probably be factored-out somewhere else. scpi-cpufreq could use it as well. Anyway, I guess we can discuss that later once the APIs of the EM framework are agreed :-)
It's just that the tests results that you provided in the cover letter has used this patch and running tests with wrong formula (it seems that's the documentation is wrong) doesn't give much confidence on the results
Thanks
Vincent
Quoted 3 lines
Thanks,
Quentin
Re: [RFC PATCH v4 12/12] OPTIONAL: cpufreq: dt: Register an Energy Model
Hi Vincent,
On Monday 30 Jul 2018 at 17:53:23 (+0200), Vincent Guittot wrote:
[...]
Quoted 13 lines
ok, so you copy/paste what is done in cpu cooling device ?
Nevertheless I still have some concerns with the formula used here and in cpu cooling device:
https://elixir.bootlin.com/linux/latest/source/Documentation/devicetree/bindings/arm/cpus.txt#L273
The documentation says
Pdyn = dynamic-power-coefficient * V^2 * f where voltage is in uV, frequency is in MHz.
and dynamic power coefficient in units of mW/MHz/uV^2.This implies that the results is in mW and we can summarize the formula with :
Quoted 8 lines
mW = C * (uV)^2 * Mhz with C = dynamic-power-coefficient then uV = 1000*mV
mW = C * (1000*mV)^2 * Mhz
mW = C * 1000000 * mV * mV * MhzWhich is different from what is used here and in cpu cooling device. I may have done something wrong with the formula but i can't catch it... My brain is not yet fully back from vacations
I think your brain works fine ;) The doc does seem to be incorrect ... I also believe that this issue has been discussed recently in another thread:
http://archive.armlinux.org.uk/lurker/message/20180720.141530.2bf75d5c.en.html
Quoted 6 lines
Which gives with the formula in the documentation:
mW = 550 * (1100000)^2 * 2362 = 1,571911×10^18 which is quite huge even for a big core running at max freq
and with the formula incpu_cooling.c:
mW = 550 * 1100 * 1100 * 2362 / 1000000000 = 1571 which seems to be a bit more reasonable
Indeed, 1.5W for a big CPU at max OPP is in the right ballpark I believe.
FYI, this is the power values I have in the EM for all OPPs on H960:
+--------+-------+--------+--------+
| A53s | A73s |
+--------+-------+--------+--------+
| MHz | mW | MHz | mW |
+--------+-------+--------+--------+
| 533 | 28 | 903 | 243 |
| 999 | 70 | 1421 | 500 |
| 1402 | 124 | 1805 | 804 |
| 1709 | 187 | 2112 | 1161 |
| 1844 | 245 | 2362 | 1571 |
+--------+-------+--------+--------+[...]
Quoted 4 lines
It's just that the tests results that you provided in the cover letter has used this patch and running tests with wrong formula (it seems that's the documentation is wrong) doesn't give much confidence on the results
I can understand that the mismatch between the code and the documentation can be slightly confusing. However, as you said yourself the code _is_ correct, so the test results are valid.
Moreover, the actual unit for the power costs doesn't make any difference with EAS as long as that doesn't cause precision issues. EAS works in relative terms, so even if the unit was in, say, uW instead of mW, the test results would still be valid. And again, that's not the case, the code does the right thing here.
Thanks,
Quentin