Karl Taht's Research Paper Blog

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: 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: 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: Andreas Sandberg, Andreas Sembrant, Erik Hagersten and David Black-Schaffer Venue:    HPCA 2013 The authors of this paper present a modeling framework to predict cache contention when co-locating applications. The model is much lighter weight than previous work, and accurate within 0.41% on average. The authors utilize a three-fold approach: A cache sharing model  - Predicts how much cache is used by an application A cache analysis tool (Cache Pirating)  - Artificially reduces cache size A phase detection framework: (Scarphase)  - Divides applications into phases It should be noted that (1) and (2) can be done directly with what is now Intel RDT, which was not available at the time of publication.     The authors show that co-location of applications exhibits extensive performance variability depending on alignment, particularly when applications exhibit extensive phase behavior. Therefore to predict performance of co-location, a u...