RFC Reduce time complexity of select_idle_sibling
Get series with b4
b4 am [email protected]Versions newest first
- v1 RFC Latest10 patches 18 repliesIn review
Patches in v1 No applies recorded yet
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [RFC PATCH 00/10] Reduce time complexity of select_idle_sibling
This is an early prototype that has not been tested heavily. While parts of it may stand on its own, the motivation to release early is Aubrey Li's series on using an idle cpumask to optimise the search and Barry Song's series on representing clusters on die. The series is based on tip/sched/core rebased to 5.10-rc6.
Patches 1-2 add schedstats to track the search efficiency of
select_idle_sibling. They can be dropped from the final version but are useful when looking at select_idle_sibling in general. MMTests can already parse the stats and generate useful data including graphs over time.
Patch 3 kills SIS_AVG_CPU but is partially reintroduced later in the
context of SIS_PROP.
Patch 4 notes that select_idle_core() can find an idle CPU that is
not a free core yet it is ignored and a second search is conducted in select_idle_cpu() which is wasteful. Note that this patch will definitely change in the final version.
Patch 5 adjusts p->recent_used_cpu so that it has a higher success rate
and avoids searching the domain in some cases.
Patch 6 notes that select_idle_* always starts with a CPU that is
definitely not idle and fixes that.
Patch 7 notes that SIS_PROP is only partially accounting for search
costs. While this might be accidentally beneficial, it makes it much harder to reason about the effectiveness of SIS_PROP.
Patch 8 uses similar logic to SIS_AVG_CPU but in the context of
SIS_PROP to throttle the search depth.
Patches 9 and 10 are stupid in the context of this series. They
are included even though it makes no sense to use SIS_PROP logic in select_idle_core() as it already has throttling logic. The point is to illustrate that the select_idle_mask can be initialised at the start of a domain search used to mask out CPUs that have already been visited.
In the context of Aubrey's and Barry's work, select_idle_mask would be initialised *after* select_idle_core as select_idle_core uses select_idle_mask for its own purposes. In Aubrey's case, the next step would be to scan idle_cpus_span as those CPUs may still be idle and bias the search towards likely idle candidates. If that fails, select_idle_mask clears all the bits set in idle_cpus_span and then scans the remainder. Similar observations apply to Barry's work, scan the local domain first, mask out those bits then scan the remaining CPUs in the cluster.
The final version of this series will drop patches 1-2 unless there is demand and definitely drop patches 9-10. However, all 4 patches may be useful in the context of Aubrey's and Barry's work. Patches 1-2 would give more precise results on exactly how much they are improving "SIS Domain Search Efficiency" which may be more illustrative than just the headline performance figures of a given workload. The final version of this series will also adjust patch 4. If select_idle_core() runs at all then it definitely should return a CPU -- either an idle CPU or the target as it has already searched the entire domain and no further searching should be conducted. Barry might change that back so that a cluster can be scanned but it would be done in the context of the cluster series.
Signature · 1 line
2.26.2