Yun Zhang will present her research seminar/general exam on Tuesday May 20
at 10AM in room 402. 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:
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 memory alias 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 performs backward data flow analysis to form
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. The experimental results show that this new alias analysis
technique can effectively locate real 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 Proceedings of the 2000 International Conference on Parallel
Processing(ICPP), 2000
7. Separation Logic: A Logic for Shared Mutable Data Structures, J. Reynold, Invited
Paper, LICS 2002
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.
