[talks] N Johnson general exam

[Melissa Lawson]

Nick Johnson will present his research seminar/general exam on Monday May 10 at 10AM in
Room 402.
The members of his committee are:  David August (advisor), Andrew Appel, and Brian
Kernighan.  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 below.
--------------------------------------------
Effective Composition of Optimizing
Transformations via Obstacle Identification

Abstract
Optimizing transformations interact in complicated, non-linear and often unknown ways.
This prevents most compilers from applying transformations in an optimal manner. Multicore
exacerbates this problem; the performance difference between the best and average
transform sequences is orders of magnitude. Common practice uses applicability and
profitability guards to decide whether each transformation should be applied greedily or
not at all, but may miss intermediate strategies with better performance. I present the
obstacle identification technique, which uses the dual of those guards to identify
limiting qualities of the program structures. By repeatedly relaxing program structure and
retesting the guards, we enumerate those relaxations which improve applicability or
profitability (obstacles). We demonstrate the promise of the obstacle identification
technique by applying it to the problem of interacting transformations. This technique
offers a competitive solution.

References
[1] F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M. F. P. O'Boyle, J. Thomson,
M. Toussaint, and C. K. I. Williams. Using machine learning to focus iterative
optimization. In CGO '06: Proceedings of the International Symposium on Code Generation
and Optimization, pages 295-305, Washington, DC, USA, 2006. IEEE Computer Society.

[2] L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves,
Devika Subramanian, Linda Torczon, and Todd Waterman. Finding effective compilation
sequences. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on
Languages, compilers, and tools for embedded systems, pages 231-239, New York, NY, USA,
2004. ACM Press.

[3] Andrew W. Appel. Modern Compiler Implementation in C. Cambridge University Press,
1998.

[4] Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven Reeves, Devika
Subramanian, Linda Torczon, and Todd Waterman. ACME: Adaptive compilation made efficient.
In LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages,
compilers, and tools for embedded systems, pages 69{77, New York, NY, USA, 2005. ACM.

[5] J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its
use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349,
July 1987.

[6] Jialu Huang, Arun Raman, Yun Zhang, Thomas B. Jablin, Tzu-Han Hung, and David I.
August. Decoupled Software Pipelining Creates Parallelization Opportunities. In
Proceedings of the 2010 International Symposium on Code Generation and Optimization, April
2010.

[7] S. Muchnick. Advanced Compiler Design and Implementation. Morgan- Kaufmann Publishers,
San Francisco, CA, 1997.

[8] Easwaran Raman, Guilherme Ottoni, Arun Raman, Matthew J. Bridges, and David I. August.
Parallel-stage decoupled software pipelining. In CGO '08: Proceedings of the sixth annual
IEEE/ACM international symposium on Code generation and optimization, pages 114-123, New
York, NY, USA, 2008. ACM.

[9] Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality saturation: A
new approach to optimization. In POPL '10: Proceedings of the 37th ACM SIGPLAN-SIGACT
symposium on Principles of programming languages, January 2010.

[10] Spyridon Triantafyllis, Manish Vachharajani, and David I. August. Compiler
optimization-space exploration. Journal of Instruction-Level Parallelism, 7, 2005.

[11] M. Wolf, D. Maydan, and D. Chen. Combining loop transformations considering caches
and scheduling. In Proceedings of the 29th Annual International Symposium on
Microarchitecture, pages 274-286, December 1996.