CSC 573 Advanced Seminar on Modeling and Improving Large-Scale Program Behavior

Large, complex software exhibit emergent behavior at the program level that can often be modeled, predicted, and improved (so we think). In this seminar we will review classic studies, examine the current research, and discuss open questions.

• Lectures and assigned reading
• Syllabus
• Additional reading

Lectures and assigned reading

• Jan. 18   Locality: programmed or universal?
• Bell's theorem without inequalities, D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, American Journal of Physics, 58 (12), December 1990.
• Jan. 25   Locality models before 1980s: how stack distance and working sets enabled virtual memory
• Evaluation techniques for storage hierarchies, by R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger, IBM System Journal, 9(2), 1970. Here is an on-line copy (be warned that the name of the first author is missing on the title page).
• (presented by Virendra Marathe) Working Sets Past and Present, by P.J. Denning, IEEE Transactions on Software Engineering, SE-6 (1), January, 1980
• Feb. 1   Above and below: effects of system and algorithm design on locality
  • On the effectiveness of set associative page mapping and its application to main memory management, by A. J. Smith, Proceedings of the 2nd International Conference on Software Engineering, San Francisco, CA, October, 1976
  • I/O complexity: The red-blue pebble game, by J. Hong and H. T. Kung, Proceedings of the ACM Conference on Theory of Computing, Milwaukee, WI, 1981
• Feb. 8   Program locality models: dependence, stream, distance, and stride (DS²)
  • Lecture notes ( adapted from a tutorial given at ASPLOS 2004 with Steve Carr, Trishul Chilimbi, and Youfeng Wu.)
  • Distance models
  • Distance-based locality analysis and prediction, by C. Ding, Y. Zhong, and X. Shen, unpublished manuscript (preliminary conference publications are here)
  • Dependence models
  • Improving Data Locality with Loop Transformations, by K. S. McKinley and S. Carr and C.-W. Tseng, TOPLAS 18(4), 1996
  • On the Problem of Optimizing Data Transfers for Complex Memory Systems, by K. Gallivan, W. Jalby, and D. Gannon, ICS 1988
  • A Data Locality Optimizing Algorithm, by M. E. Wolf and M. Lam, PLDI 1991
  • Stream models
  • Efficient Representations and abstractions for quantifying and exploiting data reference locality, by T.M.Chilimbi, PLDI 2001
  • Dynamic Hot Data Stream Prefetching for General-Purpose Programs, by T. M. Chilimbi and M. Hirzel, PLDI 2002
  • Stride models
  • Efficient Discovery of Regular Stride Patterns in Irregular Programs, by Y. Wu, PLDI 2002
• Feb. 15/22   Reference affinity and LIRS: finding working sets by a compiler and by an OS
• Whole-program reference affinity and its uses in array regrouping and structure splitting, by Y. Zhong, M. Orlovich, X. Shen, and C. Ding, PLDI 2004.
• A method for hierarchical data placement, by C. Zhang, Y. Zhong, C. Ding, and M. Ogihara, URCS Technical Report TR845. The paper proves theoretical properties of reference affinity.
• the next two were presented by Virendra Marathe
• LIRS: breaking the limit of LRU, based on the LIRS paper by S. Jiang and X. Zhang published in SIGMetrics 2002.
• CLock-Pro: an effective improvement of the CLOCK replacement by S. Jiang, F. Chen, and X. Zhang, to appear in USENIX 2005. A LIRS-based method is used to improve the Linux VM management.
• Feb. 22/29  Phase analysis: from space to time
• Locality and code profiling and run-time prediction
• Locality phase prediction, by X. Shen, Y. Zhong, and C. Ding, ASPLOS 2004
• Run-time predictor classification
• Characterizing and predicting program behavior and its variability, by E. Duesterwald, C. Cascaval, and S. Dwarkadas, PACT 2003
• Behavior clustering
• Workload design: selecting representative program-input pairs, by L. Eeckhout, H. Vandierendonck, and K. De Bosschere, PACT 2002
• Automatically characterizing large scale program behavior, by T. Sherwood, E. Perelman, G. Hamerly and B. Calder, ASPLOS 2002
• Program-based methods
• EXPERT: Expedited Simulation Exploiting Program Behavior Repetition, by W. Liu and M. Huang, ICS 2004
• Profile-based Dynamic Voltage and Frequency Scaling for a Multiple Clock Domain Microprocessor, by G. Magklis, M. L. Scott, G. Semeraro, D. H. Albonesi, and S. Dropsho, ISCA 2003
• The design, implementation and evaluation of a compiler algorithm for CPU energy reduction, by C.-H. Hsu and U. Kremer, PLDI 2003
• Feb. 29/Mar. 15  Basic theories in frequency analysis
• random variable, mean, variance, binomial distribution and its limits---Poisson and normal distributions, Poisson process, central limit theorem, the law of large numbers, Chebyshev's proof
• based on Chapters 6 and 7, "Elementary probability theory" by K. L. Chung and F. AitSahlia, 4th Ed., Springer
• Mar. 15/Mar. 22  Basic theories in temporal-spatial analysis
• linear differential equations, Fourier series, (fast) Fourier transform, Shannon's sampling theorem
• (presented by Wenzhao Tan) windowed Fourier analysis, filter banks, wavelets, wavelet transform, Daubechies, the uncertainty principle
• The following is organized by topics
• Behavior correlation (a.k.a debugging) (the first two papers were selected and presented by Chris Stewart)
• Configuration Debugging as Search: Finding the Needle in the Haystack, by A. Whitaker, R. S. Cox, and S. D. Gribble in OSDI 2004
• Automatic misconfiguration troubleshooting with PeerPressure, by H. J. Wang, J. C. Platt, Y. Chen, R. Zhang, and Y. Wang, in OSDI 2004
• Bug isolation via remote program sampling, by B. Liblit, A. Aiken, A. X. Zheng, M. I. Jordan, in PLDI 2003
• Vertical profiling: understanding the behavior of object-priented applications, by M. Hauswirth, P. F. Sweeney, A. Diwan, M. Hind, in OOPSLA 2004
• Program profiling (selected and presented by Pin Lu)
• Gprof: a call graph execution profiler, by S. L. Graham, P. B. Kessler, and M. K. McKusick, ACM Symposium on Compiler Construction, 1982
• Incremental call-path profiling, A. R. Bernat, B. P. Miller, technical report, University of Wisconsin-Madison, 2004
• Dynamic program sampling and optimization
• (presented by Virendra Marathe) Dynamo: a transparent dynamic optimization system, by V. Bala, E. Duesterwald, and S. Banerjia, in PLDI 2000 (best paper award)
• A framework for reducing the cost of instrumented code, by M. Arnold and B. Ryder, in PLDI 2001
• Dynamic data placement for improving spatial locality (presented by Kirk Kelsey)
• Finding your cronies: static analysis for dynamic object colocation, by S. Z. Guyer, K. S. McKinley, in OOPSLA 2004
• Adaptive caching for demand prepaging, by S. F. Kaplan, L. A. McGeoch, and M. F. Cole, in ISMM 2002
• Dynamic tracking of page miss ratio curve for memory management, by P. Zhou, V. Pandey, J. Sundaresan, A. Raghuraman, Y. Zhou, S. Kumar, in ASPLOS 2004
• Dynamic data and computation reordering for improving locality
• Improving Cache Performance in Dynamic Applications through Data and Computation Reorganization at Run Time, by C. Ding and K. Kennedy, in PLDI 1999 (presented by Kirk Kelsey)
• Improving Locality For Adaptive Irregular Scientific Codes, by H. Han and C. W. Tseng, in LCPC 2000
• Improving Memory Hierarchy Performance for Irregular Applications(ICS'99 version), by J. Mellor-Crummey, D. Whalley, and K. Kennedy, in IJPP, 29(3), 2001
• Compile-time Composition of Run-time Data and Iteration Reorderings, by M. M. Strout, L. Carter, and J. Ferrante, in PLDI 2003
• Restructuring Computations for Temporal Data Cache Locality, by V. S. Pingali, S. A. McKee, W. C. Hsieh, and J. B. Carter, in IJPP, 31(4), 2003
• Metrics and models for reordering transformations, by M. M. Strout and P. Hovland, in MSP 2004
• The potential of computation regrouping for improving locality, by C. Ding and M. Orlovich, in SC 2004
• Techniques for Reducing the Overhead of Run-time Parallelization, by H. Yu and L. Rauchwerger, in CC 2000

The syllabus

1. Locality: programmed or universal? (1 week, Einstein 1935, Bell
   inequality 1964, GHZ proof 1990)

2. Memory system models (2 weeks, stack distance, Mattson et al. 1970,
   A.J. Smith 1976; working set, Denning 1980; I/O complexity, Kung
   1980)

3. Program locality models (3 weeks, distance, frequency, stream, and
   dependence models; reuse signature pattern, reference affinity,
   program phases)

4. General system models (2 weeks, entropy, large-number theory,
   Markov process, queuing models)

5. Dynamic program/system optimization (4 weeks, code/data/object
   layout, data/code/path sampling, dynamic compilation, memory
   management)

6. Related topics (2 weeks, dynamic parallelization, correctness
   checking, fault tolerance)

Students need to attend classes, read assigned papers, select two
topics, present them in half-hour slots and lead their discussions.
The remaining term project is a survey paper on the two selected
topics and their relations or a paper on some other subject of mutual
interest between the student and the instructor.

This seminar is not expected to recur in the next few years.  I highly
recommend the (timeless) material in the first half of the seminar.
Feel free to sit in.

The seminar does *not* count as credits for the breadth requirement in
systems.

Additional reading

• Memory-hierarchy simulation
• LRU stack processing, B. T. Bennett and V. J. Kruskal, IBM JRD, 1975. Modeled the trace as a tree.
• Efficient methods for calculating the success function of fixed space replacement policies, by F. Olken, LBL-12370, Lawrence Berkeley Laboratory, 1981. Used a search tree to replace Mattson et al.'s stack.
• Aspects of cache memory and instruction buffer performance, by M. D. Hill, Ph.D dissertation, U. Wisconsin, 1987. Efficient simulation of direct-map and set associative cache.
• Efficient stack algorithms for analysis of write-back and sector memories, by J. G. Thompson and A. J. Smith, ACM TCS, 1989. Write-back cache simulation
• Efficient simulation of caches under optimal replacement with applications to miss characterization, by R. A. Sugumar and S. G. Abraham, SIGMetrics 1993. Improved over Olken's scheme using a (bottom-up) splay tree.
• Calculating Stack Distances Efficiently, by G. Almasi and C. Cascaval and D. Padua, MSP 2002. Improved over Olken's scheme using an efficient representation of the search tree.
• Estimating cache misses and locality using stack distances, by C. Cascaval and D. A. Padua, ICS 2003. Used dependence techniques to estimate the reuse distance
• Courses in other schools on advanced program analysis
• a seminar taught by J. N. Amaral and others at University of Alberta
• Advanced compiler seminar by L. Rauchwerger at TAMU in 2002
• Performance programming page by L. Carter at UCSD
• 2K papeers on caches by Y2K: do we need more?, J-L Bear, keynote talk at HPCA 2000.