Contention-Aware Scheduling on Multi-core Systems

Authors: Sergey Blagodurov, Sergey Zhuravlev, Alexandra Fedorova
Venue:    ACM Transactions on Computer Systems 2010

In format, this is not a traditional paper and reads more like a master's thesis. The work argues that to perform contention-aware scheduling, there must exist a classification scheme and scheduling policy. The first section of the paper dives into classification schemes. Classification in this context measures a workload's sensitivity (how much an application suffers when it receives less cache) and intensity (how much an application will harm others by utilizing the cache). The authors develop a new "Pain" scheme which characterizes both of these metrics and is able to predict contention utilizing stack distance profiles and hardware counters (LLC_LINES_IN). While the work develops procedures specifically focuses on characterizing the interactions in the LLC, the work then provides results demonstrating that LLC contention is only a small factor. Interconnect and memory controller contention often far more of an overhead than LLC itself, according to this work.

The scheduling policy used is referred to as Distributed Intensity (DI) which employs Centralized Sort, which sorts applications via their miss rate. DI is a recursive, hierarchical algorithm which greedily spreads work across different scheduling domains. The scheduling hierarchy is arranged in similar fashion to CFS, which uses Core, Pairs of Cores, and then NUMA-domains. However, unlike CFS, the scheduling all happens globally, meaning that each assignment traverses the entire hierarchy, instead of allowing the individual hierarchies to perform scheduling within their domain. This is likely an implementation/explanation simplification--there's no algorithmic reason this could not be done and maintain the same policy. The authors utilize two versions -- one which measures characterizes applications offline, and another which performs characterizations online. The online characterization is overall marginally worse than the offline, a positive result. The end result of the algorithm is evenly spreading high-miss rate workloads around the system, which results in an overall performance improvement of ~2% for workloads tested (Spec2006 mixes). The authors also show DI can be adapted to target lower energy as well.

Interesting Notes:

  • Despite an earlier section proving that the newly proposed "Pain" metric outperforms using miss rates, the authors offer that obtaining stack distance profiles (SDP) is not desirable. This seems intuitively, until it is pointed out that RapidMRC provides a methodology to obtain SDPs online using performance counters. 
  • Pre-emption is used only in the DIO (DI-online) scenario at 1B cycle intervals (~2Hz).
  • Non-LLC contention is very relevant, but hardly used in the algorithm. Clearly more opportunity exists, especially if we consider other resources like I-cache thrashing, memory bandwidth, and by extension, memory latency.
  • Assumes # threads < # cores
  • No notion of fairness


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