Classes are held on Sundays and Tuesdays 16-18 in Shprintzak 28. The Sunday sessions will be held only on alternate weeks (recall that the course is 3 points).
Exercises are to be done in pairs. Note that this means that both members of the pair should work on each one, not that you alternate!
Textbook chapters are listed in case you need to make up some study materials. Listed references are for added reading if you are interested; they are not required if you come to the lectures.
The following plan is subject to change — each week is final only after it happens...
| Class | Lecture material | Exercises | |
|---|---|---|---|
| Introduction: | |||
| 1 | 21/2/10 |
Motivation and problems The issues: techniques, metrics, and workloads Using measurements, simulations, and analysis Jain chap. 2, 3 |
|
| 23/2/10 |
Visual data representation
(slides) Different types of graphs Avoiding misleading representation Jain chap. 10, 11; Tufte, The Visual display of Quantitative Information, 1983; Michael Friendly's Gallery of Data Visualization |
ex1: plotting research results | |
| 2 | 2/3/10 | Introduction to event-driven simulation |
ex2a: basic event-driven simulation |
| Queueing analysis: | |||
| 3 | 7/3/10 |
Queues and queueing networks Response time, utilization, and system dynamics The M/M/1 queue Jain chap. 30, 31 | |
| 9/3/10 |
Little's law Operational laws and bottleneck analysis Open vs. closed systems Jain chap. 31, 33 |
ex2b: simulating an M/M/1 queue | |
| 4 | 16/3/10 |
Case studies: Analysis of network router with bounded buffer Compare two slow processors to one fast one | ex3: analysis of join random queue |
| 5 | 23/3/10 |
Queueing networks Mean value analysis Jain chap. 32, 34 | ex4: simulating an M/M/k/b queue |
| Workloads: | |||
| 6 | 11/4/10 |
Workload analysis and characterization Summary statistics such as mean and median Feitelson, Workload modeling for performance evaluation. Performance 2002 tutorials (or the long version) |
|
| 13/4/10 |
Creating a variate from a distribution Jain chap. 12, 28; Law/Kelton chap. 6, 8 | ex5: generating random variates | |
| 7 | 25/4/10 |
Useful distributions Parameter estimation techniques and goodness of fit Comparing distributions using quantile-quantile plots Law/Kelton chap. 8; Jain chap. 29 | |
| 27/4/10 |
Heavy tails and long tails Power laws and the Pareto distribution Mass-count disparity and conditional expectation Popularity and the Zipf distribution Crovella, Performance evaluation with heavy tailed distributions. JSSPP 2001 |
ex6: fitting a distribution with Q-Q plots | |
| 8 | 4/5/10 |
Case study: load balancing Oblivious balancing Balancing based on workload characteristics Harchol-Balter and Downey, Exploiting process lifetime distributions for dynamic load balancing. ACM Trans. Comput. Syst. 15(3) pp. 253-285, Aug 1997 | ex7: characterizing requests from a web server |
| 9 | 9/5/10 |
Feedback in workloads (slides) The daily cycle of activity User-based workload modeling Shmueli and Feitelson, Using site-level modeling to evaluate the performance of parallel system schedulers. 14th MASCOTS, Sep 2006 | project: extracting feedback data |
| 11/5/10 |
Self similarity The Hurst parameter |
||
| Simulation: | |||
| 10 | 16/5/10 |
Event-driven vs. time-driven simulation Simulating the system in its steady state Jain chap. 24; Law/Kelton chap. 9; Pawlikowski, Steady-state simulation of queueing processes. ACM Comput. Surv. 22(2) pp. 123-170 Jun 1990 | ex8: simulation warmup |
| 11 | 23/5/10 |
Evaluating confidence intervals Termination conditions and simulation length Variance reduction Jain chap. 25, 12; Law/Kelton chap. 11 | |
| 25/5/10 |
Case study: networking evaluation
(slides) The ns-2 simulator and its use The PlanetLab infrastructure Paxson and Floyd, Difficulties in simulating the Internet. IEEE/ACM Trans. Netw. 9(4) pp. 392-403 Aug 2001 | ex9: simulating rain to find pi | |
| 12 | 1/6/10 |
Pitfalls in simulation Overload conditions | ex10: back to event-based simulations |
| 13 | 6/6/10 |
Case study: parallel job scheduling
(slides) Scheduling on parallel supercomputers Backfilling | |
| 8/6/10 |
(Case study continued) The effect of inaccurate runtime estimates | ex11: parallel job scheduling and backfilling | |
| The End: | |||
| 14 | 15/6/10 |
Summary of exercises and simulations Complementary approaches: measurement and experimentation Final quiz | |