What Queueing Theory Teaches us About Computer Systems Design

Tutorial for The 42nd International Symposium on Computer Architecture (ISCA-2015)

Mor Harchol-Balter

Computer Science Dept, Carnegie Mellon University

Morning: SUNDAY, June 14th

Based on the new textbook,

Cambridge University Press, 2013:

THE TALK SLIDES ARE HERE: SLIDES

Abstract of Tutorial

The primary purpose of this tutorial is to explore fundamental questions in computer systems design and learn what answers queueing theory provides. Examples of such questions include:

Given a choice between a single (fast) machine or many (slow) machines, which is preferable and when?
What are good "load balancing" policies, and when does it make sense to balance load?
How do high job size variability and heavy-tailed workloads affect the choice of a scheduling policy?
If the arrival rate doubles, and the service capacity doubles, does that mean that response time should stay the same?
What are the differences one should watch for in designing closed-loop systems (where a new job only starts when a job completes) as compared with open systems (where job arrivals are independent of completions)?
If a scheduling policy favors one set of jobs, does it necessarily hurt other jobs, and by how much?
What are the big lessons in capacity provisioning? How many "spare" servers does one need? What about setup times? How much does replication help?

We will cover the standard terms that come up in queueing:

What is load? What is throughput?
What is an open system versus a closed system?
What is an Exponential distribution? What is a heavy-tailed distribution?
What is a Poisson process?
What is the Inspection Paradox?
What is a continuous-time Markov Chain?
What is a "setup time?"
What is an M/M/1, M/G/1, G/G/1, M/M/k, M/G/k, etc?
What are the common scheduling policies, and how do they compare?
What is the effect of priority on response time?
What are the common load balancing policies, and how do they compare?
What is Square-root Staffing?
What are Jackson networks of queues, and what's known about these?

We will follow the textbook, "Performance Modeling & Design of Computer Systems," whose outline is given here .

All my talks are highly interactive and fun. This talk will include LOTS of PRIZES!

Target Audience and Prerequisites

The target audience is ISCA attendees who are interested in an introduction to analytical performance modeling, for use in their work. There are NO prerequisites. No math background is needed. Tutorial will focus on lessons and intuitions, rather than derivations.

Bio

Mor Harchol-Balter is a Professor in the Computer Science at Carnegie Mellon University. Professor Harchol-Balter is heavily involved in the ACM SIGMETRICS research community, where she served as Technical Program Chair for Sigmetrics 2007 and as General Chair for Sigmetrics 2013. Mor's work focuses on designing new resource allocation policies (load balancing policies, power management policies, and scheduling policies) for server farms and distributed systems in general. She is known for her work in queueing analysis, workload characterization, and systems implementation. Professor Harchol-Balter has won a large number of teaching awards and is known for highly entertaining technical talks . She has graduated many PhD students, most of whom are now professors in top academic institutions.