scheduler-based cpu frequency scaling

This policy is implemented using the cpufreq governor interface for two main reasons:

1) re-using the cpufreq machine drivers without using the governor interface is hard.

2) using the cpufreq interface allows us to switch between the scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Quoted 6 lines · Michael Turquette

This policy is implemented using the cpufreq governor interface for two main reasons:

1) re-using the cpufreq machine drivers without using the governor interface is hard.

Quoted 3 lines

2) using the cpufreq interface allows us to switch between the scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Urgh,. so I don't really like that. It adds a lot of noise to the system. You do the irq work thing to kick the cpufreq threads which do their little thing -- and their wakeup will influence the cfs accounting, which in turn will start the whole thing anew.

I would really prefer you did a whole new system with directly invoked drivers that avoid the silly dance. Your 'new' ARM systems should be well capable of that.

From what I can tell, this "non-cpufreq" new system will probably have

You can still do 2 if you create a cpufreq off switch. You can then either enable the sched one or the legacy cpufreq -- or both if you want a trainwreck ;-)

As to the drivers, they're mostly fairly small and self contained, it should not be too hard to hack them up to work without cpufreq.

Quoting Peter Zijlstra (2015-05-05 02:00:42)

Quoted 16 lines · Michael Turquette

Quoted 9 lines

This policy is implemented using the cpufreq governor interface for two main reasons:

1) re-using the cpufreq machine drivers without using the governor interface is hard.

2) using the cpufreq interface allows us to switch between the scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Urgh,. so I don't really like that. It adds a lot of noise to the system. You do the irq work thing to kick the cpufreq threads which do their little thing -- and their wakeup will influence the cfs accounting, which in turn will start the whole thing anew.

Quoted 3 lines

I would really prefer you did a whole new system with directly invoked drivers that avoid the silly dance. Your 'new' ARM systems should be well capable of that.

Thanks for the review Peter.

We'll need something in process context for the many cpufreq drivers that might sleep during their cpu frequency transition, no? This is due to calls into the regulator framework, the clock framework and sometimes other things such as conversing with a power management IC or voting with some system controller.

Quoted 2 lines

As to the drivers, they're mostly fairly small and self contained, it should not be too hard to hack them up to work without cpufreq.

The drivers are not the only thing. I want to leverage the existing cpufreq core infrastructure:

* rate change notifiers
* cpu hotplug awareness
* methods to fetch frequency tables from firmware (acpi, devicetree)
* other stuff I can't think of now

So I do not think we should throw out the baby with the bath water. The thing that people really don't like about cpufreq are the governors IMO. Let's fix that by creating a list of requirements that we really want for scheduler-driven cpu frequency selection:

0) do something smart with scheduler statistics to create an improved frequency selection algorithm over existing cpufreq governors

1) support upcoming and legacy hardware, within reason

2) if a system exports a fast, async frequency selection interface to Linux, then provide a solution that doesn't do any irq_work or kthread stuff. Do it all in the fast path

3) if a system has a slow, synchronous interface for frequency selection, then provide an acceptable solution for kicking this work to process context. Limit time in the fast path

The patch set tries to tackle 0, 1 and 3. Would the inclusion of #2 make you feel better about supporting "newer" hardware with a fire-and-forget frequency selection interface?

Are you thinking of placing the hook somewhere such as update_entity_load_avg?

Quoting Peter Zijlstra (2015-05-06 05:22:40)

Quoted 18 lines · Michael Turquette

Quoted 17 lines

Quoting Peter Zijlstra (2015-05-05 02:00:42)

Quoted 16 lines · Michael Turquette

Quoted 9 lines

This policy is implemented using the cpufreq governor interface for two main reasons:

1) re-using the cpufreq machine drivers without using the governor interface is hard.

2) using the cpufreq interface allows us to switch between the scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Urgh,. so I don't really like that. It adds a lot of noise to the system. You do the irq work thing to kick the cpufreq threads which do their little thing -- and their wakeup will influence the cfs accounting, which in turn will start the whole thing anew.

Quoted 8 lines

Quoted 5 lines

Quoted 3 lines

I would really prefer you did a whole new system with directly invoked drivers that avoid the silly dance. Your 'new' ARM systems should be well capable of that.

Thanks for the review Peter.

Well, I didn't actually get beyond the Changelog; although I have rectified this now. A few more comments below.

Thanks for the Real Deal review Peter.

Quoted 44 lines

Quoted 6 lines

We'll need something in process context for the many cpufreq drivers that might sleep during their cpu frequency transition, no? This is due to calls into the regulator framework, the clock framework and sometimes other things such as conversing with a power management IC or voting with some system controller.

Yes, we need _something_. I just spoke to a bunch of people on IRC and it does indeed seem that I was mistaken in my assumption that modern ARM systems were 'easy' in this regard.

Quoted 25 lines

Quoted 2 lines

As to the drivers, they're mostly fairly small and self contained, it should not be too hard to hack them up to work without cpufreq.

The drivers are not the only thing. I want to leverage the existing cpufreq core infrastructure:

* rate change notifiers
* cpu hotplug awareness
* methods to fetch frequency tables from firmware (acpi, devicetree)
* other stuff I can't think of now

So I do not think we should throw out the baby with the bath water. The thing that people really don't like about cpufreq are the governors IMO. Let's fix that by creating a list of requirements that we really want for scheduler-driven cpu frequency selection:

0) do something smart with scheduler statistics to create an improved frequency selection algorithm over existing cpufreq governors

1) support upcoming and legacy hardware, within reason

2) if a system exports a fast, async frequency selection interface to Linux, then provide a solution that doesn't do any irq_work or kthread stuff. Do it all in the fast path

Quoted 7 lines

3) if a system has a slow, synchronous interface for frequency selection, then provide an acceptable solution for kicking this work to process context. Limit time in the fast path

The patch set tries to tackle 0, 1 and 3. Would the inclusion of #2 make you feel better about supporting "newer" hardware with a fire-and-forget frequency selection interface?

Quoted 8 lines

I should probably look at doing a x86 support patch to try some of this out, I'll try and find some time to play with that.

So two comments on the actual code:

1) Ideally these hooks would be called from places where we've just computed the cpu utilization already. I understand this is currently not the case and we need to do it in-situ.

Are you thinking of placing the hook somewhere such as update_entity_load_avg?

I did not choose that as a call site since I was worried that it would be too noisy; we can enter that function multiple times in the same pass through the scheduler.

On the other hand if dvfs transitions are cheap for a platform then it might not be so bad to call it multiple times. For platforms where dvfs transitions are expensive we could store per-cpu new_capacity data multiple times and make sure that we only try to program the hardware as deferred work later on.

Quoted 4 lines

That said; it would be good to have the interface such that we pass the utilization in; this would of course mean we'd have to compute it at the call sites, this should be fine I think.

I changed the code to do this but didn't have time to test it. Will send the patch with these changes tomorrow.

Quoted 2 lines

Quoted 1 line

2) I dislike how policy->cpus is handled; it feels upside down.

I agree. It feels better to push the utilization from cfs instead of pull it from the frequency selection policy.

I chose to do it this way since there isn't an obvious way to pass some private data to an irq_work callback, but I've overcome this with some per-cpu data internal to the governor.

Quoted 8 lines

If per 1 each CPU already computed its utilization and provides it in the call, we should not have to recompute it and its scale factor (which btw seems done slightly odd too, I know humans like 10 base, but computers suck at it).

Why not something like:

        usage = ((1024 + 256) * usage) >> 10; /* +25% */

This works when the max capacity is always 1024, but that is not always the case for some new ARM systems. For cpu's whose max capacity is less than 1024 we would still need to normalize against capacity_orig_of().

Doing the SCHED_LOAD_SCALE thing is fine for me now, but at some point it will probably need to be changed by Morten/Juri/Dietmar for their EAS patch series, which deals with some of these cpu capacity scale issues.

Quoted 11 lines

        old_usage = __this_cpu_read(gd->usage);
        __this_cpu_write(gd->usage, usage);

        max_usage = 0;
        for_each_cpu(cpu, policy->cpus)
                max_usage = max(max_usage, per_cpu(gd->usage, cpu));

        if (max_usage < old_usage || /* dropped */
            (max_usage == usage && max_usage != old_usage)) /* raised */
                request_change(max_usage);

Yes this should work fine. I've pulled it into the patch that I'll test and publish tomorrow.

Thanks,
Mike

Quoted 2 lines

Hi Mike,

Quoted 111 lines · Michael Turquette

Quoting Peter Zijlstra (2015-05-06 05:22:40)

Quoted 18 lines · Michael Turquette

Quoted 17 lines

Quoting Peter Zijlstra (2015-05-05 02:00:42)

Quoted 16 lines · Michael Turquette

Quoted 9 lines

This policy is implemented using the cpufreq governor interface for two main reasons:

1) re-using the cpufreq machine drivers without using the governor interface is hard.

2) using the cpufreq interface allows us to switch between the scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Urgh,. so I don't really like that. It adds a lot of noise to the system. You do the irq work thing to kick the cpufreq threads which do their little thing -- and their wakeup will influence the cfs accounting, which in turn will start the whole thing anew.

Quoted 8 lines

Quoted 5 lines

Quoted 3 lines

I would really prefer you did a whole new system with directly invoked drivers that avoid the silly dance. Your 'new' ARM systems should be well capable of that.

Thanks for the review Peter.

Well, I didn't actually get beyond the Changelog; although I have rectified this now. A few more comments below.

Thanks for the Real Deal review Peter.

Quoted 44 lines

Quoted 6 lines

We'll need something in process context for the many cpufreq drivers that might sleep during their cpu frequency transition, no? This is due to calls into the regulator framework, the clock framework and sometimes other things such as conversing with a power management IC or voting with some system controller.

Yes, we need _something_. I just spoke to a bunch of people on IRC and it does indeed seem that I was mistaken in my assumption that modern ARM systems were 'easy' in this regard.

Quoted 25 lines

Quoted 2 lines

As to the drivers, they're mostly fairly small and self contained, it should not be too hard to hack them up to work without cpufreq.

The drivers are not the only thing. I want to leverage the existing cpufreq core infrastructure:

* rate change notifiers
* cpu hotplug awareness
* methods to fetch frequency tables from firmware (acpi, devicetree)
* other stuff I can't think of now

So I do not think we should throw out the baby with the bath water. The thing that people really don't like about cpufreq are the governors IMO. Let's fix that by creating a list of requirements that we really want for scheduler-driven cpu frequency selection:

0) do something smart with scheduler statistics to create an improved frequency selection algorithm over existing cpufreq governors

1) support upcoming and legacy hardware, within reason

2) if a system exports a fast, async frequency selection interface to Linux, then provide a solution that doesn't do any irq_work or kthread stuff. Do it all in the fast path

Quoted 7 lines

3) if a system has a slow, synchronous interface for frequency selection, then provide an acceptable solution for kicking this work to process context. Limit time in the fast path

The patch set tries to tackle 0, 1 and 3. Would the inclusion of #2 make you feel better about supporting "newer" hardware with a fire-and-forget frequency selection interface?

Quoted 8 lines

I should probably look at doing a x86 support patch to try some of this out, I'll try and find some time to play with that.

So two comments on the actual code:

1) Ideally these hooks would be called from places where we've just computed the cpu utilization already. I understand this is currently not the case and we need to do it in-situ.

Are you thinking of placing the hook somewhere such as update_entity_load_avg?

I did not choose that as a call site since I was worried that it would be too noisy; we can enter that function multiple times in the same pass through the scheduler.

On the other hand if dvfs transitions are cheap for a platform then it might not be so bad to call it multiple times. For platforms where dvfs transitions are expensive we could store per-cpu new_capacity data multiple times and make sure that we only try to program the hardware as deferred work later on.

Quoted 4 lines

That said; it would be good to have the interface such that we pass the utilization in; this would of course mean we'd have to compute it at the call sites, this should be fine I think.

I changed the code to do this but didn't have time to test it. Will send the patch with these changes tomorrow.

Quoted 3 lines

2) I dislike how policy->cpus is handled; it feels upside down.

I agree. It feels better to push the utilization from cfs instead of pull it from the frequency selection policy.

Quoted 4 lines

I chose to do it this way since there isn't an obvious way to pass some private data to an irq_work callback, but I've overcome this with some per-cpu data internal to the governor.

This new interface looks like what I was also proposing in the discussion we had [1], are you going to send out something along this line?

I think it would be good to have something like that. As Peter is saying, together with Morten's/Dietmar's series, we could try to do wiser decisions on when to trigger the whole machinery.

Thanks,

- Juri

[1] https://lists.linaro.org/pipermail/eas-dev/2015-April/000129.html

Quoted 38 lines

Quoted 8 lines

If per 1 each CPU already computed its utilization and provides it in the call, we should not have to recompute it and its scale factor (which btw seems done slightly odd too, I know humans like 10 base, but computers suck at it).

Why not something like:

        usage = ((1024 + 256) * usage) >> 10; /* +25% */

This works when the max capacity is always 1024, but that is not always the case for some new ARM systems. For cpu's whose max capacity is less than 1024 we would still need to normalize against capacity_orig_of().

Doing the SCHED_LOAD_SCALE thing is fine for me now, but at some point it will probably need to be changed by Morten/Juri/Dietmar for their EAS patch series, which deals with some of these cpu capacity scale issues.

Quoted 11 lines

        old_usage = __this_cpu_read(gd->usage);
        __this_cpu_write(gd->usage, usage);

        max_usage = 0;
        for_each_cpu(cpu, policy->cpus)
                max_usage = max(max_usage, per_cpu(gd->usage, cpu));

        if (max_usage < old_usage || /* dropped */
            (max_usage == usage && max_usage != old_usage)) /* raised */
                request_change(max_usage);

Yes this should work fine. I've pulled it into the patch that I'll test and publish tomorrow.

Thanks,
Mike

Quoted 2 lines

For those that are very curious, there were recently two previous postings of these patches to the public eas-dev mailing list. Of interest in those threads is the discussion around using a utilization threadhold versus purely matching frequency to capacity utilization versus using a margin (as this series does):

https://lists.linaro.org/pipermail/eas-dev/2015-April/000074.html
https://lists.linaro.org/pipermail/eas-dev/2015-April/000115.html

This series implements an event-driven cpufreq governor that scales cpu frequency as a function of cfs runqueue utilization. The intent of this RFC is to get some discussion going about how the scheduler can become the policy engine for selecting cpu frequency, what limitations exist and what design do we want to take to get to a solution.

This work is a different take on the patches I posted in November:
http://lkml.kernel.org/r/<[email protected]>

This series depends on having frequency-invariant representations for load. This requires Vincent's recently merged cpu capacity rework patches, as well as a new patch from Morten included here. Morten's patch will likely make an appearance in his energy aware scheduling v4 series.

Thanks to Juri Lelli <[email protected]> for contributing to the development of the governor.

A git branch with these patches can be pulled from here:
https://git.linaro.org/people/mike.turquette/linux.git sched-freq

Smoke testing has been done on an OMAP4 Pandaboard and an Exynos 5800 Chromebook2. Extensive benchmarking and regression testing has not yet been done. Before sinking too much time into extensive testing I'd like to get feedback on the general design.

Michael Turquette (3):
sched: sched feature for cpu frequency selection
sched: export get_cpu_usage & capacity_orig_of
sched: cpufreq_sched_cfs: PELT-based cpu frequency scaling

Morten Rasmussen (1):
arm: Frequency invariant scheduler load-tracking support

 arch/arm/include/asm/topology.h |   7 +
 arch/arm/kernel/smp.c           |  53 ++++++-
 arch/arm/kernel/topology.c      |  17 +++
 drivers/cpufreq/Kconfig         |  24 ++++
 include/linux/cpufreq.h         |   3 +
 kernel/sched/Makefile           |   1 +
 kernel/sched/cpufreq_cfs.c      | 311 ++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c             |  48 +++----
 kernel/sched/features.h         |   6 +
 kernel/sched/sched.h            |  39 +++++
 10 files changed, 475 insertions(+), 34 deletions(-)
 create mode 100644 kernel/sched/cpufreq_cfs.c

Quoted 33 lines · Michael Turquette

This series implements an event-driven cpufreq governor that scales cpu frequency as a function of cfs runqueue utilization. The intent of this RFC is to get some discussion going about how the scheduler can become the policy engine for selecting cpu frequency, what limitations exist and what design do we want to take to get to a solution.

This work is a different take on the patches I posted in November:
http://lkml.kernel.org/r/<[email protected]>

This series depends on having frequency-invariant representations for load. This requires Vincent's recently merged cpu capacity rework patches, as well as a new patch from Morten included here. Morten's patch will likely make an appearance in his energy aware scheduling v4 series.

Thanks to Juri Lelli <[email protected]> for contributing to the development of the governor.

A git branch with these patches can be pulled from here:
https://git.linaro.org/people/mike.turquette/linux.git sched-freq

Smoke testing has been done on an OMAP4 Pandaboard and an Exynos 5800 Chromebook2. Extensive benchmarking and regression testing has not yet been done. Before sinking too much time into extensive testing I'd like to get feedback on the general design.

Michael Turquette (3):
sched: sched feature for cpu frequency selection
sched: export get_cpu_usage & capacity_orig_of
sched: cpufreq_sched_cfs: PELT-based cpu frequency scaling

Morten Rasmussen (1):
arm: Frequency invariant scheduler load-tracking support

Quoted 12 lines

 arch/arm/include/asm/topology.h |   7 +
 arch/arm/kernel/smp.c           |  53 ++++++-
 arch/arm/kernel/topology.c      |  17 +++
 drivers/cpufreq/Kconfig         |  24 ++++
 include/linux/cpufreq.h         |   3 +
 kernel/sched/Makefile           |   1 +
 kernel/sched/cpufreq_cfs.c      | 311 ++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c             |  48 +++----
 kernel/sched/features.h         |   6 +
 kernel/sched/sched.h            |  39 +++++
 10 files changed, 475 insertions(+), 34 deletions(-)
 create mode 100644 kernel/sched/cpufreq_cfs.c

Can you *please* always CC PM-related patches to linux-pm?

--
I speak only for myself.
Rafael J. Wysocki, Intel Open Source Technology Center.

If CONFIG_SMP is not defined the build will fail due to function 'gov_cfs_update_cpu' definition missing. Added empty static inline definition for NON-SMP systems.

This patch applies to:
https://git.linaro.org/people/mike.turquette/linux.git sched-freq

Signed-off-by Abel Vesa <[email protected]>

---
 kernel/sched/sched.h | 1 +
 1 file changed, 1 insertion(+)

kernel/sched/sched.h +1 -0

index ec23523..3d0996e 100644
@@ -1413,6 +1413,7 @@ static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
 #else
 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { }
 static inline void sched_avg_update(struct rq *rq) { }
+static inline void gov_cfs_update_cpu(int cpu) {}
 #endif
 
 extern void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period);

Signature · 1 line

1.9.1