From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754247AbdDKJk1 (ORCPT ); Tue, 11 Apr 2017 05:40:27 -0400 Received: from mail-wr0-f181.google.com ([209.85.128.181]:34980 "EHLO mail-wr0-f181.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752191AbdDKJkZ (ORCPT ); Tue, 11 Apr 2017 05:40:25 -0400 Date: Tue, 11 Apr 2017 11:40:21 +0200 From: Vincent Guittot To: Peter Zijlstra Cc: mingo@kernel.org, linux-kernel@vger.kernel.org, dietmar.eggemann@arm.com, Morten.Rasmussen@arm.com, yuyang.du@intel.com, pjt@google.com, bsegall@google.com Subject: Re: [PATCH v2] sched/fair: update scale invariance of PELT Message-ID: <20170411094021.GA17811@linaro.org> References: <1491815909-13345-1-git-send-email-vincent.guittot@linaro.org> <20170410173802.orygigjbcpefqtdv@hirez.programming.kicks-ass.net> <20170411075221.GA30421@linaro.org> <20170411085305.aik6gdy6n3wa22ok@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20170411085305.aik6gdy6n3wa22ok@hirez.programming.kicks-ass.net> User-Agent: Mutt/1.5.24 (2015-08-30) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Le Tuesday 11 Apr 2017 à 10:53:05 (+0200), Peter Zijlstra a écrit : > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > > > > > Thanks for the rebase. > > > > > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > > > > > Ok, so let me try and paraphrase what this patch does. > > > > > > So consider a task that runs 16 out of our 32ms window: > > > > > > running idle > > > |---------|---------| > > > > > > > > > You're saying that when we scale running with the frequency, suppose we > > > were at 50% freq, we'll end up with: > > > > > > run idle > > > |----|---------| > > > > > > > > > Which is obviously a shorter total then before; so what you do is add > > > back the lost idle time like: > > > > > > run lost idle > > > |----|----|---------| > > > > > > > > > to arrive at the same total time. Which seems to make sense. > > > > Yes > > OK, bear with me. > > > So we have: > > > util_sum' = utilsum * y^p + > > p-1 > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > n=1 > > For the unscaled version, right? Yes for the running state. For sleeping state, it's just util_sum' = utilsum * y^p > > > > Now for the scaled version, instead of adding a full 'd1,d2,d3' running > segments, we want to add partially running segments, where r=f*d/f_max, > and lost segments l=d-r to fill out the idle time. > > But afaict we then end up with (F=f/f_max): > > > util_sum' = utilsum * y^p + > > p-1 > F * d1 * y^p + F * 1024 * \Sum y^n + F * d3 * y^0 > n=1 you also have a longer running time as it runs slower. We make the assumption that d1+d2+d3 = (d1'+d2'+d3') * F If we consider that we cross a decay window, we still have the d1 to complete the past one but then p'*F= p and d'3 will be the remaining part of the current window and most probably not equal to d3 so we have with current invariance: util_sum' = utilsum * y^(p/F) + (p/F - 1) F * d1 * y^(p/F) + F * 1024 * \Sum y^n + F * d'3 * y^0 n=1 with the new invariance we have util_sum' = utilsum * y^(F*p/F) + (F*p/F - 1) d1 * y^(F*p/F) + 1024 * \Sum y^n + d3 * y^0 n=1 For a sleeping time of d at max capacity, we have a sleeping time d'=d-l, with l the lost time of the previous running time With the current implementation: util_sum' = utilsum * y^(p') util_sum' = utilsum * y^(p-l) With the new invaraince, we have util_sum' = utilsum * y^(p'+l) util_sum' = utilsum * y^(p-l+l) > > And we can collect the common term F: > > util_sum' = utilsum * y^p + > > p-1 > F * (d1 * y^p + 1024 * \Sum y^n + d3 * y^0) > n=1 > > > Which is exactly what we already did. In the new invariance scale, the F is applied on p not on the contribution value > > > So now I'm confused. Where did I go wrong? > > > Because by scaling the contribution we get the exact result of doing the > smaller 'running' + 'lost' segments.