From: Juri Lelli <juri.lelli@arm.com>
To: Yuyang Du <yuyang.du@intel.com>
Cc: peterz@infradead.org, mingo@kernel.org,
linux-kernel@vger.kernel.org, bsegall@google.com, pjt@google.com,
morten.rasmussen@arm.com, vincent.guittot@linaro.org,
dietmar.eggemann@arm.com
Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table
Date: Mon, 11 Apr 2016 11:41:28 +0100 [thread overview]
Message-ID: <20160411104128.GB14134@e106622-lin> (raw)
In-Reply-To: <1460327765-18024-2-git-send-email-yuyang.du@intel.com>
Hi,
On 11/04/16 06:36, Yuyang Du wrote:
> __compute_runnable_contrib() uses a loop to compute sum, whereas a
> table loopup can do it faster in a constant time.
>
> The following python script can be used to generate the constants:
>
> print " #: yN_inv yN_sum"
> print "-----------------------"
> y = (0.5)**(1/32.0)
> x = 2**32
> xx = 1024
> for i in range(0, 32):
> if i == 0:
> x = x-1
> xx = xx*y
> else:
> x = x*y
> xx = int(xx*y + 1024*y)
> print "%2d: %#x %8d" % (i, int(x), int(xx))
>
> print " #: sum_N32"
> print "------------"
> xxx = xx
> for i in range(0, 11):
> if i == 0:
> xxx = xx
> else:
> xxx = xxx/2 + xx
> print "%2d: %8d" % (i, xxx)
>
Thanks for the script, really useful. Do you think there is value in
making it general? Like if we want to play with/need changing LOAD_AVG_
PERIOD in the future to something different than 32.
Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
you think there is any value in removing that assumption?
Best,
- Juri
> Signed-off-by: Yuyang Du <yuyang.du@intel.com>
> Reviewed-by: Morten Rasmussen <morten.rasmussen@arm.com>
> ---
> kernel/sched/fair.c | 20 ++++++++++++--------
> 1 file changed, 12 insertions(+), 8 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index b8cc1c3..6e0eec0 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -2603,6 +2603,15 @@ static const u32 runnable_avg_yN_sum[] = {
> };
>
> /*
> + * Precomputed \Sum y^k { 1<=k<=n, where n%32=0). Values are rolled down to
> + * lower integers.
> + */
> +static const u32 __accumulated_sum_N32[] = {
> + 0, 23371, 35056, 40899, 43820, 45281,
> + 46011, 46376, 46559, 46650, 46696, 46719,
> +};
> +
> +/*
> * Approximate:
> * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> */
> @@ -2650,14 +2659,9 @@ static u32 __compute_runnable_contrib(u64 n)
> else if (unlikely(n >= LOAD_AVG_MAX_N))
> return LOAD_AVG_MAX;
>
> - /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
> - do {
> - contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
> - contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
> -
> - n -= LOAD_AVG_PERIOD;
> - } while (n > LOAD_AVG_PERIOD);
> -
> + /* Since n < LOAD_AVG_MAX_N, n/LOAD_AVG_PERIOD < 11 */
> + contrib = __accumulated_sum_N32[n>>5]; /* =n/LOAD_AVG_PERIOD */
> + n %= LOAD_AVG_PERIOD;
> contrib = decay_load(contrib, n);
> return contrib + runnable_avg_yN_sum[n];
> }
> --
> 2.1.4
>
next prev parent reply other threads:[~2016-04-11 10:39 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-04-10 22:36 [PATCH 0/4] Optimize sched avg computation and implement flat util hierarchy Yuyang Du
2016-04-10 22:36 ` [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du
2016-04-11 9:08 ` Vincent Guittot
2016-04-11 10:41 ` Juri Lelli [this message]
2016-04-11 19:12 ` Yuyang Du
2016-04-12 10:14 ` Juri Lelli
2016-04-12 18:07 ` Yuyang Du
2016-04-13 9:11 ` Juri Lelli
2016-04-11 16:59 ` Dietmar Eggemann
2016-04-11 19:17 ` Yuyang Du
2016-04-12 14:19 ` Peter Zijlstra
2016-04-12 18:12 ` Yuyang Du
2016-04-11 23:21 ` Joe Perches
2016-04-12 12:02 ` Juri Lelli
2016-04-11 23:07 ` Joe Perches
2016-04-10 22:36 ` [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue Yuyang Du
2016-04-11 9:08 ` Vincent Guittot
2016-04-11 19:41 ` Yuyang Du
2016-04-12 11:56 ` Vincent Guittot
2016-04-12 21:09 ` Yuyang Du
2016-04-13 11:11 ` Vincent Guittot
2016-04-12 12:02 ` Dietmar Eggemann
2016-04-12 20:14 ` Yuyang Du
2016-04-13 4:04 ` Joe Perches
2016-04-13 8:40 ` Morten Rasmussen
2016-04-13 15:13 ` Dietmar Eggemann
2016-04-13 15:28 ` Vincent Guittot
2016-04-13 16:20 ` Vincent Guittot
2016-04-13 18:44 ` Yuyang Du
2016-04-14 12:52 ` Dietmar Eggemann
2016-04-14 20:05 ` Yuyang Du
2016-04-18 17:59 ` Yuyang Du
2016-04-10 22:36 ` [PATCH 3/4] sched/fair: Modify accumulated sums for load/util averages Yuyang Du
2016-04-11 17:14 ` Dietmar Eggemann
2016-04-10 22:36 ` [PATCH 4/4] sched/fair: Implement flat hierarchical structure for util_avg Yuyang Du
2016-04-11 12:29 ` Vincent Guittot
2016-04-11 20:37 ` Yuyang Du
2016-04-13 11:27 ` Vincent Guittot
2016-04-13 18:20 ` Yuyang Du
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160411104128.GB14134@e106622-lin \
--to=juri.lelli@arm.com \
--cc=bsegall@google.com \
--cc=dietmar.eggemann@arm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=morten.rasmussen@arm.com \
--cc=peterz@infradead.org \
--cc=pjt@google.com \
--cc=vincent.guittot@linaro.org \
--cc=yuyang.du@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).