Modeling and Performance Evaluation
Description
This course will cover the fundamentals of the techniques of modeling and performance evaluation of computer systems. Designing computer systems invoves analyzing the cost-benefit tradeoffs. For example, one might need to guarantee a response time SLA or certain throughput requirement, while at the same time staying within a power budget or cost budget. On the other hand, one often has many choices: One fast disk, or two slow ones? More memory, or a faster processor? A fair scheduler or one that minimizes mean response time? The best choices are often counter-intuitive. Ideally, one would like to have answers to these questions before investing the time and money to build a system. This class will introduce students to analytic stochastic modeling with the aim of answering the above questions.
Topics covered:
- Operational Laws: Little's Law, response-time law, asymptotic bounds, modification analysis, performance metrics;
- Markov Chain Theory: discrete-time Markov chains, continuous-time Markov chains, renewal theory, time-reversibility; Poisson Process: memorylessness, Bernoulli splitting, uniformity, PASTA;
- Queueing Theory: open networks, closed networks, time-reversibility, Renewal-Reward, M/M/1, M/M/k, M/M/k/k, Burke's theorem, Jackson networks, classed networks, load-dependent servers, BCMP result and proof, M/G/1 full analysis, M/G/k, G/G/1, transform analysis (Laplace and z-transforms);
- Simulations: time averages versus ensemble averages, generating random variables for simulation, Inspection Paradox;
- Fluid Modeling: Mean value models for fundamentally discrete valued processes like TCP;
- Management of Server Farms: capacity provisioning, dynamic power management, routing policies;
- Analysis of Scheduling: FCFS, non-preemptive priorities, preemptive priorities, PS, LCFS, FB, SJF, PSJF, SRPT, etc.
Prerequisites
- Some familiarity with Operating Systems and Networks
- A high comfort level with concepts of Probability (say B or better in a senior/graduate level course in Probability)
- Comfort with a high level language like C, C++ or Java (or MATLAB)
Textbook
Performance Modeling and Design of Computer Systems: Queueing Theory in Action, by Mor Harchol-BalterTime and location, Spring 2014:
Thursdays: 10:10A-12:00P, Mudd 1127