diff mbox series

[RFC,03/16] sched/pelt: Add a new function to approximate runtime to reach given util

Message ID 20240820163512.1096301-4-qyousef@layalina.io
State New
Headers show
Series sched/fair/schedutil: Better manage system response time | expand

Commit Message

Qais Yousef Aug. 20, 2024, 4:34 p.m. UTC
It is basically the ramp-up time from 0 to a given value. Will be used
later to implement new tunable to control response time  for schedutil.

Signed-off-by: Qais Yousef <qyousef@layalina.io>
---
 kernel/sched/pelt.c  | 21 +++++++++++++++++++++
 kernel/sched/sched.h |  1 +
 2 files changed, 22 insertions(+)

Comments

Sultan Alsawaf (unemployed) Aug. 22, 2024, 5:36 a.m. UTC | #1
On Tue, Aug 20, 2024 at 05:34:59PM +0100, Qais Yousef wrote:
> It is basically the ramp-up time from 0 to a given value. Will be used
> later to implement new tunable to control response time  for schedutil.
> 
> Signed-off-by: Qais Yousef <qyousef@layalina.io>
> ---
>  kernel/sched/pelt.c  | 21 +++++++++++++++++++++
>  kernel/sched/sched.h |  1 +
>  2 files changed, 22 insertions(+)
> 
> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
> index 2ce83e880bd5..06cb881ba582 100644
> --- a/kernel/sched/pelt.c
> +++ b/kernel/sched/pelt.c
> @@ -487,3 +487,24 @@ unsigned long approximate_util_avg(unsigned long util, u64 delta)
>  
>  	return sa.util_avg;
>  }
> +
> +/*
> + * Approximate the required amount of runtime in ms required to reach @util.
> + */
> +u64 approximate_runtime(unsigned long util)
> +{
> +	struct sched_avg sa = {};
> +	u64 delta = 1024; // period = 1024 = ~1ms
> +	u64 runtime = 0;
> +
> +	if (unlikely(!util))
> +		return runtime;

Seems like this check can be removed since it's covered by the loop condition.

> +
> +	while (sa.util_avg < util) {
> +		accumulate_sum(delta, &sa, 1, 0, 1);
> +		___update_load_avg(&sa, 0);
> +		runtime++;
> +	}

I think this could be a lookup table (probably 1024 * u8), for constant-time
runtime approximation.

> +
> +	return runtime;
> +}
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 294c6769e330..47f158b2cdc2 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -3065,6 +3065,7 @@ unsigned long sugov_effective_cpu_perf(int cpu, unsigned long actual,
>  				 unsigned long max);
>  
>  unsigned long approximate_util_avg(unsigned long util, u64 delta);
> +u64 approximate_runtime(unsigned long util);
>  
>  /*
>   * Verify the fitness of task @p to run on @cpu taking into account the
> -- 
> 2.34.1
> 

Cheers,
Sultan
Christian Loehle Sept. 16, 2024, 3:31 p.m. UTC | #2
On 8/22/24 06:36, Sultan Alsawaf (unemployed) wrote:
> On Tue, Aug 20, 2024 at 05:34:59PM +0100, Qais Yousef wrote:
>> It is basically the ramp-up time from 0 to a given value. Will be used
>> later to implement new tunable to control response time  for schedutil.
>>
>> Signed-off-by: Qais Yousef <qyousef@layalina.io>
>> ---
>>  kernel/sched/pelt.c  | 21 +++++++++++++++++++++
>>  kernel/sched/sched.h |  1 +
>>  2 files changed, 22 insertions(+)
>>
>> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
>> index 2ce83e880bd5..06cb881ba582 100644
>> --- a/kernel/sched/pelt.c
>> +++ b/kernel/sched/pelt.c
>> @@ -487,3 +487,24 @@ unsigned long approximate_util_avg(unsigned long util, u64 delta)
>>  
>>  	return sa.util_avg;
>>  }
>> +
>> +/*
>> + * Approximate the required amount of runtime in ms required to reach @util.
>> + */
>> +u64 approximate_runtime(unsigned long util)
>> +{
>> +	struct sched_avg sa = {};
>> +	u64 delta = 1024; // period = 1024 = ~1ms
>> +	u64 runtime = 0;
>> +
>> +	if (unlikely(!util))
>> +		return runtime;
> 
> Seems like this check can be removed since it's covered by the loop condition.
> 
>> +
>> +	while (sa.util_avg < util) {
>> +		accumulate_sum(delta, &sa, 1, 0, 1);
>> +		___update_load_avg(&sa, 0);
>> +		runtime++;
>> +	}
> 
> I think this could be a lookup table (probably 1024 * u8), for constant-time
> runtime approximation.

Somewhat agreed, given that we don't seem to care about the 2.4% error margin,
we could allow some more errors here even. Something like 50 values should be
more than enough (which might fit nicely in a simple formula, too?).

FWIW
util: approximate_runtime(util)
160: 8
192: 10
224: 12
256: 14
288: 16
320: 18
352: 20
384: 22
416: 25
448: 27
480: 30
512: 32
544: 35
576: 39
608: 42
640: 46
672: 50
704: 54
736: 59
768: 64
800: 71
832: 78
864: 86
896: 96
928: 109
960: 128
992: 159
1024: 323

Fine for a RFC though.
diff mbox series

Patch

diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
index 2ce83e880bd5..06cb881ba582 100644
--- a/kernel/sched/pelt.c
+++ b/kernel/sched/pelt.c
@@ -487,3 +487,24 @@  unsigned long approximate_util_avg(unsigned long util, u64 delta)
 
 	return sa.util_avg;
 }
+
+/*
+ * Approximate the required amount of runtime in ms required to reach @util.
+ */
+u64 approximate_runtime(unsigned long util)
+{
+	struct sched_avg sa = {};
+	u64 delta = 1024; // period = 1024 = ~1ms
+	u64 runtime = 0;
+
+	if (unlikely(!util))
+		return runtime;
+
+	while (sa.util_avg < util) {
+		accumulate_sum(delta, &sa, 1, 0, 1);
+		___update_load_avg(&sa, 0);
+		runtime++;
+	}
+
+	return runtime;
+}
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 294c6769e330..47f158b2cdc2 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -3065,6 +3065,7 @@  unsigned long sugov_effective_cpu_perf(int cpu, unsigned long actual,
 				 unsigned long max);
 
 unsigned long approximate_util_avg(unsigned long util, u64 delta);
+u64 approximate_runtime(unsigned long util);
 
 /*
  * Verify the fitness of task @p to run on @cpu taking into account the