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
