Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Thu, 6 Apr 2023 11:03:41 +0800
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
Message-ID: <ZC42jZiAp9JNAqj7@chenyu5-mobl1>
References: <20230328092622.062917921@infradead.org>
 <20230328110353.988000317@infradead.org>
 <ZCqZzp98q806qfip@chenyu5-mobl1>
 <20230405094720.GA4253@hirez.programming.kicks-ass.net>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20230405094720.GA4253@hirez.programming.kicks-ass.net>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?GR2mJicNrP7hafck0LX6OH+eOOM9DZkkopXf+SHRDCPv3N9FdO8bdwEGhpyp?=
 =?us-ascii?Q?2YvyuApY07eB0g/S8RlyBCF9+Mg50sG9KgMXob4szKampY+5gjW6f2TsFdY2?=
 =?us-ascii?Q?lSNWTMLF5cJPy/64eJVjuQhgb2OORES8Zd9Emmm4jwIU83pZqtKGUqOe3iPT?=
 =?us-ascii?Q?YQPVb6dINvaYq5DP23EWj7bD+XG7BmGcjg7PD2hTbPi0oE6LKO7WKR/DU/5o?=
 =?us-ascii?Q?XRw2HZi4osfAvlFev+Dtz02Zatz1GrVAaRyOF9nAS1DT/Dl6STJxJ7qeE8U/?=
 =?us-ascii?Q?UyzSZtHxmMINll94YiBT8Jn+tut24sy0/ChZyGNfpJ23zazcx0iW8V/ZHVuu?=
 =?us-ascii?Q?sob9Iue6ETFRVusHl+I9w1uLUwcX5+Y9n3tKrGjDjuw+JJE82TpvjXpaXr7P?=
 =?us-ascii?Q?M8cT6d6+UxFl2g62eWDVaojg7Z0S05+vA2DC+h/A5CzaLiYZdE10ikDe3kfk?=
 =?us-ascii?Q?HmA2Me8BtuNYAqiYCkz1ZDiG5T2W2/uJsQzo/PRl1gcNfuvYE3anShqVXWoX?=
 =?us-ascii?Q?GI9ynt0YjV9w/Qz8L1scolv9Iy+LnrMM+cUbU62QWI8d490Y0eTF/hJ5GD4W?=
 =?us-ascii?Q?gknC1HPvQTQT0yss5rfUTjDV4BJh7CV1S4VSamB6ExAOk50tVtl7eB4FUTXE?=
 =?us-ascii?Q?rhNmSAv0DrB6SDLhZ0aZpMKxrXWStxylMiZ7NHaUZYCLeITNiQdQzUU1csMb?=
 =?us-ascii?Q?1soGmJoZ+162ZccW263fyDxbmwEceXIvOwY2h10g9iQvtJO27OPFcqWwoCQY?=
 =?us-ascii?Q?BNEwkiuB8hRdHCbTT3b+3GBVZ4m9slwhPLOw+akTRjyMVpmf37tYwhgYnTIZ?=
 =?us-ascii?Q?+23rkCOBfpv/ODR/SYXvz8GW6E7xpsk/seRZ4jcOWhQ8CqtKxY7tM2hLj+5F?=
 =?us-ascii?Q?Gr2RDVMi20BzcNFDwm7Rnip0dxXsQDu3XXLP49+cwkC0kGV9dST2E8N+pJ/A?=
 =?us-ascii?Q?fipbsaZPN64Qgbp5tK8npr1aiBLRMyEgeYB2yzjAKQ/cFBBvZha7sFM2L1gn?=
 =?us-ascii?Q?UvVk9U5CvTJcNwK9MjTebzfrKyDw48egEaBziECMmd/rkFvuvoGZoCCMZq5s?=
 =?us-ascii?Q?gu3Q0PMHo2ixrzUlU9GbcACdUudYbIby3rBJWwUBVckPE2dstuZHqW7SyOD6?=
 =?us-ascii?Q?2od1M5xjwlzbfMLsMtvoSnd7kA9CjBlMlhyXJVfdVd1pIMKadtgl4HOVmiI8?=
 =?us-ascii?Q?rYs/iRwiBKCUavebQLv0xJfXpDAF+6yejY7c9eVc2v7ydXk/75ollA59XkyD?=
 =?us-ascii?Q?lr37vkfYdUDqlBAHQoLUi2pRon0VVz2HLdxWibBuYd4H5qgQBeeclIr1qwSV?=
 =?us-ascii?Q?djVy0rCxkcsPTQ5jwFWsD9zAYzBh8jisfmPaLL6CQbpOU9GfPdnX2AbGT4yt?=
 =?us-ascii?Q?BdHJPB13ujmNb85h1YTIgYwjmxUBfRLLpT6DgQ7qTer6Qwf2illMa4m8YTJz?=
 =?us-ascii?Q?hMY8jjbghg6OoLVP6tgaw69C04YrC9U/lWi5QGBq0UmRBJfyEZR23jJGHhGa?=
 =?us-ascii?Q?MFUWmtRQgngg6XuHjoXgikxOZ22kUoAdugWGXXA8Kx7+xUDoLxoJ+VJnVZmG?=
 =?us-ascii?Q?ZQ3/URp71TnDe2spcO2BxReBuabsv2VoI5Ln1nlT?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 40c17087-1b6a-4e2f-4ec0-08db364b9254
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Apr 2023 03:04:01.1294
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: Z2+mHdMhr1jj2VN7k2QNm8fWiRz0E4elYS691cZUZCkGT4LNqzmQONazgz/7BCMGXTJ6FF4DvCJP7EazcVxW3g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR11MB6054
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-2.5 required=5.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED,SPF_HELO_NONE,
        SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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