Skip to contentSkip to conversation

sched: fair: Use the earliest break even

PATCH In review Daniel Lezcano 4 participants 19 messages Mar 11, 2020 – Mar 18, 2020 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 sched: fair: Use the earliest break even

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th	|      14844.8    |         15017.6    |
| adrestia / periodic	|        57.95    |              57    |
| adrestia / single	|         49.3    |            55.4    |
 --------------------------------------------------------------
| Hikey960              | With break even | Without break even |
 --------------------------------------------------------------
| schbench *99.0th	|      56140.8    |           56256    |
| schbench energy	|      153.575    |         152.676    |
| adrestia / periodic	|         4.98    |             5.2    |
| adrestia / single	|         9.02    |            9.12    |
| adrestia energy	|         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
 	unsigned long load, min_load = ULONG_MAX;
 	unsigned int min_exit_latency = UINT_MAX;
+	s64 min_break_even = S64_MAX;
 	u64 latest_idle_timestamp = 0;
 	int least_loaded_cpu = this_cpu;
 	int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 		if (available_idle_cpu(i)) {
 			struct rq *rq = cpu_rq(i);
 			struct cpuidle_state *idle = idle_get_state(rq);
+			s64 break_even = idle_get_break_even(rq);
+
 			if (idle && idle->exit_latency < min_exit_latency) {
 				/*
 				 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 				 * of any idle timestamp.
 				 */
 				min_exit_latency = idle->exit_latency;
+				min_break_even = break_even;
 				latest_idle_timestamp = rq->idle_stamp;
 				shallowest_idle_cpu = i;
-			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
-				   rq->idle_stamp > latest_idle_timestamp) {
+			} else if ((idle && idle->exit_latency == min_exit_latency) &&
+				   break_even < min_break_even) {
+				/*
+				 * We give priority to the shallowest
+				 * idle states with the minimal break
+				 * even deadline to decrease the
+				 * probability to choose a CPU which
+				 * did not reach its break even yet
+				 */
+				min_break_even = break_even;
+				shallowest_idle_cpu = i;
+			} else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
 				/*
 				 * If equal or no active idle state, then
 				 * the most recently idled CPU might have
kernel/sched/idle.c +7 -1
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
-	idle_set_state(this_rq(), idle_state);
+	struct rq *rq = this_rq();
+
+	idle_set_state(rq, idle_state);
+
+	if (idle_state)
+		idle_set_break_even(rq, ktime_get_ns() +
+				    idle_state->exit_latency_ns);
 }
 
 static int __read_mostly cpu_idle_force_poll;
kernel/sched/sched.h +20 -0
index 2a0caf394dd4..eef1e535e2c2 100644
@@ -1015,6 +1015,7 @@ struct rq {
 #ifdef CONFIG_CPU_IDLE
 	/* Must be inspected within a rcu lock section */
 	struct cpuidle_state	*idle_state;
+	s64			break_even;
 #endif
 };
 
@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)
 
 	return rq->idle_state;
 }
+
+static inline void idle_set_break_even(struct rq *rq, s64 break_even)
+{
+	WRITE_ONCE(rq->break_even, break_even);
+}
+
+static inline s64 idle_get_break_even(struct rq *rq)
+{
+	return READ_ONCE(rq->break_even);
+}
 #else
 static inline void idle_set_state(struct rq *rq,
 				  struct cpuidle_state *idle_state)
@@ -1860,6 +1871,15 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)
 {
 	return NULL;
 }
+
+static inline void idle_set_break_even(struct rq *rq, s64 break_even)
+{
+}
+
+static inline s64 idle_get_break_even(struct rq *rq)
+{
+	return 0;
+}
 #endif
 
 extern void schedule_idle(void);
Signature · 1 line
2.17.1
maintainer
#1 lore raw

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

Quoted 25 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

Quoted 7 lines

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Have you got some figures or cpuidle statistics for the syncquacer ?

Quoted 68 lines

| Hikey960 | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      56140.8    |           56256    |
| schbench energy       |      153.575    |         152.676    |
| adrestia / periodic   |         4.98    |             5.2    |
| adrestia / single     |         9.02    |            9.12    |
| adrestia energy       |         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
+       s64 min_break_even = S64_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                if (available_idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
+                       s64 break_even = idle_get_break_even(rq);
+
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
+                               min_break_even = break_even;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
-                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
-                                  rq->idle_stamp > latest_idle_timestamp) {
+                       } else if ((idle && idle->exit_latency == min_exit_latency) &&
+                                  break_even < min_break_even) {
+                               /*
+                                * We give priority to the shallowest
+                                * idle states with the minimal break
+                                * even deadline to decrease the
+                                * probability to choose a CPU which
+                                * did not reach its break even yet
+                                */
+                               min_break_even = break_even;
+                               shallowest_idle_cpu = i;
+                       } else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 24

Quoted 7 lines
kernel/sched/idle.c +3 -1
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
-       idle_set_state(this_rq(), idle_state);
+       struct rq *rq = this_rq();
+
+       idle_set_state(rq, idle_state);

Shouldn't the state be set after setting break even otherwise you will have a time window with an idle_state != null but the break_even still set to the previous value

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 3 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Quoted 52 lines
kernel/sched/idle.c +1 -0
+                                   idle_state->exit_latency_ns);
 }
 
 static int __read_mostly cpu_idle_force_poll;
kernel/sched/sched.h +20 -1
index 2a0caf394dd4..eef1e535e2c2 100644
@@ -1015,6 +1015,7 @@ struct rq {
 #ifdef CONFIG_CPU_IDLE
        /* Must be inspected within a rcu lock section */
        struct cpuidle_state    *idle_state;
+       s64                     break_even;
 #endif
 };
 
@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)
 
        return rq->idle_state;
 }
+
+static inline void idle_set_break_even(struct rq *rq, s64 break_even)
+{
+       WRITE_ONCE(rq->break_even, break_even);
+}
+
+static inline s64 idle_get_break_even(struct rq *rq)
+{
+       return READ_ONCE(rq->break_even);
+}
 #else
 static inline void idle_set_state(struct rq *rq,
                                  struct cpuidle_state *idle_state)
@@ -1860,6 +1871,15 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)
 {
        return NULL;
 }
+
+static inline void idle_set_break_even(struct rq *rq, s64 break_even)
+{
+}
+
+static inline s64 idle_get_break_even(struct rq *rq)
+{
+       return 0;
+}
 #endif
 
 extern void schedule_idle(void);
--

2.17.1

#2 lore raw
Quoted 11 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Quoted 32 lines
Quoted 24 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

Quoted 7 lines

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

Quoted 71 lines
Quoted 71 lines

| Hikey960 | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      56140.8    |           56256    |
| schbench energy       |      153.575    |         152.676    |
| adrestia / periodic   |         4.98    |             5.2    |
| adrestia / single     |         9.02    |            9.12    |
| adrestia energy       |         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
+       s64 min_break_even = S64_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                if (available_idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
+                       s64 break_even = idle_get_break_even(rq);
+
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
+                               min_break_even = break_even;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
-                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
-                                  rq->idle_stamp > latest_idle_timestamp) {
+                       } else if ((idle && idle->exit_latency == min_exit_latency) &&
+                                  break_even < min_break_even) {
+                               /*
+                                * We give priority to the shallowest
+                                * idle states with the minimal break
+                                * even deadline to decrease the
+                                * probability to choose a CPU which
+                                * did not reach its break even yet
+                                */
+                               min_break_even = break_even;
+                               shallowest_idle_cpu = i;
+                       } else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
Quoted 8 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 24

Quoted 4 lines
kernel/sched/idle.c +3 -1
-       idle_set_state(this_rq(), idle_state);
+       struct rq *rq = this_rq();
+
+       idle_set_state(rq, idle_state);

Shouldn't the state be set after setting break even otherwise you will have a time window with an idle_state != null but the break_even still set to the previous value

IIUC we are protected in this section. Otherwise the routine above would be also wrong [if (idle && idle->exit_latency)], no?

Quoted 6 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 3 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Quoted 2 lines
Quoted 2 lines
kernel/sched/idle.c +1 -0
+                                   idle_state->exit_latency_ns);
 }

[ ... ]

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
maintainer
#3 lore raw
Quoted 135 lines · Daniel Lezcano
Quoted 11 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Quoted 32 lines
Quoted 24 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

Quoted 7 lines

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

Quoted 71 lines
Quoted 71 lines

| Hikey960 | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      56140.8    |           56256    |
| schbench energy       |      153.575    |         152.676    |
| adrestia / periodic   |         4.98    |             5.2    |
| adrestia / single     |         9.02    |            9.12    |
| adrestia energy       |         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
+       s64 min_break_even = S64_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                if (available_idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
+                       s64 break_even = idle_get_break_even(rq);
+
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
+                               min_break_even = break_even;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
-                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
-                                  rq->idle_stamp > latest_idle_timestamp) {
+                       } else if ((idle && idle->exit_latency == min_exit_latency) &&
+                                  break_even < min_break_even) {
+                               /*
+                                * We give priority to the shallowest
+                                * idle states with the minimal break
+                                * even deadline to decrease the
+                                * probability to choose a CPU which
+                                * did not reach its break even yet
+                                */
+                               min_break_even = break_even;
+                               shallowest_idle_cpu = i;
+                       } else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
Quoted 8 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 24

Quoted 4 lines
kernel/sched/idle.c +3 -1
-       idle_set_state(this_rq(), idle_state);
+       struct rq *rq = this_rq();
+
+       idle_set_state(rq, idle_state);

Shouldn't the state be set after setting break even otherwise you will have a time window with an idle_state != null but the break_even still set to the previous value

Quoted 2 lines

IIUC we are protected in this section. Otherwise the routine above would be also wrong [if (idle && idle->exit_latency)], no?

no there are not the same because it uses the idle pointer to read exit_latency so we are sure to use exit_latency related to the idle pointer.

In your case it checks idle is not null but then it uses rq to read break_even but it might not have been already updated

Quoted 10 lines
Quoted 7 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 4 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Using local_clock() would be more latency friendly

Quoted 14 lines
Quoted 3 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 29

Quoted 3 lines
kernel/sched/idle.c +1 -0
+                                   idle_state->exit_latency_ns);
 }

[ ... ]

--
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

#4 lore raw
Quoted 139 lines · Vincent Guittot
Quoted 135 lines · Daniel Lezcano
Quoted 11 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Quoted 32 lines
Quoted 24 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

Quoted 7 lines

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

Quoted 71 lines
Quoted 71 lines

| Hikey960 | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      56140.8    |           56256    |
| schbench energy       |      153.575    |         152.676    |
| adrestia / periodic   |         4.98    |             5.2    |
| adrestia / single     |         9.02    |            9.12    |
| adrestia energy       |         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
+       s64 min_break_even = S64_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                if (available_idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
+                       s64 break_even = idle_get_break_even(rq);
+
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
+                               min_break_even = break_even;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
-                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
-                                  rq->idle_stamp > latest_idle_timestamp) {
+                       } else if ((idle && idle->exit_latency == min_exit_latency) &&
+                                  break_even < min_break_even) {
+                               /*
+                                * We give priority to the shallowest
+                                * idle states with the minimal break
+                                * even deadline to decrease the
+                                * probability to choose a CPU which
+                                * did not reach its break even yet
+                                */
+                               min_break_even = break_even;
+                               shallowest_idle_cpu = i;
+                       } else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
Quoted 8 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 24

Quoted 4 lines
kernel/sched/idle.c +3 -1
-       idle_set_state(this_rq(), idle_state);
+       struct rq *rq = this_rq();
+
+       idle_set_state(rq, idle_state);

Shouldn't the state be set after setting break even otherwise you will have a time window with an idle_state != null but the break_even still set to the previous value

Quoted 2 lines

IIUC we are protected in this section. Otherwise the routine above would be also wrong [if (idle && idle->exit_latency)], no?

Quoted 6 lines

no there are not the same because it uses the idle pointer to read exit_latency so we are sure to use exit_latency related to the idle pointer.

In your case it checks idle is not null but then it uses rq to read break_even but it might not have been already updated

Ok I will invert the lines.

Quoted 11 lines
Quoted 9 lines
Quoted 6 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 3 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Using local_clock() would be more latency friendly

Unfortunately we are comparing the deadline across CPUs, so the local_clock() can not be used here.

But if we have one ktime_get() instead of a local_clock() + ktime_get(), that should be fine, no?

Quoted 13 lines
Quoted 13 lines
Quoted 2 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 29

Quoted 2 lines
kernel/sched/idle.c +1 -0
+                                   idle_state->exit_latency_ns);
 }

[ ... ]

--
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
maintainer
#5 lore raw
Quoted 160 lines · Daniel Lezcano
Quoted 139 lines · Vincent Guittot
Quoted 135 lines · Daniel Lezcano
Quoted 11 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Quoted 32 lines
Quoted 24 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

Quoted 7 lines

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

Quoted 71 lines
Quoted 71 lines

| Hikey960 | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      56140.8    |           56256    |
| schbench energy       |      153.575    |         152.676    |
| adrestia / periodic   |         4.98    |             5.2    |
| adrestia / single     |         9.02    |            9.12    |
| adrestia energy       |         1.18    |           1.233    |
| forkbench             |        7.971    |            8.05    |
| forkbench energy      |         9.37    |            9.42    |

--------------------------------------------------------------

---
 kernel/sched/fair.c  | 18 ++++++++++++++++--
 kernel/sched/idle.c  |  8 +++++++-
 kernel/sched/sched.h | 20 ++++++++++++++++++++
 3 files changed, 43 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
index 4b5d5e5e701e..8bd6ea148db7 100644
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
 {
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
+       s64 min_break_even = S64_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                if (available_idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
+                       s64 break_even = idle_get_break_even(rq);
+
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
+                               min_break_even = break_even;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
-                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
-                                  rq->idle_stamp > latest_idle_timestamp) {
+                       } else if ((idle && idle->exit_latency == min_exit_latency) &&
+                                  break_even < min_break_even) {
+                               /*
+                                * We give priority to the shallowest
+                                * idle states with the minimal break
+                                * even deadline to decrease the
+                                * probability to choose a CPU which
+                                * did not reach its break even yet
+                                */
+                               min_break_even = break_even;
+                               shallowest_idle_cpu = i;
+                       } else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
Quoted 8 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 24

Quoted 4 lines
kernel/sched/idle.c +3 -1
-       idle_set_state(this_rq(), idle_state);
+       struct rq *rq = this_rq();
+
+       idle_set_state(rq, idle_state);

Shouldn't the state be set after setting break even otherwise you will have a time window with an idle_state != null but the break_even still set to the previous value

Quoted 2 lines

IIUC we are protected in this section. Otherwise the routine above would be also wrong [if (idle && idle->exit_latency)], no?

Quoted 6 lines

no there are not the same because it uses the idle pointer to read exit_latency so we are sure to use exit_latency related to the idle pointer.

In your case it checks idle is not null but then it uses rq to read break_even but it might not have been already updated

Ok I will invert the lines.

Quoted 10 lines
Quoted 9 lines
Quoted 6 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 3 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Quoted 7 lines
Quoted 1 line

Using local_clock() would be more latency friendly

Unfortunately we are comparing the deadline across CPUs, so the local_clock() can not be used here.

But if we have one ktime_get() instead of a local_clock() + ktime_get(), that should be fine, no?

Can't this computation of break_even be done in cpuidle framework while computing other statistics for selecting the idle state instead ? cpuidle already uses ktime_get for next hrtimer as an example. So cpuidle compute break_even and make it available to scheduler like exit_latency. And I can imagine that system wide time value will also be needed when looking at next wakeup event of cluster/group of CPUs

Quoted 23 lines
Quoted 7 lines
Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
kernel/sched/idle.c +1 -0
+                                   idle_state->exit_latency_ns);
 }

[ ... ]

Quoted 7 lines
Quoted 7 lines

--
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

--
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

#6 lore raw
Quoted 1 line · Vincent Guittot

On Fri, 13 Mar 2020 at 13:15, Daniel Lezcano <[email protected]> wrote:

[ ... ]

Quoted 18 lines
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27

Quoted 3 lines
kernel/sched/idle.c +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Quoted 7 lines
Quoted 1 line

Using local_clock() would be more latency friendly

Unfortunately we are comparing the deadline across CPUs, so the local_clock() can not be used here.

But if we have one ktime_get() instead of a local_clock() + ktime_get(), that should be fine, no?

Quoted 6 lines

Can't this computation of break_even be done in cpuidle framework while computing other statistics for selecting the idle state instead ? cpuidle already uses ktime_get for next hrtimer as an example. So cpuidle compute break_even and make it available to scheduler like exit_latency. And I can imagine that system wide time value will also be needed when looking at next wakeup event of cluster/group of CPUs

Ok, so you suggest to revisit and consolidate the whole time capture in cpuidle? I think that makes sense.

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
maintainer
#7 lore raw
Quoted 31 lines · Daniel Lezcano
Quoted 1 line · Vincent Guittot

On Fri, 13 Mar 2020 at 13:15, Daniel Lezcano <[email protected]> wrote:

[ ... ]

Quoted 18 lines
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines

Review

Quoted 3 lines
(quoted diff) +3 -0
+
+       if (idle_state)
+               idle_set_break_even(rq, ktime_get_ns() +

What worries me a bit is that it adds one ktime_get call each time a cpu enters idle

Right, we can improve this in the future by folding the local_clock() in cpuidle when entering idle with this ktime_get.

Quoted 7 lines
Quoted 1 line

Using local_clock() would be more latency friendly

Unfortunately we are comparing the deadline across CPUs, so the local_clock() can not be used here.

But if we have one ktime_get() instead of a local_clock() + ktime_get(), that should be fine, no?

Quoted 6 lines

Can't this computation of break_even be done in cpuidle framework while computing other statistics for selecting the idle state instead ? cpuidle already uses ktime_get for next hrtimer as an example. So cpuidle compute break_even and make it available to scheduler like exit_latency. And I can imagine that system wide time value will also be needed when looking at next wakeup event of cluster/group of CPUs

Quoted 2 lines

Ok, so you suggest to revisit and consolidate the whole time capture in cpuidle? I think that makes sense.

Yes

Quoted 9 lines

--
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

#8 lore raw
In reply to Daniel Lezcano

Hi Daniel,

First, I think letting the scheduler know about desired minimum idle times is an interesting optimization if the overhead can be kept at a minimum. I do have a few comments about the patch though.

Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption. The patch doesn't affect the number of idle state enter/exit cycles, so you spend the amount of energy on those transitions. The main change is that idle time get spread out, so CPUs are less likely to be in the process of entering an idle state when they are asked to wake back up again.

Isn't it fair to say that we expect the total number of wake-ups remains unchanged? Total busy and idle times across all CPUs should remain the same too? Unless chosen idle-state is changed, which I don't think we expect either, there should be no net effect on energy? The main benefit is reduced wake-up latency I think.

Regarding chosen idle state, I'm wondering how this patch affects the cpuidle governor's idle state selection. Could the spreading of wake-ups trick governor to pick a shallower idle-state for some idle CPUs because we actively spread wake-ups rather than consolidating them? Just a thought.

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

I guess you could improve the idle time stamping without adding the break-even time, they don't have to go together?

Quoted 18 lines
Quoted 18 lines
Quoted 17 lines

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 4 lines
Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

I would also like some statistics to help understanding what actually changes.

I did some measurements on TX2, which only has one idle-state. I don't see the same trends as you do. adrestia single seems to be most affected by the patch, but _increases_ with the break_even patch rather than decrease. I don't trust adrestia too much though as the time resolution is low on TX2.

TX2 tip break_even
----------------------------------------------------
adrestia / single 5.21 5.51
adrestia / periodic 5.75 5.67
schbench 99.0th 45465.6 45376.0
hackbench 27.9851 27.9775

Notes:
adrestia: Avg of 100 runs: adrestia -l 25000
schbench: Avg of 10 runs: schbench -m16 -t64
hackbench: Avg of 10 runs: hackbench -g 20 -T 256 -l 100000

Morten

#9 lore raw

Hi Morten,

Quoted 34 lines · Morten Rasmussen

Hi Daniel,

First, I think letting the scheduler know about desired minimum idle times is an interesting optimization if the overhead can be kept at a minimum. I do have a few comments about the patch though.

Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

Quoted 4 lines

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

I'm seeing the wake-ups path so sensitive, I'm not comfortable to do any changes in it. That is the reason why the patch only changes the slow path.

Quoted 9 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Quoted 12 lines

The patch doesn't affect the number of idle state
enter/exit cycles, so you spend the amount of energy on those transitions. The main change is that idle time get spread out, so CPUs are less likely to be in the process of entering an idle state when they are asked to wake back up again.

Isn't it fair to say that we expect the total number of wake-ups remains unchanged? Total busy and idle times across all CPUs should remain the same too? Unless chosen idle-state is changed, which I don't think we expect either, there should be no net effect on energy? The main benefit is reduced wake-up latency I think.

Quoted 5 lines

Regarding chosen idle state, I'm wondering how this patch affects the cpuidle governor's idle state selection. Could the spreading of wake-ups trick governor to pick a shallower idle-state for some idle CPUs because we actively spread wake-ups rather than consolidating them? Just a thought.

May be I missed the point, why are we spreading the tasks?

We are taking the decision on the same sched domain, no?

Quoted 10 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

I guess you could improve the idle time stamping without adding the break-even time, they don't have to go together?

Yes, we can add the idle start time when entering idle in the cpuidle_enter function which is different from the idle_timestamp which gives the idle task scheduling. I sent a RFC for that [1].

However, each time we would like to inspect the deadline, we will have to compute it, so IMO it makes more sense to pre-compute it when entering idle in addition to the idle start.

[1] https://lkml.org/lkml/2020/3/16/902

Quoted 38 lines
Quoted 17 lines
Quoted 17 lines
Quoted 16 lines

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 4 lines
Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

I would also like some statistics to help understanding what actually changes.

I did some measurements on TX2, which only has one idle-state. I don't see the same trends as you do. adrestia single seems to be most affected by the patch, but _increases_ with the break_even patch rather than decrease. I don't trust adrestia too much though as the time resolution is low on TX2.

TX2 tip break_even
----------------------------------------------------
adrestia / single 5.21 5.51
adrestia / periodic 5.75 5.67
schbench 99.0th 45465.6 45376.0
hackbench 27.9851 27.9775

Quoted 4 lines

Notes:
adrestia: Avg of 100 runs: adrestia -l 25000
schbench: Avg of 10 runs: schbench -m16 -t64
hackbench: Avg of 10 runs: hackbench -g 20 -T 256 -l 100000

Thanks for testing. Is that a Jetson TX2 from Nvidia? If that is the case, IIRC, it has some kind of switcher for the CPUs in the firmware, I don't know how that can interact with the testing.

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#10 lore raw
Quoted 38 lines · Daniel Lezcano

Hi Morten,

Quoted 34 lines · Morten Rasmussen

Hi Daniel,

First, I think letting the scheduler know about desired minimum idle times is an interesting optimization if the overhead can be kept at a minimum. I do have a few comments about the patch though.

Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

Quoted 7 lines
Quoted 4 lines

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

I'm seeing the wake-ups path so sensitive, I'm not comfortable to do any changes in it. That is the reason why the patch only changes the slow path.

Right. I'm not against being cautious at all. It would be interesting to evaluate how bad it really is. The extra time-stamping business cost is the same, so it really down how much we dare to use the information in the fast-path and change the CPU selection policy. And of course, how much can be gained by the change.

Quoted 11 lines
Quoted 10 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

Quoted 8 lines

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

Quoted 13 lines
Quoted 13 lines

The patch doesn't affect the number of idle state
enter/exit cycles, so you spend the amount of energy on those transitions. The main change is that idle time get spread out, so CPUs are less likely to be in the process of entering an idle state when they are asked to wake back up again.

Isn't it fair to say that we expect the total number of wake-ups remains unchanged? Total busy and idle times across all CPUs should remain the same too? Unless chosen idle-state is changed, which I don't think we expect either, there should be no net effect on energy? The main benefit is reduced wake-up latency I think.

Quoted 7 lines
Quoted 5 lines

Regarding chosen idle state, I'm wondering how this patch affects the cpuidle governor's idle state selection. Could the spreading of wake-ups trick governor to pick a shallower idle-state for some idle CPUs because we actively spread wake-ups rather than consolidating them? Just a thought.

May be I missed the point, why are we spreading the tasks?

Picking the CPU with the smallest break-even time-stamp means you pick the CPU that has been idle longest in the shallowest idle-state. If you periodically one-shot spawn tasks at a rate which is long enough that the shallowest state is the same for several CPUs, you would end up picking the least recently used CPU each time effectively spreading the wake-ups across all the CPUs in the same state.

Thinking more about it, it might not be a real problem as if one of the CPUs suddenly choose a shallower idle-state, it would become the target all new tasks from that point onwards.

Quoted 1 line

We are taking the decision on the same sched domain, no?

I'm not sure I get the relation to the sched_domain?

Quoted 16 lines
Quoted 11 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

I guess you could improve the idle time stamping without adding the break-even time, they don't have to go together?

Yes, we can add the idle start time when entering idle in the cpuidle_enter function which is different from the idle_timestamp which gives the idle task scheduling. I sent a RFC for that [1].

Quoted 5 lines

However, each time we would like to inspect the deadline, we will have to compute it, so IMO it makes more sense to pre-compute it when entering idle in addition to the idle start.

[1] https://lkml.org/lkml/2020/3/16/902

Yes, I saw that patch too. Seems to make sense :-)

Quoted 39 lines
Quoted 39 lines
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 4 lines
Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

I would also like some statistics to help understanding what actually changes.

I did some measurements on TX2, which only has one idle-state. I don't see the same trends as you do. adrestia single seems to be most affected by the patch, but _increases_ with the break_even patch rather than decrease. I don't trust adrestia too much though as the time resolution is low on TX2.

TX2 tip break_even
----------------------------------------------------
adrestia / single 5.21 5.51
adrestia / periodic 5.75 5.67
schbench 99.0th 45465.6 45376.0
hackbench 27.9851 27.9775

Quoted 8 lines
Quoted 4 lines

Notes:
adrestia: Avg of 100 runs: adrestia -l 25000
schbench: Avg of 10 runs: schbench -m16 -t64
hackbench: Avg of 10 runs: hackbench -g 20 -T 256 -l 100000

Thanks for testing. Is that a Jetson TX2 from Nvidia? If that is the case, IIRC, it has some kind of switcher for the CPUs in the firmware, I don't know how that can interact with the testing.

Sorry, I should have been clearer. It is a ThunderX2. 2x 32-core (128 threads) = 256 HW threads.

Morten

#11 lore raw
Quoted 44 lines · Morten Rasmussen
Quoted 43 lines · Daniel Lezcano

Hi Morten,

Quoted 38 lines · Morten Rasmussen

Hi Daniel,

First, I think letting the scheduler know about desired minimum idle times is an interesting optimization if the overhead can be kept at a minimum. I do have a few comments about the patch though.

Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

Quoted 8 lines
Quoted 2 lines

I'm seeing the wake-ups path so sensitive, I'm not comfortable to do any changes in it. That is the reason why the patch only changes the slow path.

Right. I'm not against being cautious at all. It would be interesting to evaluate how bad it really is. The extra time-stamping business cost is the same, so it really down how much we dare to use the information in the fast-path and change the CPU selection policy. And of course, how much can be gained by the change.

If the change provided by this patch is acceptable. I can give a try with the fast path.

Quoted 17 lines
Quoted 17 lines
Quoted 9 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

Quoted 4 lines
Quoted 1 line

It is best effort.

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

If the CPU is woken up before it reached the break even, the idle state cost in energy is greater than the energy it saved.

Am I misunderstanding your point?

Quoted 18 lines
Quoted 18 lines
Quoted 17 lines

The patch doesn't affect the number of idle state
enter/exit cycles, so you spend the amount of energy on those transitions. The main change is that idle time get spread out, so CPUs are less likely to be in the process of entering an idle state when they are asked to wake back up again.

Isn't it fair to say that we expect the total number of wake-ups remains unchanged? Total busy and idle times across all CPUs should remain the same too? Unless chosen idle-state is changed, which I don't think we expect either, there should be no net effect on energy? The main benefit is reduced wake-up latency I think.

Regarding chosen idle state, I'm wondering how this patch affects the cpuidle governor's idle state selection. Could the spreading of wake-ups trick governor to pick a shallower idle-state for some idle CPUs because we actively spread wake-ups rather than consolidating them? Just a thought.

Quoted 8 lines
Quoted 1 line

May be I missed the point, why are we spreading the tasks?

Picking the CPU with the smallest break-even time-stamp means you pick the CPU that has been idle longest in the shallowest idle-state. If you periodically one-shot spawn tasks at a rate which is long enough that the shallowest state is the same for several CPUs, you would end up picking the least recently used CPU each time effectively spreading the wake-ups across all the CPUs in the same state.

Ok, thanks for the clarification.

Quoted 3 lines

Thinking more about it, it might not be a real problem as if one of the CPUs suddenly choose a shallower idle-state, it would become the target all new tasks from that point onwards.

Right.

Quoted 3 lines
Quoted 1 line

We are taking the decision on the same sched domain, no?

I'm not sure I get the relation to the sched_domain?

Never mind. I misunderstood your comment.

Quoted 67 lines
Quoted 15 lines
Quoted 10 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

I guess you could improve the idle time stamping without adding the break-even time, they don't have to go together?

Yes, we can add the idle start time when entering idle in the cpuidle_enter function which is different from the idle_timestamp which gives the idle task scheduling. I sent a RFC for that [1].

Quoted 5 lines

However, each time we would like to inspect the deadline, we will have to compute it, so IMO it makes more sense to pre-compute it when entering idle in addition to the idle start.

[1] https://lkml.org/lkml/2020/3/16/902

Yes, I saw that patch too. Seems to make sense :-)

Quoted 44 lines
Quoted 43 lines
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 4 lines
Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

I would also like some statistics to help understanding what actually changes.

I did some measurements on TX2, which only has one idle-state. I don't see the same trends as you do. adrestia single seems to be most affected by the patch, but _increases_ with the break_even patch rather than decrease. I don't trust adrestia too much though as the time resolution is low on TX2.

TX2 tip break_even
----------------------------------------------------
adrestia / single 5.21 5.51
adrestia / periodic 5.75 5.67
schbench 99.0th 45465.6 45376.0
hackbench 27.9851 27.9775

Notes:
adrestia: Avg of 100 runs: adrestia -l 25000
schbench: Avg of 10 runs: schbench -m16 -t64
hackbench: Avg of 10 runs: hackbench -g 20 -T 256 -l 100000

Quoted 6 lines
Quoted 3 lines

Thanks for testing. Is that a Jetson TX2 from Nvidia? If that is the case, IIRC, it has some kind of switcher for the CPUs in the firmware, I don't know how that can interact with the testing.

Sorry, I should have been clearer. It is a ThunderX2. 2x 32-core (128 threads) = 256 HW threads.

Indeed, that is different :)

I've a syncquacer but we find out a bug in the firmware, hopefully it can be fixed.

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#12 lore raw
Quoted 23 lines · Daniel Lezcano
Quoted 22 lines · Morten Rasmussen
Quoted 20 lines · Daniel Lezcano
Quoted 10 lines · Morten Rasmussen
Quoted 6 lines · Daniel Lezcano
Quoted 6 lines
Quoted 6 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Quoted 7 lines
Quoted 2 lines

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

If the CPU is woken up before it reached the break even, the idle state cost in energy is greater than the energy it saved.

Am I misunderstanding your point?

Considering just the waking then yes, it reaches energy break-even. However, considering all the CPUs in the system, it just moves the idle entry/exit energy cost to a different CPU, it doesn't go away.

Whether you have:

               |-BE-|
           ____    ____
CPU0:  ___/    \__/    \___

CPU1: ____________________

Or:

               |-BE-|
           ____
CPU0:  ___/    \___________
                   ____

CPU1: ___________/ \___

_
= CPU busy = P_{busy}
_ = CPU idle = P_{idle}
/ = CPU idle exit = P_{exit}
\ = CPU idle entry = P_{entry}

The sum of areas under the curves is the same, i.e. the total energy is unchanged.

Morten

#13 lore raw
Quoted 51 lines · Morten Rasmussen
Quoted 23 lines · Daniel Lezcano
Quoted 22 lines · Morten Rasmussen
Quoted 20 lines · Daniel Lezcano
Quoted 10 lines · Morten Rasmussen
Quoted 6 lines · Daniel Lezcano
Quoted 6 lines
Quoted 6 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Quoted 7 lines
Quoted 2 lines

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

If the CPU is woken up before it reached the break even, the idle state cost in energy is greater than the energy it saved.

Am I misunderstanding your point?

Considering just the waking then yes, it reaches energy break-even. However, considering all the CPUs in the system, it just moves the idle entry/exit energy cost to a different CPU, it doesn't go away.

Whether you have:

               |-BE-|
           ____    ____
CPU0:  ___/    \__/    \___

CPU1: ____________________

Or:

               |-BE-|
           ____
CPU0:  ___/    \___________
                   ____

CPU1: ___________/ \___

Quoted 8 lines

_
= CPU busy = P_{busy}
_ = CPU idle = P_{idle}
/ = CPU idle exit = P_{exit}
\ = CPU idle entry = P_{entry}

The sum of areas under the curves is the same, i.e. the total energy is unchanged.

It is a counter-intuitive comment, now I get it, thanks for the clarification. It is a good point.

Taking into consideration the dynamic, in the case #1, the break even is not reached, the idle duration is smaller and that leads the governor to choose shallower idle states after and consequently CPU0 will be used in priority. We end up with CPU0 in a shallow state and CPU1 in a deep state.

With the case #2, we can have the CPUs in both deep state and the governor should be keeping choosing the same idle state.

I don't know what is more energy/perf efficient. IMO this is very workload dependent. The only way to check is to test. Hopefully I can find a platform for that.

Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#14 lore raw
Quoted 58 lines · Daniel Lezcano
Quoted 57 lines · Morten Rasmussen
Quoted 23 lines · Daniel Lezcano
Quoted 22 lines · Morten Rasmussen
Quoted 20 lines · Daniel Lezcano
Quoted 10 lines · Morten Rasmussen
Quoted 6 lines · Daniel Lezcano
Quoted 6 lines
Quoted 6 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Quoted 7 lines
Quoted 2 lines

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

If the CPU is woken up before it reached the break even, the idle state cost in energy is greater than the energy it saved.

Am I misunderstanding your point?

Considering just the waking then yes, it reaches energy break-even. However, considering all the CPUs in the system, it just moves the idle entry/exit energy cost to a different CPU, it doesn't go away.

Whether you have:

               |-BE-|
           ____    ____
CPU0:  ___/    \__/    \___

CPU1: ____________________

Or:

               |-BE-|
           ____
CPU0:  ___/    \___________
                   ____

CPU1: ___________/ \___

_
= CPU busy = P_{busy}
_ = CPU idle = P_{idle}
/ = CPU idle exit = P_{exit}
\ = CPU idle entry = P_{entry}

Quoted 5 lines
Quoted 2 lines

The sum of areas under the curves is the same, i.e. the total energy is unchanged.

It is a counter-intuitive comment, now I get it, thanks for the clarification. It is a good point.

No problem.

Quoted 4 lines

Taking into consideration the dynamic, in the case #1, the break even is not reached, the idle duration is smaller and that leads the governor to choose shallower idle states after and consequently CPU0 will be used in priority. We end up with CPU0 in a shallow state and CPU1 in a deep state.

Indeed. I was speculating earlier if the opposite could happen too. If we extended the second case to form a repeating pattern, could we prevent somehow prevent CPU1 from reaching a deeper state? Could we have pattern that would keep both CPUs in shallow state where it would have been more efficient to consolidate the wake-ups on CPU0 and let CPU1 enter deeper states?

Quoted 3 lines

With the case #2, we can have the CPUs in both deep state and the governor should be keeping choosing the same idle state.

Ideally yes. However it depends on the break-even times of the deeper states and when the next wake-ups happen.

Quoted 3 lines

I don't know what is more energy/perf efficient. IMO this is very workload dependent. The only way to check is to test. Hopefully I can find a platform for that.

Moving the wake-up shouldn't impact energy directly, although it have a positive latency impact as you are more likely to avoid waking up CPUs that haven't finished the idle entry sequence. However, changing the wake-up pattern could have an indirect energy impact, positive or negative. It isn't clear to me either what outcome to expect.

Morten

maintainer
#15 lore raw
In reply to Morten Rasmussen
Quoted 45 lines · Morten Rasmussen
Quoted 43 lines · Daniel Lezcano

Hi Morten,

Quoted 38 lines · Morten Rasmussen

Hi Daniel,

First, I think letting the scheduler know about desired minimum idle times is an interesting optimization if the overhead can be kept at a minimum. I do have a few comments about the patch though.

Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Vincent Guittot

Hi Daniel,

Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

Quoted 8 lines
Quoted 2 lines

I'm seeing the wake-ups path so sensitive, I'm not comfortable to do any changes in it. That is the reason why the patch only changes the slow path.

Right. I'm not against being cautious at all. It would be interesting to evaluate how bad it really is. The extra time-stamping business cost is the same, so it really down how much we dare to use the information in the fast-path and change the CPU selection policy. And of course, how much can be gained by the change.

Hmm... the fast path not even parses all idle CPUs right now so it will be difficult to make any comparison. Regarding wakeup path, the only place that could make sense IMO is the EAS slow wakeup path find_energy_efficient_cpu() which mitigates performance vs energy consumption

Quoted 136 lines
Quoted 12 lines
Quoted 11 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.

At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.

I don't follow the argument that sleeping longer should improve energy consumption.

Quoted 8 lines

May be it is not explained correctly.

The patch is about selecting a CPU with the smallest break even deadline value. In a group of idle CPUs in the same idle state, we will pick the one with the smallest break even dead line which is the one with the highest probability it already reached its target residency.

It is best effort.

Indeed. I get what the patch does, I just don't see how the patch improves energy efficiency.

Quoted 13 lines
Quoted 13 lines

The patch doesn't affect the number of idle state
enter/exit cycles, so you spend the amount of energy on those transitions. The main change is that idle time get spread out, so CPUs are less likely to be in the process of entering an idle state when they are asked to wake back up again.

Isn't it fair to say that we expect the total number of wake-ups remains unchanged? Total busy and idle times across all CPUs should remain the same too? Unless chosen idle-state is changed, which I don't think we expect either, there should be no net effect on energy? The main benefit is reduced wake-up latency I think.

Quoted 7 lines
Quoted 5 lines

Regarding chosen idle state, I'm wondering how this patch affects the cpuidle governor's idle state selection. Could the spreading of wake-ups trick governor to pick a shallower idle-state for some idle CPUs because we actively spread wake-ups rather than consolidating them? Just a thought.

May be I missed the point, why are we spreading the tasks?

Picking the CPU with the smallest break-even time-stamp means you pick the CPU that has been idle longest in the shallowest idle-state. If you periodically one-shot spawn tasks at a rate which is long enough that the shallowest state is the same for several CPUs, you would end up picking the least recently used CPU each time effectively spreading the wake-ups across all the CPUs in the same state.

Thinking more about it, it might not be a real problem as if one of the CPUs suddenly choose a shallower idle-state, it would become the target all new tasks from that point onwards.

Quoted 1 line

We are taking the decision on the same sched domain, no?

I'm not sure I get the relation to the sched_domain?

Quoted 16 lines
Quoted 11 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.

I guess you could improve the idle time stamping without adding the break-even time, they don't have to go together?

Yes, we can add the idle start time when entering idle in the cpuidle_enter function which is different from the idle_timestamp which gives the idle task scheduling. I sent a RFC for that [1].

Quoted 5 lines

However, each time we would like to inspect the deadline, we will have to compute it, so IMO it makes more sense to pre-compute it when entering idle in addition to the idle start.

[1] https://lkml.org/lkml/2020/3/16/902

Yes, I saw that patch too. Seems to make sense :-)

Quoted 39 lines
Quoted 39 lines
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines

Tested on:
- a synquacer 24 cores, 6 sched domains
- a hikey960 HMP 8 cores, 2 sched domains, with the EAS and energy probe

sched/perf and messaging does not show a performance regression. Ran 50 times schbench, adrestia and forkbench.

The tools described at https://lwn.net/Articles/724935/

--------------------------------------------------------------
| Synquacer | With break even | Without break even |
--------------------------------------------------------------

| schbench *99.0th      |      14844.8    |         15017.6    |
| adrestia / periodic   |        57.95    |              57    |
| adrestia / single     |         49.3    |            55.4    |

--------------------------------------------------------------

Quoted 4 lines
Quoted 1 line

Have you got some figures or cpuidle statistics for the syncquacer ?

No, and we just noticed the syncquacer has a bug in the firmware and does not actually go to the idle states.

I would also like some statistics to help understanding what actually changes.

I did some measurements on TX2, which only has one idle-state. I don't see the same trends as you do. adrestia single seems to be most affected by the patch, but _increases_ with the break_even patch rather than decrease. I don't trust adrestia too much though as the time resolution is low on TX2.

TX2 tip break_even
----------------------------------------------------
adrestia / single 5.21 5.51
adrestia / periodic 5.75 5.67
schbench 99.0th 45465.6 45376.0
hackbench 27.9851 27.9775

Quoted 8 lines
Quoted 4 lines

Notes:
adrestia: Avg of 100 runs: adrestia -l 25000
schbench: Avg of 10 runs: schbench -m16 -t64
hackbench: Avg of 10 runs: hackbench -g 20 -T 256 -l 100000

Thanks for testing. Is that a Jetson TX2 from Nvidia? If that is the case, IIRC, it has some kind of switcher for the CPUs in the firmware, I don't know how that can interact with the testing.

Sorry, I should have been clearer. It is a ThunderX2. 2x 32-core (128 threads) = 256 HW threads.

Morten

#16 lore raw
Quoted 43 lines · Vincent Guittot
Quoted 33 lines · Morten Rasmussen
Quoted 32 lines · Daniel Lezcano
Quoted 30 lines · Morten Rasmussen
Quoted 8 lines · Daniel Lezcano
Quoted 7 lines · Vincent Guittot
Quoted 5 lines · Daniel Lezcano

In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.

Quoted 5 lines
Quoted 2 lines

The idea makes sense but this path is only used by fork and exec so I'm not sure about the real impact

I agree the fork / exec path is called much less often than the wake path but it makes more sense for the decision.

Looking at the flow in find_idlest_cpu(), AFAICT, find_idlest_group_cpu() is not actually making the final choice of CPU, so going through a lot of trouble there looking at idle states is pointless. Is there something I don't see?

We fellow sd->child until groups == CPUs which which means that find_idlest_group() actually makes the final choice as the final group passed to find_idlest_group_cpu() is single-CPU group. The flow has been like that for years. Even before you added the initial idle-state awareness.

I agree with Vincent, if this should really make a difference it should include wake-ups existing tasks too. Although I'm aware it would be a more invasive change. As said from the beginning, the idea is fine, but the current implementation should not make any measurable difference?

Quoted 8 lines
Quoted 2 lines

I'm seeing the wake-ups path so sensitive, I'm not comfortable to do any changes in it. That is the reason why the patch only changes the slow path.

Right. I'm not against being cautious at all. It would be interesting to evaluate how bad it really is. The extra time-stamping business cost is the same, so it really down how much we dare to use the information in the fast-path and change the CPU selection policy. And of course, how much can be gained by the change.

Quoted 5 lines

Hmm... the fast path not even parses all idle CPUs right now so it will be difficult to make any comparison. Regarding wakeup path, the only place that could make sense IMO is the EAS slow wakeup path find_energy_efficient_cpu() which mitigates performance vs energy consumption

Agreed, it is not really compatible with the current fast-path policies. I would start with just hacking it in to evaluate the potential improvements to have an idea about what is on the table.

As you say, it could live somewhere slightly out the way like the EAS path, but I'm not sure if actually fits well under EAS. EAS is disabled for symmetric CPU capacities, which is probably the systems that will benefit the most. Also, as mentioned already in this thread, I don't see how the idea brings any energy savings?

Morten

#17 lore raw
In reply to Daniel Lezcano

Hi Daniel,

One more comment on the break even itself, ignoring the rest:

Quoted 6 lines · Daniel Lezcano
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 28

Quoted 10 lines
kernel/sched/idle.c +7 -1
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
-	idle_set_state(this_rq(), idle_state);
+	struct rq *rq = this_rq();
+
+	idle_set_state(rq, idle_state);
+
+	if (idle_state)
+		idle_set_break_even(rq, ktime_get_ns() +
+				    idle_state->exit_latency_ns);

I'm not sure I follow why we go for entry time + exit latency. If this is based on the minimum residency, shouldn't this be something depending on the entry latency? i.e. something like

break_even = now + entry_latency + idling_time

                     \_________________________/
                            min-residency

or am I missing something?

Quoted 3 lines
kernel/sched/idle.c +0 -0
 }
 
 static int __read_mostly cpu_idle_force_poll;
#18 lore raw
Quoted 27 lines · Valentin Schneider

Hi Daniel,

One more comment on the break even itself, ignoring the rest:

Quoted 6 lines · Daniel Lezcano
kernel/sched/idle.c +0 -0
index b743bf38f08f..3342e7bae072 100644
@@ -19,7 +19,13 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];
  */

kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 28

Quoted 10 lines
kernel/sched/idle.c +7 -1
 void sched_idle_set_state(struct cpuidle_state *idle_state)
 {
-	idle_set_state(this_rq(), idle_state);
+	struct rq *rq = this_rq();
+
+	idle_set_state(rq, idle_state);
+
+	if (idle_state)
+		idle_set_break_even(rq, ktime_get_ns() +
+				    idle_state->exit_latency_ns);

I'm not sure I follow why we go for entry time + exit latency. If this is based on the minimum residency, shouldn't this be something depending on the entry latency? i.e. something like

Quoted 5 lines

break_even = now + entry_latency + idling_time

                     \_________________________/
                            min-residency

or am I missing something?

Oh, no it is a stupid mistake from me. Thanks for pointing this out!

It should be:

	break_even = now + idle_state->target_residency_ns;

- Documentation/devicetree/bindings/arm/idle-states.yaml

* min-residency: Minimum period, including preparation and entry, for a given idle state to be worthwhile energywise.

(target_residency_ns == min-residency).

Quoted 4 lines
Quoted 4 lines
kernel/sched/idle.c +0 -0
 }
 
 static int __read_mostly cpu_idle_force_poll;
Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog