EEC 685/785 Modeling and Performance Evaluation of Computer Systems

EEC 685/785 Modeling and Performance Evaluation of Computer Systems, Fall 2003

Date	Content	Reading	Homework Due
Date	Textbook	Reading	Homework Due
Aug 26	1 Introduction
Aug 28	2-3 Introduction, Metrics	Ch. 2, 3
Sep 2	4-8 Workloads, Monitors	Ch. 6,7
Sep 4	9 Capacity		(HW #1)
Sep 9	10-13 Data presentation, Ratio games	Ch. 11-13
Sep 11	14 Regression models	Ch. 14	HW #1
Sep 16	15 Regression models	Ch. 15
Sep 18	Paper presentation #1		Paper #1
Sep 23	16-23 Experimental design	Ch. 16-18
Sep 25	24-25 Simulation & Analysis of simulation results	Ch. 24-25
Sep 30	Paper presentation #2		Paper #2
Oct 2	26 Random number generation	Ch. 26	(HW #2)
Oct 7	27 RNG testing	Ch. 27
Oct 9	28 Random variate generation	Ch. 28	HW #2
Oct 14	29 Commonly used distributions	Ch. 29
Oct 16	Midterm Exam
Oct 21	29 Commonly used distributions
Oct 23	30 Introduction to Queueing Theory	Ch. 30
Oct 28	30 Introduction to Queueing Theory		(HW #3)
Oct 30	31 Analysis of a Single Queue	Ch. 31
Nov 4	31 Analysis of a Single Queue		HW #3
Nov 6	Paper presentation #3		Paper #3
Nov 11	NO CLASS (Veteran¡¯s Day)
Nov 13	32 Queueing Networks	Ch. 32
Nov 18	33 Operational Laws	Ch. 33
Nov 20	33 Operational Laws		Paper #4
Nov 25	Paper presentation #4		(HW #4)
Nov 27	NO CLASS (Thanksgiving Day)
Dec 2	34 Mean Value Analysis	Ch. 34	HW #4
Dec 4	34 Mean Value Analysis
Dec 11	Final Exam

Paper set #1: General statistics

1. D. J. Low, ¡°Statistical physics: Following the crowd,¡± Nature 407, 465 - 466 (2000).

2. Dow Jones Averages

3. P.J.Fleming and J. J. Wallace, "How Not To Lie With Statistics: The Correct Way To Summarize Benchmark Results," Comm. ACM, Vol. 29, No. 3, March 1986, pp. 218-221.

4. James E. Smith, ¡°Characterizing Computer Performance with a Single Number,¡± Comm. ACM, pp. 1202-1206, October 1988.

5. AccuWeather.com

6. Standard Performance Evaluation Corporation

7. Transaction Processing Performance Council

Paper set #2: Benchmarks, Monitoring, and Modeling

1(a) Ran Giladi and Niv Ahituv,"SPEC as a Performance Evaluation Measure," IEEE Computer, Vol. 28, No. 8, August 1995, pp. 33-42.

1(b) John L. Henning, ¡°SPEC CPU2000: Measuring CPU Performance in the New Millennium,¡± IEEE Computer, Vol. 33, No. 7, pp. 28-35, July 2000.

1(c++) Nikki Mirghafori, Margret Jacoby, and David Patterson, "Truth in SPEC Benchmarks," ACM Computer Architecture News, Vol. 23, No. 5, December 1995, pp. 34-42.

2(a) Chunho Lee and Miodrag Potkonjak and William H. Mangione-Smith, ¡°MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communicatons Systems,¡± International Symposium on Microarchitecture, pp. 330-335, 1997.

2(b) Jakob Engblom, ¡°Why SpecInt95 Should Not Be Used to Benchmark Embedded Systems Tools,¡± Workshop on Languages, Compilers, and Tools for Embedded Systems, pp. 96-103, 1999.

3(a) B. Sprunt, ¡°The Basics of Performance-Monitoring Hardware,¡± IEEE Micro, Vol. 22, No. 4, pp. 64-71, Jul./Aug. 2002.

3(b) B. Sprunt, ¡°Pentium 4 Performance-Monitoring Features,¡± IEEE Micro, Vol. 22, No. 4, pp. 72-82, Jul./Aug. 2002.

4. Andy C. Bavier and Allen Brady Montz and Larry L. Peterson, ¡°Predicting MPEG Execution Times,¡± Measurement and Modeling of Computer Systems, pp. 131-140, 1998.

5(a) George Marsaglia, "Technical Correspondence: Remarks on Choosing and Implementing Random Number Generators," Communications of the ACM, Vol. 36, No. 7, July 1993, pp. 105-110.

5(b) Park, S.K., and Miller, K.W. "Random Number Generators: Good Ones are Hard to Find," Communications of the ACM 31, 10 (Oct. 1988), pp 1192-1201.

6. T. Camp and J. Boleng and V. Davies, ¡°A Survey of Mobility Models for Ad Hoc Network Research,¡± Wireless Communications and Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking:  Research, Trends and Applications, Vol. 2, No. 5, pp. 483-502, 2002.

Paper set #3: Power Law, Ad hoc network

1. R. L. Axtell, ¡°Zipf Distribution of US Firm Sizes,¡± Science, Vol. 293, pp.1818-1819, Sep. 2001 & Zipf¡¯s Law.

2. Calvert, K., M. Doar, and E. W. Zegura, ¡°Modeling Internet topology,¡± IEEE Communications Magazine, Vol. 35, pp. 160—163, 1997.

3. Medina, A., Matta, I., and Byers, J., ¡°On the Origin of Power Laws in Internet Topologies,¡± ACM SIGCOMM Computer Communication Review, Vol. 30, No. 2, Apr. 2000.

4. Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins and Janet Wiener, Graph Structure in the Web, Proceedings of The Ninth International World Wide Web Conference, Amsterdam, The Netherlands, May 2000.

5. Mark Crovella and Azer Bestavros, ¡°Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes,¡± SIGMETRICS, 1996.

6. V. Paxson and S. Floyd, ¡°Wide-area Traffic: The Failure of Poisson Modeling,¡± IEEE/ACM Transactions on Networking, pp.226-244, June 1995.

7. Ingmar Glauche, Wolfram Krause, Rudolf Sollacher, Martin Greiner, ¡°Continuum percolation of wireless ad hoc communication networks,¡± Elsevire Science, Physica A, Apr. 2003.

Paper set #4: Simulation and Queueing analysis

YOU SHOULD COVER TWO PAPERS IF YOU SELECT 1, 2 or 3.

1(a) Misra, J., ¡°Distributed discrete event simulation,¡± ACM Computing Survey, Vol. 18, No. 1, pp. 39-65, March 1986.

1(b) R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, B. Park, H. Song, ¡°Parsec: A Parallel Simulation Environment for Complex Systems,¡± IEEE Computer, Vol. 31, No. 10, pp. 77-85, October 1998. (http://pcl.cs.ucla.edu/projects/parsec/)

2(a) Lee Breslau, Deborah Estrin, Kevin Fall, Sally Floyd, John Heidemann, Ahmed Helmy, Polly Huang, Steven McCanne, Kannan Varadhan, Ya Xu, and Haobo Yu, ¡°Advances in Network Simulation,¡± IEEE Computer, Vol. 33, No. 5, pp. 59-67, May, 2000.

2(b) Debojyoti Dutta, Ashish Goel, and John Heidemann, ¡°Faster Network Design with Scenario Pre-filtering,¡± International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 237-246, 2002. (http://www.isi.edu/nsnam/)

3(a) Zeigler, B.P., ¡°DEVS representation of dynamical systems: event-based intelligent control,¡± Proceedings of the IEEE, Vol. 77, Issue 1, pp. 72-80, Jan. 1989.

3(b) B. P. Zeigler, H. S. Song, T. G. Kim, and H. Praehofer, ¡°DEVS framework for modelling, simulation, analysis, and design of hybrid systems,¡± Hybrid Systems II, LCNS No. 999, pp. 529-551, 1995.

4. M. Kim, ¡°Synchronized disk interleaving,¡± IEEE Trans. Computers, Vol. C-35, No. 11, 1986.

5. S. Jiang, D. He and J. Rao, ¡°A Prediction-based Link Availability Estimation for Mobile Ad Hoc Networks¡±

6. Nasipuri, A., and Das, S. R., ¡°On-Demand Multipath Routing for Mobile Ad Hoc Networks,¡± International Conference on Computer Communication and Network (ICCCN'99), Oct. 1999.

7. Marcel F. Neuts, Jun Guo, Moshe Zukerman, Hai Le Vu, The Waiting Time Distribution for a TDMA Model with a Finite Buffer, Infocom 2003.

Not covered

1. James R. Larus, "Efficient Program Tracing," IEEE Computer, Vol. 26, No. 5, May 1993, pp. 52-61.

2. Will E. Leland and Daniel V. Wilson, ¡°High Time-Resolution Measurement and Analysis of LAN Traffic: Implications for LAN Interconnection,¡± INFOCOM, pp. 1360-1366, 1991.

3. Larry W. McVoy and Carl Staelin, ¡°lmbench: Portable Tools for Performance Analysis,¡± USENIX Annual Technical Conference, pp. 279-294, 1996.

4. Robert D. Silverman, ¡°Exposing the Mythical MIPS Year,¡± IEEE Computer, Vol. 32, No. 8, pp. 22-26, August 1999.

5. Marwan Krunz and Herman Hughes, ¡°A Traffic Model for MPEG-Coded VBR Streams,¡± Measurement and Modeling of Computer Systems, pp. 47-55, 1995.

6. O. Rose, "Simple and efficient models for variable bit rate MPEG video traffic," Performance Evaluation, vol. 30, pp. 69-85Rose, July 1997.

7. Walter Willinger and Murad S. Taqqu and Robert Sherman and Daniel V. Wilson, ¡°Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level,¡± IEEE/ACM Transactions on Networking, Vol. 5, No. 1, pp. 71-86, 1997.

8. Albert-Laszlo-Barabasi, Reka Albert, Emergence of Scaling in Random Networks, Science, Vol. 286, pp. 509-512, 1999, and

9. Crovella, M. E. and Lipsky, L., ¡°Long-Lasting Transient Conditions in Simulations with Heavy-tailed Workloads,¡± Proceedings of the 1997 Winter Simulation Conference, 1997.

10. M. E. J. Newman, Who is the Best Connected Scientist? A Study of Scientific Coauthorship Networks, and

11. Deborah Estrin, Mark Handley, John Heidemann, Steven McCanne, Ya Xu, and Haobo Yu, ¡°Network Visualization with the Nam, VINT Network Animator,¡± IEEE Computer, Vol. 33, No. 11, pp. 63-68, November, 2000.

12(a) D.C. Burger and T. M. Austin, ¡°The SimpleScalar tool set, version 2.0,¡± Technical Report CS-TR-97-1342, University of Wisconsin, Madison, June 1997.

12(b) Todd Austin, Eric Larson, Dan Ernst, ¡°SimpleScalar: An Infrastructure for Computer System Modeling,¡± IEEE Computer, pp. 59-67, 2002. (http://www.simplescalar.com)

13. John Heidemann, Kevin Mills, and Sri Kumar, ¡°Expanding Confidence in Network Simulation,¡± IEEE Network Magazine, Vol. 15, No. 5, pp. 58-63, Sept./Oct., 2001.

14. Peter M. Chen, Edward K. Lee, ¡°Striping in a RAID Level 5 Disk Array,¡± 1995 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, May 15-19, 1995.

Paper presentation

You are supposed to have four 15-min presentations during the semester.

- Each of the presentations covers one paper from the paper sets in the below and at least one more paper that helps to understand to the chosen one.

- Prepare 1-page summary for distribution in class (in any format) and presentation material (preferably Power Point format). You should identify the covered papers at the end of the summary with the information on authors, title, journal name, publication year, etc.

- Grading is based on quality of your presentation and correct answers to questions as well as the number and quality of questions you ask to others.