CS 266 Prof. Alan Jay Smith Computer Systems Performance Evaluation Spring Semester, 2010 Introduction bentley84 Jon Bentley, "The Back of the Envelope", CACM, 27, 3, March, 1984, pp. 180-183. >skim bentley86 Jon Bentley, ``The Envelope is Back'', CACM, 29, 3, March, 1986, pp. 176-182. >skim mage85 David T. Mage, ``The Procrustean Fit - A Useful Statistical Tool for Decision Making'', from Journal of Irreproducible Results, 1985. >skim Monitoring and Measurement mcdaniel77 Gene McDaniel, "METRIC: A Kernel Instrumentation System for Distributed Environments", Proc. 6'th SOSP, November, 1977, pp. 93-99. >skim melvin86 Stephen Melvin and Yale Patt, ``A Microcode Based Environment for Non-Invasive Performance Analysis'', Proc. 19'th Ann. Workshop on Microprogramming, MICRO 19, October, 1986, New York, NY, ACM Sigmicro Newsletter, 17, 4, December, 1986, pp. 171-177. >skim bentley87 Jon Bentley, ``Profilers'', CACM, 30, 7, July, 1987, pp. 587-592. >skim power83 L. R. Power, "Design and Use of a Program Execution Analyzer", IBM Systems Journal, 22, 3, 1983, pp. 271-294. >skim currah75 Brian Currah, "Some Causes of Variability in CPU Time", from Computer Measurement and Evaluation, Selected Papers from the Share Project, ed. Wixon, volume III, December 1973- March, 1975, pp. 389-392. >skim merrill83 H. W. Merrill, "Repeatability and Variability of CPU Timing in Large IBM Systems", CMG Transactions, 39, March, 1983, pp. 4-2 - 4-25. >skim friedman98 Mark Friedman, "Optimizing the Performance of Wintel Applications", Proc. CMG '98, December, 1998, volume, pp. 245-259. >skim zhou00 Min Zhou and Alan Jay Smith, "Windows System Tracing and Workload Characterization", October, 1998. (This paper has been published in two parts as: "Tracing Windows95", Journal of Microprocessors and Microsystems, 24, 7, November 1, 2000, pp. 333-347, and "Analysis of Personal Computer Workloads", Proc. Seventh Intl. Symposium on Modeling, Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS)", October 24-28, 1999, University of Maryland, pp. 208-217. >skim lorch00 Jacob Lorch and Alan Jay Smith, "The VTrace Tool: Building a System Tracer for Windows NT and Windows 2000", MSDN Magazine, October, 2000, pp. 86-102. >skim Memory Management and Paging denning80 Peter Denning, ``Working Sets Past and Present'', IEEETSE, SE-6, 1, January, 1980, pp. 64-84. >read chu76 Wesley Chu and Holger Opderbeck, "Program Behavior and the Page Fault Frequency Replacement Algorithm", IEEE Computer, November, 1976, pp. 29-38. >skim, especially look at pictures smith76 Alan Jay Smith, "A Modified Working Set Paging Algorithm", IEEETC, C-25, 9, September, 1976, pp. 907-914. >skim, especially look at pictures ferrari76 Domenico Ferrari, "The Improvement of Program Behavior", IEEE Computer, November, 1976, pp. 39-47. >read matt70 R.L. Mattson, J. Gecsei, D.R. Slutz, and I.L. Traiger, ``Evaluation Techniques for Storage Hierarchies'', IBM Sys. J., 2, 1970, pp. 78-117. >background for what I said in class (don't need to read) smith77 Alan Jay Smith, "Two Methods for the Efficient Analysis of Memory Address Trace Data", IEEETSE, SE-3, 1, January, 1977, pp. 94-101. >skim, especially look at pictures smith76b Alan Jay Smith, "Analysis of the Optimal Look-ahead Demand Paging Algorithms", SIAM J. Computing, 5, 4, December, 1976, pp. 743-757. >background for what I covered in class - don't need to read coff73.io.paging.pdf Edward Coffman and Peter Denning, "Operating Systems Theory", Prentice- Hall, 1973, chapters 5-7. >skim Simulation sher72 Stephen Sherman, Forest Baskett III and J. C. Browne, "Trace-Driven Modeling and Analysis of CPU Scheduling in a Multiprogramming System", CACM, December, 1972, 15, 12, pp. 1063-1069. >read laven75 S. S. Lavenberg and D. R. Slutz, "Introduction to Regenerative Simulation", IBM J. Res. Develop., September, 1975, pp. 458-462. >read kac Mark Kac, ``Marginalia: More on randomness'', American Scientist, 72, pp. 282-283. >read reed88 Daniel Reed, Allen Malony, and Bradley McCredie, "Parallel Discrete Event Simulation Using Shared Memory", IEEETSE, 14, 4, April, 1988, pp. 541-553. >skim mcgeoch92 Catherine McGeoch, "Analyzing Algorithms by Simulation: Variance Reduction Techniques and Simulation Speedups", ACM Computing Surveys, 24, 2, June, 1992, pp. 195-212. >skim +===================================================== MIDTERM ====================================================== Benchmarking, Workloads, Tracing Walter Price, "A Benchmark Tutorial", IEEE MICRO, October, 1989, pp. 28-43. >Read David Hinnant, ``Accurate Unix Benchmarking: Art, Science or Black Magic?'', IEEE MICRO, October, 1988, pp. 64-75. >read Reinhold Weicker, ``Dhrystone: A Synthetic Systems Programming Benchmark'', CACM, 27, 10, October, 1984, pp. 1013-1030. >read Henry M. Levy and Douglas W. Clark, "On the Use of Benchmarks for Measuring System Performance", Computer Architecture News, 10, 6, December, 1982, pp. 5-8. >skim Jeff Reilly, "A Brief Introduction to the SPEC CPU95 Benchmarks", IEEE TCCA Newsletter, June, 1996, pp. 1-8. skim (carefully) John L. Henning, "SPEC CPU2000: Measuring CPU Performance in the New Millenium", IEEE Computer, July, 2000, pp. 28-35. skim (carefully) Systems Performance Evaluation Cooperative, SPEC Newsletter, selected materials, 1990-1997. See Dron90, Dixit91, Dixit91a, Keatts91, Balan92, Balan92a, Weicker92, Keith93, Gray93, Weicker97 skim (carefully) John Mashey, ``SPEC Data Helps Normalize Vendor Mips-Ratings for Sensible Comparison'' read Ronald Nichols, ``So, You Wanna Run a Benchmark'', Proc. CMG '88, Dallas, Texas, December 12-16, 1988, pp. 810-814. skim Rafael H. Saavedra-Barrera, Alan Jay Smith and Eugene Miya, Machine Characterization Based on an Abstract High-Level Language Machine'', IEEETC, 38, 12, December, 1989, pp. 1659-1679. Rafael Saavedra-Barrera and Alan Jay Smith, ``Performance Characterization of Optimizing Compilers'', IEEETSE, July, 1995, vol. 21, no. 7, pp. 615-628. Rafael Saavedra-Barrera and Alan Jay Smith, ``Measuring Cache and TLB Performance and Their Effect on Benchmark Run Times'' IEEE TC, October, 1995, 44, 10, pp. 1223-1235. Rafael Saavedra-Barrera and Alan Jay Smith, ``Analysis of Benchmark Characteristics and Benchmark Performance Prediction'', December, 1992. ACM TOCS, 14, 4, November, 1996, pp. 344-384. skim (understand at level of lecture) Jack Worlton, ``Understanding Supercomputer Benchmarks'', Datamation, September 1, 1984, pp. 121-130. read I/O smith81c Alan Jay Smith, "Input/Output Optimization and Disk Architectures: A Survey", Performance Evaluation, 1, 1981, pp. 104-117. read smith85 Alan Jay Smith, ``Disk Cache - Miss Ratio Analysis and Design Considerations'', ACM TOCS 3, 3, August, 1985, pp. 161-203. backup for class presentation smith81 Alan Jay Smith, "Analysis of Long Term File Reference Patterns for Application to File Migration Algorithms", IEEETSE, SE-7, 4, July, 1981, pp. 403-417 backup for class presentation smith81b Alan Jay Smith, "Long Term File Migration: Development and Evaluation of Algorithms", CACM, 24, 8, August, 1981, pp. 521-532. backup for class presentation coff73.io.paging.pdf Edward Coffman and Peter Denning, "Operating Systems Theory", Chapter 5, "Auxiliary and Buffer Storage Models", Prentice-Hall, 1973. skim Queueing Theory and Related: larson88.pdf Richard Larson, "There's More to a Line Than Its Wait", Technology Review, July, 1988, pp. 60-67. skim coffman73.sked.pdf Edward Coffman and Peter Denning, "Operating Systems Theory", Chapter 4, "Probability Models of Computer Sequencing Problems", Prentice-Hall, 1973. skim allen80.pdf Arnold O. Allen, "Queueing Models of Computer Systems", IEEE Computer, April, 1980, pp. 13-24. read baskett75.pdf Forest Baskett, K. Mani Chandy, Richard R. Muntz and Fernando Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers", JACM, 22, 2, April, 1975, pp. 248-260. get formulas - use for homework marshall68.pdf K. T. Marshall, "Some Inequalities in Queueing", Operations Research, 16, 3, 1968, pp. 651-665. (and "Comments on `Some Inequalities in Queueing', Richard Evans) skim - backup for class discussion. Know how to find formulas jewell63.pdf William S. Jewell, "Markov Renewal Programming. I: Formulation, Finite Return Models, II: Infinite Return Models, Examples", Operations Research, 1963, pp. 938-970. skim (if we get to it - which we don't seem to have done) smith78.pdf Alan Jay Smith, "Sequentiality and Prefetching in Database Systems", ACM TODS, 3, 3, September, 1978, pp. 223-247. backup for class discussion, if we get to it. Computer Architecture Performance peut77 Bernard L. Peuto and Leonard J. Shustek, "An Instruction Timing Model of CPU Performance", Proc. 4'th Ann. Symp. on Computer Arch., March, 1977, pp. 165-178. >read macd84 Myron H. MacDougall, "Instruction Level Program and Processor Modeling", IEEE Computer, July, 1984, pp. 14-24. >read sang84 John Sanguinetti, ``Program Optimization for a Pipelined Machine: A Case Study'', Proc. 1984 ACM Sigmetrics Conf. on Measurement and Modeling of Computer Systems, August, 1984, Cambridge, Mass., pp. 88-95. >skim Slin00 Nathan Slingerland and Alan Jay Smith, "Design and Characterization of the Berkeley Multimedia Workload", with Nathan Slingerland, Computer Science Technical Report CSD-00-1122, ACM Multimedia Systems Journal, 8, 4, 2002, pp. 315-327. >skim (backup for class lecture) Slin00b Nathan Slingerland and Alan Jay Smith, "Measuring the Performance of Multimedia Instruction Sets" Computer Science Technical Report CSD-00-1125, IEEETC, 51, 11, November, 2002, pp. 1317-1332. >skim (backup for class lecture) Smit82 Alan Jay Smith, "Cache Memories", Computing Surveys, 14, 3, September, 1982, pp. 473-530. >skim (backup for class lecture) Tse98 John Tse and Alan Jay Smith, ``CPU Cache Prefetching: Timing Evaluation of Hardware Implementations'', IEEETC, 47, 5, May, 1998, pp. 509-526. >skim Aust02 Todd Austin, Eric Larson, Dan Ernst, "SimpleScalar: An Infrastructure for Computer System Modeling", IEEE Computer, February, 2002, pp. 59-67. >for your info. Emer02 Joel Emer, Ahuja, Borch, Klauser, Luk, Manne, Mukherjee, Patil, Wallace, Binkert, Epasa, Juan, "Asim: A Performance Model Framework", IEEE Computer, February, 2002, pp. 68-76. >for your info. Magn02 Peter Magnusson, Christensson, Eskilson, Forsgren, Hallberg, Hogberg, Larsson, Moestedt, Werner, "Simics: A Full System Simulation Platform", IEEE Computer, February, 2002, pp. 50-58. >for your info. Gibs00 Jeff Gibson, Robert Kunz, David Ofelt, Mark Horowitz, John Hennessy, and Mark Heinrich, "FLASH vs. (Simulated) FLASH: Closing the Simulation Loop", Proc. ASPLOS-IX Proceedings, Cambridge, MA, November, 2000, pp. 49-58. >skim