From: Chen Yu <yu.c.chen@intel.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: <mingo@kernel.org>, <vincent.guittot@linaro.org>,
<linux-kernel@vger.kernel.org>, <juri.lelli@redhat.com>,
<dietmar.eggemann@arm.com>, <rostedt@goodmis.org>,
<bsegall@google.com>, <mgorman@suse.de>, <bristot@redhat.com>,
<corbet@lwn.net>, <qyousef@layalina.io>, <chris.hyser@oracle.com>,
<patrick.bellasi@matbug.net>, <pjt@google.com>, <pavel@ucw.cz>,
<qperret@google.com>, <tim.c.chen@linux.intel.com>,
<joshdon@google.com>, <timj@gnu.org>, <kprateek.nayak@amd.com>,
<youssefesmat@chromium.org>, <joel@joelfernandes.org>,
<efault@gmx.de>
Subject: Re: [PATCH 06/17] sched/fair: Add lag based placement
Date: Thu, 6 Apr 2023 11:03:41 +0800 [thread overview]
Message-ID: <ZC42jZiAp9JNAqj7@chenyu5-mobl1> (raw)
In-Reply-To: <20230405094720.GA4253@hirez.programming.kicks-ass.net>
On 2023-04-05 at 11:47:20 +0200, Peter Zijlstra wrote:
> On Mon, Apr 03, 2023 at 05:18:06PM +0800, Chen Yu wrote:
> > On 2023-03-28 at 11:26:28 +0200, Peter Zijlstra wrote:
> > > place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
> > [...]
> > > /*
> > > - * Halve their sleep time's effect, to allow
> > > - * for a gentler effect of sleepers:
> > > + * If we want to place a task and preserve lag, we have to
> > > + * consider the effect of the new entity on the weighted
> > > + * average and compensate for this, otherwise lag can quickly
> > > + * evaporate:
> > > + *
> > > + * l_i = V - v_i <=> v_i = V - l_i
> > > + *
> > > + * V = v_avg = W*v_avg / W
> > > + *
> > > + * V' = (W*v_avg + w_i*v_i) / (W + w_i)
> > If I understand correctly, V' means the avg_runtime if se_i is enqueued?
> > Then,
> >
> > V = (\Sum w_j*v_j) / W
>
> multiply by W on both sides to get:
>
> V*W = \Sum w_j*v_j
>
> > V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)
> >
> > Not sure how W*v_avg equals to Sum w_j*v_j ?
>
> V := v_avg
>
I see, thanks for the explanation.
> (yeah, I should clean up this stuff, already said to Josh I would)
>
> > > + * = (W*v_avg + w_i(v_avg - l_i)) / (W + w_i)
> > > + * = v_avg + w_i*l_i/(W + w_i)
> > v_avg - w_i*l_i/(W + w_i) ?
>
> Yup -- seems typing is hard :-)
>
> > > + *
> > > + * l_i' = V' - v_i = v_avg + w_i*l_i/(W + w_i) - (v_avg - l)
> > > + * = l_i - w_i*l_i/(W + w_i)
> > > + *
> > > + * l_i = (W + w_i) * l_i' / W
> > > */
> > [...]
> > > - if (sched_feat(GENTLE_FAIR_SLEEPERS))
> > > - thresh >>= 1;
> > > + load = cfs_rq->avg_load;
> > > + if (curr && curr->on_rq)
> > > + load += curr->load.weight;
> > > +
> > > + lag *= load + se->load.weight;
> > > + if (WARN_ON_ONCE(!load))
> > > + load = 1;
> > > + lag = div_s64(lag, load);
> > >
> > Should we calculate
> > l_i' = l_i * w / (W + w_i) instead of calculating l_i above? I thought we want to adjust
> > the lag(before enqueue) based on the new weight(after enqueued)
>
> We want to ensure the lag after placement is the lag we got before
> dequeue.
>
> I've updated the comment to read like so:
>
> /*
> * If we want to place a task and preserve lag, we have to
> * consider the effect of the new entity on the weighted
> * average and compensate for this, otherwise lag can quickly
> * evaporate.
> *
> * Lag is defined as:
> *
> * l_i = V - v_i <=> v_i = V - l_i
> *
> * And we take V to be the weighted average of all v:
> *
> * V = (\Sum w_j*v_j) / W
> *
> * Where W is: \Sum w_j
> *
> * Then, the weighted average after adding an entity with lag
> * l_i is given by:
> *
> * V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)
> * = (W*V + w_i*(V - l_i)) / (W + w_i)
> * = (W*V + w_i*V - w_i*l_i) / (W + w_i)
> * = (V*(W + w_i) - w_i*l) / (W + w_i)
small typo w_i*l -> w_i*l_i
> * = V - w_i*l_i / (W + w_i)
> *
> * And the actual lag after adding an entity with l_i is:
> *
> * l'_i = V' - v_i
> * = V - w_i*l_i / (W + w_i) - (V - l_i)
> * = l_i - w_i*l_i / (W + w_i)
> *
> * Which is strictly less than l_i. So in order to preserve lag
> * we should inflate the lag before placement such that the
> * effective lag after placement comes out right.
> *
> * As such, invert the above relation for l'_i to get the l_i
> * we need to use such that the lag after placement is the lag
> * we computed before dequeue.
> *
> * l'_i = l_i - w_i*l_i / (W + w_i)
> * = ((W + w_i)*l_i - w_i*l_i) / (W + w_i)
> *
> * (W + w_i)*l'_i = (W + w_i)*l_i - w_i*l_i
> * = W*l_i
> *
> * l_i = (W + w_i)*l'_i / W
> */
Got it, thanks! This is very clear.
thanks,
Chenyu
next prev parent reply other threads:[~2023-04-06 3:05 UTC|newest]
Thread overview: 55+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-28 9:26 [PATCH 00/17] sched: EEVDF using latency-nice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 01/17] sched: Introduce latency-nice as a per-task attribute Peter Zijlstra
2023-03-28 9:26 ` [PATCH 02/17] sched/fair: Add latency_offset Peter Zijlstra
2023-03-28 9:26 ` [PATCH 03/17] sched/fair: Add sched group latency support Peter Zijlstra
2023-03-28 9:26 ` [PATCH 04/17] sched/fair: Add avg_vruntime Peter Zijlstra
2023-03-28 23:57 ` Josh Don
2023-03-29 7:50 ` Peter Zijlstra
2023-04-05 19:13 ` Peter Zijlstra
2023-03-28 9:26 ` [PATCH 05/17] sched/fair: Remove START_DEBIT Peter Zijlstra
2023-03-28 9:26 ` [PATCH 06/17] sched/fair: Add lag based placement Peter Zijlstra
2023-04-03 9:18 ` Chen Yu
2023-04-05 9:47 ` Peter Zijlstra
2023-04-06 3:03 ` Chen Yu [this message]
2023-04-13 15:42 ` Chen Yu
2023-04-13 15:55 ` Chen Yu
2023-03-28 9:26 ` [PATCH 07/17] rbtree: Add rb_add_augmented_cached() helper Peter Zijlstra
2023-03-28 9:26 ` [PATCH 08/17] sched/fair: Implement an EEVDF like policy Peter Zijlstra
2023-03-29 1:26 ` Josh Don
2023-03-29 8:02 ` Peter Zijlstra
2023-03-29 8:06 ` Peter Zijlstra
2023-03-29 8:22 ` Peter Zijlstra
2023-03-29 18:48 ` Josh Don
2023-03-29 8:12 ` Peter Zijlstra
2023-03-29 18:54 ` Josh Don
2023-03-29 8:18 ` Peter Zijlstra
2023-03-29 14:35 ` Vincent Guittot
2023-03-30 8:01 ` Peter Zijlstra
2023-03-30 17:05 ` Vincent Guittot
2023-04-04 12:00 ` Peter Zijlstra
2023-03-28 9:26 ` [PATCH 09/17] sched: Commit to lag based placement Peter Zijlstra
2023-03-28 9:26 ` [PATCH 10/17] sched/smp: Use lag to simplify cross-runqueue placement Peter Zijlstra
2023-03-28 9:26 ` [PATCH 11/17] sched: Commit to EEVDF Peter Zijlstra
2023-03-28 9:26 ` [PATCH 12/17] sched/debug: Rename min_granularity to base_slice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 13/17] sched: Merge latency_offset into slice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 14/17] sched/eevdf: Better handle mixed slice length Peter Zijlstra
2023-03-31 15:26 ` Vincent Guittot
2023-04-04 9:29 ` Peter Zijlstra
2023-04-04 13:50 ` Joel Fernandes
2023-04-05 5:41 ` Mike Galbraith
2023-04-05 8:35 ` Peter Zijlstra
2023-04-05 20:05 ` Joel Fernandes
2023-04-14 11:18 ` Phil Auld
2023-04-16 5:10 ` Joel Fernandes
[not found] ` <20230401232355.336-1-hdanton@sina.com>
2023-04-02 2:40 ` Mike Galbraith
2023-03-28 9:26 ` [PATCH 15/17] [RFC] sched/eevdf: Sleeper bonus Peter Zijlstra
2023-03-29 9:10 ` Mike Galbraith
2023-03-28 9:26 ` [PATCH 16/17] [RFC] sched/eevdf: Minimal vavg option Peter Zijlstra
2023-03-28 9:26 ` [PATCH 17/17] [DEBUG] sched/eevdf: Debug / validation crud Peter Zijlstra
2023-04-03 7:42 ` [PATCH 00/17] sched: EEVDF using latency-nice Shrikanth Hegde
2023-04-10 3:13 ` David Vernet
2023-04-11 2:09 ` David Vernet
[not found] ` <20230410082307.1327-1-hdanton@sina.com>
2023-04-11 10:15 ` Mike Galbraith
[not found] ` <20230411133333.1790-1-hdanton@sina.com>
2023-04-11 14:56 ` Mike Galbraith
[not found] ` <20230412025042.1413-1-hdanton@sina.com>
2023-04-12 4:05 ` Mike Galbraith
2023-04-25 12:32 ` Phil Auld
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=ZC42jZiAp9JNAqj7@chenyu5-mobl1 \
--to=yu.c.chen@intel.com \
--cc=bristot@redhat.com \
--cc=bsegall@google.com \
--cc=chris.hyser@oracle.com \
--cc=corbet@lwn.net \
--cc=dietmar.eggemann@arm.com \
--cc=efault@gmx.de \
--cc=joel@joelfernandes.org \
--cc=joshdon@google.com \
--cc=juri.lelli@redhat.com \
--cc=kprateek.nayak@amd.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mgorman@suse.de \
--cc=mingo@kernel.org \
--cc=patrick.bellasi@matbug.net \
--cc=pavel@ucw.cz \
--cc=peterz@infradead.org \
--cc=pjt@google.com \
--cc=qperret@google.com \
--cc=qyousef@layalina.io \
--cc=rostedt@goodmis.org \
--cc=tim.c.chen@linux.intel.com \
--cc=timj@gnu.org \
--cc=vincent.guittot@linaro.org \
--cc=youssefesmat@chromium.org \
/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).