FACT: A Framework for Adaptive Contention-aware Thread Migrations

Authors: Kishore Kumar Pusukuri, David Vengerov, Alexandra Fedorova, Vana Kalogeraki
Venue: Computing Frontiers (CF) 2011

 This paper presents one of the first applications of machine learning to solve the thread scheduling problem on multi-core systems. In 2011 (and I believe still today, in 2019), OS's do not factor in resource sharing effects, such as cache, prefetcher, memory bus, memory controller. To effectively schedule tasks, the OS needs to understand how different workloads utilize resources and the overall effects of resource sharing. This paper uses a machine learning approach to predict the effects of potential thread migrations. The work finds that fuzzy rule-based predictors work best, and out performs the default scheduler by ~11% and the prior art by ~2%. The remainder of this post discusses the algorithm and problem setup. This discussion may come across as critical, but it is meant only to be though provoking and counter arguments are welcome. 

 The base algorithm searches through core groups, and for each thread in the core group, predicts the average IPC of all threads a thread was migrated. While not explicitly stated, it seems that this prediction step would also benefit from predicting migrating that thread to any potential core group, and swapping it with any potential candidate in that group. With 2 groups and 2 threads each, there are only 4 possible swaps. However, with 4 groups and 4 threads per group, I believe this is 96 possible configurations. I think fundamentally this algorithm suffers from a scaling issue in predicting potential candidates, as a modern processor has at least 2 levels of hierarchy (core pairs, NUMA domains), and typically 16-20 cores per NUMA domain (typically 1-4). However, removing the redistribution step would drastically reduce this number, and is used in practice in the Linux CFS scheduler load balances via 1-way migration. 

 The paper also only considers scenarios where there are precisely as many threads as cores. In a multi-core system, under or over subscription is common. Simply balancing the queues may not work, because internally queues would then be a mix of low- and high-resource requirements which may get arbitrarily co-scheduled due to independent queues on separate core groups. Another option would be to pair "high load" in one group and "low load" in another. However, this is not clear how to maintain when the notion of high and low load are imbalanced, or when the notion of high/low contains multiple interacting resources. 

 Full Text

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