Browsing by Subject "Scheduling"

A fundamental computational challenge that arises in the operation of online systems, services, and platforms is that of resource allocation. Broadly defined, a resource allocation problem is one where set of users generate demands, which then have to be satisfied using a limited set of resources. In many of these scenarios, requests and jobs arrive in an online sequence, meaning they arrive over time and must be allocated without knowledge of future requests.

In this thesis, we examine resource allocation problems in online settings, focusing on problems in data center scheduling and internet advertising. Our results are summarized as follows.

• Vector Scheduling: We resolve the complexity of the vector scheduling problem, a variant of the classic load balancing problem first considered by Graham, where jobs have vectors loads (as opposed to a single scalar). We study the problem in the three classical settings—identical, unrelated, and related—giving competitive algorithms for optimizing generic q-norms of the machines loads. In each setting we show these algorithm are optimal by giving asymptotically matching lower bounds. Also as a consequence of these results, we give the first constant competitive algorithm for optimizing q-norms on related machines in the scalar setting.

• Budgeted Allocation: We study a variant of the online budgeted allocation (also called AdWords) problem where advertising budgets are expressed over multiple tiers of user-attribute granularity. We show that, unlike in the single-budget AdWords problem, obtaining a constant competitive ratio is impossible and give asymptotically tight upper and lower bounds. However, we then observe that in many real-world scenarios, multi-tier budgets have a laminar structure. In this setting we obtain a competitive ratio of e/(e−1) in the small bids case, which matches the best known AdWords result for single budgets.

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

As demands for users’ applications’ data increase, the world’s computing platforms are moving towards more capable machines – servers and warehouse-scale datacenters. Diverse users share datacenters for complex computation and compete for shared resources. In some systems, such as public clouds where users pay for reserved hardware, management policies pursue performance goals. In contrast, private systems consist of users who voluntarily combine their resources and subscribe to a common management policy. These users reserve the right to opt-out from shared systems if resources are managed poorly. The system management framework needs to ensure fairness among strategic users, encouraging users to participate while guaranteeing individual performance and preserving the system’s performance. Microeconomic models are well suited for studying individual behavior and the allocation of scarce resources. In this thesis, we present three pieces of work on task colocation, resource allocation, and task scheduling problems to demonstrate the effectiveness of a microeconomic approach.

Colocating applications on shared hardware (i.e., chip-multiprocessors) improves server utilization but introduces resource contention into the memory subsystem. In the first work, we design a colocation framework based on cooperative game theory to manage shared resource contention. Our framework uses a recommendation system to predict individual applications preferences for colocated tasks. It then uses these predictions to drive novel colocation mechanisms to guarantee user fairness and preserve system performance. Attractive system outcomes encourage strategic users to participate in the datacenter.

Processor allocations are inefficient when they are based on static reservations because reservations are often conservative; users rarely know their application’s needs across time, especially when applications have complex phase behavior. In the second work, we propose a fast, lightweight performance prediction framework to help users capture their phase behaviors in parallel applications. We design a dynamic and distributed core allocation framework so that users can trade resources for better efficiency based on predicted performance. Our management framework provides efficient allocations and game-theoretic fairness guarantees. In the last work, we characterize applications’ sensitivity to non-uniform memory access (NUMA) in big memory servers. We develop performance and energy models for communication costs in a blade server. We use this model to perform case studies on NUMA-aware scheduling policies and task queue management. Our parameterized models lay the foundation for the coordinated design of scheduling policies and hardware configurations. This method can be further used to design locality-aware schedulers with microeconomic models, e.g., dynamic pricing strategies for city parking.