From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752072AbdDKNJ0 (ORCPT ); Tue, 11 Apr 2017 09:09:26 -0400 Received: from mail-wr0-f174.google.com ([209.85.128.174]:35743 "EHLO mail-wr0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751564AbdDKNJY (ORCPT ); Tue, 11 Apr 2017 09:09:24 -0400 Date: Tue, 11 Apr 2017 15:09:20 +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: <20170411130920.GB22895@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> <20170411094021.GA17811@linaro.org> <20170411104136.33hkvzlmoa7zc72l@hirez.programming.kicks-ass.net> <20170411104949.eat4o37rlqiiobeu@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: <20170411104949.eat4o37rlqiiobeu@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 à 12:49:49 (+0200), Peter Zijlstra a écrit : > > Lets go back to the unscaled version: > > running idle > |*********|---------| > > With the current code, that would effectively end up like (again > assuming 50%): > > running idle > |*_*_*_*_*|---------| > > > Time stays the same, but we add extra idle cycles. In fact it's not really like that because this doesn't reflect the impact of the decay window which is not linear with time For a task that run at max freq (1) |-------|-------|-------|---- **** **** ---****------------****------ The same task running at half frequency, will run twice longer |-------|-------|-------|---- ******** ******** ---********--------********-- With the current implementation, we are not inserting idle cycle but dividing the contribution by half in order to compensate the fact that the task will run twice longer: (2) |-------|-------|-------|---- ---********--------********-- But the final result is neither equal to |-------|-------|-------|---- * * * * * * * * ---*_*_*_*---------*_*_*_*--- nor to (1) as described below: Let assume all durations are aligned with decay window. This will simplify the formula for the explanation and will not change the demonstration. We can come back on the full equation later on. For (1), we have the equation that you write previously: util_sum' = utilsum * y^p + p-1 d1 * y^p + 1024 * \Sum y^n + d3 * y^0 n=1 Which becomes like below when we are aligned to decay window (d1 and d3 are null) (A) util_sum' = utilsum * y^p + p-1 1024 * \Sum y^n n=1 The running time at max frequency is d and p is the number of decay window period In this case p = d/1024us and l = 0 For (2), task runs at half frequency so the duration d' is twice longer than d and p'=2*p. In current implementation, we compensate the increase of running duration (and lost idle time) by dividing the contribution by 2: util_sum' = utilsum * y^p' + p'-1 512 * \Sum y^n n=1 (B) util_sum' = utilsum * y^(2*p) + 2*p-1 512 * \Sum y^n n=1 With the new scale invariance, we have the following pattern before scaling time: |-------|-------|-------|-- ******** ******** ---********--------******** Task still runs at half frequency so the duration d' is twice longer than d and p': p'=2*p just like for (2). But before computing util_sum', we change the temporal referencial to reflect what would have been done at max frequency: we scale the running time (divide it by 2) in order to have something like: |-------|-------|-------|-- **** **** ---****____--------****____ so we now have a duration d'' that is half d'and a number of period p'' that is half p' so p'' = 1/2 * p' == p util_sum' = utilsum * y^p'' + p''-1 1024 * \Sum y^n n=1 util_sum' = utilsum * y^p + p-1 512 * \Sum y^n n=1 Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay window when the task is sleeping so at the end we have a number of decay window of p''+l = p'' so we still have the same amount of decay window than previously. >