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

[Michael Kelley (LINUX)]

From: Chen Yu <yu.c.chen@xxxxxxxxx> Sent: Tuesday, June 6, 2023 9:07 PM
> 
> On 2023-06-06 at 17:38:28 +0200, Vincent Guittot wrote:
> > On Tue, 6 Jun 2023 at 16:08, Michael Kelley (LINUX)
> > <mikelley@xxxxxxxxxxxxx> wrote:
> > >
> > > From: Vincent Guittot <vincent.guittot@xxxxxxxxxx> Sent: Monday, June 5, 2023
> 2:31 AM
> > > >
> > > > Hi Michael,
> > > >
> > > > On Wed, 31 May 2023 at 19:55, Michael Kelley <mikelley@xxxxxxxxxxxxx> 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.

Vincent -- 

Fair enough.  We can revisit the topic if we discover a workload where the
imbalance produces a noticeable difference in performance for some reason.
Thanks for your review and consideration.

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

Chen --

I have not tried to think through the scenario you describe.  But I don't
think such a race condition is the primary reason that we observe the SMT
imbalance when running with CPU numbering scheme B.   It seems like
such a race would be relatively rare, and hence not a significant issue.  Or
is there a more serious consequence if the race were to happen?

Michael