CSC 573 Advanced Seminar on Modeling and Improving Large-Scale Program Behavior
| Time and place: Tuesdays 1-3pm, CSB 703.
| Instructor: Chen Ding, Prof., CSB 710, firstname.lastname@example.org, office hours Fridays 11am-12pm
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.
- Jan. 18 Locality: programmed or universal?
- 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 (DS2)
- Lecture notes ( adapted from a tutorial given at ASPLOS 2004 with Steve Carr, Trishul Chilimbi, and Youfeng Wu.)
- Distance models
- Dependence models
- Stream models
- 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
- Run-time predictor classification
- Behavior clustering
- 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
- 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)
Locality For Adaptive Irregular Scientific Codes, by H. Han
and C. W. Tseng, in LCPC 2000
- Improving Memory Hierarchy Performance for Irregular
version), by J. Mellor-Crummey, D. Whalley, and K. Kennedy,
in IJPP, 29(3), 2001
Composition of Run-time Data and Iteration Reorderings, by
M. M. Strout, L. Carter, and J. Ferrante, in PLDI 2003
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
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
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
3. Program locality models (3 weeks, distance, frequency, stream, and
dependence models; reuse signature pattern, reference affinity,
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
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
- 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
- 2K papeers on caches by Y2K: do we need more?, J-L Bear, keynote talk at HPCA 2000.
Last modified: Mon Apr 11 16:49:18 EDT 2005