Classes are held on Tuesdays 16-18 in Shprintzak 28
Once every 3 weeks we will have an extra targil hour, associated with a sub-series of exercises devoted to developing a simulation of parallel job scheduling and understanding the subtleties involved in it. In other weeks this time will be used to answer questions if need be (recall that the course is 3 points); alternatively you may have personal meetings with the TA.
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 | |
|---|---|---|---|
| 1 | 13/5/08 |
Introduction: motivation and problems the issues: techniques, metrics, and workloads using measurements, simulations, and analysis Jain chap. 2, 3 |
EXTRA HOUR ex1(sim): basic event-driven simulation reference output from ex1 |
| 2 | 16/5/08 (extra class) 9:30 AM in Tsrif HaMorim |
Data presentation:
(slides) options for showing data avoiding misleading representation Jain chap. 10, 11; Tufte, The Visual display of Quantitative Information, 1983; Michael Friendly's Gallery of Data Visualization; Ploticus gallery | |
| 3 | 20/5/08 |
Workloads: workload analysis and characterization summary statistics such as mean and median creating a variate from a distribution Jain chap. 12, 28; Law/Kelton chap. 6, 8; Feitelson, Workload modeling for performance evaluation. Performance 2002 tutorials (or the long version) |
ex2: generating random variates |
| 4 | 27/5/08 |
useful distributions and goodness of fit comparing distributions using quantile-quantile plots Law/Kelton chap. 8; Jain chap. 29 | ex3: fitting a distribution with Q-Q plots |
| 5 | 3/6/08 |
heavy tails Crovella, Performance evaluation with heavy tailed distributions. JSSPP 2001 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 |
EXTRA HOUR ex4(sim): load scaling and performance |
| 6 | 10/6/08 |
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 | ex5: extracting feedback data |
| 7 | 17/6/08 |
Simulation: 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 | ex6: simulation warmup |
| 8 | 24/6/08 |
evaluating confidence intervals termination conditions and simulation length variance reduction Jain chap. 25, 12; Law/Kelton chap. 11 |
EXTRA HOUR ex7(sim): scheduling parallel jobs with backfilling |
| 9 | 1/7/08 |
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 | ex8: simulating rain to find pi |
| 10 | 8/7/08 |
Queueing analysis: response time, utilization, and system dynamics Little's law the M/M/1 queue Jain chap. 30, 31 | ex9: simulating an M/M/1 queue |
| 11 | 15/7/08 |
queueing networks operational laws and bottleneck analysis Jain chap. 32, 33 |
EXTRA HOUR ex10(sim): parallel scheduling competition |
| 12 | 22/7/08 |
Case studies: analysis of network router with bounded buffer compare two slow processors to one fast one | ex11: analysis of join random queue |
| 13 | 29/7/08 |
summary of exercises and simulations complementary approaches: measurement and experimentation | |