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: 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:  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:   Ravi Iyer, Li Zhao, Fei Guo, Steve Reinhardt (Intel, NC State, U Michigan) Venue:      SIGMETRICS 2007 First and foremost, the biggest thing this paper has going for it is the evaluation methodology. While the paper does not have adequate space to display a lot of test cases (few workloads are shown), they provide performance numbers for a purely trace-based methodology as well as a full-system mock up. What makes this particularly impressive is that the full-system is done with a modified Linux kernel which adds priority level to processes as well as new system calls to change QoS bits in platform registers. Unlike other QoS papers, this one focuses on app prioritization. They do so by adjusting two key shared resources: memory bandwidth and cache allocation. The ideas present don't seem to provide any unsurprising insight. Essentially, giving more resources to a high-priority app (more than it's fair share) boost that app's performance at th...

Authors:  Lisa R. Hsu, Steven Reinhardt (U Michigan), Ravi Iyer, Srihari Makinei (Intel) Venue:     PACT 2006 This paper examines the resultant partition of different LLC cache allocation policies on an multi-core (CMP) system. The overall finding is that while LRU-like policies tend to degrade into something like utilitarian policies. While at first glance this is may sound good, the metric of utility is raw-IPC, which gives bias toward program with high levels of ILP. The paper also explains that utilitarian policies can result in bad fairness, and likewise fairness policies can result in poor utility. Additionally, the paper goes on to show that different metrics (raw-IPC, misses-per-access, misses-per-instruction) result in drastically different cache partitioning schemes. The paper is more a case study than a proposed solution, and suggest that a more complicated, online policy will be required to target either utility- or fairness-based cache partitioning sc...