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:     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>
From:   Steven Sistare <steven.sistare@oracle.com>
Organization: Oracle Corporation
Message-ID: <8e38ce84-ec1a-aef7-4784-462ef754f62a@oracle.com>
Date:   Mon, 22 Oct 2018 15:07:10 -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: <20181022170421.GF3117@worktop.programming.kicks-ass.net>
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/22/2018 1:04 PM, Peter Zijlstra wrote:
> On Mon, Oct 22, 2018 at 07:59:31AM -0700, Steve Sistare wrote:
>> When a CPU has no more CFS tasks to run, and idle_balance() fails to
>> find a task, then attempt to steal a task from an overloaded CPU in the
>> same LLC. Maintain and use a bitmap of overloaded CPUs to efficiently
>> identify candidates.  To minimize search time, steal the first migratable
>> task that is found when the bitmap is traversed.  For fairness, search
>> for migratable tasks on an overloaded CPU in order of next to run.
>>
>> This simple stealing yields a higher CPU utilization than idle_balance()
>> alone, because the search is cheap, so it may be called every time the CPU
>> is about to go idle.  idle_balance() does more work because it searches
>> widely for the busiest queue, so to limit its CPU consumption, it declines
>> to search if the system is too busy.  Simple stealing does not offload the
>> globally busiest queue, but it is much better than running nothing at all.
> 
> Why I don't dislike the idea; I feel it is unfortunate to have two
> different mechanisms to do effectively the same thing.
> 
> Can't we improve idle_balance() instead of building this parallel
> functionality?

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().

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() 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