From patchwork Tue Sep 8 16:53:31 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Morten Rasmussen X-Patchwork-Id: 53274 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-wi0-f197.google.com (mail-wi0-f197.google.com [209.85.212.197]) by patches.linaro.org (Postfix) with ESMTPS id 0A2F722B05 for ; Tue, 8 Sep 2015 16:49:49 +0000 (UTC) Received: by wicgb1 with SMTP id gb1sf38783601wic.3 for ; Tue, 08 Sep 2015 09:49:48 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:date:from:to:cc:subject:message-id :references:mime-version:content-type:content-disposition :in-reply-to:user-agent:sender:precedence:list-id:x-original-sender :x-original-authentication-results:mailing-list:list-post:list-help :list-archive:list-unsubscribe; bh=Z9hnsfydPsrmc9GMbiXCgz52gKLLKc/BxoIiU9/zA2Q=; b=gq+4UkDe1FnFCEhtSlds6lVzpsXL81aAk3nd+jzkqiPUpwuLZiJU8z3r6p6sWZfVdO glUv+m4Rd2OcAvRslLgXqE5CsjB7R80K0826Lo/FRZp7LIDTw2a7XhThEt4CDuAezzYA RI0Bi3TD16HoSN5wFTTMLdOmyGRSaXNqCvoAu3DF7IqWpW/A5MjKp/Nu4VMLCWHwGfxk XKobuFGXK0NHMQvpybGdc8G78irib1POdvJ2Ydha7refBnqBk10bN1/qNZGVRUOKcoDE Z9D3SVdAt5+Hl7iGDsZ2KBWRYZ4f+5BfJ5A2txwl5CaiEosHAvYi3ckt3dySL5dMZXae KLqA== X-Gm-Message-State: ALoCoQmc+2D0DjzALgF+5ms/RVL3zD5AwQyTyY5CE4FHih73pKWowmeKgCyqNKPFMVXJn3rxsK1M X-Received: by 10.112.170.67 with SMTP id ak3mr6881674lbc.6.1441730988351; Tue, 08 Sep 2015 09:49:48 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.19.134 with SMTP id f6ls72487lae.74.gmail; Tue, 08 Sep 2015 09:49:48 -0700 (PDT) X-Received: by 10.152.18.194 with SMTP id y2mr23993786lad.88.1441730988130; Tue, 08 Sep 2015 09:49:48 -0700 (PDT) Received: from mail-la0-f43.google.com (mail-la0-f43.google.com. [209.85.215.43]) by mx.google.com with ESMTPS id l9si3748646laf.101.2015.09.08.09.49.48 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 08 Sep 2015 09:49:48 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.43 as permitted sender) client-ip=209.85.215.43; Received: by lanb10 with SMTP id b10so72805886lan.3 for ; Tue, 08 Sep 2015 09:49:48 -0700 (PDT) X-Received: by 10.112.51.142 with SMTP id k14mr12958033lbo.76.1441730987984; Tue, 08 Sep 2015 09:49:47 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.59.35 with SMTP id w3csp1093142lbq; Tue, 8 Sep 2015 09:49:46 -0700 (PDT) X-Received: by 10.107.137.162 with SMTP id t34mr46485465ioi.103.1441730986580; Tue, 08 Sep 2015 09:49:46 -0700 (PDT) Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id y8si6447068pdj.156.2015.09.08.09.49.45; Tue, 08 Sep 2015 09:49:46 -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; Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755457AbbIHQto (ORCPT + 28 others); Tue, 8 Sep 2015 12:49:44 -0400 Received: from foss.arm.com ([217.140.101.70]:55481 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753454AbbIHQtl (ORCPT ); Tue, 8 Sep 2015 12:49:41 -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 2011C75; Tue, 8 Sep 2015 09:49:50 -0700 (PDT) Received: from e105550-lin.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id ADFB03F318; Tue, 8 Sep 2015 09:49:38 -0700 (PDT) Date: Tue, 8 Sep 2015 17:53:31 +0100 From: Morten Rasmussen To: Peter Zijlstra Cc: Vincent Guittot , Dietmar Eggemann , Steve Muckle , "mingo@redhat.com" , "daniel.lezcano@linaro.org" , "yuyang.du@intel.com" , "mturquette@baylibre.com" , "rjw@rjwysocki.net" , Juri Lelli , "sgurrappadi@nvidia.com" , "pang.xunlei@zte.com.cn" , "linux-kernel@vger.kernel.org" Subject: Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Message-ID: <20150908165331.GC27098@e105550-lin.cambridge.arm.com> References: <1439569394-11974-1-git-send-email-morten.rasmussen@arm.com> <1439569394-11974-6-git-send-email-morten.rasmussen@arm.com> <55E8DD00.2030706@linaro.org> <55EDAF43.30500@arm.com> <55EDDD5A.70904@arm.com> <20150908122606.GH3644@twins.programming.kicks-ass.net> <20150908125205.GW18673@twins.programming.kicks-ass.net> <20150908143157.GA27098@e105550-lin.cambridge.arm.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20150908143157.GA27098@e105550-lin.cambridge.arm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org Precedence: list List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: morten.rasmussen@arm.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.43 as permitted sender) smtp.mailfrom=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote: > On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote: > > > > Something like teh below.. > > > > Another thing to ponder; the downside of scaled_delta_w is that its > > fairly likely delta is small and you loose all bits, whereas the weight > > is likely to be large can could loose a fwe bits without issue. > > That issue applies both to load and util. > > > > > That is, in fixed point scaling like this, you want to start with the > > biggest numbers, not the smallest, otherwise you loose too much. > > > > The flip side is of course that now you can share a multiplcation. > > But if we apply the scaling to the weight instead of time, we would only > have to apply it once and not three times like it is now? So maybe we > can end up with almost the same number of multiplications. > > We might be loosing bits for low priority task running on cpus at a low > frequency though. Something like the below. We should be saving one multiplication. --- 8< --- From: Morten Rasmussen Date: Tue, 8 Sep 2015 17:15:40 +0100 Subject: [PATCH] sched/fair: Scale load/util contribution rather than time When updating load/util tracking the time delta might be very small (1) in many cases, scaling it futher down with frequency and cpu invariance scaling might cause us to loose precision. Instead of scaling time we can scale the weight of the task for load and the capacity for utilization. Both weight (>=15) and capacity should be significantly bigger in most cases. Low priority tasks might still suffer a bit but worst should be improved, as weight is at least 15 before invariance scaling. Signed-off-by: Morten Rasmussen --- kernel/sched/fair.c | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 9301291..d5ee72a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2519,8 +2519,6 @@ static u32 __compute_runnable_contrib(u64 n) #error "load tracking assumes 2^10 as unit" #endif -#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT) - /* * We can represent the historical contribution to runnable average as the * coefficients of a geometric series. To do this we sub-divide our runnable @@ -2553,10 +2551,10 @@ static __always_inline int __update_load_avg(u64 now, int cpu, struct sched_avg *sa, unsigned long weight, int running, struct cfs_rq *cfs_rq) { - u64 delta, scaled_delta, periods; + u64 delta, periods; u32 contrib; - unsigned int delta_w, scaled_delta_w, decayed = 0; - unsigned long scale_freq, scale_cpu; + unsigned int delta_w, decayed = 0; + unsigned long scaled_weight = 0, scale_freq, scale_freq_cpu = 0; delta = now - sa->last_update_time; /* @@ -2577,8 +2575,13 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa, return 0; sa->last_update_time = now; - scale_freq = arch_scale_freq_capacity(NULL, cpu); - scale_cpu = arch_scale_cpu_capacity(NULL, cpu); + if (weight || running) + scale_freq = arch_scale_freq_capacity(NULL, cpu); + if (weight) + scaled_weight = weight * scale_freq >> SCHED_CAPACITY_SHIFT; + if (running) + scale_freq_cpu = scale_freq * arch_scale_cpu_capacity(NULL, cpu) + >> SCHED_CAPACITY_SHIFT; /* delta_w is the amount already accumulated against our next period */ delta_w = sa->period_contrib; @@ -2594,16 +2597,15 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa, * period and accrue it. */ delta_w = 1024 - delta_w; - scaled_delta_w = cap_scale(delta_w, scale_freq); if (weight) { - sa->load_sum += weight * scaled_delta_w; + sa->load_sum += scaled_weight * delta_w; if (cfs_rq) { cfs_rq->runnable_load_sum += - weight * scaled_delta_w; + scaled_weight * delta_w; } } if (running) - sa->util_sum += scaled_delta_w * scale_cpu; + sa->util_sum += delta_w * scale_freq_cpu; delta -= delta_w; @@ -2620,25 +2622,23 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa, /* Efficiently calculate \sum (1..n_period) 1024*y^i */ contrib = __compute_runnable_contrib(periods); - contrib = cap_scale(contrib, scale_freq); if (weight) { - sa->load_sum += weight * contrib; + sa->load_sum += scaled_weight * contrib; if (cfs_rq) - cfs_rq->runnable_load_sum += weight * contrib; + cfs_rq->runnable_load_sum += scaled_weight * contrib; } if (running) - sa->util_sum += contrib * scale_cpu; + sa->util_sum += contrib * scale_freq_cpu; } /* Remainder of delta accrued against u_0` */ - scaled_delta = cap_scale(delta, scale_freq); if (weight) { - sa->load_sum += weight * scaled_delta; + sa->load_sum += scaled_weight * delta; if (cfs_rq) - cfs_rq->runnable_load_sum += weight * scaled_delta; + cfs_rq->runnable_load_sum += scaled_weight * delta; } if (running) - sa->util_sum += scaled_delta * scale_cpu; + sa->util_sum += delta * scale_freq_cpu; sa->period_contrib += delta;