Karl Taht's Research Paper Blog

Authors: Kay Ousterhout, Patrick Wendell, Matei Zaharia, Ion Stoica Venue:    SOSP 2013 This work presents Sparrow, a stateless, decentralized scheduler for cluster scheduling. The scheduling component uses two key ideas: batch sampling and late binding. Batch sampling is an extension of the power of two choices [1], which shows that the "tail" can quickly be cut off by simply sampling between two machines versus randomly selecting one. Batch sampling generalizes this by sampling dm machines, and placing the m   tasks on the machine with the lowest load. Late binding delays the actual task transfer until the machine is ready to process the request. This can be thought of as having a place holder in the worker's queue, and when the worker is finally ready to process it, the actual task is transferred from the scheduler to the worker. This avoids having to rely on inaccurate metrics such as queue depth. Each worker maintains its "instance" of Sparrow, which us...

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. I...

Authors: Hongzi Mao, Mohammad Alizadeh, Ishai Menache, Srikanth Kandula Venue: HotNets-XV This work presents DeepRM, a deep reinforcement learning approach to the bin-packing task of job scheduling in a cluster. The authors utilize a synthetic environment which comprises of d  resource types. Jobs arrive online and and are scheduling during discrete time steps. No preemption occurs. In their simulated framework, they find the RL algorithm improves average slow down significantly compared to Tetris, Shortest Job First, and Packer. However, average job completion time is slightly higher. Intuitively, this makes sense since the RL algorithm is given a single reward, which is defined in respect to slowdown in this work. Overall, this work marks an important step toward automation of job scheduling in a resource constrained environment. RL Formulation In order to fix the state representation, only the vector representation of M  jobs is encoded in the state space, plus a scal...

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 algor...

Authors: Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, Mohammad Alizadeh Venue: Proceedings of the ACM Special Interest Group on Data Communication This paper utilizes reinforcement learning to schedule learn a scheduling policy for Spark jobs. The scheduler has two main decisions: (i) what stage to schedule and (ii) how much parallelism to exploit for that stage. The RL problem is formulated as given the state of the cluster and DAG input, output a scheduling action. Reward is defined as -T x J where T is the time step and J is the number of jobs in the system. The decision making process is particularly difficult because an job can present a DAG of any shape for dependencies, yet, the neural network input is of fixed size. To solve this, a method based on graph convolutional neural networks [1] is used. The RL policy network predicts a composite action of stage of maximum parallelism level. To train the network in the case of continuous job arrivals, ...

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 th...

Authors: Yu Gan, Yanqi Zhang, Kelvin Hu, Dailun Cheng, Yuan He, Meghna Pancholi, Christina Delimitrou Venue: ASPLOS 2018 Seer presents a framework to diagnose and avoid QoS violations in real-time. The motivation, design, and experimental framework in this paper are some of the best and most through I have seen in my recent reading. The work begins by discussing the microservice design of cloud providers. Such frameworks have numerous layers of abstraction, are often written in multiple programming languages, and have complex (and changing) dependency graphs. A performance bug in one microservice can cause QoS in many others, and diagnosing the root cause can be difficult. The work then builds a complex data collection framework which uses RPC-level and perf counters. When perf counters aren't available, the system uses microbenchmarks to diagnose the bottleneck. This area is particularly complex, and the authors even note that their system is similar to Dapper and Zipkin wh...

Authors: Yoongu Kim, Michael Papamichael, Onur Mutlu, and Mor Hachol-Balter Venue:   MICRO 2010 This paper presents Thread Cluster Memory Scheduling (TCM), a memory scheduling algorithm that targets optimizing both system throughput and fairness. To achieve this, three key ideas are employed. Firstly, threads are clustered as either bandwidth intensive or non-intensive. The idea here is that low-bandwidth threads are more sensitive to latency. While an example is presented, an easier way to reason about this is that a low-bandwidth thread needs only a small fraction of memory service time to see a significant performance increase. In other words, it has a high ROI with minimal impact to other threads. As such, non-BW-intensive threads are always given the highest priority. The second observation to be exploited is the disparity in behavior among high-bandwidth threads. Specifically, a metric niceness  measures a threads susceptibility to interference and impact on ot...

Authors: Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D. Joseph, Randy Katz, Scott Shenker, Ion Stoica Venue: NSDI 2011 Mesos is a thin management layer that allows various cluster computing frameworks to efficiently share resources. The two key principles leveraged by Mesos are its fine-grained resource sharing model at the level of tasks, and a distributed (decentralized) scheduling mechanism. The result is a framework which offers better overall system utilization, scalability to at least 50,000 nodes, and flexibility to port to many different (and future) frameworks. Fine-grain resource sharing is done via a notion of resource-offers, which are each a list of free resources on multiple slaves. The master decides how many resources to offer each framework, this distribution is done via a pluggable allocation module. A scheduler  registers with the master to be offered resources, and an executor process is launched on slave notes to run the framework'...