Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752776AbdHHXLV (ORCPT ); Tue, 8 Aug 2017 19:11:21 -0400 Received: from mail-oi0-f50.google.com ([209.85.218.50]:35356 "EHLO mail-oi0-f50.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752495AbdHHXLS (ORCPT ); Tue, 8 Aug 2017 19:11:18 -0400 MIME-Version: 1.0 In-Reply-To: References: <20170804154023.26874-1-joelaf@google.com> From: Joel Fernandes Date: Tue, 8 Aug 2017 16:11:16 -0700 Message-ID: Subject: Re: [PATCH] sched/fair: Make PELT signal more accurate To: Vincent Guittot Cc: linux-kernel , kernel-team@android.com, Peter Zijlstra , Juri Lelli , Brendan Jackman , Dietmar Eggeman , Ingo Molnar Content-Type: text/plain; charset="UTF-8" Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6128 Lines: 138 Hi Vincent, On Mon, Aug 7, 2017 at 6:24 AM, Vincent Guittot wrote: > Hi Joel, > > On 4 August 2017 at 17:40, Joel Fernandes wrote: >> The PELT signal (sa->load_avg and sa->util_avg) are not updated if the amount >> accumulated during a single update doesn't cross a period boundary. This is >> fine in cases where the amount accrued is much smaller than the size of a >> single PELT window (1ms) however if the amount accrued is high then the >> relative error (calculated against what the actual signal would be had we >> updated the averages) can be quite high - as much 3-6% in my testing. On >> plotting signals, I found that there are errors especially high when we update >> just before the period boundary is hit. These errors can be significantly >> reduced if we update the averages more often. >> >> Inorder to fix this, this patch does the average update by also checking how >> much time has elapsed since the last update and update the averages if it has >> been long enough (as a threshold I chose 128us). > > Why 128us and not 512us as an example ? I picked it because I see it shows a good reduction in the error to fewer occurrences. > 128us threshold means that util/load_avg can be computed 8 times more > often and this means up to 16 times more call to div_u64 Yes this is true, however since I'm using the 'delta' instead of period_contrib, its only does the update every 128us, however if several updates fall within a 128us boundary then those will be rate limited. So say we have a flood of updates, then the updates have to be spaced every 128us to reach the maximum number of division, I don't know whether this is a likely situation or would happen very often? I am planning to run some benchmarks and check that there is no regression as well as Peter mentioned about the performance aspect. >> In order to compare the signals with/without the patch I created a synthetic >> test (20ms runtime, 100ms period) and analyzed the signals and created a report >> on the analysis data/plots both with and without the fix: >> http://www.linuxinternals.org/misc/pelt-error.pdf > > The glitch described in page 2 shows a decrease of the util_avg which > is not linked to accuracy of the calculation but due to the use of the > wrong range when computing util_avg. Yes, and I corrected the graphs this time to show what its like after your patch and confirm that there is STILL a glitch. You are right that there isn't a reduction after your patch, however in my updated graphs there is a glitch and its not a downward peak but a stall in the update, the error is still quite high and can be as high as the absolute 2% error, in my update graphs I show an example where its ~ 1.8% (18 / 1024). Could you please take a look at my updated document? I have included new graph and traces there and color coded them so its easy to correlate the trace lines to the error in the graph: Here's the updated new link: https://github.com/joelagnel/joelagnel.github.io/blob/master/misc/pelt-error-rev2.pdf > commit 625ed2bf049d "sched/cfs: Make util/load_avg more stable" fixes > this glitch. > And the lower peak value in page 3 is probably linked to the inaccuracy This is not true. The reduction in peak in my tests which happen even after your patch is because of the dequeue that happens just before the period boundary is hit. Could you please take a look at the updated document in the link above? In there I show in the second example with a trace that corresponds the reduction in peak during the dequeue and is because of the delay in update. These errors go away with my patch. > I agree that there is an inaccuracy (the max absolute value of 22) but > that's in favor of less overhead. Have you seen wrong behavior because > of this inaccuracy ? I haven't tried to nail this to a wrong behavior however since other patches have been posted to fix inaccuracy and I do see we reach the theoretical maximum error on quite a few occassions, I think its justifiable. Also the overhead is minimal if updates aren't happening several times in a window, and at 128us interval, and the few times that the update does happen, the division is performed only during those times. So incases where it does fix the error, it does so with minimal overhead. I do agree with the overhead point and I'm planning to do more tests with hackbench to confirm overhead is minimal. I'll post some updates about it soon. Thanks! -Joel > >> >> With the patch, the error in the signal is significantly reduced, and is >> non-existent beyond a small negligible amount. >> >> Cc: Vincent Guittot >> Cc: Peter Zijlstra >> Cc: Juri Lelli >> Cc: Brendan Jackman >> Cc: Dietmar Eggeman >> Signed-off-by: Joel Fernandes >> --- >> kernel/sched/fair.c | 8 ++++++-- >> 1 file changed, 6 insertions(+), 2 deletions(-) >> >> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c >> index 4f1825d60937..1347643737f3 100644 >> --- a/kernel/sched/fair.c >> +++ b/kernel/sched/fair.c >> @@ -2882,6 +2882,7 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa, >> unsigned long weight, int running, struct cfs_rq *cfs_rq) >> { >> u64 delta; >> + int periods; >> >> delta = now - sa->last_update_time; >> /* >> @@ -2908,9 +2909,12 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa, >> * accrues by two steps: >> * >> * Step 1: accumulate *_sum since last_update_time. If we haven't >> - * crossed period boundaries, finish. >> + * crossed period boundaries and the time since last update is small >> + * enough, we're done. >> */ >> - if (!accumulate_sum(delta, cpu, sa, weight, running, cfs_rq)) >> + periods = accumulate_sum(delta, cpu, sa, weight, running, cfs_rq); >> + >> + if (!periods && delta < 128) >> return 0; >> >> /* >> -- >> 2.14.0.rc1.383.gd1ce394fe2-goog >>