mpm + scheduling   17

Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
Cloud computing has motivated renewed interest in resource allocation problems with new consumption models. A common goal is to share a resource, such as CPU or I/O bandwidth, among distinct users with different demand patterns as well as different quality of service requirements. To ensure these service requirements, cloud offerings often come with a service level agreement (SLA) between the provider and the users. An SLA specifies the amount of a resource a user is entitled to utilize. In many cloud settings, providers would like to operate resources at high utilization while simultaneously respecting individual SLAs. There is typically a tradeoff between these two objectives; for example, utilization can be increased by shifting away resources from idle users to "scavenger" workload, but with the risk of the former then becoming active again. We study this fundamental tradeoff by formulating a resource allocation model that captures basic properties of cloud computing systems, including SLAs, highly limited feedback about the state of the system, and variable and unpredictable input sequences. Our main result is a simple and practical algorithm that achieves near-optimal performance on the above two objectives. First, we guarantee nearly optimal utilization of the resource even if compared to the omniscient offline dynamic optimum. Second, we simultaneously satisfy all individual SLAs up to a small error. The main algorithmic tool is a multiplicative weight update algorithm, and a duality argument to obtain its guarantees. Experiments on both synthetic and real production traces demonstrate the merits of our algorithm in practical settings.
scheduling 
18 hours ago by mpm
A Survey of Preferences in Virtual Machine Placement
With the rapid developments of virtualization techniques, cloud data centers have had enabled cost effective, flexible, and customizable deployments of applications in virtualized infrastructure. Virtual machine placement problem is a problem of paramount importance to the design of cloud data centers. It aims to assign each virtual machine to a server in the cloud environment. Typically, the problem involves complex relations and multiple design factors as well as local policies that govern the assignment decisions. It also involves different parties including cloud administrators and customers that we need to consider their preferences while opting for a solution. Thus, it is significant to not only return an optimized solution to the underlying placement problem but also a solution that reflects the given preferences of these parties. In this paper, we provide a detailed review on the role of preferences in the current literature of the virtual machine placement problem. We further discuss some challenges and identify possible research opportunities to better incorporate preferences within the problem.
scheduling 
21 days ago by mpm
Tetris is Hard, Even to Approximate
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all pieces above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p^(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of (2 - epsilon), for any epsilon>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.
scheduling 
8 weeks ago by mpm
Combinatorial Auction-Based Mechanisms for VM Provisioning and Allocation in Clouds
Current cloud providers use fixed-price based mechanisms to allocate Virtual Machine (VM) instances to their users. The fixed-price based mechanisms do not provide an efficient allocation of resources and do not maximize the revenue of the cloud providers. A better alternative would be to use combinatorial auction-based resource allocation mechanisms. In this PhD dissertation we will design, study and implement combinatorial auction-based mechanisms for efficient provisioning and allocation of VM instances in cloud computing environments. We present our preliminary results consisting of three combinatorial auction-based mechanisms for VM provisioning and allocation.We also present an efficient bidding algorithm that can be used by the cloud users to decide on how to bid for their requested bundles of VM instances
scheduling  auction 
8 weeks ago by mpm
Easily implementable time series forecasting techniques for resource provisioning in cloud computing
Workload predictions in cloud computing is obviously an important topic. Most of the existing publications employ various time series techniques, that might be difficult to implement. We suggest here another route, which has already been successfully used in financial engineering and photovoltaic energy. No mathematical modeling and machine learning procedures are needed. Our computer simulations via realistic data, which are quite convincing, show that a setting mixing algebraic estimation techniques and the daily seasonality behaves much better. An application to the computing resource allocation, via virtual machines, is sketched out.
scheduling 
8 weeks ago by mpm
Scheduling in distributed systems: A cloud computing perspective
Scheduling is essentially a decision-making process that enables resource sharing among a number of activities by determining their execution order on the set of available resources. The emergence of distributed systems brought new challenges on scheduling in computer systems, including clusters, grids, and more recently clouds. On the other hand, the plethora of research makes it hard for both newcomers researchers to understand the relationship among different scheduling problems and strategies proposed in the literature, which hampers the identification of new and relevant research avenues. In this paper we introduce a classification of the scheduling problem in distributed systems by presenting a taxonomy that incorporates recent developments, especially those in cloud computing. We review the scheduling literature to corroborate the taxonomy and analyze the interest in different branches of the proposed taxonomy. Finally, we identify relevant future directions in scheduling for distributed systems
scheduling 
january 2019 by mpm
Scheduling Jobs with Random Resource Requirements in Computing Clusters
We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs' resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have low complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.
scheduling 
january 2019 by mpm
An efficient cloud scheduler design supporting preemptible instances
Maximizing resource utilization by performing an efficient resource provisioning is a key factor for any cloud provider: commercial actors can maximize their revenues, whereas scientific and non-commercial providers can maximize their infrastructure utilization. Traditionally, batch systems have allowed data centers to fill their resources as much as possible by using backfilling and similar techniques. However, in an IaaS cloud, where virtual machines are supposed to live indefinitely, or at least as long as the user is able to pay for them, these policies are not easily implementable. In this work we present a new scheduling algorithm for IaaS providers that is able to support preemptible instances, that can be stopped by higher priority requests without introducing large modifications in the current cloud schedulers. This scheduler enables the implementation of new cloud usage and payment models that allow more efficient usage of the resources and potential new revenue sources for commercial providers. We also study the correctness and the performace overhead of the proposed scheduler agains existing solutions.
scheduling 
january 2019 by mpm
The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS
This paper analyzes the impact on application performance of the design and implementation choices made in two widely used open-source schedulers: ULE, the default FreeBSD scheduler, and CFS, the default Linux scheduler.
scheduling  concurrency  linux  bsd 
october 2018 by mpm
Learning-based Dynamic Pinning of Parallelized Applications in Many-Core Systems
This paper introduces a reinforcement-learning based resource allocation framework for dynamic placement of threads of parallel applications to Non-Uniform Memory Access (NUMA) many-core systems. We propose a two-level learning-based decision making process, where at the first level each thread independently decides on which group of cores (NUMA node) it will execute, and on the second level it decides to which particular core from the group it will be pinned. Additionally, a novel performance-based learning dynamics is introduced to handle measurement noise and rapid variations in the performance of the threads. Experiments on a 24-core system show the improvement of up to 16% in the execution time of parallel applications under our framework, compared to the Linux operating system scheduler.
scheduling  performance 
august 2018 by mpm
A Two-Stage Auction Mechanism for Cloud Resource Allocation
With the recent growth in the size of cloud computing business, handling the interactions between customers and cloud providers has become more challenging. Auction theory has been proposed to model these interactions due to its simplicity and a good match with real-world scenarios. In this paper, we consider cloud of clouds networks (CCNs) with different types of servers along with customers with heterogeneous demands. For each CCN, a CCN manager is designated to handle the cloud resources. A comprehensive framework is introduced in which the process of resource gathering and allocation is addressed via two stages, where the first stage models the interactions between customers and CCN managers, and the second stage examines the interactions between CCN managers and private cloud providers (CPs). For the first stage, an options-based sequential auction (OBSA) is adapted to the examined market, which is capable of providing truthfulness as the dominant strategy and resolving the entrance time problem. An analytical foundation for OBSAs is presented and multiple performance metrics are derived. For the second stage, two parallel markets are assumed: flat-price and auction-based market. A theoretical framework for market analysis is provided and the bidding behavior of CCN managers is described.
scheduling 
august 2018 by mpm
On Non-Preemptive VM Scheduling in the Cloud
We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) for the duration of their service. To avoid costly preemptions, we consider non-preemptive scheduling: Each VM has to be assigned to a server which has enough residual capacity to accommodate it, and once a VM is assigned to a server, its service \textit{cannot} be disrupted (preempted). Prior approaches to this problem either have high complexity, require synchronization among the servers, or yield queue sizes/delays which are excessively large. We propose a non-preemptive scheduling algorithm that resolves these issues. In general, given an approximation algorithm to Knapsack with approximation ratio r, our scheduling algorithm can provide rβ fraction of the throughput region for β<r. In the special case of a greedy approximation algorithm to Knapsack, we further show that this condition can be relaxed to β<1. The parameters β and r can be tuned to provide a tradeoff between achievable throughput, delay, and computational complexity of the scheduling algorithm. Finally extensive simulation results using both synthetic and real traffic traces are presented to verify the performance of our algorithm.
scheduling 
august 2018 by mpm
Mage: Online Interference-Aware Scheduling in Multi-Scale Heterogeneous Systems
In this episode, we discuss how to define and manage SLOs for services with dependencies, each of which may (or may not!) have their own SLOs.
scheduling  performance 
july 2018 by mpm
CARMA: Contention-aware Auction-based Resource Management in Architecture
Traditional resource management systems rely on a centralized approach to manage users running on each resource. The centralized resource management system is not scalable for large-scale servers as the number of users running on shared resources is increasing dramatically and the centralized manager may not have enough information about applications' need. In this paper we propose a distributed game-theoretic resource management approach using market auction mechanism to find optimal strategy in a resource competition game. The applications learn through repeated interactions to choose their action on choosing the shared resources. Specifically, we look into two case studies of cache competition game and main processor and co-processor congestion game. We enforce costs for each resource and derive bidding strategy. Accurate evaluation of the proposed approach show that our distributed allocation is scalable and outperforms the static and traditional approaches.
scheduling  auction 
december 2017 by mpm
Faster task allocation by idle ants
We model and analyze the distributed task allocation problem, which is solved by ant colonies on a daily basis. Ant colonies employ task allocation in which ants are moved from one task to the other in order to meet changing demands introduced by the environment, such as excess or shortage of food, dirtier or cleaner nest, etc. The different tasks are: nursing (overseeing the hatching of newbies), cleaning, patrolling (searching for new food sources), and foraging (collecting and carrying the food to the nest). Ants solve this task allocation efficiently in nature and we mimic their mechanism by presenting a distributed algorithm that is a variant of the ants algorithm. We then analyze the complexity of the resulting task allocation distributed algorithms, and show under what conditions an efficient algorithm exists. In particular, we provide an Ω(n) lower bound on the time complexity of task allocation when there are no idle ants, and a contrasting upper bound of O(lnn) when a constant fraction of the ants are idle, where n is the total number of ants in the colony. Our analysis suggests a possible explanation of why ant colonies keep part of the ants in a colony idle, not doing anything
ants  scheduling  bio-inspired 
july 2015 by mpm
Lottery and stride scheduling
two very related approaches to doing efficient proportional-share scheduling. I believe this is the canonical way of doing things, since mClock (by Gulati et al., presented at OSDI 2010) used stride scheduling successfully to schedule disk I/O in a hypervisor.
io  scheduling 
july 2011 by mpm

Copy this bookmark:



description:


tags: