[talks] S Beard General Exam

Melissa M. Lawson mml at CS.Princeton.EDU
Wed Oct 12 10:49:16 EDT 2011

Stephen Beard will present his research seminar/general exam 
on Wednesday October 19 at 10AM in Room 402.  The members of
his committee are;  David August (advisor), Andrew Appel, 
and Vivek Pai.  Everyone is invited to attend his talk and 
those faculty wishing to remain for the oral exam following 
are welcome to do so.  His abstract and reading list follow 
Client Driven Memory Profiling

Profiling provides vital insight to a program’s run-time
characteristics including data and control information. Control flow
profiling is popular because it improves compiler optimizations
without excessive profiling overhead (less than 2×). While memory
profiling can enable aggressive speculative optimizations to overcome
the perennial limits of static memory analysis, it is rarely used due
to its excessive profiling overhead (29× to 290×). To help address
this problem, this paper presents Client Driven Memory Profiling
(CDMP). Most speculative transformations are only concerned with some
subset of the dependences in the program. Given this information, CDMP
profiles only those dependences which are of use to the client
optimizations. As a result, CDMP incurs a running time overhead of 66×
averaged across the C/C++ SPEC CPU2006 benchmark suite, a 2.2×
improvement over the 143× overhead incurred by a state-of-the-art
memory profiler. After combining our client targeting optimization
with sampling techniques found in prior work, CDMP achieve a running
time overhead of 1.8×, a 4.1× improvement over the 7.3× overhead of
sampling alone, with no additional error over sampling.

Reading List
1.1 Textbooks
1. A. W. Appel. Modern Compiler Implementation in C. Cambridge
University Press, 1998
2. S. Muchnick. Advanced Compiler Design and Implementation.
Morgan-Kaufmann Publishers, San Francisco, CA, 1997

1.2 Performance and Path Profiling
3. S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A call
graph execution profiler. In Proceedings of the 1982 SIGPLAN symposium
on Compiler construction, SIGPLAN ’82, pages 120–126, New York, NY,
USA, 1982. ACM
4. T. Ball, P. Mataga, and M. Sagiv. Edge profiling versus path
profiling: The showdown. In Proceedings of the 25th ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages, pages 134–148,
January 1998

1.3 Dependence Profiling
5. T. Chen, J. Lin, X. Dai, W.-C. Hsu, and P.-C. Yew. Data dependence
profiling for speculative optimizations. In E. Duesterwald, editor,
Compiler Construction, volume 2985 of Lecture Notes in Computer
Science, pages 2733–2733. Springer Berlin / Heidelberg, 2004
6. A. K. Peng Wu and C. Cascaval. Compiler-driven dependence profiling
to guide program parallelization. In LCPC, pages 232–248, 2008
7. M. Kim, H. Kim, and C.-K. Luk. SD3 : A scalable approach to dynamic
data-dependence profiling. In Proceedings of the 2010 43rd Annual
IEEE/ACM International Symposium on Microarchitecture, MICRO ’10,
pages 535–546, Washington, DC, USA, 2010. IEEE Computer Society

1.4 Sampling
8. M. Arnold and B. G. Ryder. A framework for reducing the cost of
instrumented code. In Proceedings of the ACM SIGPLAN 2001 conference
on Programming language design and implementation, PLDI ’01, pages
168–179, New York, NY, USA, 2001. ACM

1.5 Analysis
9. M. Hind. Pointer analysis: Haven’t we solved this problem yet? In
2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software
Tools and Engineering (PASTE’01), 2001
10. B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for
millions of lines of code. Code Generation and Optimization, IEEE/ACM
International Symposium on, 0:289–298, 2011

1.6 Speculative Parallel Optimization
11. J. G. Steffan and T. C. Mowry. The potential for using
thread-level data speculation to facilitate automatic parallelization.
In Proceedings of the 4th International Symposium on High-Performance
Computer Architecture, pages 2–13, February 1998

More information about the talks mailing list