From patchwork Mon Apr 11 17:14:04 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dietmar Eggemann X-Patchwork-Id: 65555 Delivered-To: patch@linaro.org Received: by 10.140.93.198 with SMTP id d64csp1474066qge; Mon, 11 Apr 2016 10:14:13 -0700 (PDT) X-Received: by 10.98.40.200 with SMTP id o191mr34359374pfo.83.1460394853157; Mon, 11 Apr 2016 10:14:13 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id gi2si4617323pac.105.2016.04.11.10.14.12; Mon, 11 Apr 2016 10:14:13 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753535AbcDKROK (ORCPT + 29 others); 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 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 8722B28; Mon, 11 Apr 2016 10:12:54 -0700 (PDT) Received: from [10.1.207.26] (e107985-lin.cambridge.arm.com [10.1.207.26]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 04EC03F25F; Mon, 11 Apr 2016 10:14:05 -0700 (PDT) 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> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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: 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, > }; > > /* > 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); }