Karl Taht's Research Paper Blog

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: Aleksander Maricq, Dmitry Duplyakin, Ivo Jimenez, Carlos Maltzahn, Ryan Stutsman, Robert Ricci Venue: OSDI 2018 This paper performs in-depth statistical analysis to understand the performance variability present in real-systems. The goal is to quantify variability, and understand how to tame it from both a researcher's and cloud provider's perspective. To do so, the authors collect nearly 900,000 data points over the course of 10 months on real systems. A key insight is that the distribution of runs is a non-normal distribution, as such, typical parameterized analysis with closed form solutions should not be applied. In fact, typical analysis using CoV yields significantly different results than those which make no assumptions about the distribution. Thus, the authors make use of non-parameterized techniques to establish confidence intervals and error tolerance. From a researcher's perspective, the authors build a tool which performs such analysis on a given d...

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: Luiz Barroso, Mike Marty, David Patterson, and Parthasarathy Ranganathan Venue:    CACM (Magazine) This work shows that while architects have tackled problems and the nanosecond scale, and software has optimized for the millisecond scale, there exists a significant void in microsecond operation optimization. The result is that many operations which take in the order of a few microseconds degenerate into millisecond operations, or at least, reduce efficiency by up to or more than an order of magnitude in many cases. One such example is an RDMA, which by itself is only a ~2us operation. However, after dispatching, kernel-scheduling, interrupt-based notifications, and a TCP/IP stack, the transportation blows up to ~75us. The authors imply that this area is prime for research to optimize warehouse-scale computing. Such areas include reduced lock contention, lower-overhead interrupt handling, improved scheduling, and hardware-offloading in the mi...