15-745 Spring 2008 Papers for in-class discussions

The readings will be organized as follows:

You will pick a half-lecture slot in one of the lectures between Feb 12 and Feb 17. A sign-up sheet is on Seth's door; it will also be circulated in class during the lecture on Tuesday, Feb 10.
You 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; 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). You will have a total of 40 minutes to present your two papers including 10-15 mins that should be reserved for discussion.
Seth will make the first such presentation, on Tuesday Feb 19, so you know what structure to follow in your own presentations.
Before each class from Feb 10 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 dkoes 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 bold font should be summarized.

Seth Goldstein (Tuesday, 2/10)
Lazy Threads: Implementing a Fast Parallel Call Seth Copen Goldstein, Klaus Erik Schauser, and David E. Culler. Journal of Parallel and Distributed Computing. 1996.
Learning a Better Compiler [Jim Cipar] (Tuesday, 2/10)
- Mark Stephenson and Saman Amarasinghe. Predicting Unroll Factors Using Supervised Classification. In CGO 2005.
- AbouGhazaleh, N., Ferreira, A., Rusu, C., Xu, R., Liberato, F., Childers, B., Mosse, D., and Melhem, R. Integrated CPU and l2 cache voltage scaling using machine learning. In LCTES 2007.
- Calder, B., Grunwald, D., Jones, M., Lindsay, D., Martin, J., Mozer, M., and Zorn, B. Evidence-based static branch prediction using machine learning. ACM Trans. Program. Lang. Syst. 19, 1 (Jan. 1997)
Compiling for Multicore Jeehyung Lee, 2-12
- Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In MICRO 2005.
- William Thies, Vikram Chandrasekhar, and Saman Amarasinghe. A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs. In MICRO 2007
- J. G. Steffan and T. C. Mowry. The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization. In HPCA 1998.
Dynamic Compilation/Optimization Rob Arnold, 2-18
- 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.
Pointer Analysis Will Klieber, 2-18
- Ghiya, Lavery, and Sehr, "On the importance of points-to analysis and other memory disambiguation methods for C programs" PLDI 2001
- Hardekopf, B. and Lin, C. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In PLDI 2007.
- Nevin Heintze and Olivier Tardieu, "Ultra-fast aliasing analysis using CLA: a million lines of C code in a second" PLDI 2001
- 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.
GPUs and memory hierarchy Matt Stanton, Thurs 2-18
- 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.)
- Brook for GPUs: stream computing on graphics hardware. (Buck, I., Foley, T., Horn, D., Sugerman, J., Fatahalian, K., Houston, M., and Hanrahan, P.) In ACM SIGGRAPH 2004 Papers
- nVidia Corporation. nVidia CUDA programming guide, version 1.1 (Read sections 2 and 3, skim sections 4.2 and 6, and look at the other sections if you have time.)
Object-Oriented Optimizations Keith Bare, 2-19
- 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
Proving Compilers Correct Q Youn Hong, 2-25
- 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.
Software PipeliningVinod Chandrasekaran, 2-25
- 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 Iulian Moraru, 2-26
- 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.
SIMD / Vector John Bauman, 2-26
- 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
Code Verification Miguel Silva, 2-26
- 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.

Papers: still available

Adaptive Compilation
- 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.
Register Allocation Complexity
- 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
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
- 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
- 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
Power and Energy
- 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.
- 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.
Other
- Near-Optimal Instruction Selection on DAGs David Ryan Koes and Seth Copen Goldstein. CGO 2008.