Date: Fri, 28 Apr 2017 16:52:59 +0100
From: Morten Rasmussen <morten.rasmussen@arm.com>
To: Vincent Guittot <vincent.guittot@linaro.org>
Cc: peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org,
        dietmar.eggemann@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: <20170428155258.GA12012@e105550-lin.cambridge.arm.com>
References: <1491815909-13345-1-git-send-email-vincent.guittot@linaro.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1491815909-13345-1-git-send-email-vincent.guittot@linaro.org>
User-Agent: Mutt/1.5.24 (2015-08-30)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 7450
Lines: 179

Hi Vincent,

Sorry for crashing the party this late. As you know, it takes a long
period of uninterrupted review time to properly review PELT stuff.

Disclaimer: I haven't read the rest of the thread yet.

On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote:
> The current implementation of load tracking invariance scales the
> contribution with current frequency and uarch performance (only for
> utilization) of the CPU. One main result of this formula is that the
> figures are capped by current capacity of CPU. Another one is that the
> load_avg is not invariant because not scaled with uarch.
> 
> The util_avg of a periodic task that runs r time slots every p time slots
> varies in the range :
> 
>     U * (1-y^r)/(1-y^p) * y^i < Utilization < U * (1-y^r)/(1-y^p)
> 
> with U is the max util_avg value = SCHED_CAPACITY_SCALE
> 
> At a lower capacity, the range becomes:
> 
>     U * C * (1-y^r')/(1-y^p) * y^i' < Utilization <  U * C * (1-y^r')/(1-y^p)
> 
> with C reflecting the compute capacity ratio between current capacity and
> max capacity.
> 
> so C tries to compensate changes in (1-y^r') but it can't be accurate.

I would say that C is trying to compensate for difference in running
time, which is difference between r and r'. But I think that is what you
are saying as well.

> Instead of scaling the contribution value of PELT algo, we should scale the
> running time. The PELT signal aims to track the amount of computation of
> tasks and/or rq so it seems more correct to scale the running time to
> reflect the effective amount of computation done since the last update.
> 
> In order to be fully invariant, we need to apply the same amount of
> running time and idle time whatever the current capacity. Because running
> at lower capacity implies that the task will run longer, we have to track
> the amount of "stolen" idle time and to apply it when task becomes idle.

Overall, I agree that scaling time according to compute capacity is the
right thing to do, if we want accurate scale-invariance. The current
implementation is an approximation which isn't perfect, but it is easy
to implement.

One thing that became clear to me after reading the patch and tried to
recreate what it does, is that you don't seem to consider waiting time
and the patch doesn't scale it. That is fine for utilization, but it
breaks load. For load, you have to scale waiting time as well, which
makes things rather complicated as you would need two scaled time
deltas, one for utilization and one for load.

What currently happens is that waiting tasks as low OPPs are
accumulating load at the rate of the highest OPP without accumulating
"stolen" time. So waiting tasks accumulate too much load at lower OPPs.
We have confirmed it by scheduling two periodic tasks on the same cpu
and verified that the load does ramp up faster than it should.

For the aggregate cfs_rq util/load sums, I can't convince myself whether
they break when "stolen" time isn't inserted at the same time in the
task signal as it is for the cfs_rq signal. If you have two periodic
tasks scheduled on the same cpu with aligned periods, then the first
task will inject its stolen time as soon as it finishes, while the
aggregate sum won't inject the stolen time until it has completed the
second task and inject the stolen for both tasks at the same time. As
long as no tasks are migrated to/from the cpu it should work, but I'm not
convinced that it works if tasks are migrated or new tasks show up
before the stolen time has been committed to the aggregate sum. Have you
looked more into this?

Another question is what happens to blocked utilization? IIUC, the
stolen time is injected when the task wakes up again so the utilization
drops to where it should be. Does that mean that the blocked
contribution of the task is inflated the entire time while it is
blocked?

> But once we have reached the maximum utilization value (SCHED_CAPACITY_SCALE),
> it means that the task is seen as an always-running task whatever the
> capacity of the cpu (even at max compute capacity). In this case, we can
> discard the "stolen" idle times which becomes meaningless. In order to
> cope with rounding effect of PELT algo we take a margin and consider task
> with utilization greater than 1000 (vs 1024 max) as an always-running task.

I understand why the threshold is necessary, but I'm slightly concerned
that it might introduce corner cases where things could go very wrong. I
haven't proven that it is indeed a problem, but is it possible to have
aggregate sum of utilization >1000 without the cpu being fully utilized?
So the tasks will have their stolen time injected, but the cfs_rq
utilization won't?

> 
> Then, we can use the same algorithm for both utilization and load and
> simplify __update_load_avg now that the load of a task doesn't have to be
> capped by CPU uarch.

As said above, waiting time has to be handled differently for
utilization and load.

> The responsivness of PELT is improved when CPU is not running at max
> capacity with this new algorithm. I have put below some examples of
> duration to reach some typical load values according to the capacity of the
> CPU with current implementation and with this patch.
> 
> Util (%)     max capacity  half capacity(mainline)  half capacity(w/ patch)
> 972 (95%)    138ms         not reachable            276ms
> 486 (47.5%)  30ms          138ms                     60ms
> 256 (25%)    13ms           32ms                     26ms
> 
> On my hikey (octo ARM platform) with schedutil governor, the time to reach
> max OPP when starting from a null utilization, decreases from 223ms with
> current scale invariance down to 121ms with the new algorithm. For this
> test, i have enable arch_scale_freq for arm64.

Note that the time to reach a specific utilization with your
implementation depends on the OPP. The lower the OPP, the slower
utilization accumulates.

[...]

> @@ -2852,19 +2850,54 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
>  	}
>  	sa->period_contrib = delta;
>  
> -	contrib = cap_scale(contrib, scale_freq);
>  	if (weight) {
>  		sa->load_sum += weight * contrib;
>  		if (cfs_rq)
>  			cfs_rq->runnable_load_sum += weight * contrib;
>  	}
>  	if (running)
> -		sa->util_sum += contrib * scale_cpu;
> +		sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;
>  
>  	return periods;
>  }
>  
>  /*
> + * Scale the time to reflect the effective amount of computation done during
> + * this delta time.
> + */
> +static __always_inline u64
> +scale_time(u64 delta, int cpu, struct sched_avg *sa,
> +		unsigned long weight, int running)
> +{
> +	if (running) {
> +		sa->stolen_idle_time += delta;
> +		/*
> +		 * scale the elapsed time to reflect the real amount of
> +		 * computation
> +		 */
> +		delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu));
> +		delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu));
> +
> +		/*
> +		 * Track the amount of stolen idle time due to running at
> +		 * lower capacity
> +		 */
> +		sa->stolen_idle_time -= delta;
> +	} else if (!weight) {
> +		if (sa->util_sum < (LOAD_AVG_MAX * 1000)) {
> +			/*
> +			 * Add the idle time stolen by running at lower compute
> +			 * capacity
> +			 */
> +			delta += sa->stolen_idle_time;
> +		}
> +		sa->stolen_idle_time = 0;
> +	}
> +
> +	return delta;

As mentioned above, waiting time, i.e. !running && weight, is not
scaled, which causes trouble for load.

Morten