CSC 573 Advanced Seminar on Modeling and Improving LargeScale Program Behavior
Time and place: Tuesdays 13pm, CSB 703. 
Instructor: Chen Ding, Prof., CSB 710, cding@cs.rochester.edu, office hours Fridays 11am12pm 
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 online 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, SE6 (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 redblue 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^{2})
 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
 Wholeprogram 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.
 CLockPro: an effective improvement of the CLOCK replacement by S. Jiang, F. Chen, and X. Zhang, to appear in USENIX 2005. A LIRSbased method is used to improve the Linux VM management.
 Feb. 22/29 Phase analysis: from space to time
 Locality and code profiling and runtime prediction
 Runtime predictor classification
 Behavior clustering
 Programbased methods
 EXPERT: Expedited Simulation Exploiting Program Behavior Repetition, by W. Liu and M. Huang, ICS 2004
 Profilebased 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 limitsPoisson 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 temporalspatial 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
objectpriented 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 callpath profiling, A. R. Bernat, B. P. Miller, technical report, University of WisconsinMadison, 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. MellorCrummey, D. Whalley, and K. Kennedy,
in IJPP, 29(3), 2001
 Compiletime
Composition of Runtime 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 Runtime 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
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, largenumber 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 halfhour 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.
 Memoryhierarchy 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, LBL12370, 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 directmap and set associative cache.
 Efficient stack algorithms for analysis of writeback and sector memories, by J. G. Thompson and A. J. Smith, ACM TCS, 1989. Writeback 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 (bottomup) 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?, JL Bear, keynote talk at HPCA 2000.
cding@cs.rochester.edu
Last modified: Mon Apr 11 16:49:18 EDT 2005