Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753533AbcDKROK (ORCPT ); Mon, 11 Apr 2016 13:14:10 -0400 Received: from foss.arm.com ([217.140.101.70]:51132 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750879AbcDKROI (ORCPT ); Mon, 11 Apr 2016 13:14:08 -0400 Subject: Re: [PATCH 3/4] sched/fair: Modify accumulated sums for load/util averages To: Yuyang Du , peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> <1460327765-18024-4-git-send-email-yuyang.du@intel.com> Cc: bsegall@google.com, pjt@google.com, morten.rasmussen@arm.com, vincent.guittot@linaro.org, juri.lelli@arm.com From: Dietmar Eggemann Message-ID: <570BDB5C.3000608@arm.com> Date: Mon, 11 Apr 2016 18:14:04 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.6.0 MIME-Version: 1.0 In-Reply-To: <1460327765-18024-4-git-send-email-yuyang.du@intel.com> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3939 Lines: 127 On 10/04/16 23:36, Yuyang Du wrote: > After we dropped the incomplete period, the current period should be > a complete "past" period, since all period boundaries, in the past > or in the future, are predetermined. > > With incomplete current period: > > | | | | | > -------------------* > ^ ^ > | | > current > > With this patch: > > | | | | | > -------------------* > ^ ^ > | | > current > > So, the precomputed sums in __accumulated_sum_N[] and > __accumulated_sum_N32[] should be updated accordingly. > > Update the script to generate the constants: > > print " #: inv_N sum_N" > print "-----------------------" > y = (0.5)**(1/32.0) > x = 2**32 > xx = 1024 > for i in range(0, 32): > if i == 0: > x = x-1 > else: > x = x*y > xx = int(xx*y + 1024) > print "%2d: %#x %8d" % (i, int(x), int(xx)) > So since with this patch series, we always operate on period boundaries you want to add 1024 instead of 1024*y (1024 * 0.5^(1/32) = 1002) for the most recent period in the past? Paul Turner's pelt program could be adapted like this: diff --git a/pelt.c b/pelt.c index b36194e8bb9c..3c6b42e88c2d 100644 --- a/pelt.c +++ b/pelt.c @@ -39,8 +39,8 @@ void calc_yn_sum(int n) printf("sum y^n\n"); printf(" %8s %8s %8s\n", "exact", "floor", "error"); for (i = 1; i <= n; i++) { - sum = (y * sum + y * 1024); - sum_fl = floor(y * sum_fl+ y * 1024); + sum = (y * sum + 1024); + sum_fl = floor(y * sum_fl + 1024); printf("%2d: %8.0f %8.0f %8.0f\n", i, sum, sum_fl, sum_fl - sum); } to achieve this. $ ./pelt sum y^n exact *floor* error 1: 1024 1024 0 2: 2026 2026 -0 ... 31: 23371 23360 -11 32: 23894 23883 -11 > 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) > > Signed-off-by: Yuyang Du > --- > kernel/sched/fair.c | 12 ++++++------ > 1 file changed, 6 insertions(+), 6 deletions(-) > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c > index 68273e8..49e9f1a 100644 > --- a/kernel/sched/fair.c > +++ b/kernel/sched/fair.c > @@ -666,7 +666,7 @@ static unsigned long task_h_load(struct task_struct *p); > */ > #define LOAD_AVG_PERIOD 32 > #define LOAD_AVG_MAX 47742 /* maximum possible load avg */ > -#define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_AVG_MAX */ > +#define LOAD_AVG_MAX_N 347 /* number of full periods to produce LOAD_AVG_MAX */ > > /* Give new sched_entity start runnable values to heavy its load in infant time */ > void init_entity_runnable_average(struct sched_entity *se) > @@ -2591,9 +2591,9 @@ static const u32 __decay_inv_multiply_N[] = { > * over-estimates when re-combining. > */ > static const u32 __accumulated_sum_N[] = { > - 0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103, > - 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082, > - 17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371, > + 0, 1024, 2026, 3006, 3965, 4904, 5822, 6721, 7600, 8461, 9303, > + 10127,10933,11722,12494,13250,13990,14714,15422,16115,16793,17457, > + 18106,18742,19364,19973,20569,21152,21722,22280,22826,23360,23883, > }; > > /* > @@ -2601,8 +2601,8 @@ static const u32 __accumulated_sum_N[] = { > * lower integers. > */ > static const u32 __accumulated_sum_N32[] = { > - 0, 23371, 35056, 40899, 43820, 45281, > - 46011, 46376, 46559, 46650, 46696, 46719, > + 0, 23883, 35824, 41795, 44780, 46273, > + 47019, 47392, 47579, 47672, 47719, 47742, > }; > > /* >