-
Chang Woo Yang, Adam Wierman, Sanjay Shakkottai and Mor Harchol-Balter
Under submission.
[show/hide abstract]
Scheduling policies that are biased toward small jobs have received growing attention due to their superior mean delay performance. Such policies include Shortest-Remaining-Processing-Time (SRPT), Preemptive-Shortest-Job-First (PSJF), and Least-Attained-Service (LAS). In this paper, we study the delay distribution of LAS and the class of scheduling policies called SMART-LD (SMAll-Response- Time for Large-Deviations) that included SRPT, PSJF, and their variants to understand policies that prioritized short jobs. We study the delay distribution (rate function) of the SMART-LD class and LAS in a discrete-time queueing system under the many sources large deviations regime. We prove that all SMART-LD policies have the same asymptotic delay distribution as SRPT and illustrate the improvements SMART-LD policies and LAS make over First-Come-First-Served (FCFS). Furthermore, we show that the delay distribution of SMART-LD policies stochastically improves upon the delay distribution of LAS across all job sizes.
-
Jason Marden and Adam Wierman
Under submission.
[show/hide abstract]
We consider a variation of the resource allocation problem. In the traditional problem, there is a global planner who would like to assign a set of players to a set of resources so as to maximize welfare. We consider the situation where the global planner does not have the authority to assign players to resources; rather, players are self-interested. The question that emerges is how can the global planner entice the players to settle on a desirable allocation with respect to the social welfare? To study this question, we focus on a class of games that we refer to as distributed welfare games. Within this context, we investigate how the global planner should distribute the welfare to the players? We measure the efficacy of a distribution rule in two ways: (i) Does a pure Nash equilibrium exist? (ii) How does the welfare associated with a pure Nash equilibrium compare to the social welfare associated with the optimal allocation? In this paper we explore the applicability of cost sharing methodologies for distributing welfare in such resource allocation problems. We demonstrate that obtaining desirable distribution rules, such as distribution rules that are budget balanced and guarantee the existence of a pure Nash equilibrium, often comes at a significant informational and computational cost. In light of this, we derive a systematic procedure for designing desirable distribution rules with a minimal informational and computational cost for a special class of distributed welfare games. Furthermore, we derive a bound on the price of anarchy for distributed welfare games in a variety of settings. Lastly, we highlight the implications of these results using the problem of sensor coverage.
-
A.A.A. Kock, L.F.P. Etman, J.E. Rooda, L.J.B.F. Adan, M. van Vuuren and Adam Wierman
Under submission.
[show/hide abstract]
In this chapter, we propose an aggregate model for manufacturing systems consisting of tandem flow lines with finite buffers and parallel servers. The proposed model is a multiserver station with wip-dependent process times. We develop an algorithm to measure the wip-dependent process times directly from industrial data such as arrival times at and departure times from the manufacturing system. Simulation results show that the aggregate model accurately approximates the mean flow time.
-
Wei Chen, Dayu Huang, Ankur Kulkarni, Jayakrishnan Unnikrishnan, Quanyan Zhu, Prashant G. Mehta, Sean Meyn and Adam Wierman
Under submission.
[show/hide abstract]
TD learning and its refinements are powerful tools for approximating the solution to dynamic programming problems. However, the techniques provide the approximate solution only within a prescribed finite-dimensional function class. Thus, the question that always arises is how should the function class be chosen? The goal of this paper is to propose an approach for TD learning based on choosing the function class using the solutions to associated fluid and diffusion approximations. In order to illustrate this new approach, the paper focuses on an application to dynamic speed scaling for power management.
-
Jason Marden and Adam Wierman
Under submission.
[show/hide abstract]
Recently, game theory has been proposed as a tool for cooperative control. Specifically, the interactions of a multi-agent distributed system are modeled as a non-cooperative game where agents are self-interested. In this work, we prove that this approach of non-cooperative control has limitations with respect to engineering multi-agent systems. In particular, we prove that it is not possible to design budget balanced agent utilities that also guarantee that the optimal control is a Nash equilibrium. However, it is important to realize that game-theoretic designs are not restricted to the framework of non-cooperative games. In particular, we demonstrate that these limitations can be overcome by conditioning each player's utility on additional information, i.e., a state. This utility design fits into the framework of a particular form of stochastic games termed state-based games and is applicable in many application domains.
-
Ho-Lin Chen, Jason Marden and Adam Wierman
Proceedings of INFOCOM, 2009.
[show/hide abstract]
Load balancing is a common approach to task assignment in distributed architectures. In this paper, we show that the degree of inefficiency in load balancing designs is highly dependent on the scheduling discipline used at each of the back-end servers. Traditionally, the back-end scheduler can be modeled as Processor Sharing (PS), in which case the degree of inefficiency grows linearly with the number of servers. However, if the back-end scheduler is changed to Shortest Remaining Processing Time (SRPT), the degree of inefficiency can be independent of the number of servers, instead depending only on the heterogeneity of the speeds of the servers. Further, switching the back-end scheduler to SRPT can provide significant improvements in the overall mean response time of the system as long as the heterogeneity of the server speeds is small.
-
Lachlan L. H. Andrew, Adam Wierman and Ao Tang
Perf. Eval. Review, 2009.
[show/hide abstract]
This paper investigates the performance of online dynamic speed scaling algorithms for the objective of minimizing a linear combination of energy and response time. We prove that (SRPT, $P^-1(n)$), which uses Shortest Remaining Processing Time (SRPT) scheduling and processes at speed such that the power used is equal to the queue length, is 2-competitive for a very wide class of power-speed tradeoff functions. Further, we prove that there exist tradeoff functions such that no algorithm can attain a competitive ratio less than 2.
-
Adam Wierman, Lachlan L. H. Andrew and Ao Tang
Proceedings of INFOCOM, 2009.
[show/hide abstract]
Energy usage of computer communications systems has quickly become a vital design consideration. One effective method for reducing energy consumption is dynamic speed scaling, which adapts the processing speed to the current load. This paper studies how to optimally scale speed to balance mean response time and mean energy consumption under processor sharing scheduling. Both bounds and asymptotics for the optimal speed scaling scheme are provided. These results show that a simple scheme that halts when the system is idle and uses a static rate while the system is busy provides nearly the same performance as the optimal dynamic speed scaling. However, the results also highlight that dynamic speed scaling provide at least one key benefit -- significantly improved robustness to bursty traffic and mis-estimation of workload parameters.
-
Misja Nuyens, Adam Wierman and Bert Zwart
Operations Research, 2008. 56(1):88-101.
[show/hide abstract]
Recently, the class of SMART scheduling policies (disciplines) has been introduced in order to formalize the common heuristic of ``biasing toward small jobs.'' We study the tail of the sojourn-time (response-time) distribution under both SMART policies and the Foreground-Background policy (FB) in the GI/GI/1 queue. We prove that these policies behave very well under heavy-tailed service times, but behave poorly under light-tailed service times. Specifically, for heavy-tailed service times, we show that the sojourn-time tail under FB and all SMART policies are equal to that of the service time tail, up to a constant. In contrast, for light-tailed service times with no mass in the endpoint of the distribution, we show that, on a logarithmic scale, the sojourn-time tail of FB and all SMART policies is as large as possible.
-
Misja Nuyens and Adam Wierman
Performance Evaluation, 2008. 65(3-4):286-307.
[show/hide abstract]
Recently, computer systems researchers have begun to apply the Foreground-Background (FB) scheduling discipline to a variety of applications, and as a result, there has been a resurgence in theoretical research studying the discipline as well. In this paper, we will bring together results from both of these research streams and provide a survey of state-of-the-art theoretical results characterizing the performance of FB with emphasis on the impact of these results to computer systems.
-
Adam Wierman and Misja Nuyens
Proceedings of ACM Sigmetrics, 2008.
[show/hide abstract]
Motivated by the optimality of Shortest Remaining Processing Time (SRPT) for mean response time, in recent years many computer systems have used the heuristic of favoring small jobs in order to dramatically reduce user response times. However, rarely do computer systems have knowledge of exact remaining sizes. In this paper, we introduce the class of epsilon-SMART policies, which formalizes the heuristic of favoring small jobs in a way that includes a wide range of policies that schedule using inexact job-size information. Examples of epsilon-SMART policies include (i) policies that use exact size information, e.g., SRPT and PSJF, (ii) policies that use job-size estimates, and (iii) policies that use a finite number of size-based priority levels. For many epsilon-SMART policies, e.g., SRPT with inexact jobsize information, there are no analytic results available in the literature. In this work, we prove four main results: we derive upper and lower bounds on the mean response time, the mean slowdown, the response-time tail, and the conditional response time of epsilon-SMART policies. In each case, the results explicitly characterize the tradeoff between the accuracy of the job-size information used to prioritize and the performance of the resulting policy. Thus, the results provide designers an understanding of how accurate job-size information must be in order to achieve desired performance guarantees.
-
Ho-Lin Chen, Jason Marden and Adam Wierman
Performance Evaluation Review, 2008. 36(2):110-112.
[show/hide abstract]
Load balancing is a common approach to distributed task assignment. In this paper we study the degree of inefficiency in load balancing designs. We show that the degree of inefficiency is highly dependent on the back-end scheduler.
-
Jason Marden and Adam Wierman
Proceedings of CDC, 2008.
[show/hide abstract]
We consider a variation of the resource allocation problem. In the traditional problem, there is a global planner who would like to assign a set of players to a set of resources so as to maximize social welfare. We consider the situation where the global planner does not have the authority to assign players to resources; rather, players are self-interested. The question that emerges is how can the global planner entice the players to settle on a desirable allocation with respect to the social welfare? To study this question, we focus on a class of games that we refer to as distributed welfare games. Within this context, we investigate how the global planner should distribute the social welfare to the players? We measure the efficacy of a distribution rule in two ways: (i) Does a pure Nash equilibrium exist? (ii) How does the social welfare of a pure Nash equilibrium compare to the social welfare of the optimal allocation? This comparison is referred to as the price of anarchy. To answer these questions, we derive sufficient conditions on the distribution rule that ensures the existence of a pure Nash equilibrium in any single-selection distributed welfare game. Furthermore, we derive a price of anarchy for distributed welfare games in a variety of settings. Lastly, we highlight the implications of these results using the sensor coverage problem.
-
Stochastic analysis of power-aware scheduling
Adam Wierman, Lachlan L. H. Andrew and Ao Tang
Proc. of Allerton, 2008.
[show/hide abstract]
Energy consumption in a computer system can be reduced by dynamic speed scaling, which adapts the processing speed to the current load. This paper studies the optimal way to adjust speed to balance mean response time and mean energy consumption, when jobs arrive as a Poisson process and processor sharing scheduling is used. Both bounds and asymptotics for the optimal speeds are provided. Interestingly, a simple scheme that halts when the system is idle and uses a static rate while the system is busy provides nearly the same performance as the optimal dynamic speed scaling. However, dynamic speed scaling which allocates a higher speed when more jobs are present significantly improves robustness to bursty traffic and mis-estimation of workload parameters.
-
Adam Wierman
Invited paper in Performance Evaluation Review, 2007. 34(4):4 - 12.
[show/hide abstract]
The growing trend in computer systems towards using scheduling policies that prioritize jobs with small service requirements has resulted in a new focus on the fairness of such policies. In particular, researchers have been interested in whether prioritizing small job sizes results in large jobs being treated
-
Adam Wierman
Co-recipient of the CMU SCS Distinguished Dissertation Award
Finalist receiving Honorable Mention for the INFORMS OR in Telecommunications Dissertation Award Ph.D. Thesis, 2007.
-
Adam Wierman, Erik Winands and Onno Boxma
Performance Evaluation, 2007. 64:1009-1028. Also appeared in the Proceedings of IFIP Performance 2007.
[show/hide abstract]
We present a simple mean value analysis (MVA) framework for analyzing the effect of scheduling within queues in classical asymmetric polling systems with gated or exhaustive service. Scheduling in polling systems finds many applications in computer and communication systems. Our framework leads not only to unification but also to extension of the literature studying scheduling in polling systems. It illustrates that a large class of scheduling policies behaves similarly in the exhaustive polling model and the standard M/GI/1 model, whereas scheduling policies in the gated polling model behave very differently than in an M/GI/1.
-
Adam Wierman
Proceedings of Allerton, 2007.
[show/hide abstract]
In recent years, the response times experienced by large job sizes have been the focus of a growing number of papers. Though results about many scheduling disciplines have appeared, to this point, results characterizing the response time of large job sizes have been limited to either mean value analysis or law of large numbers scalings. We will present a novel framework that unifies these results and provides new results characterizing the distributional behavior of large job sizes. Also, we will illustrate the impact these new results have (i) for the analysis of the response time tail, (ii) for the analysis of busy periods, and (iii) for predicting response times of customers upon arrival.
-
Adam Wierman, Takayuki Osogami, Mor Harchol-Balter and Alan Scheller-Wolf
Performance Evaluation, 2006. 63(12):1253-1272.
[show/hide abstract]
We ask the question, ``for minimizing mean response time, which is preferable: one fast server of speed 1, or k slow servers each of speed 1/k?'' Our setting is the M/PH/k system with two priority classes of customers, high priority and low priority, where PH is a phase-type distribution. We find that multiple slow servers are often preferable, and we demonstrate exactly how many servers are preferable as a function of the load and service time distribution. In addition, we find that the optimal number of servers with respect to the high priority jobs may be very different from that preferred by low priority jobs, and we characterize these preferences. We also study the optimal number of servers with respect to overall mean response time, averaged over high and low priority jobs. Lastly, we ascertain the effect of the service demand variability of high priority jobs on low priority jobs.
-
Bianca Schroeder, Adam Wierman and Mor Harchol-Balter
Proceedings of NSDI, 2006.
[show/hide abstract]
Workload generators may be classified as based on a closed system model, where new job arrivals are only triggered by job completions (followed by think time), or an open system model, where new jobs arrive independently of job completions. In general, system designers pay little attention to whether a workload generator is closed or open. Using a combination of implementation and simulation experiments involving static and dynamic workloads, this paper illustrates that there is a vast difference in behavior between these open and closed models in real-world settings. In addition, this work synthesizes many of the differences in behavior between the models into eight simple principles.
-
Bianca Schroeder, Mor Harchol-Balter, Arun Iyengar, Erich Nahum and Adam Wierman
Proceedings of IEEE ICDE, 2006.
[show/hide abstract]
Scheduling/prioritization of DBMS transactions is important for many applications that rely on database backends. A convenient way to achieve scheduling is to limit the number of transactions within the database, maintaining most of the transactions in an external queue, which can be ordered as desired by the application. While external scheduling has many advantages in that it doesn't require changes to internal resources, it is also difficult to get right, in that its performance depends critically on the particular multiprogramming limit used (the MPL), i.e. the number of transactions allowed into the database. If the MPL is too low, throughput will suffer, since not all DBMS resources will be utilized. On the other hand, if the MPL is too high, there is insufficient control on scheduling. The question of how to adjust the MPL to achieve both goals simultaneously is an open problem, not just for databases but in system design in general. Herein we study this problem in the context of transactional workloads, both via extensive experimentation and queueing theoretic analysis. We find that the two most critical factors in adjusting the MPL are the number of resources that the workload utilizes and the variability of the transactions' service demands. We develop a feedback based controller, augmented by queueing theoretic models for automatically adjusting the MPL. Finally, we apply our methods to the specific problem of external prioritization of transactions. We find that external prioritization can be nearly as effective as internal prioritization, without any negative consequences, when the MPL is set appropriately.
-
Chang Woo Yang, Adam Wierman, Sanjay Shakkottai and Mor Harchol-Balter
Proceedings of ACM Sigmetrics, 2006.
[show/hide abstract]
Scheduling policies that prioritize short jobs have received growing attention in recent years. The class of SMART policies includes many such disciplines, e.g. Shortest Remaining Processing Time (SRPT) and Preemptive Shortest Job First (PSJF). In this work, we study the delay distribution of SMART policies and contrast this distribution with that of the Least-Attained-Service (LAS) policy, which indirectly favors short jobs by prioritizing jobs with the least attained service (age). We study the delay distribution (rate function) of LAS and the SMART class in a discrete-time queueing system under the many flows regime. Our analysis in this regime (large capacity and large number of flows) is enabled by the introduction of a two dimensional queue representation, which creates tie-break rules. These additional rules do not alter the policies, but greatly simplify their analysis. We demonstrate that the queue evolution of all the above policies can be described under this single two dimensional framework. We prove that all SMART policies have the same delay distribution as SRPT and illustrate the improvements SMART policies make over First-Come-First-Served (FCFS). Furthermore, we show that the delay distribution of SMART policies stochastically improves upon the delay distribution of LAS. However, the delay distribution under LAS is not too bad -- the distribution of delay under LAS for most jobs sizes still provides improvement over FCFS. Our results are complementary to prior work that studies delay-tail behavior in the large buffer regime under a single flow.
-
Adam Wierman
Performance Evaluation Review, 2006. 34(3):21-23.
-
Adam Wierman, Mor Harchol-Balter and Takayuki Osogami
Proceedings of ACM Sigmetrics, 2005.
[show/hide abstract]
We define the class of SMART scheduling policies. These are policies that bias towards jobs with small remaining service times, jobs with small original sizes, or both, with the motivation of minimizing mean response time and/or mean slowdown. Examples of SMART policies include PSJF, SRPT, and hybrid policies such as RS (which biases according to the product of the remaining size and the original size of a job). For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely insensitive to the variability of the job size distribution. In particular, we focus on the SRPT and PSJF policies and prove insensitive bounds in these cases.
-
Adam Wierman and Mor Harchol-Balter
Proceedings of ACM Sigmetrics, 2005.
[show/hide abstract]
In addition to providing small mean response times, modern applications seek to provide users predictable service and, in some cases, Quality of Service (QoS) guarantees. In order to understand the predictability of response times under a range of scheduling policies, we study the conditional variance in response times seen by jobs of different sizes. We define a metric and a criterion that distinguish between contrasting functional behaviors of conditional variance, and we then classify large groups of scheduling policies. In addition to studying the conditional variance of response times, we also derive metrics appropriate for comparing higher conditional moments of response time across job sizes. We illustrate that common statistics such as raw and central moments are not appropriate when comparing higher conditional moments of response time. Instead, we find that cumulant moments should be used.
-
Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf and Adam Wierman
Queueing Systems, 2005. 51:331-360.
[show/hide abstract]
We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes -- ``smart'' prioritization (giving priority to the smaller jobs) versus ``stupid'' prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the $m$ classes into just two classes.
-
Adam Wierman
Thesis Proposal, 2005.
-
Adam Wierman, Nikhil Bansal and Mor Harchol-Balter
Operations Research Letters, 2004. 32:73-76.
[show/hide abstract]
We compare the overall mean response time (a.k.a. sojourn time) of the Processor Sharing (PS) and Feedback (FB) queues under an M/GI/1 system. We show that FB outperforms PS under service distributions having decreasing failure rates; whereas PS outperforms FB under service distributions having increasing failure rates.
-
Adam Wierman, Julia Salzman, Michael Jablonski and Anant Godbole
Discrete Mathematics, 2004. 275:367-373.
[show/hide abstract]
Given a configuration of t indistinguishable pebbles on the n verticies of a graph G, we say that a vertex v can be reached if a pebble can be placed on it in a finite number of ``moves.'' G is said to be pebbleable if all its verticies can be thus reached. Now given the n-path P_n how large (resp. small) must t be so as to be able to pebble the path almost surely (resp. almost never)? It was known that the threshold th(P_n) for pebbling satisfies $n 2^c \sqrt\lg n \leq th(P_n) \leq n 2^\sqrt\lg n$, where $c < 1 /\sqrt2 is arbitrary. We improve the upper bound for the threshold function to $th(P_n) \leq n 2^d \sqrt\lg n, where $d>1$ is arbitrary.
-
Adam Wierman and Mor Harchol-Balter
Performance Evaluation Review, 2004. 32(2):12-13.
-
Takayuki Osogami, Adam Wierman, Mor Harchol-Balter and Alan Scheller-Wolf
Performance Evaluation Review, 2004. 32(2):3-5.
-
Adam Wierman, Takayuki Osogami and Jorgen Olsen
Performance Evaluation Review, 2003. 31(2):6-8.
-
Adam Wierman, Takayuki Osogami and Jorgen Olsen
Proceedings of MASCOTS, 2003.
[show/hide abstract]
We present a general analytical framework for the modeling and analysis of TCP variations. The framework allows the modeling of multiple variations of TCP, including TCP-Vegas, TCP-SACK, and TCP-Reno, under general network situations. In particular, the framework allows us to propose the first analytical model of TCP-Vegas for arbitrary on-off traffic that is able to predict the operating point of the network. The analysis provided by our framework leads to many interesting observations with respect to both the behavior of bottleneck links that are shared by TCP sources and the effectiveness of the design decisions in TCP-SACK and TCP-Vegas.
-
Adam Wierman and Mor Harchol-Balter
Best Student Paper Award recipient
Proceedings of ACM Sigmetrics, 2003.
[show/hide abstract]
It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy's fairness. For example, a policy that biases towards small job sizes so as to minimize mean response time may end up being unfair to large job sizes. In this paper we define three types of unfairness and demonstrate large classes of scheduling policies that fall into each type. We end with a discussion on which jobs are the ones being treated unfairly.
-
Nikhil Bansal and Adam Wierman
Carnegie Mellon School of Computer Science Technical Report CMU-CS-02-201, 2002.
[show/hide abstract]
We propose a framework for comparing the performance of two queueing policies. Our framework is motivated by the notion of competitive analysis, widely used by the computer science community to analyze the performance of online algorithms. We apply our framework to compare M/GI/1/FB and M/GI/1/SJF with M/GI/1/SRPT, and obtain new results about the performance of M/GI/1/FB and M/GI/1/SJF.
-
Mor Harchol-Balter, Karl Sigman and Adam Wierman
Performance Evaluation Review, 2002. 30(3):9-11.
-
Mor Harchol-Balter, Karl Sigman and Adam Wierman
Performance Evaluation, 2002. 49(1-4):241-256.
[show/hide abstract]
We explore the performance of an M/GI/1 queue under various scheduling policies from the perspective of a new metric: the slowdown experienced by largest jobs. We consider scheduling policies that bias against large jobs, towards large jobs, and those that are fair, e.g., Processor-Sharing. We prove that as job size increases to infinity, all work conserving policies converge almost surely with respect to this metric to no more than $1/(1 - \rho)$, where $\rho$ denotes load. We also find that the expected slowdown under any work conserving policy can be made arbitrarily close to that under Processor-Sharing, for all job sizes that are sufficiently large.