Re: [RFC PATCH 1/1] sched/fair: Fix SMT balance dependency on CPU numbering

[Chen Yu <yu.c.chen@intel.com>]

On 2023-06-06 at 17:38:28 +0200, Vincent Guittot wrote:
> On Tue, 6 Jun 2023 at 16:08, Michael Kelley (LINUX)
> <mikelley@microsoft.com> wrote:
> >
> > From: Vincent Guittot <vincent.guittot@linaro.org> Sent: Monday, June 5, 2023 2:31 AM
> > >
> > > Hi Michael,
> > >
> > > On Wed, 31 May 2023 at 19:55, Michael Kelley <mikelley@microsoft.com> wrote:
> > > >
> > > > With some CPU numbering schemes, the function select_idle_cpu() currently
> > > > has a subtle bias to return the first hyper-thread in a core. As a result
> > > > work is not evenly balanced across hyper-threads in a core. The difference
> > > > is often as much as 15 to 20 percentage points -- i.e., the first
> > > > hyper-thread might run at 45% load while the second hyper-thread runs at
> > > > only 30% load or less.
> > > >
> > > > Two likely CPU numbering schemes make sense with today's typical case
> > > > of two hyper-threads per core:
> > > >
> > > > A. Enumerate all the first hyper-theads in a core, then all the second
> > > >    hyper-threads in a core.  If a system has 8 cores with 16 hyper-threads,
> > > >    CPUs #0 and #8 are in the same core, as are CPUs #1 and #9, etc.
> > > >
> > > > B. Enumerate all hyper-threads in a core, then all hyper-threads in the
> > > >    next core, etc.  Again with 8 cores and 16 hyper-threads, CPUs #0 and
> > > >    #1 are in the same core, as are CPUs #2 and #3, etc.
> > > >
> > > > Scheme A is used in most ACPI bare metal systems and in VMs running on
> > > > KVM.  The enumeration order is determined by the order of the processor
> > > > entries in the ACPI MADT, and the ACPI spec *recommends* that the MADT
> > > > be set up for scheme A.
> > > >
> > > > However, for reasons that pre-date the ACPI recommendation, Hyper-V
> > > > guests have an ACPI MADT that is set up for scheme B.  When using scheme B,
> > > > the subtle bias is evident in select_idle_cpu().  While having Hyper-V
> > > > conform to the ACPI spec recommendation would solve the Hyper-V problem,
> > > > it is also desirable for the fair scheduler code to be independent of the
> > > > CPU numbering scheme.  ACPI is not always the firmware configuration
> > > > mechanism, and CPU numbering schemes might vary more in architectures
> > > > other than x86/x64.
> > > >
> > > > The bias occurs with scheme B when "has_idle_cpu" is true and
> > >
> > > I assume that you mean has_idle_core as I can't find has_idle_cpu in the code
> >
> > Yes.  You are right.
> >
> > >
> > > > select_idle_core() is called in the for_each_cpu_wrap() loop. Regardless
> > > > of where the loop starts, it will almost immediately encountered a CPU
> > > > that is the first hyper-thread in a core. If that core is idle, the CPU
> > > > number of that first hyper-thread is returned. If that core is not idle,
> > > > both hyper-threads are removed from the cpus mask, and the loop iterates
> > > > to choose another CPU that is the first hyper-thread in a core.  As a
> > > > result, select_idle_core() almost always returns the first hyper-thread
> > > > in a core.
> > > >
> > > > The bias does not occur with scheme A because half of the CPU numbering
> > > > space is a series of CPUs that are the second hyper-thread in all the
> > > > cores. Assuming that the "target" CPU is evenly distributed throughout
> > > > the CPU numbering space, there's a 50/50 chance of starting in the portion
> > > > of the CPU numbering space that is all second hyper-threads.  If
> > > > select_idle_core() finds a idle core, it will likely return a CPU that
> > > > is the second hyper-thread in the core.  On average over the time,
> > > > both the first and second hyper-thread are equally likely to be
> > > > returned.
> > > >
> > > > Fix this bias by determining which hyper-thread in a core the "target"
> > > > CPU is -- i.e., the "smt index" of that CPU.  Then when select_idle_core()
> > > > finds an idle core, it returns the CPU in the core that has the same
> > > > smt index. If that CPU is not valid to be chosen, just return the CPU
> > > > that was passed into select_idle_core() and don't worry about bias.
> > > >
> > > > With scheme B, this fix solves the bias problem by making the chosen
> > > > CPU be roughly equally likely to either hyper-thread.  With scheme A
> > > > there's no real effect as the chosen CPU was already equally likely
> > > > to be either hyper-thread, and still is.
> > > >
> > > > The imbalance in hyper-thread loading was originally observed in a
> > > > customer workload, and then reproduced with a synthetic workload.
> > > > The change has been tested with the synthetic workload in a Hyper-V VM
> > > > running the normal scheme B CPU numbering, and then with the MADT
> > > > replaced with a scheme A version using Linux's ability to override
> > > > ACPI tables. The testing showed no change hyper-thread loading
> > > > balance with the scheme A CPU numbering, but the imbalance is
> > > > corrected if the CPU numbering is scheme B.
> > >
> > > You failed to explain why it's important to evenly select 1st or 2nd
> > > hyper-threads on the system.  I don't see any performance figures.
> > > What would be the benefit ?
> >
> > As I noted below, it's not completely clear to me whether this is a
> > problem.  I don't have a specific workload where overall runtime is
> > longer due to the SMT level imbalance.  I'm not a scheduler expert,
> > and wanted input from those who are.  Linux generally does a good
> > job of balancing load, and given the code in fair.c that is devoted to
> > balancing, I inferred at least some importance.  But maybe balancing
> > is more important for the higher-level domains, and less so for the
> > SMT domain.
> 
> As long as the hyper-threads on a core are the same, I don't see any
> need to add more code and complexity to evenly balance the number of
> time that we select each CPU of the same core when the whole core is
> idle.
>
In theory if a core is idle, either the 1st hyper thread or the 2nd hyper
thread is ok to run the wakee. Would there be a race condition between the
check of has_idle_core + idle core checking in select_idle_cpu() and the
task enqueue?  If the 2 hyper threads within 1 core are falling asleep
and wake up quickly, we have a false positive of has_idle_core, and
incorrectly think coreX is idle, and queue too many tasks on the first hyper
thread on coreX in B scheme, although coreX is not idle.

thanks,
Chenyu