15-745 Spring 2007 Papers for in-class discussions

The readings will be organized as follows:

You will form pairs and pick a half-lecture slot in one of the lectures between Feb 22 and March 8. A sign-up sheet is on Seth's door; it will also be circulated in class during the lecture on Tuesday Feb 20.
Each pair will pick one of the research areas below, and will discuss two of the papers from that research area. Some areas have more than two papers, and you can pick any two you like. However, it is advisable to pick the first paper as one of your two, since it is usually the most important (please let us know which ones you pick, so we can let the rest of the class know in advance). Each pair will have 40 minutes total, of which the first 25-30 minutes will be devoted to them presenting the papers, and the last 10-15 mins will be for discussion.
Seth will make the first such presentation, on Tuesday Feb 20, on "Exotic Architectures", so you know what structure to follow in your own presentations.
Before each class from Feb 22 onwards, all students will be responsible for turning in a small summary of one paper each from the two groups being presented that day (so, you will be required to summarize a total of two papers in each class). Your summary should include 3 bullet points about the paper's main contributions and approach, 3 bullet points about what you think the paper's strengths are, and 3 bullet points about where you think the weaknesses lie. Email a pdf to Mahim before class.

Our hope is that reading a collection of new and classic research papers will give you some ideas for your class projects, so keep your thinking caps on during the readings, presentations and discussions :)

Papers: vouched for so far

The papers in a light font were part of the group but will not be discussed in class and should not be summarized.

Exotic architectures [Seth, Tuesday Feb 20]
- Doug Burger et.al., "Scaling to the End of Silicon with EDGE Architectures", IEEE Computer July 2004. (local copy).
- Steve Swanson, Ken Michelson, Andrew Schwerin and Mark Oskin. WaveScalar In the 36th Annual International Symposium on Microarchitecture (MICRO-36), December 2003
- Jan Hoogerbrugge and Henk Corporaal and Hans Mulder, ``Software pipelining for transport-triggered architectures'', MICRO 24 (1991).
GPUs and memory hierarchy [Jim McCann and Ronit Slyper, Thursday Feb 22]
- Optimizing Compiler for the Cell Processor PACT 2005. (A. Eichenberger, K. O'Brien, K. O'Brien, P. Wu, T. Chen, P. Oden, D. Prener, J. Shepherd, B. So, Z. Sura, A. Wang, T. Zhang, P. Zhao, and M. Gschwind.) (available here)
- nVidia Corporation. nVidia CUDA programming guide, version 0.8, Feb 12, 2007. (Read sections 2 and 3, skim sections 4.2 and 6, and look at the other sections if you have time.)
Advanced Languages [Hormoz Zarnani and Eric Malloy, Tuesday Feb 27]
- Necula and Lee. The design and implementation of a certifying compiler. PLDI'98.
- Engler, Chelf, Chou and Hellen. Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions. OSDI'00.
SIMD / Vector [David Borel and Peter Nelson, Tuesday Feb 27]
- Vectorization for SIMD architectures with alignment constraints PLDI 2004. (A. Eichenberger, P. Wu, K. O'Brien)
- Efficient SIMD Code Generation for Runtime Alignment and Length Conversion CGO 2005. (P. Wu, A. Eichenbreger, A. Wang)
- Integrated Simdization Framework with Virtual Vectors ICS 2005. (P. Wu, A. Eichenberger, A. Wang, P. Zhao)
- All are at http://domino.research.ibm.com/comm/research_projects.nsf/pages/cellcompiler.refs.html
IA-64 / VLIW from a Compiler Optimization Perspective [Frederic De Mesmay and Theodoros Strigkos, Thursday March 1]
- Rumi Zahir, Jonathan Ross, Dale Morris and Drew Hess. ``OS and Compiler Considerations in the Design of the IA-64 Architecture,'' in Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 212-221, November 2000. p212-zahir.pdf
- Scott A. Mahlke and Richard E. Hank and James E. McCormick and David I. August and Wen-Mei W. Hwu, A comparison of full and partial predicated execution support for ILP processors, ISCA 1995.
- Sebastian Winkel, Exploring the Performance Potential of Itanium Processors with ILP-based Scheduling, in CGO 2004 March 2004.
Register Allocation [Ajay Mathew and Sumit Kumar Jha, Thursday March 1]
- Pereira and Palsberg. Register allocation via coloring of chordal graphs. APLAS'05
- Pereira and Palsberg. Register allocation after classical SSA elimination is NP-complete. FOSSACS'06
Adaptive Compilation [Yi-Fan Tsai, Tuesday March 6]
- John Cavazos, Grigori Fursin, Felix Agakov, Edwin Bonilla, Michael F.P. O’Boyle, and Olivier Temam. Rapidly Selecting Good Compiler Optimizations using Performance Counters, In CGO 2007.
- Prasad A. Kulkarni, David B. Whalley, Gary S. Tyson, Jack W. Davidson. Evaluating Heuristic Optimization Phase Order Search Algorithms, In CGO 2007.
- Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S., Subramanian, D., Torczon, L., and Waterman, T. ACME: adaptive compilation made efficient. In Proceedings of the 2005 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools For Embedded Systems (Chicago, Illinois, USA, June 15 - 17, 2005). LCTES '05. ACM Press, New York, NY, 69-77.
Reuse Signature Analysis and Optimization [Tom Cauchois, Tuesday March 6]
- Ding, C. and Zhong, Y. Predicting whole-program locality through reuse distance analysis. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (San Diego, California, USA, June 09 - 11, 2003). PLDI '03. ACM Press, New York, NY, 245-257.
- Fang, C., Carr, S., Önder, S., and Wang, Z. Reuse-distance-based miss-rate prediction on a per instruction basis. In Proceedings of the 2004 Workshop on Memory System Performance (Washington, D.C., June 08 - 08, 2004).
- X. Shen, Y. Zhong, and C. Ding. Regression-Based Multi-Model Prediction of Data Reuse Signature, In Proceedings of the 4th Annual Symposium of the Las Alamos Computer Science Institute, November 2003.
- Y Zhong, S.G. Dropsho, and C. Ding. Miss rate prediction across all program inputs In PACT 2003. Page(s):79 - 90.
Pointer Analysis 2 [Cody Hartwig and Elie Krevat, Thursday March 8]
- Ghiya, Lavery, and Sehr, "On the importance of points-to analysis and other memory disambiguation methods for C programs" PLDI 2001
- Nevin Heintze and Olivier Tardieu, "Ultra-fast aliasing analysis using CLA: a million lines of C code in a second" PLDI 2001
Proving Compilers Correct [Dan Licata and Jake Donham, Thursday March 8]
- Leroy, X. Formal certification of a compiler back-end or: programming a compiler with a proof assistant. In Proceedings of the 33rd Annual Symposium on Principles of Programming Languages (POPL) 2006, 42-54.
- Lerner S., Millstein T., Rice E. and Chambers C. Automated Soundness Proofs for Dataflow Analyses and Transformations via Local Rules. In Proceedings of the 33rd Annual Symposium on Principles of Programming Languages (POPL) 2005, 364-377.

Papers: still available

Pointer Analysis 1
- Rakesh Ghiya and Laurie J. Hendren. ``Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C,'' in Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Florida, pages 1-15, January 1996. p1-ghiya.pdf
- Lattner and Adve. Automatic pool allocation: improving performance by controlling data structure layout in the heap. PLDI'05.
Eliminating Memory References
- Rastislav Bodik, Rajiv Gupta and Mary Lou Soffa. ``Load-Reuse Analysis: Design and Evaluation,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 64-76. May 1999. p64-bodik.pdf
- Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu and Peng Tu. ``Register Promotion by Sparse Partial Redundancy Elimination of Loads and Stores,'', in Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 26-37, June 1998. p26-lo.pdf
- T. Chilimbi, "Efficient representations and abstractions for quantifying and exploiting data reference locality" PLDI 2001
Profiling 1
- Robert Cohn and P. Geoffrey Lowney. ``Hot Cold Optimization of Large Windows/NT Applications,'' in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, pages 80-89, December 1996. p80-cohn.pdf
- Aggressive Inlining. Andrew Ayers, Richard Schooler, Robert Gottlieb. PLDI '97
Profiling 2
- James R. Larus. ``Whole Program Paths,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 259-269, May 1999. p259-larus.pdf
- Glenn Ammons and James R. Larus. ``Improving Data-Flow Analysis with Path Profiles,'' in Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation,pages 72-84, June 1998. p72-ammons.pdf
Dynamic Compilation/Optimization
- Michael D. Smith. "Overcoming the Challenges to Feedback-Directed Optimization," Proc. ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo'00), invited lecture, Boston, MA, January 18, 2000.
- Matthew Arnold, Stephen Fink, David Grove, Michael Hind and Peter F. Sweeney. ``Adaptive Optimization in the Jalapeno JVM,'' in Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 47-65, October 2000. p47-arnold.pdf
- Steve S.W. Liao, Perry H. Wang, Hong Wang, Gerolf Hoflehner, Daniel Lavery, John P. Shen. Post-pass binary adaptation for software-based speculative precomputation PLDI 2002.
- Vasanth Bala, Evelyn Duesterwald and Sanjeev Banerjia. ``Dynamo: a Transparent Dynamic Optimization System,'' in Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation, pages 1-12, June 2000. p1-bala.pdf
- Brian Grant, Matthai Philipose, Markus Mock, Craig Chambers and Susan J. Eggers. ``An Evaluation of Staged Run-Time Optimizations in DyC,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 293-304, May 1999. p656-grant.pdf
- Alexander Klaiber. ``The Technology Behind Crusoe Processors,'' Transmeta Corporation. paper_aklaiber_19jan00.pdf
- Matthew C. Merten, Andrew R. Trick, Erik M. Nystrom, Ronald D. Barnes, and Wen-mei W. Hwu. ``A Hardware Mechanism for Dynamic Extraction and Relayout of Program Hot Spots,'' in Proceedings of the 27th International Symposium on Computer Architecture, pages 59-70, June 2000. p59-merten.pdf
- cliff-asplos94.ps
- Trishul M. Chilimbi and Martin Hirzel, ``Dynamic hot data stream prefetching for general-purpose programs,'' Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 199-209, 2002.
Software Pipelining
- Mikhail Smelyanskiy, Scott Mahlke, Edward Davidson, Probabilistic Predicate-Aware Modulo Scheduling in CGO 2004
- Hongbo Rong, Zhizhong Tang, R. Govindarajan, Alban Douillet, Guang Gao, Single-Dimension Software Pipelining for Multi-Dimensional Loops in CGO 2004
- Hongbo Rong, Alban Douillet, R. Govindarajan, Guang Gao Code Generation for Single-Dimension Software Pipelining of Multi-Dimensional Loops in CGO 2004
Transactional Memory
- Adl-Tabatabai, A., Lewis, B. T., Menon, V., Murphy, B. R., Saha, B., and Shpeisman, T. Compiler and runtime support for efficient software transactional memory. SIGPLAN Not. 41, 6 (Jun. 2006), 26-37.
- Tim Harris, Mark Plesko, Avraham Shinnar, and David Tarditi. Optimizing Memory Transactions. In PLDI 2006.
Power and Energy (1)
- C-H. Hsu and U. Kremer, The Design, Implementation, and Evaluation of a Compiler Algorithm for CPU Energy Reduction, Proceedings of the ACM SIGPLAN conference on Programming Language Design and Implementation(PLDI'03), June 2003.
- Y. Zhu, G. Magklis, M. L. Scott, C. Ding, D. H. Albonesi, The Energy Impact of Aggressive Loop Fusion, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques (PACT'04), September 2004.
Power and Energy (2)
- Q. Wu, M. Martonosi, D. W. Clark, V. J. Reddi, D. Connors, Y. Wu, J. Lee, D. Brooks, A Dynamic Compilation Framework for Controlling Microprocessor Energy and Performance, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, November 2005.
- M. Kandemir, N. Vijaykrishnan, M.J. Irwin, Compiler Optimizations for Low Power Systems, Chapter 10: Power Aware Computing, Ed. by R. Graybill, R. Melhem, Kluwer Academic / Plenum Publishers, 2002.
- N. AbouGhazaleh, D. Mosse, B. Childers, R. Melhem, M. Craven, Collaborative Operating System and Compiler Power Management for Real-Time Applications, Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium(RTAS'03), May 2003.
Object-Oriented Optimizations
- Hauswirth, M., Sweeney, P. F., Diwan, A., and Hind, M. Vertical profiling: understanding the behavior of object-priented applications. In Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (Vancouver, BC, Canada, October 24 - 28, 2004).
- Hazelwood, K. and Grove, D. Adaptive online context-sensitive inlining. In Proceedings of the international Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (San Francisco, California, March 23 - 26, 2003). ACM International Conference Proceeding Series, vol. 37. IEEE Computer Society, Washington, DC, 253-264.
- T Yasue, T Suganuma, H Komatsu, and T Nakatani. An efficient online path profiling framework for Java just-in-time compilers In PACT 2003. Page(s):148 - 158