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.