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;
Subject: Re: [PATCH 00/10] steal tasks to improve CPU utilization
To:     Valentin Schneider <valentin.schneider@arm.com>,
        Peter Zijlstra <peterz@infradead.org>
Cc:     mingo@redhat.com, subhra.mazumdar@oracle.com,
        dhaval.giani@oracle.com, daniel.m.jordan@oracle.com,
        pavel.tatashin@microsoft.com, matt@codeblueprint.co.uk,
        umgwanakikbuti@gmail.com, riel@redhat.com, jbacik@fb.com,
        juri.lelli@redhat.com, linux-kernel@vger.kernel.org
References: <1540220381-424433-1-git-send-email-steven.sistare@oracle.com>
 <20181022170421.GF3117@worktop.programming.kicks-ass.net>
 <8e38ce84-ec1a-aef7-4784-462ef754f62a@oracle.com>
 <a43db228-ddd0-c30f-6ba0-8d54f17f57c7@arm.com>
From:   Steven Sistare <steven.sistare@oracle.com>
Organization: Oracle Corporation
Message-ID: <abf3ae2a-a7f4-2524-0da6-09599928b47a@oracle.com>
Date:   Wed, 24 Oct 2018 15:27:49 -0400
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101
 Thunderbird/52.9.1
MIME-Version: 1.0
In-Reply-To: <a43db228-ddd0-c30f-6ba0-8d54f17f57c7@arm.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On 10/24/2018 11:34 AM, Valentin Schneider wrote:
> Hi,
> 
> On 22/10/2018 20:07, Steven Sistare wrote:
>> On 10/22/2018 1:04 PM, Peter Zijlstra wrote:
> [...]
>>
>> We could delete idle_balance() and use stealing exclusively for handling
>> new idle.  For each sd level, stealing would look for an overloaded CPU
>> in the overloaded bitmap(s) that overlap that level.  I played with that
>> a little but it is not ready for prime time, and I did not want to hold
>> the patch series for it.  Also, I would like folks to get some production
>> experience with stealing on a variety of architectures before considering
>> a radical step like replacing idle_balance().
> 
> I think this could work fine for standard symmetrical systems, but I have
> some concerns for asymmetric systems (Arm big.LITTLE & co). One thing that
> should show up in 4.20-rc1 is the misfit logic, which caters to those
> asymmetric systems.
> 
> If you look at 757ffdd705ee ("sched/fair: Set rq->rd->overload when
> misfit") on Linus' tree, we can set rq->rd->overload even if
> (rq->nr_running == 1). This is because we do want to do an idle_balance()
> when we have misfit tasks, which should lead to active balancing one of
> those CPU-hungry tasks to move it to a more powerful CPU.
> 
> With a pure try_steal() approach, we won't do any active balancing - we
> could steal some task from a cfs_overload_cpu but that's not what the
> load balancer would have done. The load balancer would only do such a thing
> if the imbalance type is group_overloaded, which means:
> 
>   sum_nr_running > group_weight &&
>   group_util * sd->imbalance_pct > group_capacity * 100
> 
> (IOW the number of tasks running on the CPU is not the sole deciding
> factor)
> 
> Otherwise, misfit tasks (group_misfit_task imbalance type) would have
> priority.
> 
> Perhaps we could decorate the cfs_overload_cpus with some more information
> (e.g. misfit task presence), but then we'd have to add some logic to decide
> when to steal what.

Hi Valentin,

Asymmetric systems could maintain a separate bitmap for misfits; set a bit 
when a CPU goes on CPU, clear it going off.  When a fast CPU goes new idle,
it would first search the misfits mask, then search cfs_overload_cpus.
The misfits logic would be conditionalized with CONFIG or sched feat static 
branches so symmetric systems do not incur extra overhead.

> We'd also lose the NOHZ update done in idle_balance(), though I think it's
> not such a big deal - were were piggy-backing this on idle_balance() just
> because it happened to be convenient, and we still have NOHZ_STATS_KICK
> anyway.

Agreed.
 
> Another thing - in your test cases, what is the most prevalent cause of
> failure to pull a task in idle_balance()? Is it the load_balance() itself
> that fails to find a task (e.g. because the imbalance is not deemed big
> enough), or is it the idle migration cost logic that prevents
> load_balance() from running to completion?

The latter.  Eg, for the test "X6-2, 40 CPUs, hackbench 3 process 50000",
CPU avg_idle is 355566 nsec, and sched_migration_cost_ns = 500000,
so idle_balance bails at the top:
          if (this_rq->avg_idle < sysctl_sched_migration_cost ||
            ...
            goto out

For other tests, we get past that clause but bail from a domain:
      if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost) {
           ...
           break;

> In the first case, try_steal() makes perfect sense to me. In the second
> case, I'm not sure if we really want to pull something if we know (well,
> we *think*) we're about to resume the execution of some other task.

355.566 microsec is enough time to steal, go on CPU, do useful work, and go 
off CPU, particularly for chatty workloads like hackbench.  The performance
data bear this out.  For the higher loads, the average timeslice for 
hackbench 

Perhaps I could skip try_steal() if avg_idle is very small, although with
hackbench I have seen average time slice as small as 10 microsec under 
high load and preemptions.  I'll run some experiments.

>> We could merge the stealing code into the idle_balance() code to get a
>> union of the two, but IMO that would be less readable.
>>
>> We could remove the core and socket levels from idle_balance()
> 
> I understand that as only doing load_balance() at DIE level in
> idle_balance(), as that is what makes most sense to me (with big.LITTLE
> those misfit migrations are done at DIE level), is that correct?

Correct. 
> Also, with DynamIQ (next gen big.LITTLE) we could have asymmetry at MC
> level, which could cause issues there.

We could keep idle_balance for this level and fall back to stealing as in
my patch, or you could extend the misfits bitmap to also include CPUs 
with reduced memory bandwidth and active tasks. (if I understand the asymmetry 
correctly).

>> and let
>> stealing handle those levels.  I think that makes sense after stealing
>> performance is validated on more architectures, but we would still have
>> two different mechanisms.
>>
>> - Steve
> 
> I'll try out those patches on top of the misfit series to see how the
> whole thing behaves.

Very good, thanks.

- Steve