<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.6000.16640" name=GENERATOR></HEAD>
<BODY
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>Yun Zhang will present her research seminar/general
exam on Tuesday May 20 </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>at 10AM in room 402. The members of her committee
are: David August (advisor), </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>Andrew Appel, and Doug Clark. Everyone is invited
to attend her talk and those </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>faculty wishing to remain for the oral exam following
are welcome to do so. Her </SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>abstract and reading list follow
below.</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2><SPAN
class=493181313-14052008>----------------------------</SPAN></FONT></DIV>
<DIV>
<DIV style="MIN-HEIGHT: 14px; MARGIN: 0px; FONT: 12px Helvetica"><FONT
face=Arial color=#0000ff size=2></FONT><BR></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>Abstract:</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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.</FONT></DIV>
<DIV style="MIN-HEIGHT: 14px; MARGIN: 0px; FONT: 12px Helvetica"><BR></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>Reading List</FONT></DIV>
<DIV style="MIN-HEIGHT: 14px; MARGIN: 0px; FONT: 12px Helvetica"><BR></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>Books:</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>1. Modern Compiler Implementation in ML, by A. W. Appel, Cambridge
University Press, 1998</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>2. Advanced compiler design and implementation, by S. S. Muchnick, Morgan
Kaufman, 1997</FONT></DIV>
<DIV style="MIN-HEIGHT: 14px; MARGIN: 0px; FONT: 12px Helvetica"><BR></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>Papers:</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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.</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>4. Detecting Parallelism in C Programs with Recursive Data Sturctures, R.
Ghiya, L. J. Hendren and Y. Zhu, Computational Complexity, page 159-173,
1998</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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.</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>7. Separation Logic: A Logic for Shared Mutable Data Structures, J.
Reynold, Invited Paper, LICS 2002</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>8. Analysis of Pointers and Structures, D. R. Chase, M. Wegman, F. K.
Zadeck, Proceedings of the ACM SIGPLAN ’90 Conference on</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>Programming Language Design and Implementation, pp. 296–310,
1990.</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>11. Points-to analysis by type inference in programs with structures and
unions, B. Steensgaard, Lecture Notes in Computer Science,</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>1060 (T. Gyimothy, ed.), pp. 136–150, Springer-Verlag, 1996. Proceedings
from the International Conference on Compiler Construction.</FONT></DIV>
<DIV style="MARGIN: 0px"><FONT style="FONT: 12px Helvetica" face=Helvetica
size=3>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.</FONT></DIV></DIV></BODY></HTML>