The Linux Scheduler: A Decade of Wasted Cores

Authors: Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quema, Alexandra Fedorova
Venue: EuroSys 2016

Before diving into this paper, it's worth mentioning that this paper is presented more like a technical report rather than a research paper. Its clearly very important work, but the authors present software "bugs" within Linux, and fixes for those bugs. The paper is not trying to establish something completely new (other than a set of tools), but rather analysis and fixes.

. . .

The paper presents findings that the Linux CFS scheduler breaks a fundamental invariant: make sure that ready threads are scheduled if cores are idle. Due to increased complexity within the scheduler to deal with multiprocessors and NUMA domains, the scheduler has issues which prevent this invariant from being met. The CFS scheduler relies on a hierarchy of "scheduling groups" of cores and NUMA domains (scheduling domains). As an aside, it is not clear if the word "node" is used to mean a NUMA domain or a core, and some parts are muddied because of this.

  1. Group Inbalance bug. Balancing between groups looks at average load. Because averaging the load formulation can obfuscate the presence of idle cores, the scheduler can fail to balance the cores. Fix: use minimum load within a group instead of average. Potential issue: lots of ping-ponging. Though it is said this does not occur, it would be of interest to see the net impacts across all workloads and/or the changes in number of migrations.
  2. Scheduling Group Construction Bug. The way scheduling groups are created can cause cores to be contained within multiple groups, and cause cores in separate NUMA domains to be grouped together. This can lead to work not getting spread across cores evenly, particularly when used in conjunction with taskset commands for core masking. The fix changes how the groups are constructed... though it is not clear how (only 1 short paragraph on this fix).
  3. Overload-on-Wakeup Bug. When a sleeping thread wakes up, it wakes up where it slept. The idea is to preserve cache locality. However, depending on sleep time scales, this is not ideal and can cause sleeping threads to interrupt busy cores while idle cores remain present. A good example is when multiple threads are sleeping on a synchronization point, and then all wake up together. Fix: schedule wake ups on cores idle for longer amounts of time.
  4. Missing Scheduling Domain. This example is truly a code bug. Users have the ability to disable cores via /proc. When a core is re-enabled after this, it is not added back to the scheduler properly and thus receives no work.

The examples in this paper are strong and clearly illustrate performance issues. However, some do feel a bit contrived, such as the 2, which occurs when taskset is used, or 4 which occurs when cores are disabled then re-enabled. Nevertheless, the corrections are important. The paper also presents a tooling methodology to monitor the scheduler and track the invariant. Under violations, the tool can then perform better tracing. The tool itself is the novel component, but receives little attention in the paper. How long does the tool have to run to detect the bugs? How is performance impacted with and without the tool? Does running the tool actually make sense -- is the overhead of the tool better than the gains?

Overall, a good read to get into the scheduler and very interesting violations by the scheduler -- almost 10 years after its deployment!

Comments

Post a Comment

Popular posts from this blog

Fundamental Latency Trade-offs in Architecting DRAM Caches (Alloy Cache)

Authors: Moinuddin K. Qureshi and Gabriel H. Loh Venue:    MICRO 2012 The authors present a new architecture for DRAM cache which targets optimizing latency rather than hit rate. The authors show that for every optimization made to improve hit rate, one must also consider the added cache latency, thus resulting in a new "break even hit rate". The authors compare to three key baselines: an infeasibly large SRAM-tag array, the prior "LH-Cache", and a ideal latency-optimized cache. They find that "unoptimizations" improve latency, while minimally impacting hit-rate. Their final result is a cache which boosts performance 35% improvement over the baseline, and nearly 20% better than the previous LH-cache. The specific contributions are: Moving to a direct mapped cache provides significant improvement (by reducing latency) Combining tag-store and data-store into a single entity improves performance 21% Implementing a small per-core predictor enhances per...
Read more

ZCOMP: Reducing DNN Cross-Layer Memory Footprint Using Vector Extensions

Authors: Berkin Akin, Zeshan A. Christi, and Alaa R. Alameldeen Venue: MICRO, 2019 With accelerators dominating the deep learning space in architecture conferences, this paper stands out as it focuses on reducing DNN inference/training overhead while using a CPU. An obvious question is, with the wide-spread use of GPUs/TPUs for deep learning, why should we focus on optimizing CPUs for deep learning. In a recent paper published at HPCA 2019, Facebook claims that CPUs are preferred for applications where a tight integration is required between DNN and non-DNN tasks. Also, Intel's recent AVX512 has specialized support for DNNs in the form of new instructions called Vector Neural Network Instructions (VNNI). Broadly, optimizing DNNs can be viewed from two different perspectives; computation, and communication. This paper targets reducing communication overhead, more specifically, activation or feature-map communication overhead by compressing them. Compressing activations/weights...
Read more

AutoFDO: Automatic Feedback-Directed Optimization for Warehouse-Scale Applications

Authors: Dehao Chen, David Xinliang Li, Tipp Moseley Venue:    CGO 2016 This paper presents AutoFDO, a system used which profiles warehouse-scale applications, and applies feedback to the compilation for the next release. AutoFDO works by profiling and storing profiles in an aggregate database, annotating the profiles via an intermediate representation, and finally providing feedback. On average, this technique boosts performance by around 10% and works well even with stale releases. For profiles to be useful, they must be in an intermediate representation. This is built from binary-level profile, which uses LBR to map instruction frequencies. By using these frequencies, program counters, and the source, a source profile can be generated. The source profile can be used to build an annotated call-graph with edge frequencies, with some inaccuracy. These annotated call-graphs can then be used as feedback to the compiler. Because of the size of the applications and scale of d...
Read more