Karl Taht's Research Paper Blog

Authors: Robert Grandl, Ganesh Anathanarayanan, Srikanth Kandula, Sriram Rao, Aditya Akella Venue: SIGCOMM 2014 Cluster level scheduling is a complex topic in which performance, fairness, and hard constraints must all be considered. Fundamentally, a perfectly fair solution sacrifices performance. This work presents a resource-aware cluster scheduling scheme which maximizes performance and includes additional parameters to balance fairness requirements. For simplicity, I will divide the discussion into two sections: the central idea and additional heuristics. Tetris performs scheduling by analyzing jobs resource requirements in terms of CPUs, memory, disk I/O, and network usage. Each job, task (a subset of a job), and machine is assigned a resource vector. To determine the optimal positioning of a task, a heuristic is used which takes the dot product of the job's resource requirements vs a candidates available resources. The machine with the maximum dot product is selected to p...

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: Akshitha Sriraman, Abhishek Dhanotia, Thomas F. Wenisch Venue: ISCA 2019 This work comprises of two main parts: a detailed analysis and tool to improve course-grain parameters based on general application (microservice) behavior. The author's analyze workloads in Facebook's datacenter in the categories of Web, Feed, Ads, and Cache which have varying throughput and latency requirements. The data center workloads exhibit significant front-end stalls (instruction fetch misses), significant branch  mispredictions, and significant back-end stalls (mostly data cache misses). uSKU is presented as a tool which automates the process of parameter tuning in an effort to improve system optimization for specific classes of microservices. Core frequency, uncore frequency, core count, code-and-data prioritization, prefetchers, transparent and static huge pages are explored. Knobs are tested independently and thus to do not consider dependent effects (Gaussian process search seem...

Authors: Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, Ion Stoica Venue:   NSDI 2011 This work presents a very computationally efficient scheduling algorithm in the context of data centers. The problem is presented as fair resource allocation, but the goal is accomplished through choosing which task to schedule (and how many of each). This done by assigning each task with a resource vector of it's requirements, and a corresponding vector of available resources. The algorithm considers each job's allocation via it's dominant resource. For example, if a job uses 1 CPU and 1 GB of memory, but there are 4 CPUs and 8GB of memory, it would be dominated  by it's CPU usage (1/4 > 1/8). Tasks are continually scheduled such that the job with the lowest dominant resource share will be given priority. The algorithm takes O(log(n)) for n tasks. The work presents 4 main properties, and was well as 4 other "nice to have". I'll briefly ...

Authors: Makhlouf Hadji, Djamal Zeghlache Venue:  ICCC 2012 (International Conference on Cloud Computing) This paper presents a cloud resource allocation formulated as a graph, which can be solved optimally by applying a min-cost, max flow algorithm. The exact formulation in previous work suffers from scalability due to its NP-hard formulation. In contrast, MCMF is itself a polynomial algorithm with exact correctness. The real magic of how this works is actually a subtlety which related bin-packing to max-flow. I am not 100% clear on exactly how this problem is reduced from an NP-hard assignment problem to a polynomial, but Google's OR-tools provides a decent high-level description: " How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1. Next, the flow-in-equals-flow-out condition forces the flow out of...

Authors: Shu Wang, Chi Li, Henry Hoffman, Shan Lu, William Sentosa, Achmad Imam Kistijantoro Venue: ASPLOS 2018 This paper presents a control theory approach to solving performance problems in workloads with many configurable parameters. The authors reference database workloads such as Cassandra, HBase, HDFS, and Hadoop MapReduce. The authors employ control theory with two key components outside of traditional control theory: a dynamic pole (error tolerance factor), and a virtual goal. Combined, these two approaches allow SmartConf to meet performance goals and hard constraints better than previous approaches. The authors also go into detail as to how their approach could be integrated into commercial software. See Yukta (ISCA 2018) for a similar-flavor paper which also uses control theory.  The remainder of this post will be subjective. This paper is exceptionally well-written, using many real-world examples to build motivation. Objectively, the paper's novelty is software ...

Authors: G. E. Suh, L. Rudolph, S. Devadas Venue:    SuperComputing 2004 This paper was released around the same era in which multi-core CPUs began to go mainstream. As a result, this is one of the first works to address resource partitioning, specifically, LLC partitioning. The authors utilize a framework to partition the cache based of marginal gains by allocating more cache. The work proposes a framework to allocate cache chunks (groups of blocks) by this scheme. However, to minimize hardware overhead, they are only able to sample marginal gains by way-granularity. They mention that this is one of the reasons in which their scheme performs sub-optimally. The results show a few outliers with significant gains (30%+), but excluding these, the results are lackluster. The significance of this work is primarily that it addresses the subject and emphasizes the importance in the future. Full Text

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

Authors: Jian Lin, Qingda Lu, .. P. Sadayappan et al. Venue:    HPCA 2008 The authors of this paper present an in-depth analysis and optimization of cache partitioning on a real-system. They accomplish this by using OS-page coloring, which induces only ~2% overhead. Since they cite the goal of their study primarily as analysis and potential, they subtract out this overhead. The authors show significant discrepancy compared to previous studies, which they cite as an artifact of simulations which are too small in length, and use too small of datasets. The real system approach allows for much longer runs with larger datasets. Benchmarks are divided into 4 categories: Red : Highly sensitive to cache size (bzip2, mcf, omnetpp, astar, sphinx3, xalanc) Yellow : Moderately sensitive (gcc, leslie3d, soplex, Gems, tonto, lbm, perl, catcus, h264) Green : Marginally sensitive (bwaves, zeus, gromacs, povray, libq, wrf) They create 27 workloads which each comprise of two benchm...

Authors: Shekhar Srikantaiah, Mahmut Kandemir, Qian Wang Venue:    MICRO 2009 This paper presents a new scheme for dynamic cache partition of a shared LLC. SHARP control leverages control their and separates the optimization into two layers: a local, per-core decision and a global, system-wide decision. Formal control theory provides performance guarantees, is resilient to minor inaccuracies, offers quick adaptive response and allows for high-level objects to be easily specified. The authors even provide a sketch of a proof which includes time-varying behavior. Each per-core controller is a reinforced oscillation resistant controller, which dynamically adjusts it's parameters based on the phase-behavior of applications. The global decision in managed in two steps, the PAN controller allocates addition cache ways to prevent under utilization, whereas the SHARP controller makes the decision of where to remove cache ways when the system is over subscribed. Significant experiment...

Authors: Ravi Iyer, Ramesh Illikkal, Omesh Tickoo, Li Zhao, Padma Apparo, Don Newell Venue:   Computer Networks 2009 The authors of this paper seek to understand the importance of resource allocation in a VM/cloud environment. At the time of publishing, only time-multiplexing and core allocation isolated VMs from a performance standpoint, which they refer to as a Virtual Platform Architecture (VPA) . The authors suggest that cache space, memory, bandwidth and power equally need to be virtualized as well. They focus on memory bandwidth and cache allocation. They motivate the problem by performing measurements and effects of resource contention and show significant performance degradation. Then then show that a simplistic model can perform fairly accurate predictions of cache occupancy, MPI, and cache contention. Perhaps the most elegant part of the paper is the description of the cache and memory bandwidth monitoring and allocation technology, which I assume laid foundatio...

Authors: Andreas Sembrant, Trevor Carlson, Erik Hagersten, David Black-Shaffer, Arthur Perais, Andre Seznec, and Pierre Michaud Venue:    MICRO 2015 The authors of this paper explore the utility of large instruction queues, load-store queues, register files, and other processor structures. These resources significantly boost performance by leveraging ILP and MLP. However, when resources are allocated to instructions that are not yet ready to be executed, it wastes significant energy. The authors spend significant effort to determine that a IQ of half-size (64->32), with a "Long Term Parking" structure for non-ready and non-urgent instructions, has negligible impacts on performance. Furthermore, the authors find that a majority of this benefit can be acquired via non-urgent instructions only. The authors then propose a solution to leverage this benefit, and find a design which is 1% slower, but 40% lower E(D^2)P for MLP-sensitive applications, and 3% slower but 38% l...

Authors: Xiaofei Liao, Rentong Guo, Danping Yu Venue:    International Journal of Parallel Programming 2016 The authors present a novel dynamic cache partitioning mechanism based on the phase behavior of program. They use a similar phase detection to Sembrant et al. to detect phases. To reduce the overhead further, they make an assumption that the current phase will continue, and trigger only a phase change when the IPC deviates more than a threshold. To partition the cache, they utilize their FractalMRC algorithm, which predicts the optimal cache partitioning via a miss-rate-curve. If the phase is already seen, then the MRC will be stored in the table. They show that overall their approach nets up to 21.4% performance improvement using Spec2006 benchmarks. The authors cite low overhead ~1%-2% on average in various configurations. However, it is unclear if this also factors in the overhead of the FractalMRC algorithm, which they state has an overhead of "less than 1s to c...

Authors:  Raghavendra Pothukuchi, Sweta Pothukuchi, Petros Voulgaris, Josep Torrellas Venue:     ISCA 2018 This work targets optimization of difference resources within a computer. The specific example used targets minimizing the energy-delay product via thread scheduling and DVFS on an Arm big.LITTLE board. This paper is done by the same authors of "Using MIMO Formal Control to Maximize Resource Efficiency in Architectures". While the prior work synthesizes many simultaneous optimization problems into a single controller, this work separates out the controllers into coordinated multi-layer formal controllers, specifically Structured Singular Value controllers. The SSV controllers offer the benefits of uncertainty guardbands for safety, max and min settings, discrete value support, and allow for passing information between multiple controllers. They call their generic framework Yukta (possibly named after the 1999 Miss World winner). The key idea is that this ap...

Authors: Ramazan Bitirgen, Engin Ipek, Jose F. Martinez Venue:    MICRO 2008 This paper presents a scheme to dynamically allocate system resources. The paper focuses on LLC cache partitioning via ways, bandwidth partitioning, and DVFS. They propose Coordinated Hill-climbing , to dynamically allocate these resources. The system profiles first in the default fair-share configuration. If the prediction framework has a high CoV (coeffient of variation) for the baseline performance, the algorithm does nothing. However, if the CoV is accurate, a profiling phase occurs. Once the initial training set is provided, the controller continues to sample for every 1 and 5 intervals. The model itself is a ensemble of fifty, 2-layer FC ANN's, each of which have 9 inputs (power, cache usage, read hits/misses, write hits/misses, bandwidth usage and L2 cache dirty ratio). The model attempts to predict the performance given the statistics. The model guides the search, such that search is shifte...