Taewook Oh will present his research seminar/general exam on Monday April 23 at 10AM in Room 402. The members of his committee are David August (advisor), Brian Kernighan, and Andrew Appel. 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. --- [Abstract] Program specialization improves the performance of a program by optimizing it with respect to invariants in the program and its input. For example, by specializing an interpreter with respect to the script, a compiler can produce a highly optimized interpreter customized for the given script. To specialize loops in the program, applying unrolling during specialization is essential. Existing specializers, however, require explicit user annotations to the program to achieve the optimal degree of unrolling. To address this problem, we present a new program specialization technique called IPLS(Invariant-induced Pattern based Loop Specialization), which maximizes the benefit of unrolling without user annotations. First, IPLS traces the values of instructions in the loop that depend solely on invariants and recognizes repeating patterns of these values across multiple iterations. Then, it generates a specialized loop for the recognized pattern by unrolling the original loop to match the pattern length. Without any hints from the user about the program, IPLS specializes loops to reflect the structure of the loop induced by the invariants, so it gets the most of the benefit from unrolling. Experiments show that proposed technique effectively specializes real-world programs that the prior techniques fail to specialize, with a geomean speedup of 14.4% over the original codes. [Reading list] * Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 * Research Papers 1. W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bring- mann, R. G. Ouellette, R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery, The superblock: An effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, vol. 7, pages 229-248, January 1993. 2. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, R. A. Bringmann, and W. W. Hwu, Effective compiler support for predicated execution using the hyperblock, in Proceedings of the 25th International Symposium on Microarchitecture, pages 45–54, December 1992. 3. C.-Y. Fu, M. D. Jennings, S. Y. Larin, and T. M. Conte, Value speculation scheduling for high performance processors, In Proceedings of the 8th Interna- tional Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), pages 262–271, 1998. 4. A. Gelnstrup, H. Makholm, and J. P. Secher, C-Mix: specialization of C pro- grams, eds, J. Hatcliff, T. Mogenses, and P. Thiemann, Partial Evaluation: Practice and Theory, LNCS, vol. 1706, pages 108-153, Springer-Verlag, 1999. 5. C. Consel, L. Hornof, F. Noel, J. Noye, and N. Volansche, A uniform approach for compile-time and run-time specialization, In Selected Papers from the 1996 International Seminar on Partial Evaluation, pages 54–72, Dagstuhl Castle, Ger- many, Feb. 1996. Springer-Verlag, Berlin, Germany. 6. B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J. Eggem. Annotation- directed run-time specialization in C, In Proceedings of the ACM SIGPLAN Svmvosium on Partial Evaluation and Semantics-Based Program manipulation, pages 163–178, Amsterdam, The Netherlands, June 1997. ACM. 7. A. Shankar, S. S. Sastry, R. Bodik, and J. E. Smith. Runtime specialization with optimistic heap analysis, In OOPSLA 05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 327–343, 2005. 8. A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Re- itmaier, M. Bebenita, M. Chang, and M. Franz, Trace-based Just-in-Time Type Specialization for Dynamic Languages, In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 465– 478, 2009. ACM. 9. C. F. Bolz, A. Cuni, M. Fijakowski, and A. Rigo. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler, In ICOOOLPS, pages 18–25, Genova, Italy, 2009. ACM 10. A. Yermolovich, C. Wimmer, and M. Franz. Optimization of Dynamic Lan- guages Using Hierarchical Layering of Virtual Machines, In DLS, pages 79–88, Orlando, Florida, USA, 2009. ACM.