[talks] Taewook Oh generals

[Melissa M. Lawson]

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.