[talks] Y Zhang general exam

[Melissa Lawson]

Yun Zhang will present her research seminar/general exam on Tuesday October 14
at 11AM in Room 302.  The members of her committee are:  David August (advisor), 
Andrew Appel, and Doug Clark.  Everyone is invited to attend her talk and those 
faculty wishing to remain for the oral exam following are welcome to do so.  Her 
abstract and reading list follow below.
----------------------------

Abstract

Shape Aware Memory Analysis for Multi-core Architecture

Limited memory alias analysis inhibits automatic parallelization for multi-core
architecture.  Alias analysis generally considers memory accesses to separated parts of
recursive data structures, especially cyclic ones, dependent since the analysis has no
shape information indicating how the program traverses the data structure. For example,
accesses to the left child of a binary tree node are separated from accesses to the right
child, but current memory analysis methods conservatively conclude the accesses may alias
with each other.  This work proposes a three-step loop-aware memory analysis that performs
dependence tests on loops that traverse recursive data structures to benefit automatic
code parallelization.The first step captures shape information of recursive data
structures using separation logic, the second traces two pointers' definition chains, and
the third combines the two definition chains with the shape information of the data
structure to see if the two pointer accesses separate or alias between loop iterations.
Corresponding soundness proof in separation logic is demonstrated on a couple of typical
examples. The experimental results show that this loop-aware alias analysis can
effectively disprove false cross-iteration dependences, which unveils opportunities for
automatic parallelization, eases the work of instruction distribution and reduces data
communications between cores.

Reading List

Books:
1. Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998
2. Advanced compiler design and implementation, by S. S. Muchnick, Morgan Kaufman, 1997

Papers:
3. Shape Analysis with Inductive Recursion Synthesis.  B. Guo, N.  
Vachharajani, and D. I. August, Proceedings of the ACM SIGPLAN 2007 Conference on
Programming Language Design and Implementation (PLDI), June 2007.
4. Detecting Parallelism in C Programs with Recursive Data Sturctures, R. Ghiya, L. J.
Hendren and Y. Zhu, Computational Complexity, page 159-173, 1998 5. Practical and Accurate
Low-level Pointer Analysis, B. Guo, M.J.  
Bridges, S. Triantafyllis, G. Ottoni, E. Raman, and D. I. August, Proceedings of the Third
International Symposium on Code Generation and Optimization (CGO), March 2005.
6. Identifying Parallelism in Programs with Cyclic Graphs, Y. Hwang and J. Saltz,
Proceedings of the International Conference on Parallel Processing(ICPP), 2000 7. A Novel
Approach for Detecting Heap-based Loop-carried Dependences, A. Tineo,  F. Corbera, A.
Navarro, R. Asenjo, and E.L. Zapata, Proceedings of the International Conference on
Parallel Processing(ICPP), 2005 8. Analysis of Pointers and Structures, D. R. Chase, M.
Wegman, F. K.  
Zadeck, Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and
Implementation, pp. 296-310, 1990.
9. Automatic Thread Extraction with Decoupled Software Pipelining, G.  
Ottoni, R. Rangan, A. Stoler, D. I. August, Proceedings of the 38th IEEE/ACM International
Symposium on Microarchitecture (MICRO), November 2005 10. Revisiting the Sequential
Programming Model for Multi-core, M.  
Bridges, N. Vachharajani, Y. Zhang, T. Jablin, D. I. August, Proceedings of the 40th
IEEE/ACM International Symposium on Microarchitecture (MICRO), 2007 11. Points-to analysis
by type inference in programs with structures and unions, B. Steensgaard, Lecture Notes in
Computer Science, 1060 (T. Gyimothy, ed.), pp. 136-150, Springer-Verlag, 1996. Proceedings
from the International Conference on Compiler Construction.
12. Relevant context inference, R. Chatterjee, B. G. Ryder, and W. A.  
Landi, Proceedings of the ACM Symposium on Principles of Programming Languages, pp.
133-146, January 1999.