Performance Modeling and Design of Computer Systems

by Harchol-balter, Mor

• ISBN13: 9781107027503
• ISBN10: 1107027500
• Format: Hardcover
• Copyright: 2013-02-18
• Publisher: Cambridge Univ Pr

Summary

Computer systems design is full of conundrums: -Given a choice between a single machine with speed s, or n machines each with speed s/n, which should we choose? -If both the arrival rate and service rate double, will the mean response time stay the same? -Should systems really aim to balance load, or is this a convenient myth? -If a scheduling policy favors one set of jobs, does it necessarily hurt some other jobs, or are these "conservation laws" being misinterpreted? -Do greedy, shortest-delay, routing strategies make sense in a server farm, or is what's good for the individual disastrous for the system as a whole? -How do high job size variability and heavy-tailed workloads affect the choice of a scheduling policy? -How should one trade off energy and delay in designing a computer system? -If 12 servers are needed to meet delay guarantees when the arrival rate is 9 jobs/sec, will we need 12,000 servers when the arrival rate is 9,000 jobs/sec? Tackling the questions that systems designers care about, this book brings queueing theory decisively back to computer science. The book is written with computer scientists and engineers in mind and is full of examples from computer systems, as well as manufacturing and operations research. Fun and readable, the book is highly approachable, even for undergraduates, while still being thoroughly rigorous and also covering a much wider span of topics than many queueing books. Readers benefit from a lively mix of motivation and intuition, with illustrations, examples, and more than 300 exercises - all while acquiring the skills needed to model, analyze, and design large-scale systems with good performance and low cost. The exercises are an important feature, teaching research-level counterintuitive lessons in the design of computer systems. The goal is to train readers not only to customize existing analyses but also to invent their own.

Table of Contents

Introduction to Queueing

Motivating examples

Queueing theory terminology

Necessary Probability Background

Probability review

Generating random variables

Sample paths, convergence, and averages

The Predictive Power of Simple Operational Laws: 'What If' Questions and Answers

Operational laws

Modification analysis

From Markov Chains to Simple Queues

Discrete-time Markov Chains

Ergodicity theory

Real-world examples: Google, Aloha

Generating functions for Markov Chains

Exponential distributions and Poisson Process

Transition to continuous-time Markov Chains

M/M/1 and PASTA

Server Farms and Networks: Multi-server, Multi-queue Systems

Server farms: M/M/k and M/M/k/k

Capacity provisioning for server farms

Time-reversibility and Burke's Theorem

Jackson network of queues

Classed network of queues

Closed networks of queues

Real-World Workloads: High-Variability and Heavy Tails

Tales of tails: real-world workloads

Phase-type workloads and matrix-analytic

Networks of time-sharing (PS) servers

M/G/I queue and inspection paradox

Task assignment for server farms

Transform analysis

M/G/I transform analysis

Power optimization application

Smart Scheduling

Performance metrics

Non-preemptive, non-size-based policies

Preemptive, non-size-based policies

Non-preemptive, size-based policies

Preemptive, size-based policies

Scheduling: SRPT and fairness

Table of Contents provided by Publisher. All Rights Reserved.